Блог пользователя wozchod

Is it even possible?
Автор wozchod, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

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!

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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

    → Ответить