logrt's blog

How to solve this problem optimally?
By logrt, history, 3 years ago, In English

Given a grid A of size N*M, 2 players are playing a game on it taking alternate turns. In each turn, a player chooses a subset of elements from any row and replaces each one of them with their proper divisor. A proper divisor of a number N is any divisor of N, not equal to N. The player who is unable to move, loses. Determine the winner of the game.

Problem Constraints:

1<=N, M<=10^3 1<=A[i][j]<=10^6

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

Comments Comments (5)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I suppose if you wanted the strategy of the loser, they would be able to play forever if there are at least 2 proper divisors of A[i][j]. Otherwise the other cases: (0, 1) and one are pretty simple to figure out. Can you please send the problem link, thanks.

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

    Proper divisors of N are all divisors smaller than N.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, but couldn't they just pick 1 and divide? As long as a[i][j] is greater than 1, they would be passing along their state to the other person, and vice versa. This would continue forever.

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

        No, you replace those numbers with proper divisors, not divide them by that. If you divide N by 1 you get N and the problem doesnt allow that

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

If i had one nickle for every time i saw someone ask about this question in codeforces i would have two nickles, but it's kind of strange since it happened twice.

Here is my solution: https://codeforces.net/blog/entry/93095?#comment-819536

→ Reply