Hi.Can you please explain why the 3rd for loop needs to be kept.Can't we just do bK=bA&bB and directly send bK into the count function without having the 3rd for loop and inturn the if loop?
Thank you. On Wed, Jun 4, 2014 at 10:13 AM, royappa <[email protected]> wrote: > /////////////////////////////////////////// > // Demo 2: my version of solution to problem B > // Note that to change the special operation from "AND" to "OR" > // just takes a one-character change > /////////////////////////////////////////// > > #include <iostream> > #include <string.h> > > using namespace std; > > typedef long long LL; > > LL memo[32][2][2][2]; > > int getBit(int M, int p) > { > return (M>>p)&1; > } > > LL gendig(int p, bool prefixIsLessA, bool prefixIsLessB, bool > prefixIsLessK, int A, int B, int K) > { > if (p == -1) > return prefixIsLessA && prefixIsLessB && prefixIsLessK ? 1 > : 0; > > LL& r = memo[p][prefixIsLessA][prefixIsLessB][prefixIsLessK]; > if (r != -1LL) > return r; > r = 0; > int pA = getBit(A, p); > int pB = getBit(B, p); > int pK = getBit(K, p); > // Using the decimal template, we just generate all combinations > of the bits in position "p" for A,B,K > // Of course since this is binary we can range only up to 1, not 9 > // We only count those combinations which are legal for the > problem requirements > // This implementation is of course not as efficient or as short > as the reference solution (although asymptotically the same time) > // But it requires less case analysis: we are just trying all > combos > for (int bA = 0; bA <= (prefixIsLessA?1:pA); bA++) > { > for (int bB = 0; bB <= (prefixIsLessB?1:pB); bB++) > { > for (int bK = 0; bK <= (prefixIsLessK?1:pK); bK++) > { > if ((bA & bB) == bK) > { > r += gendig(p-1, > prefixIsLessA||(bA<pA), prefixIsLessB||(bB<pB), prefixIsLessK||(bK<pK), A, > B, K); > } > } > } > } > return r; > } > > int main() > { > int T; > cin >> T; > for (int testCase = 1; testCase <= T; testCase++) > { > int A, B, K; > cin >> A >> B >> K; > memset(memo, -1LL, sizeof(memo)); > cout << "Case #" << testCase << ": "; > cout << gendig(31, false, false, false, A, B, K) << endl; > } > return 0; > } > > -- > 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/ce145062-477a-4336-9649-077076349ecf%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%3Di2X2tpk91CyAfJAVdm2nPtvaxtSk-vHuoKKOr9ftxHcH8A%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
