Codeforces Round #1071

Problem A

The problem reduces to finding the longest string such that

1. there are only $k$ characters in the string
2. every $x$ characters are different

The answer is $$kx+1$$

Problem B

Suppose that you don't skip any floors. The distance you need to travel is$$S = \sum_{i = 1}^{n} |a_i - a_{i-1}|$$

To figure out which floor to skip, we consider skipping each floor in the sequence, in particular to skip floor $i$, the points is augmented by $$|a_{i + 1} - a_i| + |a_i - a_{i - 1}| - |a_{i + 1 } - a_{i - 1}|$$

Note that this works for all $i$ in $[1, n-1]$. For the edge cases where $i = 0$ or $i = n$, the augmented points are simply $|a_1 - a_0|$ and $|a_n - a_{n - 1}|$ respectively. Note that it is only important to store the best net difference because we can apply the difference at the end.

Problem C

Two observations help simplify the problem:

1. We can immediately lower bound $k$ by $\min_ia_i$ as choosing $k_0=\min_i a_i$ is possible if we choose $x_i=a_i$, namely $a_i\%a_i=0$
2. $\forall x, m$, $x<m \implies x\pmod m\equiv x$.

Suppose we choose some $k\gt k_0$. Let $a_j=\min_i a_i$. Then $a_j \% x_j = a_j$ as $$x_j \ge k \gt k_0 = a_j$$ Namely, we see that it must be true then that $$a_i\equiv a_j\pmod{x_i}\iff k\le x_i\big|a_i-a_j$$ Note that the biggest $x_i$ which divides $|a_i-a_j|$ is $|a_i-a_j|$ itself. Hence, it is clear that $$k=\min_i x_i=\min_i |a_i-a_j|$$ Without loss of generality, let us sort $a$. Namely, this makes $j=0$. The closest number to $a_0$ is $a_1$. Hence, $$k=\min_i |a_i-a_0|=a_1-a_0$$

Hence, the final answer must be the best of the two strategies, namely $$k=\max(a_0, a_1 - a_0)$$

Problem D

Problem D is a typical bitwise manipulation question. The order of the numbers we want to generate looks as follow:

This solution minimizes the number of bit positions whereby there exists a 0 in any row, while preserving a lexographical sorting. We systematically sacrifice the leftmost bits, and iterate thorugh all the permutations which require the sacrifice but have not appeared.

Notice that the rightmost $n-i$ bits are always 1s, the $i$th bit is a 0, and the leftmost $i-1$ bits iterate through the ordered sequence $[0,(1<<(i-1)) - 1)$ (see underlined). Hence, in the solution, we generate $n-i$ 1s, and then shift $i$ into position.