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

CodeChef June Cook-off D-Power Permutation
Автор simp1eton, 13 лет назад, По-английски

Hi,

I was doing the problem D-Power Permutation on CodeChef. The problem statement is given below:

http://www.codechef.com/problems/DPOWPERM/

I coded a PIE solution, but I kept getting TLE on the CodeChef server. I tried running on 10 testcases of max N and max D and randomised bijection on my own computer, but I got the result in 0.016 sec. Can someone help me out and tell me what is wrong?

Thanks in advance!

My code is given below:

http://pastebin.com/mZcEaGcJ

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

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

At first your solution is wrong. Try this test
4 12
2 1 4 3.
Your answer I guess is 6, and the correct one is 9.
Read editorial for correct solution.

Random tests are the worst tests for this problem.
Try test where lengths of cycles are the first 20 primes and D=1018.
For this problem this test requires the most operations.
In order to improve your solution you need save all primes p for which A[p]=1 in array and in your recursion iterate only through this array. But of course you need to change logic of you solution.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Thank you! I realised that my solution is incomplete after I read your analysis. I only took into account numbers that are coprime with all the cycle lengths :(.

    Thanks for the very interesting contest! It seems that you like math problems a lot XD
    → Ответить