CF-2131 (Codeforces Round 1042, Div. 3) Solution

Zero delta predicted. Are you kidding me?

2131A. Lever

Notice that the step $2$ does not affect step $1$.

For each $i$, the maximum number of times step $1$ can be performed is $\max(a_i - b_i, 0)$. So we can just sum up the number of times step $1$ is performed.

Submission #333289337

2131B. Alternating Series

First, observe that every adjacent pair has different signs and every element is non-zero.

Then, let us try to minimize the sum of a subarray. It must have a length of $3$ and the first and third elements must be negative. So the sum is $a_{mid} - 2$. But we need that $a_{mid - 1} + a_{mid} + a_{mid + 1} \geq 1$. So we have $a_{mid} = 3$.

Now, let us try to construct the array from left to right. We can see that $a_1 = -1$ because we cannot pick $1$ due to the previous condition and we need to minimize the absolute value. Keep going, for every even index $i$, we’ll pick $a_i = 3$, except for $i = n$ where we pick $2$. For every odd index $i$, we’ll pick $a_i = -1$.

Submission #333498392

2131C. Make it Equal

Notice that for every element $S_i$ or $T_i$, we can replace it with $S_i \bmod k$ or $k - S_i \bmod k$. So we can just store the minimum of $S_i \bmod k$ and $k - S_i \bmod k$ for every element. Thus, for the elements can become each other, their values stored are equal. Then we can check if the two sets are equal.

Submission #333526673

Built with Hugo
Theme Stack designed by Jimmy