Here is the link to the problem :http://codeforces.me/contest/1073/problem/D
Here is the link to my submission : http://codeforces.me/contest/1073/submission/44895822
It shows TLE on test case #8.
Why does this binary search show TLE ? Problem D: Educational Codeforces Round 53 (Rated for Div. 2)
Here is the link to the problem :http://codeforces.me/contest/1073/problem/D
Here is the link to my submission : http://codeforces.me/contest/1073/submission/44895822
It shows TLE on test case #8.
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
It seems that you increment 'c' by 1 for every candy you buy. As the solution can be 1018, you will not finish a calc(mid) invocation in time when mid is large.
Also, 'high' starts at 3e10, and you look for a solution in [low, high]. But the solution can be way larger than that.
Yes, it works for the test#8 though , but I get TLE on test#9(Link: https://codeforces.me/contest/1073/submission/44903513 ). Thanks anyways. On a side note , do you think my code can be optimized more to get it accepted ? or do I need to change my approach entirely?
I'd suggest storing values that are less or equal than T in a set. That way you won't be spending time considering bigger elements. But, I'm still not sure if that will get AC. Probably you should give up binsearch and think of another idea.
The binary search part is unnecessary: 44923323
In a case like
Your calc function runs in O(T) time.