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.

funny meme image

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?

Do yourself a favor and listen to Towa-sama's singing! Here are some links to cool songs.

What is the discrepancy of the last stage? How can we make it smaller in previous stages?

Use dynamic programming.

This problem was originally going to appear in Codeforces Round 668 (Div. 2), but it was removed one day before the contest for balance reasons :P

Consider two of the strings. We can obviously achieve our goal using at most $$$4n$$$ characters. How can we save some of them?

Find a long common subsequence that has a simple structure. You'll need to involve the third string as well.

Either $$$00\dots 0$$$ or $$$11\dots 1$$$ is a subsequence of each string.

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.

What is the general structure of an almost sorted permutation?

How many almost sorted permutations of length $$$n$$$ exist? In other words, how many ways are there to reverse subarrays?

Two options — either solve recursively in a greedy fashion or find a smart bijection.

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. fonny image 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!

How can we solve this problem without the restriction that the xor of all edge weights is $$$0$$$?

When does the solution to the unrestricted problem fail for the real problem?

Leave the xor sum of the weights of the unassigned edges in the spanning tree fixed. How do we minimize their sum?

Exactly one unassigned edge ends up with a non-zero weight. If we don't use all unassigned edges, which others can we use?

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.