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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
You solution runs too slow because of dozens of modulo operations.
Try to use:
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).
Thats not it. My solution ran even slower doing that. I could not remove the
MODfrom the multiplications, though.Indeed!
I don't really know how to overcome this.
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.