My submission(Problem D). returns the correct answer on all test cases but gets TLE on higher recursion levels. I am unable to understand how memoization can be implemented in this case. Any help would be appreciated.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 151 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/23/2024 08:22:13 (k3).
Desktop version, switch to mobile version.
Supported by
There can be at-most
2^29particles afterNexplosions. If you consider a state of the particle in terms of Grid,Level,Direction(X,Y,T,Dir)fromPigeon Hole Principlethere must exist (at some point2^k > 321^2 * 30 * 3^2) two or more particles starting in the same Grid, moving in the same direction at the Same level. For these kinds of particles,you only need to track one instance (Memoize instances)of it. By this way you wont be keeping track of more than321^2 * 8particles at an instance.This leaves you with a complexity of
O(Height*Breadth*Levels*Distance*Directions)O(N^2 * 30 * 5 * 8)O(N^2)