I exactly implemented the tutorial for the problem G. Hits Different. The solution they gave looks like they have the same time complexity as mine. But still, I get a TLE on test case 2. My Submission

# | User | Rating |
---|---|---|

1 | tourist | 3751 |

2 | Benq | 3727 |

3 | cnnfls_csy | 3691 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | orzdevinwang | 3559 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 164 |

5 | maroonrk | 163 |

6 | SecondThread | 160 |

7 | nor | 157 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | Geothermal | 143 |

I exactly implemented the tutorial for the problem G. Hits Different. The solution they gave looks like they have the same time complexity as mine. But still, I get a TLE on test case 2. My Submission

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/26/2023 12:51:27 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Pass by (const) reference unless you have a reason not to do so.

+1

Did that but still getting a TLE. My Submission

"The solution they gave looks like they have the same time complexity as mine."

I haven't read the problem. However, there is another nested loop in

`sum()`

. I can't find why they have the same complexity.They did a precomputation of the main algorithm that you are doing every time for every test case. The time complexity for your solution is

~ T * (1500*(1500+1)/2)(considering the nested for loops in`solve()`

and the loops in`sum()`

function). So in the worst case, it goes upto~1.125 * 1e9number of iterations. What the solution does is it precomputes the main algorithm in~1.125*1e6and then for each test case, it is performing an O(1) operation. So in the worst case, it won't exceed2.5*1e7which is roughly 2.5sec (if I take 1e7 iterations in one sec).thanks dr. ankan