[Competitive Programming Review Note] Google Kickstart Round E problem 3

if you want to see my solution for Problem 2 [High Buildings] → https://medium.com/@eunpyolee0420/competitive-programming-review-note-google-kickstart-round-e-problem-2-94d45b80eecb

This is the problem #3 of Kickstart 2020 Round E and it’s title is “Toys”

And the problem statement is following:

Problem

Little Axel has N toys numbered from 1 to N. Each toy has two properties:

• Ei — enjoyment, which is the number of minutes Axel can play with toy number i without getting bored with it;
• Ri — remembrance, which is the number of minutes it takes Axel to forget toy number i after having played with it.

The toys are arranged in a circle, from 1 to N clockwise. Axel plays with them one by one.

When Axel reaches toy i which he has not played with yet, or which he has already forgotten about, he plays with it for Ei minutes and then immediately moves to the next one (clockwise).

If he reaches a toy that he has not forgotten yet (if less than Ri minutes have passed since the last time he finished playing with it), he will stop and cry.

We can define the time Axel spent playing as the sum of Ei of every toy Axel played with before stopping. If Axel played with a toy several times, it should be counted that many times.

Given the description of the toys, remove the smallest possible number of them in order to make Axel play either an indefinitely long time, or (if that is not possible) as long as possible before he stops.

Note:

• Axel has never played with these toys before;
• he cannot be left without toys;
• he always starts with the toy that has the smallest number;
• after finishing playing with the toy that has the largest number, he will move to the toy that has the smallest number.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. Next N lines contain 2 integers each: Ei and Ri. The i-th line is describing the toy number i.

Output

For each test case, output one line containing Case #x: y z, where:

• x is the test case number (starting from 1);
• y is the minimal number of toys to remove so that Axel could play with the rest of them either indefinitely or as long as possible;
• z is the longest time Axel will play in minutes or "INDEFINITELY" (without quotes) if he will play indefinitely long time.

Limits

Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ei ≤ 109.
1 ≤ Ri ≤ 109.

Test Set 1

1 ≤ N ≤ 12.

Test Set 2

1 ≤ N ≤ 105.

Sample

Input

Output

4
1
5 1
2
5 10
10 3
3
30 17
5 10
10 3
3
5 10
5 10
5 11
Case #1: 0 5
Case #2: 0 INDEFINITELY
Case #3: 1 INDEFINITELY
Case #4: 0 25

Comments

One thing I want to point out is that we are guaranteed to travel the first cycle without crying because no “cool time”(Remember time period) will block us during the first cycle! In other words, we can start from the point right after the first cycle and run hypothetical second round to figure out how to maximize the result!!

The crucial algorithm behind maximizing the result is to take the least valuable (who has the longest cooltime or E[i] + R[i]) and check whether this will be one of the inefficient member of the current toy combination or not (if it is inefficient, then remove this toy from our cycle)

And yes, this sounds a lot like a “Greedy Algorithm”

So I’ll use “priority_queue that will store the cooltime (E[i] + R[i]) of the toy i. And then, by running the hypothetical second cycle, I’ll start investigating the least efficient toys and decide whether or not to take that out and put the update information back to priority queue and put this candidate into the priority_queue and repeat the steps to find the maximizing combination on the fly.

What we need to store:

cur_cycle // current cycle’s length which is initialized by the sum(all E[i] in the toys) representing the first cycle’s result

e, r //vector for E’s and R’s for toy i

pq // priority queue which will store cooltime of toy i (E[i] R[i], and its toy id

max_enjoyment // the global max enjoyment and is initialized with cur_cycle since we are starting at the hpyothetical second cycle

min_rm_count // Representing the minimum number of removed toys for the tie breaker of two or more maximizing results

cur_enjoyment // Representing the current enjoyment and is initialized with cur_cylce

rm_count // the current number of removed toys

First, run the first cycle and initialize max_enjoyment and cur_enjoyment

We also define those data structure and variable we need to store key informations and now we are ready to run the second cycle!

Second, run the Greedy Algorithm!

Since we are starting from the first toy and move clockwise, iterate through the toys by that rule.
At each iteration, we will put the cooltime[i] (R[i] + E[i]) and its id i in to the priority queue which is “max heap” (so that it will always give us the current most inefficient toy which has the longest cooltime) and add the E[i] to cur_enjoyment (so that we are investigating a hypothetical case when we are including toy i in the cycle) Then we have to check whether cur_cycle >= longest_cooltime because if cur_cycle < longest_cooltime then we are destined to cry and the best result we want to have is the infinite loop of playing toys (means all of cooltime[i] will be doable under the cycle length . If cur_cycle < longest_cooltime then we need to take this out from our current cycle (greedy: take out the least inefficient toy) and since we are starting at the second cycle, we need to subtract 2 * E[i] of this toy i from our cur_enjoyment and E[i] of this toy i from our cur_cycle . (+ Don’t forget to increment the rm_count since we removed this toy!)

Until either we have no more toys to inspect or all of the candidate toys (toys in the pq) can build a infinite-loop combination, we keep investigate. And then, we update our max_enjoyment by comparing current max_enjoyment value with the cur_enjoyment (update min_rm_count using rm_count for the tie breaker because we want the maximizing result with the smallest number of rm_count! - here, I’m using — negating technique to handle the `rm_count` minimization by changing their magnitude direction)

Lastly, return the maximizing result based on the results you created in the previous step!

If our pq is not empty (which means there are some toys altogether forming a infinite loop), it is a “INDEFINITELY” case and we just need to return the minimized rm_count

Otherwise, we don’t have a combination of toys that can make a infinite loop so, return the maximizing result of a definite toy cycle and its # of toys removed from the cycle

The entire code for this:

I think the reason why this was so hard is that I was trying to do something during the first cycle which makes me overwhelmed by the many possibilities I need to take care of. But by having the hypothetical situation where you are starting at the second cycle and start investigate the maximizing result using the Greedy Algorithm, the problem got way simpler which is just “maximizing the result by investigating the current least inefficient toy in terms of the current cycle length.

Plus, the negating technique was interesting approach to apply when your maximization is to minimize.