Maintain current amount of gold Robin has. Process all ai.

• If ai>=k, increase counter by ai
• If ai==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.

pow(i,i) is odd if i is odd, even if i is even.

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

Answer is impossible if n less than 3.

Lets first find minimum no of people that should be unhappy (say K).

Lets sort A, now average should be more than 2*Ak

Lets say pot has X gold.
Let S be the total gold.

$$$2*Ak \lt (S+X)/N$$$
$$$2*N*Ak \lt S+X$$$
$$$2*N*Ak-S \lt X$$$
$$$2*N*Ak-S+1 \le X$$$

So X should be max(0,2*N*ak-S+1)

For each starting day lets 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 dp1[u] denotes the best possible sum we can get if we consider only subtree of u and u is destroyed.
For each subtree dp2[u] denotes the best possible sum we can get if we consider only subtree of u and u is not destroyed.

Lets 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 atleast 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 atleast m,

Here, lets 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 C/m days
• If this milk came on dj day, we can drink it until dj+k-1 day

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

Lets say we are playing game on targets B1,B2,B3,...,Bm
What is the optimal strategy for players?

Players should always chose the maximum target.

Lets sort B in descending order.
Then Robin takes B1,B3,B5... and Sheriff will take B2,B4,....

Because B1 \ge B2, B3 \ge B4, 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 no of targets is even, and B1 = B2, B3 = B4, and so on...

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

How to check if frequency of every no is even?
Zobrist Hashing