Help needed for problem The Meaningless Game (round 426 div1 A)
Difference between en1 and en2, changed 2 character(s)
Hi,↵

I have tried the following to solve this problem [problem:833A] 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: ↵
   ↵
3(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.↵

3(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 [submission: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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English NerfThis 2021-12-25 00:35:32 2
en1 English NerfThis 2021-12-23 06:47:26 2209 Initial revision (published)