Hi Lalit, if you mean changing the loops to be like shown below, it's a good
question.
If you do that, the results are too big. In my original version, the third loop
prevents count() from being called too many times, so it does not overcount.
Another way to say this: if bA&bB==1, and the K prefix is already "equal", then
using bK=1 will result in a K prefix which is GREATER than any valid prefix.
But we will call count() anyway, thus resulting in an overcount.
The real answer is that I prefer not to shorten the code. It would not result
in a better asymptotic complexity, and it loses the simplicity because then we
are applying some problem-specific logic to make the "K" be treated differently
than the "A" and "B". That approach requires extra thought to code and debug.
By creating a "solution template", my goal is to have something in my "mental
library" which I can apply quickly in a contest situation with minimum changes
and less thought, because that approach is quicker and requires less debugging.
It is NOT to write the best or shortest code but the simplest, quickest code
that works, which is what you usually want for a contest.
I hope my goal makes sense. Thanks for the great question! It made me
understand this approach even better. At first I thought the code below would
work fine and when it didn't, I had to think. :-)
/////////////
for (int bA = 0; bA <= (prefixIsLessA?1:pA); bA++)
{
for (int bB = 0; bB <= (prefixIsLessB?1:pB); bB++)
{
int bK = bA & bB;
r += gendig(p-1, prefixIsLessA||(bA<pA),
prefixIsLessB||(bB<pB), prefixIsLessK||(bK<pK), A, B, K);
}
}
/////////////
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/0ce5b876-8689-4368-b468-71cf5a25f579%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
