I wrote a recursive solution with O(n^3) time complexity imo.
But I am getting TLE Verdict on submission .
I wrote a recursive solution with O(n^3) time complexity imo.
But I am getting TLE Verdict on submission .
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
The main issue is that the parameter
valXandvalYis thesolvefunciton may be negative, and lead to many useless states. Since we only care about whether we have enough x and y, so change LINE22 intoreturn dp[i][valX][valY] = min(1 + solve(i + 1, max(0, valX - v[i].ff), max(0, valY - v[i].ss)), solve(i + 1, valX, valY));would just be fine.Thank u so much!
Still got a TLE. Submission
I got the following update.
Accepted
The default dp value should also be changed. Change
1e9in LINE21 and LINE43 into-1.Why taking -1 gets an AC whereas taking 1e9 as dp value gets a TLE.
AC submission
TLE Submission
Difference in the runtime is also huge. TLE submission takes 2.2s still no output whereas AC submission takes 0.3s with just this small change. Can you clarify?
In the TLE Submission, the default dp value is
1e9. This means that when you call thesolvefunction and the currentdp[i][valX][valY]is 1e9, it keeps doing recursion.Assume current state is valX=10, valY=10, and the suffix of the input data is like
[..., {1,1}, {1,1}, {1,1}, {1,1}]. We cannot subtract valX and valY to 0 even if we use all the suffix, so thedp[i][valX][valY]is 1e9. When you visit this state again, LINE21 check that the dp value is 1e9 and still need to be searched. The runtime would be exponential to n in the worst case.Generally speaking, it's a bad idea to mix the
UNVISITEDstatus and theINVALIDstatus when we do dfs with memorization.