simp1eton's blog

CodeChef June Cook-off D-Power Permutation
By simp1eton, 13 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    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
    → Reply