Codeforces Round #1111

I did this contest live. I am still not that great at div 2, I only solved by to D easy. Post contest I will try D hard, E and F

A

Given a list of numbers, you will have some starting sum, call it $s$. For each operation, one of two things happens. If one is $-1$, and one is $1$, then the sum is unchanged. If both are $-1$, then the sum increases by $4$, and if both are $1$, then the sum decreases by $4$ after the flip. Hence, we can think about the problem as moving the sum up and down by $4$ each time, and we want to know if we can reach $0$.

It is important to remember that to move by $4$ or $-4$, we must have a pair of adjacent $-1$ or $1$ respectively. Thus, we keep track of how many pairs of these we have to compute whether or not we can get to $0$.

B

The problem asks us to make a list of numbers (all of which have to be $>1$) such that the smallest subarray sum (which sums to $m$) is of length $k$. The list I came up with was a list of $k-1$ $\lfloor\frac{m}{k}\rfloor$'s, and then a single $\lfloor\frac{m}{k}\rfloor + m\% k$ at the end. The rest of the numbers in the list is $1$. The sum indeed is correct. Furthermore, since all the numbers are too small, the smallest subarray sum is indeed of length $k$.

C

There are four cases for each digit: either we start with a 0, and go to either 0 or 1, or we start with a 1 and go to either 0 or 1. The interesting cases are 0 to 1 and 1 to 0.

For 1 to 0, as long as you have an odd number of such flips to complete, you can just do it in one move. If there is an even number $n$ of such flips to complete, you can complete it in two moves with one move flipping $n-1$ digits and another move flipping $1$.

For 0 to 1, you can piggyback as many as you want as long as there is a 1 to 0 flip happening. Suppose there exist no 1 to 0 flips. There is still a way to kill arbitrary amounts of 0 to 1s. This can happen as long as you have at least one 0 to 0 and 1 to 1.

D Easy

The problem asks what is the smallest k such that a list is k-sortable. To be k-sortable, a list must be able to be sorted by only swapping indicies $i$, $j$ such that $i\oplus j \le k$.

The first observation is that $k$ must be of form $1<<n$. For contradiction suppose that $k=1<<n | m$ with $0<m<(1<<n)$. We claim that $k_0=1<<n$ works iff $k$ works. Suppose $k$ works. For swap $s=i\oplus j\le k_0<k$, clearly both $k_0, k$ can do the job.

Consider swap $k_0<s\le k$. Specifically we know that $s=k_0| m_0$ with $0<m_0<(1<<n)=k_0$. Let $i_0 = i\&\sim k_0$ and $j_0=j\&\sim k_0$. (note this is possible because we assume that the list is $k$-sortable, namely $i\oplus j=s\le k$).

First, we swap $i, i_0$ and $j, j_0$. This is valid since $i\oplus i_0=i\& k_0\le k_0$ and $j\oplus j_0=j\&k_0\le k_0$.

Then we swap $i_0$ and $j_0$. This is valid beacuse $i_0\oplus j_0 = (i\&\sim k_0)\oplus (j\&\sim k_0) = (i\oplus j)\&\sim k_0=s\&\sim k_0=m_0\le k_0$.

Then, making swap $i, i_0$ and $j, j_0$ gives the same total effect as swapping $i, j$. This move can be visualized using the diagram below.

Note that in case 1, $s<k_0$ and case 2, $s\ge k_0$.

In general, we can prove that if $\lfloor\frac{i}{2k_0}\rfloor = \lfloor\frac{j}{2k_0}\rfloor=d$, then $i$ and $j$ can be swapped. Specifically, let $i=d(2k)+r_i$ and $j=d(2k)+r_j$ with $0\le r_i, r_j<2k$. Let $r_{i,0}=r_i\%k$ and $r_{j,0}=r_j\%k$. Let $i_0=d(2k)+r_{i,0}$ and $j_0=d(2k)+r_{j,0}$. We claim that the same motion can be done to swap $i,j$, namely swapping $i, i_0$ and $j, j_0$, then swapping $i_0, j_0$, then swapping $i, i_0$ and $j, j_0$. Recall that $k=1<<n$, hence $2k=1<<(n+1)$.

First, we prove that we can swap $i, i_0$ (or $j, j_0$ if you swap all $i$ in proof with $j$, including subscripts). $$\begin{aligned} i\oplus i_0 = (d(2k_0)+r_i) \oplus (d(2k_0)+r_{i,0}) \\ = (d<<(n+1)+r_i) \oplus (d<<(n+1)+r_{i,0}) \\ = (d<<(n+1)|r_i) \oplus (d<<(n+1)|r_{i,0}) \\ = \sim (d <<(n+1))\& (r_i \oplus r_{i,0})\le r_i \oplus r_{i,0} \end{aligned}$$ We can observe that this value is either equal to $0$ or $k$, both of which are $\le k$.

