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

My solution gets TLE on 712D (Memory and Scores)
Автор dcordb, история, 8 лет назад, По-английски

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?

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

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

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).

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить