Hello codeforces!

This is my first blog written here, so I apologize if this blog is not good. Any suggestion for improvement will be welcome!

Example Problem:

You are given two integers ($$$0$$$ <= $$$l$$$ <= $$$r$$$ <= $$$10^9$$$) and you have to count the number of pairs ($$$i$$$, $$$j$$$) which $$$i$$$ & $$$j$$$ = 0 with $$$l$$$ <= $$$i$$$, $$$j$$$ <= $$$r$$$. Which "&" denotes the Bitiwse AND.

What is Digit DP?

Problems like "count the number of pairs of numbers that satisfy some condition" or "count the number of numbers that satisfy some condition" can usually be done with digit DP, depending on the constants.

You can read more about digit DP at these links:

Link 1

Link 2

In some of these problems, the DP transitions are like: "I am in a position (digit) of the number that I am building and I have some options of digits that I can put in this position". However, in this problem, we cannot build a DP of this type.

How to solve this problem?

In this case, we will approach this DP in a similar way but, instead of thinking of the transition as "put this digit or not?" we will think in this transition as "set this bit or not?". Note that now with this idea, this problem becomes much easier, because in general we will have 3 options for the transition of dp in this problem.

1 — Set the current bit in $$$i$$$.

2 — Set the current bit in $$$j$$$.

3 — Set the current bit in none of the numbers.

Note that we cannot set a bit in both numbers, because their bitwise AND must result in 0.

Note that we must also be careful to know if both numbers are inside the range $$$[l, r]$$$. For that, we will decrase the value of $$$l$$$ and increase $$$r$$$ and use some dimensions of the DP to know if both numbers are bigger than $$$l$$$ and lower than $$$r$$$.

In the end, the DP will look like this:

DP[current_bit][i is bigger than l][i is lower than r][j is bigger than l][j is lower than r]

int a, b;
int dp[MAXLOG][2][2][2][2];

int solve(int i, int j, int k, int l, int m)
{
  if (i < 0)
    return (j && k && l && m) ? 1 : 0;
  if (dp[i][j][k][l][m] != -1)
    return dp[i][j][k][l][m];
  int ret = 0;
  int ll = a & (1LL << i);
  int rr = b & (1LL << i);
  if ((j || !ll) && (l || !ll))
    ret += solve(i - 1, j, (rr) ? 1 : k, l, (rr) ? 1 : m);
  if ((k || rr) && (l || !ll))
    ret += solve(i - 1, (!ll) ? 1 : j, k, l, (rr) ? 1 : m);
  if ((m || rr) && (j || !ll))
    ret += solve(i - 1, j, (rr) ? 1 : k, (!ll) ? 1 : l, m);
  return dp[i][j][k][l][m] = ret;
}

Problems:

Daniel and Spring Cleaning

Fun with Stones

Coincidence

Little Girl and Maximum XOR

If you know about more problems of this type and if you can share with us, it would be awesome :)