Consider the number of spare balloons we can spare

while we can spare more, give more to the next rank, and then delete ones that can be floated, keep going until we have no more to spare, and keep track of the best rank in the mean time

Implmentation-wise, using a double pointer style for-loop is way easier to reason than a while loop, even though while loop seems more intuitive - took me an hour to figure it out.

This is similar to the first version. However, this approach failed on test 10!!!

The key insight I was missing is that we should only try getting rid of the teams ahead of us. Otherwise, our final rank can not be improved regardless

Algorithm

	1. Add all t > k to the priority queue

	2. while we can remove from the PQ, we remove, and update the current k count.

	3. Since now we reduced k count, we need to move pointer further to include more entries > current k

724C: Ray Tracing

Claim: the ray will always hit a corner

Proof: If not, then we will form a closed loop, however, since we start at a corner, such loop is impossible

Claim: the ray hits each point only once Proof: If not, then we will have a case where it comes in the oppsoite direciton to where it is from. Since the whole sequence is reversible, this means it will come from a corner and to a corner

Algorithm

	1. For each 2 * n * m points, keep track of when it is first hit
	2. Simulate the process by calculating the next point to hit, and the hit time
	3. For each point, calculate from which x or y axis it is hit, take the earlier point, and add the distance to the answer

Note that map<PII, LL> can fit in all cached answers, if we use it to store only reached points

706D: Vasiliy’s Multiset

Maintain a set for inserted numbers and its count to handle type 1 and 2 request

For type 3 request

	1. Use set.lower_bound() to decide if there is entry for the best prefix + 1, with this we can know if it is possible to put 1 bit or 0 bit on that position 

	2. look at the requested number, and pick the opposite number

	3. start with 2^30, all the way to 2^0

Note the bitwise operation is a bit tricky. Took me some time to think it through. On our bit search, we have the assumption that this search will yield a number in the set, by induction.

735C: Tennis Championship

n = 2 , answer = 1

n = 3, answer = 2

Given the max number of games the winner plays, what is the min number of players we need?

g(n +1 ) = g(n) + g(n - 1) => this is the fibonacci sequence starting at n = 2

So we can calcuate fib until the answer > n, and the previous number is the answer

note that we need to keep track of the answer x as well, since we are calculating f(x)

740C: Alyona and mex (!!!)

When the subarrays have no overlap, trival case, just plug in into each gap, i.e., ans LT min length of the subarray, i.e., there is no point putting more than that number in that array

	0. Int final answer to 0
	1.  Get all subarrays, and sort by the start index, we also keep track of min gaplength
	2. For each subarray, scan it first to get what elements are populated, and then fill in the blanks with misssing ones

What if the input is n = m, and each l = 1 and r = n? This means we can not scan all entries for segment

Therefore, we just construct the array as 0,1,…,ans, 0, 1,…ans. This will make sure any segment of length ans in the answer will have the exact set we need

734D: Anton and Chess

For all 8 differnet lines, keep track the closest one to the king, and its type, and finally decide if it is possible

732C: Sanatorium(!!!)

Idea 1: Formula

min number of missing meal means number of days stay = highest number of on the list

If all 3 numbers are same, no missing.

If only 1 number has highest value:

number of full days = highest number - 1, and then the other 2 meals have 3 * number of days

if two numbers has highest value, 3 possiblilies,

	1. (b, d) = full days? not really! consider the zig zag pattern!
	2. (b, l) = full days, in the final answer, --dinner
	3. (l, d) = full days, in the final answer, breakfast--

Idea 2: brute force

brute force the tuple of (arrival, departure)

732D: Exams

Start from the tail, keep track of which exams we have to pass.

If it is a new exam, add days to the budget

If it is idle or seen example, budget–

Then we bsearch on the position of tail

733C: Epidemic in Monstropolis(!!!)

Obviously, before sum = after sum

so given the first item, we can calculate which items that final item is made of

if no such index exists, or if all items scanned are the same, it is not possible. Otherwise, start with the first heaviest monster in the left, and then eat all the way to the left, and finally eat all the way to the right

repeat for each item segment

What is wrong with this algorithm?

	1. I got WAed because my first biggest monster approach does not work in the case of [2, 2,1 ] => 5.

	2. To fix it, we just need to find the first maxI that can move, and then be greedy and try to each as much as we can
	
	3. My checks of two arrays having the same sum is implicit. Therefore, it didn't catch the case where a's sum > b's sum

733D: Kostya the Sculptor(!!!)

A lot of implementation details in the answer

1. Should separate the case of alone and combined, i.e., the map we use should handle the combined case only

2. Because we are looking for the best of 2, we need only to store the best bottom only. Storing the best two makes the implementation complicated => this is what gave me WA

3. To avoid adding to itself, at each item, we hold on all update to the state until all quries related to the 3 choices of bottom are done

727C: Guess the Array

Consider n = 3 case, we can just a1 + a2, a2 + a3, and a3 + a1 to solve it. We can use it as the seed for the n > 3 case

1. a1 + a2, a2 + a3, a3 + a1, solve a1, a2, a3, as per n = 3 case

2. a1 + a4, a1 + a5....., all the way to a1 + an