This problem appeared in the coding round of a company(cannot name) which was hiring interns at 100k stipend(India). This was the toughest problem of the round. I have seen similar problems at other contests but do not know the optimal solution.
Statement:
You have a shield whose power increases by 1 every second. You are given N time intervals when a Missile is fired at you. You can face it if your shield has enough power by then, or you can use counter-Missile to divert the incoming missile and decide not to take the damage. If you decide to take the damage, the power of the shield reduces by the power of incoming missile. The power of the shield should remain non-negative.
The shield starts generating power from time = 0.
Test Case:
N = 3 (Number of missiles fired at you)
Details of N Missiles.
Time -> Damage
20 ->20
21 ->4
22 ->3
It is optimal to use counter-missile on the first attack although you had enough power to take the attack.
So the minimum number of missiles that you should use is 1
Initial power = 20 since time = 20(You must have gained 1, 20 times)
N = 1 , Use counter-Missile : Power remaining: 20
N = 2; Take the attack : Power remaining : 17
N = 3, Take the attack : Power remaining : 15.
The task is to find the minimum number of missiles.
So, the answer for the case : 1.
Constraints:
N <= 1e5;
Damage <= 1e9 (I was surprised here).
The solution seems DP-ish but I dont know how to solve for Damage <= 1e9.
The problem seems to be straightforward binary search since the search space for a number of counter missiles is monotonic i.e. as we increase the number of counter missiles there will be a threshold after which we will be able to always survive. Search Space will be like [False False False ... False True True True...] so we just need to find the First True for which we will apply Binary Search.
Now Comming To the Check Function Part in our Binary Search: The check. function tells Whether we will survive with 'mid' number of counter missiles or not.So it can be easily Implemented in o(nlog(n)) complexity with the help of Max Heap or sorted set in cpp.(I assume that damage array and attack time array is sorted based on time if not u can sort it urself ). Implementation :
bool check(int mid){
int shieldValue=0; int time=0; set<int>pq; for(int i=0;i<n;i++){ shieldValue+=attack_time[i]-time; time=attack_time[i]; shieldValue-=damage[i]; pq.insert(damage[i]); while(shieldValue<=0){ mid--; shieldValue+=pq.rbegin(); pq.erase(pq.rbegin()); } } return mid>=0;}
So, what you are saying is that, we should defend only a prefix of missiles fired at us?
no that is not what i am saying , i am saying we have to avoid shield value to drop to zero at any instant of time
Well following this strategy, we won't need to binary search over the answer.
We will count the needed defends in the while loop where you are using the priority queue. Instead of
mid--we will writecount++. And return the value of count.oh! that seems to be correct , indeed nice observation!
Would be better if you could correct it in the main explanation. Also, please take a note:
shieldValuecan be zero.Else your approach is really nice and correct!
I also wrote a
Thanks, that helped. Thanks to both. Also, I think that WHILE could be replaced by IF because at most one removal is done in every iteration.
Yes, that is also correct.
Why can't you name the company? You are posting from fake id and If coding round is over then I see no point of hiding company name.
It is a problem stolen from our contest
What is the expected difficulty(rating) of this problem.
1700-1800