Next, we prove that we can swap $i_0, j_0$. $$\begin{aligned} i_0\oplus j_0 = (d(2k_0)+r_{i,0}) \oplus (d(2k_0)+r_{j,0}) \\ = (d<<(n+1)+r_{i,0}) \oplus (d<<(n+1)+r_{j,0}) \\ = (d<<(n+1)|r_{i,0}) \oplus (d<<(n+1)|r_{j,0}) \\ = \sim (d <<(n+1))\& (r_{i,0} \oplus r_{j,0})\le r_{i,0} \oplus r_{j,0}\le k \end{aligned}$$ as both values are mod $k$.

The proof is if and only if, but i'm too lazy to prove the inverse. The key is that you would have two seperate ds, which would not cancel out nicely (as above), hence leaving a residual larger than k.

More intuiatively, the result above shows that within each $2k$ block, arbitrary swaps can be conducted. However, you can swap outside of your $2k$ block, but only with the same $2k$ block. Hence, if each $2k$ block can be sorted, then the entire list can be sorted.

To find the minimum k, binary search can be employed. This is because k-sortability is monotonic on k.

D Hard

The main idea is aleady exploited in D easy. The main challenge is to figure out how to do the queries. This problem has the perfect structure for segment tree, in particular due to the nature of the relationship between k and spans of length powers of 2.

The transition per level is as follows: If the left and right children have (value not index) ranges which are non intersecting and sorted, then the min k between each is used. Notice that if through the entire traversal the ranges are non-intersecting and sorted, it means that the entire list is sorted, hence k=0 is appropriate. If the ranges are intersecting or unsorted, then we pick k based on the level we are at. In particular, we consider the index range spanned by the left and right children, and choose k to be half of that range, namely 2k = length of range. This mirrors thte fact that any range of length 2k can be sorted with k-sortability.

E

We can determine upper and lower bounds on the value of $k$ for a tree of order $n$. The lower bound is given by the "star" tree, where each node is connected to the root. This gives a lower bound of $2(n-1)$, as each outside node ($n-1$ of them) introduces $2$ steps. The upper bound is given by the "line" tree, where each node is connected to the next. In particular the line tree has the odd nodes increasing to the center, then the even ones decreasing from the center. This gives an upper bound of $\frac{n(n-1)}{2} + \lfloor\frac{n}{2}\rfloor$.

The claim is that for every $k$ that needs to be made above $2(n-1)$ (all the way up to the upper bound), there is some set of mutations on the tree which makes it achievable. We notice that any tour of the graph must be of even length, hence $k$ must be even, and the mutations work in steps of 2. The constructive is as follows: by moving some node "down" the subtree (even or odd depending on the value of the node), we can increase the value of $k$ by $2$.

We greedily kill as much excess $k$ as possible by moving the lower nodes first, then the higher nodes down the tree.

F

We say that $u$ and $v$ are in some good $S$ $\iff$the set of paths going through $u$ and $v$ (namely $P_u, P_v$) is the same $P_u=P_v$.

The inverse is very easy. If $P_u=P_v$, then $\{u, v\}$ is a good set.

Let $u, v$ be in some good $S$. To show that $P_u=P_v$, we need to show that $p\in P_u \iff p\in P_v$. $$p\in P_u \iff u\in p\iff S\subseteq p\iff v\in p\iff p\in P_v$$ The first equivalence is by definition of $P_u$, the second equivalence is by definition of a good set. It is mirrored on the other side.

We can exploit the transitivity of the good set relation to find all good sets. In particular, if $u, v$ are in some good set, and $v, w$ are in some good set, then $u, v, w$ can all be in the same good set. This is because $P_u=P_v=P_w$. Suppose we partition the entire set of nodes into maximal good sets, namely $S_1, S_2, \ldots, S_k$. We claim the solution to the entire problem is $$\sum_{i = 1}^{k} 2^{|S_i|}-1\pmod{998244353}$$ This is because for each maximal good set, we can choose any nonempty subset of it to be a good set.

Hence, if we have some mechanism to hash the set of all paths which go through a node, we can use that to find all maximal good sets. Note that to evaluate the gigantic powers of 2 mod 998244353, we must use a precomputed array. As always it is important to remember your mod rules.