dcordb's blog

My solution gets TLE on 712D (Memory and Scores)
By dcordb, history, 8 years ago, In English

Hi everyone. My solution to problem 712D gets TLE, even though its complexity is . Where d is the difference between the score of Memory and Lexa. Note that  - 2·105 ≤ d ≤ 2·105.

The funny thing is that in my laptop (Intel Core i5, 4gb ram) my solution runs in 1.2s. What do you think about this, is CF that slow? Anyway could you help me?

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

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

You solution runs too slow because of dozens of modulo operations.
Try to use:

if (some_variable >= MOD)
    some_variable -= MOD;

As for second part of the question, I don't understand either why it's so slow on CF servers. My laptop also runs in 1.1s (compiled g++ -O2).

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

    Thats not it. My solution ran even slower doing that. I could not remove the MOD from the multiplications, though.

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

      Indeed!
      I don't really know how to overcome this.

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

        Nevermind I solved it by trying to express f(i, d) as f(i + 1, d - 1). It has the same complexity as my previous solution though.

        → Reply