Codeforces Round 970 Discussion stream (with hints)

• No of ones must be even.
• If no of ones is zero, then no of twos must be even.

These are necessary and sufficient conditions.

If it is a square matrix, then N must be a perfect square.

If N is a perfect square, then R=C=Sqrt(N).

Now, we can create R*C beautiful matrix, and then create required string. Then check if it is equal to given string.

Lets try to create array greedily.

$A_1=L$,

$A_i-A_{i-1}=i-1$ for all $2 \le i$,

In general, after simplification,

$A_i=L+(i-1) \cdot i/2$ for all $2 \le i$.

Longest array length depends only on $R-L$. We need the largest $N$ such that $N \cdot (N-1)/2 \le R-L$.

Permutation cycle

Create a graph with edge $i \to p_i$, and notice that each connected component is a cycle. For each connected components count the no of black nodes, and then update this count for all nodes.

Solve for N = even first.

We should look at chars at odd index and even index. Greedily chose the one that appears maximum no of times, and replace all the other chars.

For N = odd, we can iterate on index i that needs to be deleted. Chars at odd index before index i we will remain at odd index, and chars at even index after i will move to odd index.

One can either use sliding window or prefix sum to find new frequecies at odd and even index after deleting char at index i.

We should find sum of product of all pairs, then we can divide by $N \cdot (N-1)/2$ for expected value.

$\sum_{i=1}^{n} \sum_{j=1}^{i-1} a_i \cdot a_j$

$= \sum_{i=1}^{n} a_i \cdot (\sum_{j=1}^{i-1} a_j)$

You can now iterate on index i, and maintain a running sum of all the index before it. Use this sum and $a_i$ to find sum of product of all pairs.

Solve for $N=2$ first.

Forget about $K$, and try to find smallest two positive nos you can have in the array.

Use only $a_i = a_i - a_j$ operation.

Let $u \ge v$. If we repeatedly doing $u = u - v$, as long as we can. We will end up with $u = u \bmod v$.

This algorithm now sounds familiar?

Euclidean algorithm

The two nos you will end up will be $\gcd(a_1,a_2)$ and $\gcd(a_1,a_2)$, then we can change them to $0$ and $\gcd(a_1,a_2)$.

Now, we can generalise this, and say we will end up with $n$ times $\gcd(a_1,a_2,…,a_n)$.

We can change one of these to $0$, and for remaining we can do, $a_i = a_i + a_j$ operation to obtain first $N-1$ multiples of gcd. Then check which is the kth smallest missing no.

$a_i = a_i + a_j$, this operation only changes the value which is larger. So if we change any no to $0$, we can never increase it.

This was the reason why constraints were change to $1 \le a_i$.

Thanks neal and Dominater069 for flagging earlier hints I had were wrong.

Because we want smallest median, we should do operation as long as we can. We will end up with $a_i = a_i \bmod x$.

Binary search for the median, and try to find how many nos can be $\le \text{mid}$.

To get this count, we need count of nos in range $[j \cdot x, j \cdot x+\text{mid}]$. We can find this sum in $O(N/X)$ using prefix sum. With overall time complexity $O(N/X) \cdot \log X$.

Queries can contain repeated $X$, but memorise the result for so that you do not have to find it again. This will lead to $N \cdot \log^2 N$ time complexity.