Hello, This is chromate00 (a.k.a. hjroh0315 on BOJ). The 3rd Chromate Cup Algorithm Division will be held soon! All tasks are developed by me, and all tasks will have statements both Korean and English.
- Date: January 7th (Sun), 20:00 ~ 22:30 KST (2 hours, 30 mins)
- Tasks: 11 tasks. Each task has a score given, and the tasks are sorted increasingly in order of score. The score is proportional to the expected difficulty evaluated by the problemsetter and testers. Still, we suggest you to read each task at least once, the perceived difficulty may vary.
- Difficulty: Bronze ~ Ruby in solved.ac tier (*800 ~ *3000 expected in Codeforces rating)
- Penalty: Uses the same rule as AtCoder. Formally, the penalty is calculated by (Last AC time)+(Sum of tries before AC)*5 mins.
- Language bonus: Language bonus for TL/ML exists for specific languages. See (link; Korean text) for details.
- Standings Freeze: None.
- solved.ac Profile Badge & Background: Each is given to participants who scored at least 250/1500 correspondingly. Please understand that the production/distribution may take two weeks or more.
- Specs: There are at least one interactive task(s). We suggest that you read the guide (link) before participating in the contest.
- Do note that this contest is not held as solved.ac Arena.
- Score Distribution: $$$250-500-1000-1000-1250-1500-2000-2000-3000-4000-4000$$$.
This contest could be held thanks to the testers biximo dhyang24 eggx50000 naeby Stygian_Nymph utilforever, and also to Startlink for great services Baekjoon Online Judge and BOJ Stack.
The contest's Overview tab also contains the same information as above. If the Overview tab and the announcement have different information, the Overview tab will be considered as more recent.
About the raffle:
A total of 13 people will get a Mom's Touch Thigh Burger voucher. The probability is proportional to the score squared. Please understand that only people who reside in Korea currently or can use the voucher are eligible for the raffle. If you cannot use the voucher please inform us in the raffle announcement after the contest ends.
For people new to Baekjoon Online Judge: You may refer to https://help.solved.ac/en/arena/getting-started/link-account (read until the second to last section) for creating a new account and linking the account to solved.ac.
orz
update: the contest date was mistakenly written as 13th, it is actually the 7th (today or tomorrow based on timezone). the announcement is fixed now
Please comment 30 minutes before start of the contest for the reminder.
certainly
friendly reminder: Contest starts in 30 minutes!
I can't see the contest in the solve.ac Arena :|, where should I register?
Just come and solve on https://www.acmicpc.net/contest/view/1220 ! There is no register; this is not a solved.ac Arena contest
The contest has finished! While the editorial is being prepared (Korean editorial is almost finished, English editorial may take up to 24hrs), please use the comments section to freely discuss about the tasks.
Is there a way to see failed tests after the contest? I wrote a stress test, but could not get runtime from it
Due to the limitations of Baekjoon Online Judge, not on the site itself. I could check your solution on Polygon if you want, though.
that would be nice, thanks
Your solution got both TLE and MLE for specific inputs. On most large random inputs it got an MLE (And I think this is why it showed up as Runtime Error). On very specific cactus graphs (especially, the triangle cacti with $$$66667$$$ vertices and $$$99999$$$ edges) it got a TLE.
Ah, that makes much more sense, thank you
Great problems! Thanks for making me feel like I'm still capable of solving decently hard problems :)
Problem G is cute, never thought of this funny complexity.
Is J something smarter than making a network with m + maxc * 100 edges and running Johnson's on it?
The essential solution for J is the same, except the graph may contain negative cycles. Our team checked that these two algorithms in specific pass the task.
However, other algorithms may pass as well if it can deal with negative cycles nicely.
tbh that was one of the easier problems in the contest — you just replace edges where a is not zero with c edges, and run min cost max flow
Ok, thanks. I guess I'm not that well-versed in what works fast in MCMF and what doesn't... I believe my solution is about $$$O(nm + \mathit{flow} \cdot (n + m \log m))$$$, where $$$m$$$ is with extra edges included, but I understand that it might be not fast enough.