Hi everyone!
The 16th season of COCI is starting soon! The first round will be held tomorrow, October 16th 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 pavkal5, paula, ominikfistric, Shtef and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you tomorrow!
Reminder: the contest starts in one hour.
How can I do submission now for practice the problems?
Typo in the announcement
Thanks! We'll fix it soon.
Sorry, but I can't see the tasks in the given site. Where should I go in this site?
Sorry, the registration closed at 14:10 UTC.
How to solve problem C?
... if the intended solution for problems sets was actually FWHT like what I described here, why is TL so tight. I had to optimize the for loops for it to pass.
If that was going to fail I was legitamately going to find the answer under modulo $$$1000000009$$$ and $$$1000000033$$$ (because $$$3$$$-rd root exists there) then combine them using CRT.
TLE code AC code
The official solution runs in 0.135 seconds, so it seemed fine to leave the TL at 1 second.
The difference is probably because we stored numbers in the form a + bw, where a and b are integers and w^3 = 1, so there is no need for floating point values.
How to solve Volontiranje for full score?
My solutions:
Ljeto: just simulate it, keeping track of the last spray time for each player
Kamencici: dynamic programming: for each substring, compute the maximum number of red pebbles you can have already collected on reaching this state and still win the game. The actual implementation got a little messy, but it's O(n²).
Logicari: this type of graph always contains a single cycle with trees hanging off it. Use a DFS to find the cycle and delete an arbitrary edge A-B from it. Root the resulting tree at A. Consider all possibilities for whether A and B have blue eyes, then do a tree DP to determine the minimum number of blue eyes to solve each subtree, under 4 conditions: subtree root is/is not blue-eyed, subtree's parent is/is not blue-eyed.
Sets: Consider a 3×3×3×...×3 bitmap with a 1 in a cell if there is card with the coordinates of that cell, 0 otherwise. If you take the circular convolution of that bitmap with itself 3 times, then the origin cell will contain 6 times the desired answer (because each unordered set has 6 orderings) plus N (because it will count sets consisting of the same card used 3 times). Use Fourier transforms (no need for FFT because it's only a 3-element transform, done along each axis) to do the convolution. There are ways to do it with exact arithmetic, but I was in a rush so just used double-precision complex and it worked.
Volontiranje: I don't have a formal proof of correctness for this. Start by finding the length of the longest increasing subsequence in the usual way; as part of this you'll get the LIS that ends at each position. Now we'll try to repeatedly extract and remove the "lowest" LIS (last element is as small as possible, then the second-last is as small as possible etc). This can be done recursively; the trick is that if the recursion fails to find a solution from a particular element, that element will never be useful again and can be deleted, which avoid an exponential explosion.
The crucial observation which proves the correctness of the algorithm you described for Volontiranje is the following one.
Let $$$i_1,i_2,\dots, i_q$$$ and $$$j_1,j_2,\dots, j_q$$$ be two disjoint longest increasing subsequences. Then also $$$\min(i_1,j_1), \min(i_2,j_2), \dots, \min(i_q,j_q)$$$ and $$$\max(i_1,j_1), \max(i_2,j_2), \dots, \max(i_q,j_q)$$$ are disjoint longest increasing subsequences on the same set of indices.
Thanks to this fact, we may assume that there is a set of disjoint longest increasing subsequences of largest cardinality where the subsequences are ordered (we say that $$$(i_k)\le (j_k)$$$ if $$$i_k\le j_k$$$ for each $$$1\le k\le q$$$). If we replace the smallest of such subsequences with the absolute minimum among all subsequences we still get a valid solution. Hence we have shown that we may assume that the minimum longest increasing subsequence is chosen; then we repeat the algorithm on the remaining indices.
Why in Logicari taking the arbitrary edge does work?
The tasks, test data, and solutions are now published! You can find them here.
You can submit your solutions here (HONI).
In the editorial of problem Kamenčići it is solved by DP, how can we solve it without dp?
deleted
Getting AC on a YES/NO problem without multitest is not something that allows you to say "I got AC so I think it's safe to say my solution works." I recommend stress testing your solution before saying it's correct if you don't have a proof.
If k=2 and the string is CCCCPC, then according to you player 1 takes from the left, player 2 takes from the right(arbitrarily), player 1 takes from the right, player 2 loses.
In reality, player 2 has a winning strategy: just take from the left if player 1 took from the left and take from the right if player 1 took from the right.