Keshav DhandhaniaFormer TopCoder India #1. DM me for 1-on-1 mentorship (paid) · 2w
The problem is all about figuring out the parameter to be greedy on. One way to think about the greedy parameter is you need to figure out what is the effect of a certain decision on the global score.
In this problem, the global score is not a single number. It's two numbers = (your score, opponent's score). How can you reduce this to a single number?
One way to make it a single number is overall score = (your score - opponent's score). So if overall score is positive, you win. If it is negative, the opponent wins. Next, you need to figure out what is the effect of a certain decision on the global score.
The overall score increases by A[i] if you choose i-th element, and it decreases by B[i] if you do not. So, the total effect of choosing vs not choosing i-th element is A[i] + B[i]. Hence, that is the parameter you should be greedy on.
Sort pairs (A[i], B[i]) by A[i] + B[i] (descending order). The players pick the elements 1 by 1 (alternating) from this sorted list of pairs.
Read more… (196 words)