wozchod's blog

Is it even possible?
By wozchod, history, 3 years ago, In English

Hello everyone, I invented a task and now I can not solve it. Can anyone help please. The condition is very simple: Two people are playing a game. They have an array of numbers and they take the numbers from the array in some order. Each time the number is taken by the one whose sum of already selected is less. The winner is the one who, after all the numbers are chosen, will have more sum. Who will win and by how much.

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

Comments Comments (6)
| Write comment?
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Well the first thing that came to my mind is bitmasks. Let dp[Mask][Mask2] be the winner if only numbers that have 1 in Mask appear in array now and first player took numbers that have 1 in Mask2. It is O(3^n) because Mask2 is submask of Mask. But I think it is possible to solve it faster.

→ Reply
»
3 years ago, # |
  Vote: I like it -32 Vote: I do not like it

Well, Your account is old and you have just solved 4 problems, It's a little SUS that you're asking this problem with this account!

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

Can you clarify what are the rules if both people have equal sum? Who gets to pick? Who starts the game is also a good question.

For instance if array is [1,2,3,4], and first person picks 3 (arbitrarily we choose first person to go first) then the second person chooses [1,2], we then have a tie where either person could choose 4. How do you resolve this tie?

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

    In general, the cases when, with an equal amount, the move goes to the next player and when the player who has achieved equality continues the move are not very different, but for definiteness, let's say that the move goes to the next

    → Reply