### keko37's blog

By keko37, history, 3 years ago,

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!

• +116

| Write comment?
 » 3 years ago, # |   +61 Reminder: the contest starts in less than one hour!
 » 3 years ago, # |   +71 The problem hiperkocka was wonderful.
•  » » 3 years ago, # ^ |   +16 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: SpoilerWe'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.
•  » » » 3 years ago, # ^ |   +8 My solution: Solutioniterate 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 -
•  » » » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +22 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  » 3 years ago, # | +36 How to solve D? •  » » 3 years ago, # ^ | +3 SpoilerLet'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. •  » » » 3 years ago, # ^ | +3 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? •  » » » » 3 years ago, # ^ | +9 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. •  » » » 3 years ago, # ^ | +5 Could you elaborate a bit more on the full solution ? What exactly your states and transitions look like ? •  » » » » 3 years ago, # ^ | 0 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.  vector> dp(1); dp[0].resize(L + 1); dp[0][0] = 1; for (int i = 0; i < N; i++) { vector> dp2(i + 2, vector(L + 1)); for (int p = 0; p <= i; p++) { for (int x = 0; x <= L; x++) { if (x + 2 * r[i] <= L && p >= 2) dp2[p - 1][x + 2 * r[i]] += dp[p][x] * p * (p - 1); if (x + r[i] <= L && p >= 1) dp2[p][x + r[i]] += dp[p][x] * p * 2; dp2[p + 1][x] += dp[p][x]; } } dp = move(dp2); }  •  » » » » » 3 years ago, # ^ | ← Rev. 2 → 0 Ohh, i think i get it. Thank you. •  » » » » » 3 years ago, # ^ | 0 Hello! I'm having trouble understanding the first recurrence relation in the dp. dp2[p - 1][x + 2 * r[i]] += dp[p][x] * p * (p - 1); 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. •  » » » » » » 3 years ago, # ^ | 0 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);  » 3 years ago, # | +16 Could anyone share the solution for E? Thanks for the contest btw •  » » 3 years ago, # ^ | +19 SpoilerWith 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)$. •  » » » 3 years ago, # ^ | +19 What exactly do you mean by a "sparse table"? •  » » » » 3 years ago, # ^ | +19 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. •  » » » » » 3 years ago, # ^ | +8 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?). •  » » » » » » 3 years ago, # ^ | +11 in-contest snippet of code vector> to(n+1); for(int i = n; i >= 0; i--) { to[i].resize(D); fill(all(to[i]), n); if(i == n) continue; to[i][0] = min(to[i+1][0], seg.qry(v[i].f, v[i].s)); seg.upd(v[i].f, v[i].s, i); } for(int d = 1; d < D; d++) { for(int i = n-1; i >= 0; i--) { to[i][d] = to[to[i][d-1]][d-1]; } } int q; cin >> q; while(q--) { int lhs, rhs; cin >> lhs >> rhs; lhs--; rhs--; int ret = 0; for(int d = D-1; d >= 0; d--) { if(to[lhs][d] <= rhs) { ret += 1 << d; lhs = to[lhs][d]; } } cout << ++ret << "\n"; }  •  » » 3 years ago, # ^ | +19 HintBinary lifting SpoilerFor 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.  » 3 years ago, # | +51 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). •  » » 3 years ago, # ^ | +29 I now know at least 3 people who read it wrongly this way. Kinda weird how so many people read it wrongly... •  » » » 3 years ago, # ^ | +29 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). •  » » » 3 years ago, # ^ | +3 Now at least$4$. •  » » » » 3 years ago, # ^ | +8 5 :( •  » » » » » 3 years ago, # ^ | +8 6 •  » » » » » » 3 years ago, # ^ | ← Rev. 2 → +22 7 , and didnt figure out that i have misread it until after the contest •  » » 3 years ago, # ^ | +23 oooooh, now I seeee :( •  » » 3 years ago, # ^ | ← Rev. 2 → +16 I also misread the problem this way, but I couldn't come up with a solution faster than SpoilerN^(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? •  » » » 3 years ago, # ^ | +8 Sounds like you came up with the same solution as me. I also got TLE with it, even on the smaller cases. •  » » » 3 years ago, # ^ | 0 +1  » 3 years ago, # | +21 When will upsolving be open? •  » » 3 years ago, # ^ | ← Rev. 2 → +18 I just checked and its open. Tasks -> HONI -> 2021/2022 -> 2.kolo •  » » » 3 years ago, # ^ | +3 Thanks! It wasn't open when I posted the comment  » 3 years ago, # | +8 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? •  » » 3 years ago, # ^ | +16 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. •  » » » 3 years ago, # ^ | +8 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. •  » » » » 3 years ago, # ^ | +8 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. •  » » » 3 years ago, # ^ | +23 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.  » 3 years ago, # | ← Rev. 5 → +11 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.
•  » » 3 years ago, # ^ |   +36 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.
 » 3 years ago, # |   +26 The tasks, test data, and solutions are now published! You can find them here.You can submit your solutions here (HONI).