shauncodes's blog

TLE for same theoretical Time Complexity?
By shauncodes, history, 12 months ago, In English

This is for the recent 2116C - Gellyfish and Flaming Peony question.

I use an $$$O(N^2)$$$ Dynamic Programming solution. Both are EXACTLY same, except one had don't pick first and the other has pick first.

322569273 -> TLE because I pick an element in the set first

322570586 -> AC because I don't pick an element in the set first

Can someone explain why one gives TLE while the other AC even though the TC is the same?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I just want to point out that if you use gcd instead of __gcd it will pass no matter the order

But for the reason, if you pick "dontpick" first, it will fill all the dead-ends state (i,0), so when you call "pick" most of it will go to if (dp[i][g] != -1) and return in O(1)

→ Reply