Problem : https://codeforces.com/contest/1538/problem/D

Solution Link : https://codeforces.com/contest/1538/submission/119077891

Can anyone explain why I am getting TLE on test 6 for this solution?

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

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

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

1 | 1-gon | 207 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

5 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Problem : https://codeforces.com/contest/1538/problem/D

Solution Link : https://codeforces.com/contest/1538/submission/119077891

Can anyone explain why I am getting TLE on test 6 for this solution?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/15/2021 23:31:32 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I get TLE like you too. But after I changed using long long to int then I got AC.

This problem is so weird that you got AC when you use int but get TLE when you use long long

yeah I got AC too. But why long long is leading to TLE?

The time to process with long long is a little bit longer than that of int. So using int can speed up your program for a little bit and got AC in cases that your program execution time exceed the time limit with a very small amount of time.

Yeah, I remember one of the dp problems in CSES having the same problem, took me a long time to figure out what went wrong.

kshitijanand36 ..

I had the same problem. I fixed it by simply writing prime factorization (I counted all prime numbers from $$$2$$$ to $$$ \sqrt {10 ^ 9} $$$))

TL6: https://codeforces.com/contest/1538/submission/119027345

AC: https://codeforces.com/contest/1538/submission/119038949

i don't know why many people didn't get TLE with that solution. but as i know T*sqrt(1e9)*2 = 4e8 = 4seconds is TLE. at least, that's the reason for your TLE.

To be safe, you need to precalculate all prime numbers from 2 to sqrt(1e9) and only check thoses numbers.

Yes, I did the same and it worked