[Competitive Programming Review Note] Google Kickstart Round E problem 3
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 11Case #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 thecooltime[i] (R[i] + E[i])
and its idi
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 theE[i]
tocur_enjoyment
(so that we are investigating a hypothetical case when we are including toyi
in the cycle) Then we have to check whethercur_cycle >= longest_cooltime
because ifcur_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 ofcooltime[i]
will be doable under thecycle length
. Ifcur_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 subtract2 * E[i] of this toy i
from ourcur_enjoyment
andE[i] of this toy i
from ourcur_cycle
. (+ Don’t forget to increment therm_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 currentmax_enjoyment
value with thecur_enjoyment
(updatemin_rm_count
usingrm_count
for the tie breaker because we want the maximizing result with the smallest number ofrm_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 minimizedrm_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.