Hi everyone!
The third round of COCI will be held tomorrow, December 7th at 14:00 UTC. You can access the judging system here. If you are not familiar with the COCI contest format, we encourage you to read the announcement.
The round was prepared by keko37, celin, fbabic, vito1036, psruk, mkisic and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you tomorrow!
MY FAVORITE OLYMPIAD!!!! I LOVE CROATIA!!
why you made a new acc?
how difficult are the problems?
COCI problems have different scores usually. (more score, harder)
How would that compare to cf rating though?
Why not just participate and see it yourself?
Because i want to go play in a yugioh tournament, and i dont wanna skip the yugioh tournament to participate in a contest where i would solve 0 problems
I'm guessing you would at least solve 1-2 problems (maybe more) and get subtasks from others. Do whichever one feels more fun though :))
for Karte I have a code but im not sure it should work
code
I always take the M cards however there can be a case where one of the M cards is completely useless and dosent do a combo with any other card and thus is never optimal to take
How to solve E?
Let's call the elements added in a query a block. For each block create a segment tree where values in the nodes are the positions of the minimum in the range that that node covers. Construction for each block is $$$x_i - 1$$$ queries. You will find the minimum by doing divide and conquer on the blocks in similar fashion. When you find a minimum and remove it from its block you will need to recalculate the tree which will take at most $$$\log_2{x_i}$$$ queries. I also added memoization in my code just in case.
Rough estimate of the number of queries in the worst case: $$$2000 + 40 \cdot \log_2{2000} + 40 \cdot \log_2{40} \leq 2700$$$.
Orz
Instead of divide and conquer, you can keep a sorted vector of pairs {block index, minimum in block} which you can update naively after each query with a binary search.
Why is it not specified whether the grader is adaptive or not?? I believe it is very important for a question like this since randomized solution could exist. In fact, I think the grader is not adaptive because my solution is randomized (using quick select), and it obtained 75 points. If the grader was adaptive, my solution would probably have gotten 15/0 points. If someone decided not to implement his randomized algorithm because he assumed the grader is adaptive, it would have cost the person a lot of points.
Hi, the grader is not adaptive, and you are right.
I didn’t include it in the statement because I didn’t anticipate that a solution could pass under much tighter constraints using quickselect. The intended solutions for each subtask are entirely deterministic.
Normally I would assume the grader is adaptive if not specified, but the assumption would've been wrong here. We apologize for the inconvenience.