EndMyMisery's blog

Two seemingly equal solutions give two different verdicts?
By EndMyMisery, history, 2 months ago, In English

Hi codeforces community!

So I was solving this problem: 1703G - Good Key, Bad Key

I wrote first solution: 283940469 ~ TLE

I wrote second solution: 283940935 ~ AC

Two programs are very similar to each other so i will list most notable differences between them:

  • First solution uses C-array a of size N = 1e5 defined globally. Second solution uses vector of size n which is defined for each test case
  • First solution uses vector<vector<ll>> dp, with N rows and each row is of size 31 and for each test it fills every row with vector<ll>(31, -1). Second solution uses similar dp vector but has n rows and is defined in the solve function
  • First solution accesses variables n, k, dp from the global scope. Second solution passes references to vectors as parameters and variable k also as parameters for each recursive call.

I sincerely thought first solution would be faster than second solution.

So, my question is why is that first solution gets TLE but second solution gets AC?

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
2 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

In first solution you are refilling the whole $$$dp$$$ array

  fill(dp.begin(), dp.end(), vector<ll>(31, -1));

So for each test case it does at least N operations (which will lead to TLE when you have 10^4 testcases)

→ Reply
»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

You reset your dp vector in each test case. In the first submission your dp size is $$$N$$$ so you'll get $$$O(TN)$$$ complexity, which reaches $$$10^9$$$.

→ Reply