Please read the new rule regarding the restriction on the use of AI tools. ×

ycperson's blog

By ycperson, history, 4 weeks 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

»
4 weeks 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).

»
4 weeks 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.

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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:

»
4 weeks 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$$$ ."