Counting "bitwise pairs" with Digit DP

Revision en34, by Ayalla, 2022-10-12 18:41:45

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]

Code

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 :)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en34 English Ayalla 2022-10-12 18:41:45 68
en33 English Ayalla 2021-06-28 17:23:36 184 adding a problem
en32 English Ayalla 2021-02-21 19:31:49 10 Tiny change: 'lem:**\n\nAre you given two' -> 'lem:**\n\nYou are given two'
en31 English Ayalla 2021-02-21 19:19:53 0 (published)
en30 English Ayalla 2021-02-21 19:18:47 4 Tiny change: 'int dp[MAXN][2][2][2]' -> 'int dp[MAXLOG][2][2][2]'
en29 English Ayalla 2021-02-21 19:17:50 2 Tiny change: 'his:\n\n**$DP$[current_b' -> 'his:\n\n**DP[current_b'
en28 English Ayalla 2021-02-21 19:17:20 2
en27 English Ayalla 2021-02-21 19:16:36 20
en26 English Ayalla 2021-02-21 19:13:04 565
en25 English Ayalla 2021-02-21 19:08:05 2 Tiny change: 'range [$l$ $r$]. For' -> 'range [$l$, $r$]. For'
en24 English Ayalla 2021-02-21 19:07:29 4 Tiny change: ' range [$l, r$]. For t' -> ' range [$l$ $r$]. For t'
en23 English Ayalla 2021-02-21 19:06:43 2 Tiny change: ' range [$l$, $r$]. For t' -> ' range [$l, r$]. For t'
en22 English Ayalla 2021-02-21 19:03:25 2 Tiny change: 'ntegers ($1$ <= $l$ <' -> 'ntegers ($0$ <= $l$ <'
en21 English Ayalla 2021-02-21 19:02:42 1 Tiny change: 'range [$l$ , $r$]. Fo' -> 'range [$l$, $r$]. Fo'
en20 English Ayalla 2021-02-21 19:01:51 21
en19 English Ayalla 2021-02-21 19:00:27 28
en18 English Ayalla 2021-02-21 18:58:59 6 Tiny change: 'gers ($1$ $<=$ $l$ $<=$ $r$ $<=$ $10^9$) a' -> 'gers ($1$ <= $l$ <= $r$ <= $10^9$) a'
en17 English Ayalla 2021-02-21 18:58:37 8
en16 English Ayalla 2021-02-21 18:57:51 6 Tiny change: 'tegers (1 <= l <= r <= 10^9) and' -> 'tegers (1 $<=$ l $<=$ r $<=$ 10^9) and'
en15 English Ayalla 2021-02-21 18:56:56 9 Tiny change: '### **How we will solve thi' -> '### **How to solve thi'
en14 English Ayalla 2021-02-21 18:55:46 9 Tiny change: '3 &mdash; Do not set the cur' -> '3 &mdash; Set the cur'
en13 English Ayalla 2021-02-21 18:54:54 2 Tiny change: 'r]**\n\n\n<spo' -> 'r]**\n\n\n\n<spo'
en12 English Ayalla 2021-02-21 18:52:07 65
en11 English Ayalla 2021-02-21 18:50:25 2 Tiny change: 'n r]**\n\n<spoil' -> 'n r]**\n\n\n<spoil'
en10 English Ayalla 2021-02-21 18:50:01 74
en9 English Ayalla 2021-02-21 17:38:14 64
en8 English Ayalla 2021-02-21 17:30:50 11
en7 English Ayalla 2021-02-21 17:30:25 10
en6 English Ayalla 2021-02-21 17:29:41 18
en5 English Ayalla 2021-02-21 17:28:08 143
en4 English Ayalla 2021-02-21 17:27:14 1 Tiny change: 'ome!\n\n** Example Pr' -> 'ome!\n\n**Example Pr'
en3 English Ayalla 2021-02-21 17:26:52 166
en2 English Ayalla 2021-02-21 17:25:56 129
en1 English Ayalla 2021-02-21 17:22:42 2164 Initial revision (saved to drafts)