Queen_of_Mirzapur's blog

Coding Round Problem

By Queen_of_Mirzapur, history, 4 years ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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;

}

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    So, what you are saying is that, we should defend only a prefix of missiles fired at us?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        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 write count++. And return the value of count.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          oh! that seems to be correct , indeed nice observation!

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +7 Vote: I do not like it

            Would be better if you could correct it in the main explanation. Also, please take a note:

            • Use a multiset.
            • The shieldValue can be zero.

            Else your approach is really nice and correct!
            I also wrote a

            Solution
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              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.

              → Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

It is a problem stolen from our contest

→ Reply