CodeJam 2014: How to solve task "New Lottery Game"?

Question

I want to know efficient approach for the New Lottery Game problem.

The Lottery is changing! The Lottery used to have a machine to generate a random winning number. But due to cheating problems, the Lottery has decided to add another machine. The new winning number will be the result of the bitwise-AND operation between the two random numbers generated by the two machines.

To find the bitwise-AND of X and Y, write them both in binary; then a bit in the result in binary has a 1 if the corresponding bits of X and Y were both 1, and a 0 otherwise. In most programming languages, the bitwise-AND of X and Y is written X&Y.

For example: The old machine generates the number 7 = 0111. The new machine generates the number 11 = 1011. The winning number will be (7 AND 11) = (0111 AND 1011) = 0011 = 3.

With this measure, the Lottery expects to reduce the cases of fraudulent claims, but unfortunately an employee from the Lottery company has leaked the following information: the old machine will always generate a non-negative integer less than A and the new one will always generate a non-negative integer less than B.

Catalina wants to win this lottery and to give it a try she decided to buy all non-negative integers less than K.

Given A, B and K, Catalina would like to know in how many different ways the machines can generate a pair of numbers that will make her a winner.

---

For small input we can check all possible pairs but how to do it with large inputs. I guess we represent the binary number into string first and then check permutations which would give answer less than K. But I can't seem to figure out how to calculate possible permutations of 2 binary strings.

Answer 1

I used a general DP technique that I described in a lot of detail in another answer.

We want to count the pairs (a, b) such that a < A, b < B and a & b < K.

The first step is to convert the numbers to binary and to pad them to the same size by adding leading zeroes. I just padded them to a fixed size of 40. The idea is to build up the valid a and b bit by bit.

Let f(i, loA, loB, loK) be the number of valid suffix pairs of a and b of size 40 - i. If loA is true, it means that the prefix up to i is already strictly smaller than the corresponding prefix of A. In that case there is no restriction on the next possible bit for a. If loA ist false, A[i] is an upper bound on the next bit we can place at the end of the current prefix. loB and loK have an analogous meaning.

Now we have the following transition:

long long f(int i, bool loA, bool loB, bool loK) {
  // TODO add memoization
  if (i == 40)
    return loA && loB && loK;
  int hiA = loA ? 1: A[i]-'0';  // upper bound on the next bit in a
  int hiB = loB ? 1: B[i]-'0';  // upper bound on the next bit in b
  int hiK = loK ? 1: K[i]-'0';  // upper bound on the next bit in a & b
  long long res = 0;
  for (int a = 0; a <= hiA; ++a)
    for (int b = 0; b <= hiB; ++b) {
      int k = a & b;
      if (k > hiK) continue;
      res += f(i+1, loA || a < A[i]-'0',
                    loB || b < B[i]-'0',
                    loK || k < K[i]-'0');
    }
  return res;
}

The result is f(0, false, false, false).

The runtime is O(max(log A, log B)) if memoization is added to ensure that every subproblem is only solved once.

Answer 2

What I did was just to identify when the answer is A * B. Otherwise, just brute force the rest, this code passed the large input.

// for each test cases
long count = 0;
if ((K > A) || (K > B)) {
    count = A * B;
    continue; // print count and go to the next test case
  }

count = A * B - (A-K) * (B-K);

for (int i = K; i < A; i++) {
  for (int j = K; j < B; j++) {
    if ((i&j) < K) count++;
  }
}

I hope this helps!

Answer 3

just as Niklas B. said.

the whole answer is.

#include <algorithm>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define MAX_SIZE 32

int A, B, K;

int arr_a[MAX_SIZE];
int arr_b[MAX_SIZE];
int arr_k[MAX_SIZE];

bool flag [MAX_SIZE][2][2][2];
long long matrix[MAX_SIZE][2][2][2]; 

long long
get_result();

int main(int argc, char *argv[])
{
  int case_amount = 0;
  cin >> case_amount;

  for (int i = 0; i < case_amount; ++i)
  {
    const long long result = get_result();
    cout << "Case #" << 1 + i << ": " << result << endl;
  }

  return 0;
}


long long
dp(const int h,
   const bool can_A_choose_1,
   const bool can_B_choose_1,
   const bool can_K_choose_1)
{
  if (MAX_SIZE == h)
    return can_A_choose_1 && can_B_choose_1 && can_K_choose_1;

  if (flag[h][can_A_choose_1][can_B_choose_1][can_K_choose_1])
    return matrix[h][can_A_choose_1][can_B_choose_1][can_K_choose_1];

  int cnt_A_max = arr_a[h];
  int cnt_B_max = arr_b[h];
  int cnt_K_max = arr_k[h];

  if (can_A_choose_1)
    cnt_A_max = 1;

  if (can_B_choose_1)
    cnt_B_max = 1;

  if (can_K_choose_1)
    cnt_K_max = 1;

  long long res = 0;

  for (int i = 0; i <= cnt_A_max; ++i)
  {
    for (int j = 0; j <= cnt_B_max; ++j)
    {
      int k = i & j;

      if (k > cnt_K_max)
        continue;

      res += dp(h + 1,
                can_A_choose_1 || (i < cnt_A_max),
                can_B_choose_1 || (j < cnt_B_max),
                can_K_choose_1 || (k < cnt_K_max));
    }
  }

  flag[h][can_A_choose_1][can_B_choose_1][can_K_choose_1] = true;

  matrix[h][can_A_choose_1][can_B_choose_1][can_K_choose_1] = res;

  return res;
}

long long
get_result()
{
  cin >> A >> B >> K;

  memset(arr_a, 0, sizeof(arr_a));
  memset(arr_b, 0, sizeof(arr_b));
  memset(arr_k, 0, sizeof(arr_k));

  memset(flag, 0, sizeof(flag));
  memset(matrix, 0, sizeof(matrix));

  int i = 31;
  while (i >= 1)
  {
    arr_a[i] = A % 2;
    A /= 2;

    arr_b[i] = B % 2;
    B /= 2;

    arr_k[i] = K % 2;
    K /= 2;

    i--;
  }


  return dp(1, 0, 0, 0);
}