Thanks a lot for that explanation.I too understood the approach even better now.
On Wed, Jun 4, 2014 at 6:41 PM, royappa <[email protected]> wrote: > 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. > -- 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/CAL%3D%3Di2XSySXkgUyiDt%2BVAj%2BqRFprSh-FJhcj-Yr2dgKrBhG2%3DQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
