Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

luvcoding99's blog

Quantbox 2022 Online Assessment Question: Monster fight
By luvcoding99, history, 9 months ago, In English

I need to fight N monsters whose energy is given by the array Arr[1:n]. I need to maximize my glory points which are defined as the net number of battles won. Initially, I have Energy E and 0 glory points. I must battle the monsters sequentially from left to right in a queue. I have the following 4 options: 1. If my current energy is greater than the monster's energy I can defeat it and lose energy equal to that of the monster's energy and gain a glory point. 2. I may choose not to compete with the monster. Then neither my energy nor my glory point changes. 3. I may delay my encounter with the monster by sending him to the back of the queue. Then neither my energy nor my glory point changes. 4. I may lose to the monster to gain its energy but lose a glory point. My energy should always be greater than 0. And glory points at all times greater than or equal to 0. Find the maximum value of glory points. Constraints: 1=<N<=1000 1<=E<=10^6 1<=Arr[i]<=10^6

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A clarification. If energy of monster you're battling with is lesser than your energy, still you can choose to lose from that monster to gain its energy. Am I correct?

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

    Yes you can

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

    If that is true, then notice that due to sending a monster at the back of the queue option, you can fight the monsters in any order (which is easy to prove).

    Sort all the monsters on the basis of energies. Fix the number of monsters you lose to. Call it $$$k$$$. It is optimal that you lose to $$$k$$$ monsters with highest energies (suffix of length $$$k$$$ in the sorted list).

    It is optimal to win against some prefix of monsters in the list. For every $$$k$$$, find the highest $$$j$$$ such that $$$j \le n-k$$$ and $$$sum[1..j] \le sum[n-k+1..n] + E$$$. Note that $$$sum[i..j]$$$ denotes the sum of energies of monster from $$$[i..j]$$$ in the sorted list. You score for that $$$k$$$ is $$$j-k$$$.

    Do this for all possible $$$k$$$ and find maximal score. You may use binary search for that.

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you give a proof that the monsters can be ordered in any possible way we want

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

        Let's say you have m monsters left at a given point — a_1, a_2, ... a_m, and you want to battle monster a_i. You can send all monsters from a_1 to a_i-1 to the back so that now a_i is the first monster in the queue. You can fight it now.

        The same can now be applied to remaining monsters.

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

      I don't think we need to select k monsters to defeat just maintain a multiset keep eliminating the lowest monster until you can, update the answer with current points and then lose by the most powerful monster. this easily works in O(nlogn), and log factor can be further improved by 2 pointers.

      → Reply