Hi everyone!
The second round of COCI will be held tomorrow, November 13th 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 Bartol, paula, pavkal5, 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 less than one hour!
The problem hiperkocka was wonderful.
I normally hate construction problems but this one wasn't too bad. Here's my construction — I'm curious whether others had significantly different ones:
We're make a construction with the extra property that all instances of a particular tree node have the same parity (parity of the number of 1 bits). Find any leaf of the tree and delete that node and edge. Solve the problem recursively for N-1 and the remaining tree. Make a second copy of the solution, but toggle the top and bottom bit in all the node indices. The removed edge can now be added back as edges between the two copies, and the parity condition ensures that none of them will coincide.
My solution:
iterate i from 0 to (2^n)-1 .consider the tree in which root is i and xor of ith edge(fixed order) is 2^i.if this tree doesn't has any edge in common with previous trees then we take it -
I think that probably ends up being equivalent to my solution (certainly the ith edge of my trees have xor $$$2^i$$$, for certain numbering of the edges), but obviously is a little easier to code.
My solution is similar to kshitij_sodani's one but I make the additional observation that one can choose the roots as the vertices which belong to a subspace of $$$\mathbb F_2^n$$$.
Let us root the tree at $$$n$$$ and, for each $$$0\le i<n$$$, let $$$p_i$$$ be the parent of $$$i$$$. The edge $$$p_i - i$$$ corresponds to flipping the $$$i$$$-th bit. So, if we choose where to put the vertex $$$n$$$ in the hypercube we have fixed a placing of the whole tree in the hypercube. How do we choose the $$$2^{n-1}$$$ roots? Let $$$z = \sum_{a: p_a=n} 2^a$$$. A vertex $$$0\le v<2^{n-1}$$$ is chosen as a root if $$$z\wedge a$$$ has an even number of bits.
It is not hard to check that this produces a valid tiling.
How to solve D?
Let's suppose we already know the relative order of the magnets. We can work out how many cells need to be kept empty between the magnets to satisfy the requirements — let's call it G. We can then assign the N magnets to L-G cells in choose(N, L-G) ways, and then insert the gaps. That's sufficient to solve case 2 (just iterate over all permutations).
To solve the full problem, we need to use DP to figure out the number of permutations that give rise to each possible value of G. More generally, we compute the number of ways to arrange the smallest k magnets into p contiguous pieces (with gaps between). To add the next magnet, we consider the cases of it being adjacent to 0, 1 or 2 of the existing pieces.
I think I have thought a very similar way, but I couldn't build DP. First, I considered sorting the array. Then I thought of building a DP like $$$dp[i][j][k]$$$ where this element holds the number of ways of permuting numbers from $$$i^{th}$$$ index to $$$j^{th}$$$ index such that at least $$$k$$$ slots are needed for permuting that way. Can I continue from here or do I need to think something else?
I started thinking along those lines (although 1..j instead of i..j), but I don't see a way to define the recurrence relation since knowing the slots required by a permutation of 1..j doesn't give you enough information to know how many extra slots are required when inserting j+1 into all possible positions.
Could you elaborate a bit more on the full solution ? What exactly your states and transitions look like ?
Here's the core of the DP from my solution. $$$i$$$ is the number of the magnet being added, $$$p$$$ is the number of segments before adding it, $$$x$$$ is the number of empty spaces required before adding it. The three sections of the inner loop are for if the new magnet gets attached to 2, 1 or 0 of the existing segments.
Ohh, i think i get it. Thank you.
Hello! I'm having trouble understanding the first recurrence relation in the dp.
I understand that this is the transition where we merge two segments so, in my head, we should increase dp2[p — 1][x + 2 * r[i]] by dp[p][x] * the number of all the 2 consecutive segments we can chose to merge aka (p-1). I know this way of thinking about it is somehow wrong, but I can't figure out why.
I considered the segments to be unordered relative to each other. Your way would work too (treating the segments as having an order), as long as you also adjust the transition for adding a new segment. Off the top of my head, I think it would become
dp2[p + 1][x] += dp[p][x] * (p + 1);
Could anyone share the solution for E? Thanks for the contest btw
With a segment tree that supports range set and range minimum query, scanning from right to left you can find the leftmost person to the right that conflicts with someone. You'll need to discretize heights.
Once you've computed this, you can maintain a sparse table of how far to the right you can go starting with each person.
After you're done this precomputation, you can answer queries in $$$\mathcal{O}(\log N)$$$.
What exactly do you mean by a "sparse table"?
CP algorithms definition linked here.
I think of sparse tables as the data structure which enables performing binary lifting, but I admit I do not really follow the terminology myself.
For binary lifting I stored the position reached after inserting $$$2^i$$$ maximal lineups starting from each position $$$j$$$. But that doesn't sound like quite the same as the sparse tables you've linked to — I'm not sure what you'd store in a sparse table (number of lineups and endpoint of the last one?).
Binary lifting
For each query, it will be optimal to start constructing the first lineup from $$$p$$$ and extending it as far as possible before starting the next lineup, and repeating. So for each suspect S, one needs to know far a lineup starting with that suspect can be extended to the right. As a first step, we can compute the next person to the right of S with similar height ("similar" meaning an overlapping range). That can be computed with a line sweep by height, keeping an ordered set of suspects. When a new suspect is added, consider the immediate neighbours in the sorted set as candidates for this relationship.
A lineup starting at S extends either to the next person similar to S, or as far as the lineup starting to the right of S. So a downwards sweep allows computing the position of the next lineup startup for each S.
To answer a query one can follow these pointers from $$$p$$$ until one has moved past $$$q$$$. That's too slow for the last test case, but binary lifting reduces it to $$$O(\log N)$$$ per query.
I ended up wasting a lot of time on problem E because I missed the constraint that a lineup must consist of a contiguous range of people — I thought one could pick any subset. If you're interested in a challenge see if you can find a sub-quadratic solution (I did).
I now know at least 3 people who read it wrongly this way. Kinda weird how so many people read it wrongly...
Good to know it's not just me :-) My guess is that when I wrote the code to read the input I only saw reference to two sorts of ranges (range of heights and range of people for queries) so forgot that there is a third sort of range (range of people in a lineup).
Now at least $$$4$$$.
5 :(
6
7 , and didnt figure out that i have misread it until after the contest
oooooh, now I seeee :(
I also misread the problem this way, but I couldn't come up with a solution faster than
N^(3/2)*log(n) using Mo algo. Sadly, this doesn't pass the TL even with optimizations like using hilberts curve.
Is there a faster solution?
Sounds like you came up with the same solution as me. I also got TLE with it, even on the smaller cases.
+1
When will upsolving be open?
I just checked and its open. Tasks -> HONI -> 2021/2022 -> 2.kolo
Thanks! It wasn't open when I posted the comment
I struggle to understand why the solution for problem Kutijie works. I understand the graph representation as I also used in my own 35p solution. But, I feel like the we should look for strongly connected components instead of only connected components. Could anyone please enlighten me why it works?
Looking at strongly connected components is the right idea. You may notice that the graph generated by a permutation P, where there only exist directed edges i -> P[i], is made up of multiple simple cycles. For each cycle, all the vertices on it are in the same SCC. This is the same as saying that all the vertices in one connected component (ignoring how edges are directed) are in the same SCC.
I think I get it now. The graph generated by a single permutation consists only of simple cycles and singletons because P is a permutation and at some point and this means that checking for a SCC is the same as checking for a CC. Tho, is there any proof for the fact the simple cycles thing? I can visualize why it happens but I'm just wondering.
Each node in the graph generated by the permutation has exactly one edge entering it and one edge leaving it, so if you choose a node V and repeatedly go forward using the edge leaving V, you will at some point return to V, thus V is on a simple cycle.
I didn't realize each CC is a SCC during the contest.
So I used a stupid method with bitmask and get passed. Time complexity is $$$O(n^3/w)$$$.
Now I know how silly I was.
Problem D is very nice and the way the recurrence is built is very interesting. I have never seen such a way of thinking :
"Instead of finding the answer for a whole subarray, find the sum of the answers if this subarray is splitted into $$$k$$$ independent groups. If we do it this way, the answer for the whole subarray is stored in the 'DP for splitting the subarray into 1 group'."
It is very, very clever to do so. Are there any other problems that relies on this idea or is it a very specific DP? If there are no known similar problems, Bartol [orz], can you at least share the story for the preparation of the problem? Thank you so much.
There was a great blog post some time ago about this topic — link.
This idea is usually used when trying to construct permutations with certain properties.
The tasks, test data, and solutions are now published! You can find them here.
You can submit your solutions here (HONI).