↵
**UPD:** I figured out how to use spoilers! Also added implementations for all problems.↵
↵
Thanks for participating in our contest!↵
↵
[problem:1509A]↵
↵
Author: [user:Kuroni,2021-04-13]↵
<br>↵
First solve: [user:cfg0d,2021-04-16] at 00:01:02↵
↵
<spoiler summary = "Hint"
How can you write the condition that $\frac{a_u + a_v}{2}$ is an integer in a more useful way? Think of the parities.↵
</spoiler>↵
↵
↵
<spoiler summary = "Tutorial"
<br
[tutorial:1509A]↵
</spoiler>↵
↵
↵
<spoiler summary = "Comments from the authors"
↵
</spoiler>↵
↵
[Implementation](https://codeforces.com/contest/1509/submission/113263196)↵
↵
↵
[problem:1509B]↵
↵
Author: [user:Ari,2021-04-13]↵
<br>↵
First solve: [user:blue5002,2021-04-16] at 00:04:51↵
↵
<spoiler summary = "Hint"
You can think of the partition as associating to each $M$ character a $T$ to its left and a $T$ to its right. What's the best way to perform this assignment?↵
↵
<spoiler summary = "Answer"
Assign greedily from left to right.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Tutorial"
[tutorial:1509B]↵
</spoiler>↵
↵
↵
<spoiler summary = "Comments from the authors"
Do yourself a favor and listen to Towa-sama's singing!↵
[Here](https://www.youtube.com/watch?v=3UV8OZj2olg) [are](https://www.youtube.com/watch?v=2D0B3wTjE20) [some](https://www.youtube.com/watch?v=ZQ3gmQzpvBM) [links](https://www.youtube.com/watch?v=2o_H09MdT94) [to](https://www.youtube.com/watch?v=64kI2BWRd2g) [cool](https://www.youtube.com/watch?v=9RBY7u5qas8) [songs.](https://www.youtube.com/watch?v=Ud73fm4Uoq0)↵
</spoiler>↵
↵
[Implementation](https://codeforces.com/contest/1509/submission/113263820)↵
↵
↵
[problem:1509C]↵
↵
Author: [user:Ari,2021-04-13]↵
<br>↵
First solve: [user:Dukkha,2021-04-16] at 00:05:32↵
↵
<spoiler summary = "Hint 1"
What is the discrepancy of the last stage? How can we make it smaller in previous stages?↵
↵
<spoiler summary = "Answer"
The discrepancy of the last stage is always the difference between the largest and the smallest $a_i$. We can make it smaller in the previous stages by placing the smallest or the largest $a_i$ at the end.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2"
Use dynamic programming.↵
</spoiler>↵
↵
↵
<spoiler summary = "Tutorial"
[tutorial:1509C]↵
</spoiler>↵
↵
↵
<spoiler summary = "Comments from the authors"
This problem was originally going to appear in [contest:1405], but it was removed one day before the contest for balance reasons :P↵
</spoiler>↵
↵
[Implementation](https://codeforces.com/contest/1509/submission/113263837)↵
↵
↵
[problem:1508A]↵
↵
Author: [user:Ari,2021-04-13]↵
<br>↵
First solve (Div. 2): [user:traxex2,2021-04-16] at 00:22:48↵
<br>↵
First solve (Div. 1): [user:tourist,2021-04-16] at 00:05:04↵
↵
<spoiler summary = "Hint 1"
Consider two of the strings. We can obviously achieve our goal using at most $4n$ characters. How can we save some of them?↵
↵
<spoiler summary = "Answer"
Take advantage of any common subsequence in our two strings by including the characters in it only once.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2"
Find a long common subsequence that has a simple structure. You'll need to involve the third string as well.↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3"
Either $00\dots 0$ or $11\dots 1$ is a subsequence of each string.↵
</spoiler>↵
↵
↵
<spoiler summary = "Tutorial"
[tutorial:1508A]↵
</spoiler>↵
↵
↵
<spoiler summary = "Comments from the authors"
This problem was originally suggested as a 2B. It turned out to be too hard and was switched to 2C, before being further switched to 1A because it was still too hard. Some testers still believed this problem to be even harder, but we ended up deciding to have it as 1A with a larger score than usual.↵
<br>↵
<br>↵
Apologies to the testers who had to solve this as if it was the second easiest problem in the contest :^)↵
</spoiler>↵
↵
[Implementation](https://codeforces.com/contest/1508/submission/113263847)↵
↵
↵
[problem:1508B]↵
↵
Author: Both of us!↵
<br>↵
First solve (Div. 2): [user:shenmadongdong.qaq,2021-04-16] at 00:29:52↵
<br>↵
First solve (Div. 1): [user:tourist,2021-04-16] at 00:08:19↵
↵
<spoiler summary = "Hint 1"
What is the general structure of an almost sorted permutation?↵
↵
<spoiler summary = "Answer"
Start with the identity permutation, choose some disjoint subarrays, and reverse each of them.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2"
How many almost sorted permutations of length $n$ exist? In other words, how many ways are there to reverse subarrays?↵
↵
<spoiler summary = "Answer"
$2^{n - 1}$↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3"
Two options — either solve recursively in a greedy fashion or find a smart bijection.↵
</spoiler>↵
↵
↵
<spoiler summary = "Tutorial"
[tutorial:1508B]↵
</spoiler>↵
↵
↵
<spoiler summary = "Comments from the authors"
This problem's creation has a funny story. Back when we were coming up with problems for Round 668, I (Ari) came up the following relatively simple and standard problem and shared it.↵
<br>↵
<br>↵
↵
<br>↵
<br>↵
The next day, Kuroni saw the problem, but misread it and ended up solving the version that made it into this contest, which we think is a lot cooler!↵
<br>↵
<br>↵
One more fun fact for your consideration: This problem's name in Polygon is "sorrow".↵
</spoiler>↵
↵
[Implementation](https://codeforces.com/contest/1508/submission/113263859)↵
↵
↵
[problem:1508C]↵
↵
Author: [user:Kuroni,2021-04-13]↵
<br>↵
First solve (Div. 2): [user:deepspacewaifu,2021-04-16] at 01:42:36↵
<br>↵
First solve (Div. 1): [user:maroonrk,2021-04-16] at 00:33:17↵
↵
<spoiler summary = "Hint 1"
How can we solve this problem without the restriction that the xor of all edge weights is $0$?↵
↵
<spoiler summary = "Answer"
Just assign $0$ to every unassigned edge :P↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2"
When does the solution to the unrestricted problem fail for the real problem?↵
↵
<spoiler summary = "Answer"
When any minimum spanning tree (of the graph with every unassigned edge having weight $0$) contains every unassigned edge, and the xor sum of all the edge weights is not $0$.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3"
Leave the xor sum of the weights of the unassigned edges in the spanning tree fixed. How do we minimize their sum?↵
↵
<spoiler summary = "Answer"
Assign the entire xor sum to a single edge, and assign weight $0$ to every other edge.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 4"
Exactly one unassigned edge ends up with a non-zero weight. If we don't use all unassigned edges, which others can we use?↵
↵
<spoiler summary = "Answer"
Any edge that isn't part of the MST when we consider unassigned edges to have weight $0$, and that doesn't form a cycle with pre-assigned edges with smaller weights.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Tutorial"
[tutorial:1508C]↵
</spoiler>↵
↵
↵
<spoiler summary = "Comments from the authors"
If the unassigned edges in the graph don't form a forest, then the answer is simply the weight of the MST where all the unassigned edges have weight $0$. Thus the interesting tests in this problem require these edges to form a forest, which means $m \ge \frac{n(n - 1)}{2} - (n - 1)$. This automatically limits the maximum value of $n$ to approximately $2\sqrt{m}$. Concretely, $n \le 633$ for all interesting tests in this problem. You can also use this to obtain a solution that runs in $O(m \sqrt{m})$, which a tester found, and which passes if implemented reasonably.↵
</spoiler>↵
↵
[Implementation](https://codeforces.com/contest/1508/submission/113263168)↵
↵
↵
[problem:1508D]↵
↵
Author: [user:Ari,2021-04-14]↵
<br>↵
First solve: [user:ksun48,2021-04-16] at 00:57:13↵
↵
<spoiler summary = "Hint 1"
It is always possible to find the sequence.↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2"
There's a simple algorithm that fixes a point and repeatedly moves its current label to the correct position. When does it work?↵
↵
<spoiler summary = "Answer"
When the permutation of the labels is a single cycle.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3"
Any permutation can be split into one or more cycles. What can we do to these cycles?↵
↵
<spoiler summary = "Answer"
Merge them, by swapping two elements in different cycles.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 4"
We would like to merge all cycles of the permutation by swapping elements in different cycles and then repeatedly move each label from a certain point to its correct location. How can we do this without intersections?↵
↵
<spoiler summary = "Answer"
Fix a point beforehand to perform the final step, and sort angularly with respect to this point.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Tutorial"
[tutorial:1508D]↵
</spoiler>↵
↵
↵
<spoiler summary = "Comments from the authors"
This problem was originally proposed with the points always being the vertices of a convex polygon. This allows us to do a slightly different solution where we first merge the cycles and choose the pivot afterwards by choosing a point unaffected by the previous swaps.↵
<br>↵
<br>↵
The reason for having $n = 2000$ in this problem rather than a larger $n$ like $10^5$ is because of the validator: it is essential to not have three collinear points in this problem, and I don't know how to check this for large $n$. The small $n$ also makes the checker much easier to write, though it's possible (albeit tricky) to write a checker that works in $O(n \log n)$.↵
<br>↵
<br>↵
Regarding the number of operations used: The solution described in the editorial uses approximately $\frac{3}{2}n$ operations in the worst case when the permutation consists of cycles of size $2$. The minimum number of operations is lower bounded by $n - 1$ by combinatorics reasons when the permutation is a single cycle. Moreover, by Euler's formula, we have an upper bound of $3n - 6$ operations for any valid sequence, which goes down to $2n - 3$ when the points are the vertices of a convex polygon. I don't know of a solution that uses $cn$ operations for some $c < 3/2$, nor do I know of a general test case where it can be proven that at least $cn$ operations are needed for some $c > 1$, so I'd be really interested in seeing either.↵
</spoiler>↵
↵
[Implementation](https://codeforces.com/contest/1508/submission/113263865)↵
↵
↵
[problem:1508E]↵
↵
Author: [user:Kuroni,2021-04-14]↵
<br>↵
First solve: [user:ecnerwala,2021-04-16] at 01:02:26↵
↵
<spoiler summary = "Hint 1"
During the process, we will repeatedly push the same label down until we no longer can. What happens at this point?↵
↵
<spoiler summary = "Answer"
The labels that have been fully pushed down will look like a post-order of the tree, while the other labels will look like a pre-order of the tree.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2"
Look at the children of a particular vertex. What can we say about the ones that are fully pushed down in relation to the ones that aren't?↵
↵
<spoiler summary = "Answer"
Every fully pushed down label is smaller than every other label.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3"
For each node, the order of the labels of its children stays fixed. ↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 4"
How can we use the previous observations to identify the state of the process?↵
↵
<spoiler summary = "Answer"
We can reconstruct the DFS order and the fully pushed down labels. Then check that the current pushing step of the process is valid.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Tutorial"
[tutorial:1508E]↵
</spoiler>↵
↵
↵
<spoiler summary = "Comments from the authors"
This problem was inspired by a wrong solution to [problem:1477D], but it seems that knowing that problem beforehand doesn't help at all to solve this one.↵
</spoiler>↵
↵
[Implementation](https://codeforces.com/contest/1508/submission/113263313)↵
↵
↵
[problem:1508F]↵
↵
Author: [user:Kuroni,2021-04-13]↵
<br>↵
First solve: [user:ecnerwala,2021-04-16] at 01:52:02 (The only contestant who solved this problem!)↵
↵
<spoiler summary = "Hint 1"
Start by solving the problem for $q$-encodings only.↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2"
We can get an encoding by including every possible edge. Which of them can we exclude?↵
↵
<spoiler summary = "Answer"
We need to keep an edge $u \to v$ if and only if no other path from $u$ to $v$ exists.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3"
What does the previous observation look like from the perspective of a single vertex?↵
↵
<spoiler summary = "Answer"
Each vertex has at most two outgoing edges, one on each side, and we can easily characterize when one of them is redundant.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 4"
We need to solve the full version now. For a vertex $u$, how do the endpoints of its outgoing edges change when we add a new interval?↵
↵
<spoiler summary = "Answer"
The endpoints of the right edges increase monotonically, while the endpoints of the left edges decrease monotonically.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 5"
How can we use the previous observation to characterize edges becoming redundant more concretely?↵
↵
<spoiler summary = "Answer"
For each right edge, we can find a particular left edge, such that the right edge becomes redundant once the left edge appears. This gives us an interval of times for each edge during which it is relevant.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 6"
Use Mo's algorithm on the input intervals to find the relevant edges.↵
</spoiler>↵
↵
↵
<spoiler summary = "Tutorial"
[tutorial:1508F]↵
</spoiler>↵
↵
↵
<spoiler summary = "Comments from the authors"
Huge shoutouts to [user:tfg,2021-04-14] who came up with one of the key steps of the solution! Including this problem probably would have not been possible without him. ❤️↵
</spoiler>↵
↵
[Implementation](https://codeforces.com/contest/1508/submission/113263058)↵
↵
Finally, here's some funny moments that happened while we were working on the round :)↵
↵
<spoiler summary = "Memes"
↵
↵
↵
↵
↵
</spoiler>↵
↵
