Counting "bitwise pairs" with Digit DP

Правка en1, от Ayalla, 2021-02-21 17:22:42

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!

\textbf{Example Problem}

Are you given two integers (1 <= 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.

\textbf{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: https://mirror.codeforces.com/blog/entry/53960 https://www.geeksforgeeks.org/digit-dp-introduction/

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.

\textbf{How we will 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 — Do not 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[MAXLOG][2][2][2][2] DP[current_bit][i is bigger than l][i is lower than r][j is bigger than l][j is lower than r]

\textbf{Other problems} https://mirror.codeforces.com/contest/1245/problem/F https://atcoder.jp/contests/abc138/tasks/abc138_f

История

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