Hi everyone!
The 15th season of COCI is starting soon! If you are not familiar with COCI contest format, we encourage you to read the announcement. The biggest news this season is the new judging system and full feedback! You can access the judging system here. There you can also find problems from the previous seasons.
The first round will be held this Saturday, October 17th at 14:00 UTC. The round was prepared by Gabrijel, mkisic, pavkal5, satja, stjepanp, dpaleka and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you on Saturday!
(We are aware that the round overlaps with Codeforces Raif Round 1, but the time sadly cannot be changed. Sorry about that.)
Expected difficulty? CF Div1 or 2 or 1.5?
It should be somewhere between CF Div. 1 and Div. 2. You can also check out last year's problems and solutions here to get a feeling for the difficulty.
Keep in mind that the last three problems are worth the same number of points, and are sorted alphabetically, not by difficulty. But, they have different difficulties. This is to train our students to recognise easier and harder problems, a useful skill for IOI and similar contests.
Friendly reminder: the contest starts in
onethree hours.Are you sure? It says it starts in more than 2 hours...
Oops, it was three, sorry
Will be there editorial ? How to solve Bajka and Papričice ? I got partial points only (20,50).
I can tell you about Bajka. My solution is Dynamic Programming.
Define dp[i][j] = min cost to reach character j of favorite word (included) such that current position in text is i.
Base Case is j=0 and you can perform transition in O(n).
Thank you Arkham_Knight !
The editorial and official solutions will be published (probably) tomorrow.
Thank you paula ! I liked the contest .
Was there some registration deadline? when I was late for an hour there wasn’t an active event in the UI..
I'm sorry you missed it :(. Registration was open until 14:10 UTC (10 minutes into the contest).
can anyone give a good test case for Patkice?
my idea was to check N,E,S,W from 'o' then check the path that leads to 'x' then to add the start direction and the distance/steps taken in an array or else if the path leads to '.' then add 1e6 to the array with the start direction, then sort the array of four elements if they have equal distances then sort them with smallest(direction('N','E','W','S')-'A') .
my code doesn't seems to work or i'm missing something ... my code works on sample cases but fails on real tests (0) :(
my code
or is there a way to download the test data paula?
Thank you.
One bug I faced in contest was that I didn't account for the case where the current pushed me back to the initial island (o). Maybe you have a similar bug?
Edit
It does seem to have a similar bug. Try this case:
OHH(face palming).. thank you so much . i'm so dumb because i spent so much time on this problem figuring why my solution doesn't work... That was the bug. got accepted 50/50. once again thank you socho.
No worries. Congrats on AC :)
The editorial is published! link
How to prove |S(y) − (n+S(x)) / 2| in task papricice?
Intuitively, we want $$$S(y) - S(x)$$$ and $$$n - S(y)$$$ to be "as equal as possible", so we should minimise their absolute difference, which is equal to $$$\lvert 2S(y) - (n + S(x)) \rvert$$$.
A formal proof: Let $$$d = \lvert 2S(y) - (n + S(x)) \rvert$$$. Component sizes are $$$S(x)$$$, $$$\frac{n - S(x) + d}{2}$$$ and $$$\frac{n - S(x) - d}{2}$$$. Maximum of the three numbers is equal to $$$\max \left( S(x), \frac{n - S(x) + d}{2} \right)$$$, and it is minimised when $$$d$$$ is minimal. Minimum is equal to $$$\min \left( S(x), \frac{n - S(x) - d}{2} \right)$$$, and is maximised when $$$d$$$ is minimal. So the difference between the max and the min is minimised when $$$d$$$ is minimal.