Codeforces Round 974 Discussion stream (with hints)

Maintain current amount of gold Robin has. Process all $a_i$.

• If $a_i \geq k$, increase counter by $a_i$
• If $a_i = 0$ and we have some gold, decrease current gold by 1 and increase answer.

On last day only leaf grown between $n-k+1$ and $n$ day will remain.

$\text{pow}(i, i)$ is odd if $i$ is odd, even if $i$ is even.

We need number of odd numbers between $n-k+1$ and $n$

Answer is impossible if $n < 3$.

Let’s first find minimum number of people that should be unhappy (say $K$).

Let’s sort $A$, now average should be more than $2 \cdot A_k$

Let’s say pot has $X$ gold. Let $S$ be the total gold.

$$2 \cdot A_k < \frac{S+X}{N}$$ $$2 \cdot N \cdot A_k < S+X$$ $$2 \cdot N \cdot A_k - S < X$$ $$2 \cdot N \cdot A_k - S + 1 \leq X$$

So $X$ should be $\max(0, 2 \cdot N \cdot A_k - S + 1)$

For each starting day let’s find how many jobs it overlaps with.

Two Pointers

In addition, $h$ of the $n$ vertices each has a single horse available.

Just forget this condition exists, and assume each place contains unlimited horses.

Now for each place try to find the minimum time, if we reach there using a horse, and without a horse.

Try to solve above problem using a modified version of Dijkstra’s algorithm

At last fix a meeting point, and take maximum of minimum time each person takes to reach there with or without horse.

DP on trees

For each subtree $\text{dp1}[u]$ denotes the best possible sum we can get if we consider only subtree of $u$ and $u$ is destroyed.

For each subtree $\text{dp2}[u]$ denotes the best possible sum we can get if we consider only subtree of $u$ and $u$ is not destroyed.

Let’s first process each day one by one.

We should maintain list of all drinkable milks in a map. We should remove all non drinkable milk. We should add all the new milk we have got today.

Now split into 2 cases:

• Latest milk quantity is less than $m$.
• Latest milk quantity is at least $m$.

For case 1, when latest milk quantity is less than $m$, We should bruteforce by taking latest milk and until we have total $m$, or no milk remains.

Then increase time by 1.

For case 2, when latest milk quantity is at least $m$,

Here, let’s try to find how long can we drink current milk.

We can drink it until:

• Some other milk comes
• If current quantity is $C$, then we can drink it for next $\lfloor C/m \rfloor$ days
• If this milk came on day $d_j$, we can drink it until day $d_j+k-1$

Take minimum of these 3, and assume we have gotten $m$ milk each day. Then remove this quantity from latest milk, and increase time.

Let’s say we are playing game on targets $B_1, B_2, B_3, \ldots, B_m$

What is the optimal strategy for players?

Players should always choose the maximum target.

Let’s sort $B$ in descending order. Then Robin takes $B_1, B_3, B_5, \ldots$ and Sheriff will take $B_2, B_4, \ldots$

Because $B_1 \geq B_2$, $B_3 \geq B_4$, and so on…

At this point, Sheriff can never win. When can we have a draw?

We will have a draw if and only if number of targets is even, and $B_1 = B_2$, $B_3 = B_4$, and so on…

In other words, frequency of every number in $B$ should be even.

How to check if frequency of every number is even?

Zobrist Hashing