### keko37's blog

By keko37, history, 2 months ago,

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, paulica, ominikfistric, Shtef and me.

Feel free to discuss the problems in the comment section after the contest ends.

Hope to see you tomorrow!

• +177

 » 7 weeks ago, # |   +17 Reminder: the contest starts in one hour.
•  » » 7 weeks ago, # ^ |   +4 How can I do submission now for practice the problems?
 » 7 weeks ago, # |   0 Typo in the announcement
•  » » 7 weeks ago, # ^ |   +13 Thanks! We'll fix it soon.
•  » » » 7 weeks ago, # ^ |   0 Sorry, but I can't see the tasks in the given site. Where should I go in this site?
•  » » » » 7 weeks ago, # ^ |   -18 Sorry, the registration closed at 14:10 UTC.
 » 7 weeks ago, # |   +4 How to solve problem C?
 » 7 weeks ago, # | ← Rev. 4 →   0 ... 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.
•  » » 7 weeks ago, # ^ |   +36 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.
 » 7 weeks ago, # |   +5 How to solve Volontiranje for full score?
 » 7 weeks ago, # |   +77 My solutions: SpoilerLjeto: just simulate it, keeping track of the last spray time for each playerKamencici: 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.
•  » » 7 weeks ago, # ^ |   +31 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.
•  » » 13 days ago, # ^ |   0 Why in Logicari taking the arbitrary edge does work?
 » 7 weeks ago, # |   +23 The tasks, test data, and solutions are now published! You can find them here.You can submit your solutions here (HONI).
 » 7 weeks ago, # |   -15 In the editorial of problem Kamenčići it is solved by DP, how can we solve it without dp?
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   -21 deleted
•  » » » 7 weeks ago, # ^ |   +11 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.
 » 7 weeks ago, # |   -28 Who needs this competition? It is not in Russia