ycperson's blog

Question about vector vs. array in a certain problem
By ycperson, history, 2 months ago, In English

I was doing this problem https://mirror.codeforces.com/contest/1822/problem/G1 recently, and I was comparing my code to the editorial implementation and I kept getting TLE again and again, trying to make the code more and more similar to the implementation given. The ultimate thing that allowed AC was changing the static array "a" to a vector of size n as in the implementation. Anyone know why the vector performs better? Because I thought static arrays were faster if anything.

My AC submission: https://mirror.codeforces.com/contest/1822/submission/280480288

My submission just before that (using static array a): https://mirror.codeforces.com/contest/1822/submission/280480106

(Just scroll down to the main function at the very bottom -- there is a bunch of template stuff above it not for the problem).

Thank you in advance for any help.

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

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

Auto comment: topic has been updated by ycperson (previous revision, new revision, compare).

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

This has nothing to do with vector or static array. https://mirror.codeforces.com/contest/1822/submission/280482428

for (auto i : a) counts[i] = 0;

Your static array has size $$$2 \cdot 10^5$$$, and we have $$$t \le 10^4$$$. Replaced this with

for (size_t i = 0; i < n; i++) counts[a[i]] = 0;

and got AC.

P.S. Also for some reason you have chosen old 32-bit C++-17 compiler instead of new 64-bit C++-20 compiler.

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

    Ah yes. My neglect of the fact that n's sum over the tests has a bound, so there's a difference between what I did to restore array a, as opposed to the given implementation. Thank you.

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    cause the new 64 bit compiler is shit, C++17 forever :red_heart:

    → Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

the problem was not from the type of the array a .the problem was from it's size .

in your code you have this line 

for (auto i : a) counts[i] = 0;

in the TLE code a.size()== $$$20^5+1$$$ and in the worst case scenario t= $$$10^4$$$ so it makes $$$20^9+1 $$$ iterations which is definitely a TLE

but the other code works because "The sum of n over all test cases does not exceed $$$20^5$$$ ."

→ Reply