storyteller123's blog

Help needed for this game theory problem .
By storyteller123, history, 7 years ago, In English

Two players are playing a game where they are given an array of integers (A[i]<=10^6) .Each player can choose a number from the array and separate it as x,y where x*y=A[i] and put these numbers back in the array.A player loses if he cannot make any move.Also we cannot represent a number as 1*Number.My doubt here is how can I find the most optimal way of playing like I had some of the ways of separating a number like 1. Prime*Composite 2.Composite*Composite 3.Prime*Prime.But how do I determine the winning/Losing state ?

  • Vote: I like it
  • -3
  • Vote: I do not like it

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

Calculate grundy number G[i] for each number in array and take XOR of it; you can see that grundy number of any element depends upon the number of prime factors of that number in this problem let P(a[i])denotes the number of prime factors of a[i]; if(P(a[i]%2==1)G[i]=0; else G[i]=1; now take XOR of all the grundy numbers and you have your answer

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I may be wrong ....

But, here's my approach.

Regardless of what move you make, the size of the list increases by 1 after each move.

At the end, the size of the list is P, where P = sum of the number of prime factors of every A[i].

We know the final size of the list, and we also know the size increases by 1 in each move.

Number of moves = (P — N)

The parity of the number of moves will tell you who makes the last move.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not quite good at game theory in competitive programming. But I can recommend you a book written in Competitive Programmer's Handbook — a new book on competitive programming. If I understand this correctly, I think you can check the "Game theory--Sprague–Grundy theorem" chapter in that book. Specifically, you can check page 234, which talks about subgames.

→ Reply