Hi everyone!
The third round of COCI will be held tomorrow, December 12th at 14:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.
The round was prepared by Gabrijel, mkisic, pavkal5, dpaleka and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you tomorrow!
What is the difficulty of problems in COCI?
There's one easy problem and another somewhat easy (algorithmic) problem. The rest are split into multiple subtasks and range from medium to very hard. A nice and really high quality problemset in my opinion, but 4/5 problems is pretty tough for most people to hit, even Masters/Grandmasters.
Reminder: the contest starts in less than one hour.
Problem Selotejp is direct copy of 1404E - Bricks.
Sorry, we were not aware of this problem. We know that problem is very general and that probably was already on some contest but still we thought that it is quality bitmask dp for Croatian version of competition.
Will the problems be available for upsolving?
Yes, you can find them under the "Tasks" tab.
My solutions
Selection sort using the following procedure. Identify the thinnest book. Move all books that are on top of it to the right pile, using your left hand. Pick up the thinnest book in your right hand. Move the books you moved to right pile back to the left pile (using left hand). Put the thinnest book on the right pile. Repeat for the second-thinnest book, and so on. You now have the books reverse-sorted on the right-hand pile, so can move them all to the left pile.
Insert all the words for both players into a trie. As the trie is built, mark each node to indicate whether it is a valid prefix for each of the players. Then recursively (bottom-up) determine whether each state is a winning state for each player. It is a winning state if there is a child node which is a valid prefix for the player and which is a losing state for the other player.
Sort all possible rotations of all rows, using the standard suffix array technique. This allows every rotated row to be assigned a rank. Now for each column we can create a new string, where the symbols are the ranks of the rows if that column should be moved to the front. We again use a suffix array to identify the optimal rotation of each column, and pick the best across all columns.
Running time O(n log n) (although my suffix array implementation is actually O(n log² n)). I had to do a bit of micro-optimisation to make it fast enough.
We solve it by DP, deciding how to handle each cell in turn, left to right then top to bottom. The state is whether each bottom-most handled cell has vertical tape in it, and whether the previous cell has horizontal tape it in it, for $$$2^{m+1}$$$ states (it could be reduced slightly, since the last cell can't have both horizontal and vertical tape). We then consider each possible way to handle the next cell (new horizontal or vertical tape, or extend existing tape).
Running time $$$O(2^m nm)$$$.
This one gave me the most trouble. Build the tree bottom-up, a row at a time. Maintain a persistent segment tree with an item per entry in the bottom row, which is 1 if the entry is the left-most child of some element of the current top row, or 0 otherwise. Adding a new row involves setting one value from 1 to 0. Because it is persistent, we can do the following queries:
The LCA of two nodes is either the higher of the two (if one is an ancestor of the other), or it is the LCA of their left-most descendants. We can find those descendants, then use binary search with the first query type to find the level containing the LCA.
This is O(n log² n). I believe it could be improved to O(n log n), by first constructing a compressed tree containing the bottom row and all the a[i]'s, and then using standard LCA algorithms on that tree.
I overcomplicated problem C. I tried all possible rotation of columns, construct an ordering of row suffixes incrementally (like how we actually implement suffix arrays), and then computed the optimal row rotation which involves real suffix arrays. Then we have $$$M$$$ candidates of length-$$$NM$$$ binary strings to compare. I maintained these carefully with bitset and compared them with
_Find_first(), so my code doesn't compile on my machine. Didn't bothered to think too much, since I solved the problems in reverse orders and had plenty of time to do anything.D is the second time copy-pasting BOJ 13444 :) Not much to say, but I really loved figuring it out back then. It's quite standard if solved with bitmasks, though.
I think I have a different motifs for E, and I quite liked the problem. Instead of compressing the tree I have flattened the tree to $$$(N+1) \times (N+1)$$$ square grid. Last row contains numbers $$$1, 2, \ldots, N + 1$$$ denoting the index of nodes it belongs in depth $$$i$$$ (minus $$$i(i-1)/2$$$ or whatsoever). You can observe that the difference of $$$i-1$$$-th row and $$$i$$$-th row is simply an addition to a suffix. Fenwick trees are sufficient to determine what it is.
Now the problem boils down to:
The mapping can be described as follows. Define $$$pos[i]$$$ as a starting position of suffix for row $$$i$$$. Then a mapping for a row $$$r$$$ can be defined as a $$$k$$$-th smallest element, or counting numbers $$$\le c$$$ in a set $$$[pos[0], pos[1], \ldots, pos[r]]$$$. You can use persistent segment trees here.
To find the first row, notice that two cells in same row have same values iff no suffix additions were done in between. It's a range minimum query over a reverse permutation of $$$pos$$$.
I don't quite follow how your square grid is defined — you've said what to put into the last row but not the other rows. I have a feeling it might be quite closely related to my persistent segment tree but I'm not sure. Maybe you can show what it contains for the first sample case?
Thanks for the comment. I've updated the reply to better illustrate the concept.
For the sample case:
Brackets indicate the range updates. The first range update is not needed, but I used it to simplify the implementation.
Ok, a row in your grid corresponds to a prefix sum of the leaves in my segment tree.
Another way in which you could improve the last problem's complexity to $$$O(n$$$ $$$log$$$ $$$n)$$$ is by noticing that you can find the depth of the LCA of the $$$u$$$-th and $$$v$$$-th node in the bottom row by finding when do all numbers in your presistent segment tree between $$$u+1$$$ and $$$v$$$ become 0. That can easily be solved by remembering when did each element become 0 and using RMQ.
The editorial is published: link
You can solve all problems here: https://oj.uz/problems/source/539