Brute force that tripped me

this was a simple problem in the sense that they were looking for a specific optim that was easy to guess than prove that it was needed.

It’s one of those brute force problems where the search space “happens” to not be too bad, even worse one of those types as the search space easily exceeds but a subtlety in the problem makes the args that it is so.

Noticing that the last arg needs no iterating over seems like a constant factor optimisiation but is crucial here. And to be honest, I think we should do these optims even in general since they are “free”; some premature optims are really free.

The bound on solutions

$A_n$ can be determined in $O(1)$ from the prefix, my argument was that it should not matter much if we go ONE level deep, I mean what’s 10 from 11; it’s a “will fail” case either way is what I had in mind.

$A_1$’s coeff is 1, so you can always adjust $A_1$ and $A_n$ to find a solution. Say prefix has remainder $rem$, $rem=qN+r$, set $q=A_n$ and $r=A_0$ to make a valid solution.

Note that for each such value of $A_n$ in a $solution$, what all $rem$ mappings can I have, it’ll be $N$ as $rem\in [0,N)$ and $rem$ mapping would map to a prefix we need to evaluate.

So, $prefix<=N\times solutions$