1
$\begingroup$

I have a list of tokens T, of length n. Initially I have power p and a score of zero. In one move, I can play any token t either face up or face down.

(a) I can play t face up, provided that I have at least as much power as t (i.e, t <= p). Playing this move scores 1 point (score+=1), but decreases power p by t (i.e, p-=t).

or

(b) I can play t face down, provided that I have a positive score (i.e, score > 0). Playing this decreses score by 1 (i.e, score-=1), but increases power p by t (i.e, p+=t).

A token cannot be played more than once. Not all tokens need to be played.

I want to maximize the score after playing any number of tokens.

The solution is to sort the tokens and use the smallest possible token as long as there's enough power. If we don't have enough power to play the smallest possible token t face up at any point, then, we play the largest possible token, face down.

This approach is conserving as much power as possible while playing face up. And, gaining the maximum possible power while playing face down. It sounds reasonable when I write this down in English.

But why does this work ? This appears to be a greedy method. And I think I have to use some form of contradiction to prove correctness.

Here is what I have tried so far:

An optimal solution exists. It achieves maximum score M.

T was {t_0, t_1, ... t_n-1}, but after sorting T becomes: {t_0', t_1', ... t_n-1'}.

Let's assume the optimal solution plays tokens in the following sequence S_opt: {face_up(t_0'), face_up(t_1'), face_down(t_n-1'), ...}.

The first move has to be face_up(t_0') in the optimal solution (provided t_0' was less than or equal to p) as we start with zero score. Length of S_opt may not be equal to n.

If I have to contradict this, I have to assume a better permutation of {t_0', t_1', ... t_n-1'} exists, and that it will achieve a score that is more than M. Let me call this sequence of moves, S_contradiction

I'm going to consider the first token in S_opt that is not the same as S_contradiction. I'm going to call this token in S_opt as S_opt_t_f and in S_contradiction as S_contradiction_t_f.

Now, there are two cases:

case 1: S_opt_t_f is greater than S_contradiction_t_f

case 2: S_contradiction_t_f is greater than S_opt_t_f

I'm not sure how to proceed further with this approach.

I also thought about 'trading' power for score. That is, buying the maximum possible power for the least expense of score, or by spending the least possible power for gaining the maximum possible score. I do not know how to construct a proper proof with this approach.

Can you please help me with the proof ? Thanks!

This is a question from LeetCode: 948. Bag of Tokens.

$\endgroup$
3
  • 2
    $\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$
    – D.W.
    Commented Apr 5 at 19:42
  • 1
    $\begingroup$ Hi forgot an important fact from the linked site: Each token can be played at most once. $\endgroup$
    – gnasher729
    Commented Apr 5 at 21:35
  • $\begingroup$ @gnasher729, yes. Sorry, I forgot. Will edit now. Thanks. $\endgroup$
    – rranjik
    Commented Apr 5 at 21:46

1 Answer 1

3
$\begingroup$

If $(t_0, t_1, …, t_{n-1})$ is the sequence of tokens played by your greedy solution, you can show by induction that for any $k\in \{0, …, n\}$, the sequence $(t_0, …, t_{k-1})$ is the sequence of $k$ tokens that grants the greatest score AND the greatest power.

There is nothing to prove for the initialization (because there is only one $0$-length sequence). For the induction:

  • either $t_k$ is played face up, and it is the lowest value among all remaining tokens (otherwise you could switch it with a token previously played face up and increase the power);
  • or $t_k$ is played face down, and it is the greatest value among all remaining tokens (otherwise you could switch it with a token previously played face down and increase the power).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.