Codeforces Round 967 Discussion stream (with hints)

Let v be the element that remains when all the elements are equal. What is the minimum no of operations required?

Let the number of times v be present in the array is fv. Because we will have to delete all the elements not equal to v, the minimum no of operations required will be n — fv.

It turns out that this minimum is the answer ie we should never delete any element equal to v from the array.

Since we want the minimum number of operations required, we should choose the element with the maximum value of fv.

Let $c_i$ be the index such that $p[c_i] = i$. Lets look at $c_{i}$ and $c_{i+1}$.

If $c_{i} \lt c_{i+1}$, Then when typewriter 1 writes $i$, it can also write $i+1$ without using carriage return operations, and typewriter 2 writes $i$; it will have to use carriage return operations for writing $i+1$.

Similar case for $c_{i} \gt c_{i+1}$

The sum of carriage return operations required by both typewriters will be $n-1$

The answer is -1 when $n$ is even.

For odd $N$, following pattern works

${1,3,5,7,9,11,10,8,6,4,2}$

How can you check if U and V have an edge connecting them?

Notice that the answer for query(U,V) is the midpoint of the path between U and V. In case the path has even elements, it returns an element close to U.

U and V will be connected by an edge if and only if Query(U,V) returns U.

Let’s root tree at 1. We will try to find the parents of all nodes.

Query(1,Y), let the result be MID1. Now Query(MID1,Y), let the result be MID2. Now Query(MID2,Y), let the result be MID3. Keep going until Query(MIDK,Y) returns MIDK. In that case, MIDK will be the parent of Y.

The length of the required sequence if no distinct elements in A.

We will greedily build the required sequence. When we select an odd index element for S, we will try to choose an element as large as possible. When we select an even index element for S, we will try to choose an element as small as possible.

Let the index of the last taken element be $i$, and R be the largest possible index such that A[R…N] contains all the elements not chosen so far.

In case of odd index element for S, select the largest not chosen element in A[i+1…R] In case of even index element for S, select the smallest not chosen element in A[i+1…R]

We can use a segment tree to query for the minimum and maximum range, and in the case of ties, we should choose the element with the smaller index. Once we have selected an element in S, we should remove all its occurrences from the segment tree.

Let’s define 3 dp. $dpValid[h][k]$ as the no of valid max heap trees of height h, and value on root is k. $dpValidChild[h][k]$ as the no of valid max heap trees of height h, and value on root is k, and we have not done any operations on root yet. $dpWays[h][k]$ as the no of different trees of height h, and value on root is k.