Codeforces Round 995 Discussion Stream (with Hints)

Assume $b_{n+1}=0$. Monocarp should solve problems on day i only if $a_i>b_{i+1}$. For all such days, find sum of difference.

Let $d=a+b+c$. Monocarp will travel $d$ km every $3$ days.

So you will need a minimum of $\lceil 3n/d \rceil$ days.

The required no of days is between $\lceil 3n/d \rceil$ and $\lceil 3n/d \rceil + 3$; check all 4 possibilities.

Result is one of 3 possibilities

1. All are 1
2. All are 0
3. Only one 1 and the rest all are 0

Try to figure out conditions for all these cases.

Based on the sum of all array and x,y, first, find the minimum and the maximum possible sum of $a_i+a_j$.

Count Pairs Whose Sum is Less than Target

There are many ways to solve this problem. The optimal price will always be some ai,bi.

First, use Coordinate Compression to reduce the range of ai and bi.

Now, for each point, using your favourite range sum data structure, you can find how many people will buy at that price and how many of them will leave a -ve review.

Explicitly maintain range of intervals where joker can exist, based on these ranges find new ranges.

The crux of the problem is at any point, there will be atmax 3 different such intervals.

Introduce a new n+1th snake. For each pair of snakes, L and R, find the minimum distance between them.

Now this is a Travelling salesman problem