The following code despite being asymptotically fine, is still giving TLE on the 31st test case. I have tried everything, but I am not able to optimize this code further. I need inputs from more coders, any help would be appreciated. The problem link is this and my attempt is this (Incase the code is not readable, inform me I will format and edit in the code)
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/14/2024 10:07:07 (l2).
Desktop version, switch to mobile version.
Supported by
After seeing this post, I decided to try to solve the same problem. I was able to come up with a solution, but I got the same verdict: TLE on test 31. I went to look at the editorial and realised that I had missed a vital part of the problem statement (which you did too). The thing we both missed, is that the values in the matrix are non-negative meaning they can be zero. And as it happens to be, test 31 is the first time a zero appears as one of the input values. Can you see why your code fails when one of the numbers is zero?
Reading the editorial spoiled the rest of the solution for me. I didn't code it yet, but I'm pretty sure I'll be able to get AC on the problem now. But I'm afraid that your code might be too slow to get AC, I'm not sure. Try to come up with a solution to deal with these zeroes, and try to make it as efficient as possible. If you need more help, I can try give you good advice. I can also show you my code (c++, it's about 6 times faster than yours) at some point if you want to know how I made it more efficient.
EDIT: I checked your other submissions to the problem, and they were way faster than the one you linked (this one seemed to be the fastest, about the same speed as mine: 184454528). Making your final solution from this (or any of the later ones actually) will make it fast enough in order to get AC.
Also I managed to now solve the problem.