First proper Codeforces round

This was my first Codeforces round (Div2 754) where I competed live. It was very fun and I solved the first three problems. My main issue was not the actual solutions but mainly the implementations. I spent more time debugging than thinking which was a bit of a pain since I just wanted to get on with the harder problems. I'm going to give brief solutions for the first three problems.

Problem A: You are given three positive integers $a_1, a_2$ and $a_3$ and a function $d(a_1, a_2, a_3) = |a_1 + a_3 -2\cdot a_2|$. We can pick any two of the three numbers and add $1$ to one of them and subtract $1$ from the the other. The problem asks for the minimum value of $d(a_1, a_2, a_3)$ that can be achieved given the allowed move.

The idea is that we can only increase/decrease $d(a_1, a_2, a_3)$ by $3$. So we just need to see what $a_1+a_3-2\cdot a_3$ mod $3$ is and this is our answer.

Problem B: We are given a binary string $b$ of length $n$. To do this we are allowed to do the following two things which counts as one move:

1. Choose a subsequence of any length such that the elements are in non-increasing order.
2. Reverse the chosen subsequence.

We want to find the minimum number of moves needed to sort the binary string in non-decreasing order.

The first thing to notice is that if we have $x$ $1'$s in $b$, then the last $b$ bits should be all $1'$s. Suppose the last $x$ bits have $y$ $0's$ within them. Then there must be $y$ $1'$s preceding the $x$ last bits. We can select all $y$ $1'$s preceding the last $x$ bits and then all $y$ $0'$s within the last $x$ bits as our subsequence and reverse it. This subsequence has non-increasing elements and will sort $b$ in non-decreasing order. We have an $O(n)$ solution.

Problem C: We are given a string $s$ of length $n$ consisting of only the characters $a$, $b$ or $c$. We want to find the length of the smallest substring of $s$ which satisfies:

1. Substring has length $\geq 2$.
2. $a$ occurs strictly more times than $b$.
3. $a$ occurs strictly more times than $c$.

The only substring of length $2$ satisfying these conditions is $aa$. If this is not present then we know that any substring satisfying these conditions must have the form $(a(b\cup c)^{*})^* \cup a$. The possible substrings of length $3$ are: $aba, aca$. The substrings of length $4$ are $abca, acba$. A substring of length $5$ or $6$ cannot exist satisfying these conditions since we can't have something like $ababa$ or $abcaba$ since it contains the smaller substring $aba$ which works too. Importantly, there is are $2$ substrings of length $7$, which are $abbacca$ and $accabba$. Anything larger would necessarily include a smaller substring within it. Thus we just check for these and output the smallest. Runs in $O(n)$.

Although I didn't solve $D$ in the contest, I still had some ideas for it. I will present these below.

Problem D: We are playing a game on a tree between two players $A$ and $B$, where $A$ moves first. $A$ first chooses a node in the tree to place a token on. For the remaining turns each player can move the token from $u$ to $v$ iff

1. $\{u,v\}$ is an edge,
2. $v$ has not already been visited, and
3. $u\oplus v \leq \min(u,v)$.

$A$ wins if it is $B$'s turn and $B$ cannot make a move (inverse for $B$ winning). We are asked to assign one number from $\{1, 2, ..., n\}$ for each node in the tree such that the number of starting nodes where $A$ wins is maximized.

My first instinct was to check when exactly $u\oplus v \leq \min(u, v)$. I observed that $u \oplus v \leq \min(u,v)$ iff $u$ and $v$ have the same number of bits in their binary representation. The proof is easy. I partitioned the set of integers from $1$ to $n$ into sets where any pair in the same set satisfies $u\oplus v \leq \min(u,v)$.

$$\{1\}$$

$$\{2, 3\}$$

$$\{4, 5, 6, 7\}$$

$$\{8, 9, 10, 11, 12, 13, 14, 15\}$$

$$...$$

A natural strategy is to try to label the nodes such that for any $\{u,v\}$ edge in the tree, we have $u\oplus v > \min(u,v)$, i.e. $u$ and $v$ are not in the same partition as described above. I played around with some examples and for the examples I tried, I could always find a labeling where this was true, hence a labeling where $A$ wins for all nodes. Importantly, as far as I could tell, the line graph seems like the hardest graph to do this on since we have $n-1$ edges which need to have nodes labelled from different sets, as opposed to other graphs where a node can have multiple children, which can have labels from the same set.

At this point I was convinced that we could always label the nodes such that $A$ wins on all of them. To generate this labeling, it felt like a recursive procedure could work, starting from the leaves, and working inwards. Sadly, I ran out of time.

Reflection:

I solved $A$ a bit slowly, but stayed calm and solved it smoothly. $B$ went very well, except I misread the problem output which cost me a lot of time (like over $20$ mins), I actually got the solution really quickly. $C$ was annoying because of all the tricky cases. I found all of them eventually though. A good contest for me.