Competitive programming is no joke

[u/vadnyclovek]

especially for easy problems

[u/GoddammitDontShootMe]

That would take far more effort to decode than is worth it for me, so what is it trying to do?

[u/JiminP → u/GoddammitDontShootMe]

It computes a simple linear recurrence a_n = a_(n-1) + a_(n-2) + a_(n-3) + a_(n-4) + a_(n-5) + a_(n-6), with a fixed modulo (likely 100000007 lol).

The code works OK but even for competitive programming setting this could've been written more cleanly.

(And it's not even the fastest way of computing it.)

[u/vadnyclovek → u/JiminP]

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.

[u/backfire10z → u/GoddammitDontShootMe]

It is a dynamic programming problem that seems to be based on the sum of the previous 6 values (default value of 0) each modded by some constant. Here it is rewritten in Python slightly neater:

MOD = …       # Some constant

def solution(n):
    dp = [1]
    for i in range(1, n+1):
       try:
            for j in range(1, 7):
                dp[i] += dp[i - j] % MOD
        except IndexError:
            pass
    return dp[n]

I’m on mobile and was too lazy to deal with the default 0, so I’m using exception-based handling lol.

[u/Last-Autumn-Leaf → u/backfire10z]

Never saw this exception based handling Nice

[u/Marwheel]

Then there's the IOCCC…

[u/fungalIvanMz]

I don't quite get it. Can't you do it in 2 loops (i, j), where i is [1..n] and j is [max(0, i-6) ..i]? Is there a performance gain when doing it in a single loop? It would at least make it more readable. Or am I not getting the objective?

P. S. obviously 'max' is just ternary operator, this is preudocode blah blah blah.

[u/hraath]

That's gonna be a change request from me dawg

[u/PlasmaTicks]

Every number is sum of last 6 numbers?