samatbor's blog

TL solutions
By samatbor, history, 7 years ago, In English

Hello Codeforces community, Recently I have started to notice that many solutions that I write are pretty slow, although it's always right solutions (they were intended by problemsetters). I've tried to look at code of red participants but didn't find any crucial difference in style of writing. There is one example of problem which I've tried to solve many times, but it didn't pass all the tests (due to TLE) http://codeforces.com/contest/719/submission/21066177 (the problem is http://codeforces.com/problemset/problem/719/E) Could you help me with it? If yes, please, could you tell me what makes my code so slow?

Thanks in advance for any help.

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your Code runs in O(nlg2)...Try to optimize it to O(nlg)...

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

    Yeah, thanks, I see, but I didn't want to write memoization of matrix' degrees, because I'v seen the solutions that don't do it, but still runs in 2 ms. Maybe you can see some non-asymptotical slow moments?

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

      Lots of my friends got tle with this solution too...(maybe all of them)

      My suggestion is to don't try to get accept by this ways... You may change your code a little and get accept (for example your binpow function is recursive and has function-call, maybe your time decreases if you change it) but the goal is not to get accept verdict, it's to solve the problem...

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

        Ok, I'll try to upgrade my code to O(n * lg n) Thanks for help!

        → Reply