Https://www.codechef.com/viewsolution/29977474

1

https://www.codechef.com/viewsolution/29977474
@shubham_avasth Sir,can you kindly explain your solution of the problem Monstbat in codechef february lunchtime 2020?

Why are you pushing -cur in pairs into t1? and then again why r you inserting cur,new_cur in t1?What is the role of t2?
Thanks in advance…

2

I start by pushing all the attacking and defending monsters of the two players in priority queues. Then, I simulate all moves the players would take greedily (not considering future game states).

The pairs \{cur, new\_cur\} I push into the vector t1 represent \{ sum1 - sum2, \ value \ of \ sum1 - sum2 \ obtained \ after \ applying \ the \ best \ move\} at every attacking step of player 1 in the sequence of moves being simulated.

t2 is similar to t1, the only difference is that it is for the player 2 and sum1 - sum2 is replaced with sum2 - sum1. t2 is not useful though.

After simulating the longest possible sequence of moves, I calculate the answer taking care of the fact that a player can end their turn at any step to maximize their score.

Hope it helps. In case it doesn’t, feel free to ask again.

3

@shubham_avasth Sir, sorry for the late response . Thanks for your answer. I still have queries from your code . I kindly request you to explain them?

1.Why are you pushing {cur,cur} when one of the attack arrays or defence arrays are exhausted?Also why are you pushing {-cur,-cur} for p==0 although you have already negated cur at the end of the previous iteration?
2.The last loop where you calculate the final answer , can you kindly explain the logic behind it?
You have previously said “I calculate the answer taking care of the fact that a player can end their turn at any step to maximize their score” but can you kindly explain it again in a bit more elaborative way?
3. Lastly ,how you came up with the intution of the approach you took?
I hope that you can kindly answer these queries so that I can be a better programmer…
Thanks in advance…

4
  1. Please note that in both the cases, I am pushing the pairs to the vector t1. If it is the first player’s turn and they cannot make a move, I push the current state to the vector. If it is the second player’s turn, I am pushing the state that player 1 will receive, therefore an extra negation (note that I am pushing the pair to t1).
  2. You basically want me to explain:
    ans = max(t1[i].F, min(ans, t1[i].S))
    Here, the max takes care of early ending of the game.
    The first argument to max is the score player 1 will obtain if they reach the i^{th} iteration of the game. This is also the score they will get if they decide to end the game at this step. If they decide to continue though, the score they will obtain is the second argument to max function, i.e. min(ans, t1[i].S). t1.S is the score player 2 will receive at heir turn, which they may decide to end. In case they don’t, we will move to the next round. ans is the maximum value player 1 can obtain if he plays optimally if he reaches the next round, which we calculated earlier. Since player 2 always tries to minimize the score, min is used in the second term.
  3. As I wrote earlier, I just simulated the whole sequence of possible turns. The best step at each turn is very easy to observe, so the only problem left is to take care of the cases where a player decides to end his turn to get an optimal score. This can be easily handled through a single loop.
    Basically, this was my intuition to solve the question.

Finally, I would just want to add that my solution is not a very good one. A recursive approach would be much better and intuitive. You can take a look at some recursive solutions to this problem as well.

Hope it helps.

5

By the way, the link you mentioned does not point to my submission.

6

Yes yes,I noticed it later.Sorry for that

7

@shubham_avasth sir I am still having some doubts.
If I try to summarise what’s happening in that “ans=” line it will be
ans=max(score if chef stops the game,score chef continues to play the game).
Please correct if I am wrong.
Now you have said that t1.s is the score player 2 will receive at her turn , but in t1 you have actually pushed X-Y which is actually chef’s score.
Can you do a bit re-explanation as to why you are taking the min as the second argument to max?
You have explained that bcz player 2 always tries to minimize x-y …it’s still not clear for me.
I apologise for having to make you explain again and again. It is just bcz I tried to follow an approach similar to yours which didn’t work. So I am trying to understand where I faultered.
Thank you for the explanation you have given previously…

8

Both t1.F and t1.S are the values of \Sigma X - \Sigma Y in the different turns.
The second player tries to maximise \Sigma Y - \Sigma X, which is the same as minimising \Sigma X - \Sigma Y. The min takes care of both the case where the second player decides to stop in their turn and the case where the second player decides to continue.

Hope it helps. Feel free to ask again if you have any doubt.

9

@shubham_avasth sir,many many thanks. You just nailed it down with this explanation . I have understood the logic.
My wholehearted thanks to you for taking time and patience to clear my doubt.
Hope to meet you someday at some coding competition.

1 Like