NerfThis's blog

By NerfThis, history, 6 months ago, In English

Hi,

I have tried the following to solve this problem 833A - The Meaningless Game with the following approach.

  1. preprocessing: get all the prime numbers from 2 to the floor(square root of 10^9).
  2. for the input a and b, get their prime factorizations using the prime number list.
  3. do the following check:

(a). check if both a and b's prime factorizations contain the same set of prime numbers, i.e, there is no prime number that only exists in one of the factorization but not the other.

(b). if passing the above check, then for each prime number P that appears in the factorization, do the following check:

A few notes: Say P appears v1 times in a's factorization and v2 times in b's factorization.

Of all the times P appear in a round, assume the 1st player(Slastyona) wins c1 times and the 2nd player(her dog) wins c2 times, we then have:

c1 * 2 + c2 = v1

c1 + c2 * 2 = v2

from the above two equations, we have c2 = (v2 * 2 — v1) / 3, c1 = v2 — (v2 * 2 — v1) / 3 * 2. So we check if v2 * 2 — v1 >= 0 and is divisible by 3, we also check if c1 >= 0. If these conditions are all true, the check for the prime number P passes otherwise it fails.

Intuition:

  1. The reason that I chose to use prime factorization is that each round if we are given a composite number k, we can convert it to a product of only prime numbers and use multiple rounds to get the same result. For example, if k is 6, then k^2 = 36, we can have 1 round of k = 2 and another round of k = 3 to get the same result.

  2. The max prime number we need to consider is upper bounded by the square root of 10^9 since if there is prime factor that is bigger than this upper bound, then the winner of that round will multiply a number that is bigger than 10^9.

However, the above approach is incorrect and it fails on test case 4. Unfortunately I can not see the input that gives the wrong output. My submission link is 140311042

I think my approach is not correct but could not figure out why it is wrong, can some one help to provide some insights on why this gives the wrong answer?

Thanks!

Read more »

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

By NerfThis, history, 8 months ago, In English

Hi,

I am trying to solve this problem from atcoder : B — LRUD Game. After reading the editorial and this https://codeforces.com/blog/entry/66849#comment-510066, I still do not understand the solution and have the following 2 questions:

  1. why we need to process all moves by both players backwards?
  2. When processing backwards, other than the last move by the 2nd player, we need to first do updates based on the 2nd player's moves, then the 1st player's moves. Doing it the opposite yields a wrong answer.

Can some one help me understand the above 2 key ideas?

This is my AC submission after reading other people's submission: submission link.

Thanks!

Read more »

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