Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

hydro_lyte's blog

By hydro_lyte, history, 5 years ago, In English

The question is- We are given two integers L and R. We are required to determine the count of special numbers ranging in between L and R. If the binary representation of X contains a pattern 101, then X is called special number. Constraints- 1 ≤ L ≤ R ≤ 10^18

We have to print the total count of special numbers in the range [L,R]

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Use the same DP that you use for digit DP, and add two extra states: one to represent if this pattern has occurred in the binary representation so far (0 or 1), and the second to represent the size of the prefix of the pattern that is currently matching (0, 1, 2, or 3).