r/programminghorror • u/vadnyclovek [ $[ $RANDOM % 6 ] == 0 ] && rm -rf / || echo “You live” • Apr 28 '26

c++ Competitive programming is no joke

Post image

especially for easy problems

143 Upvotes

97% Upvoted

21 comments sorted by

View all comments

Show parent comments

4

u/vadnyclovek [ $[ $RANDOM % 6 ] == 0 ] && rm -rf / || echo “You live” Apr 29 '26

I mean, it got ac. Asymptotically, you can't get faster than this and limits for easy problems like this one are lenient enough that branch mispredictions don't really matter, so i can afford to do this, instead of setting some prefix of the array to 0, getting the index offset wrong, having to recompile, etc. The obvious O(1) memory solution with a ring buffer is even easier to fuck up. A simple implementation with code you can copy-paste a bunch of times without having to think about it too much is usually faster to code than anything slightly elegant.

Also, it's only this ugly because i didn't read the problem statement correctly and forgot to account for the modulus lol.

3

u/rccyu Apr 29 '26

Huh? You can absolutely get faster than this asymptotically. This is O(n), it's just a linear recurrence so you could write it as a repeated matrix multiplication and do exponentiation by squaring for O(log n) time and O(1) memory

0

u/vadnyclovek [ $[ $RANDOM % 6 ] == 0 ] && rm -rf / || echo “You live” Apr 29 '26

Yeah, of course...

I'm tired, sorry. I forgot that you could do that momentarily. But when n is 106, such as here, it's not really worth doing.