codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1979B.md (2320B)


      1 Source: https://codeforces.com/problemset/problem/1979/B
      2 
      3 B. XOR Sequences
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given two distinct non-negative integers $x$ and $y$. Consider two infinite sequences $a_1, a_2, a_3, \ldots$ and $b_1, b_2, b_3, \ldots$, where
     22 
     23 * $a_n = n \oplus x$;
     24 * $b_n = n \oplus y$.
     25 
     26 Here, $x \oplus y$ denotes the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) operation of integers $x$ and $y$.
     27 
     28 For example, with $x = 6$, the first $8$ elements of sequence $a$ will look as follows: $[7, 4, 5, 2, 3, 0, 1, 14, \ldots]$. Note that the indices of elements start with $1$.
     29 
     30 Your task is to find the length of the longest common subsegment$^\dagger$ of sequences $a$ and $b$. In other words, find the maximum integer $m$ such that $a_i = b_j, a_{i + 1} = b_{j + 1}, \ldots, a_{i + m - 1} = b_{j + m - 1}$ for some $i, j \ge 1$.
     31 
     32 $^\dagger$A subsegment of sequence $p$ is a sequence $p_l,p_{l+1},\ldots,p_r$, where $1 \le l \le r$.
     33 
     34 Input
     35 
     36 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     37 
     38 The only line of each test case contains two integers $x$ and $y$ ($0 \le x, y \le 10^9, x \neq y$) — the parameters of the sequences.
     39 
     40 Output
     41 
     42 For each test case, output a single integer — the length of the longest common subsegment.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 4
     50 
     51 0 1
     52 
     53 12 4
     54 
     55 57 37
     56 
     57 316560849 14570961
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 1
     64 8
     65 4
     66 33554432
     67 ```
     68 
     69 Note
     70 
     71 In the first test case, the first $7$ elements of sequences $a$ and $b$ are as follows:
     72 
     73 $a = [1, 2, 3, 4, 5, 6, 7,\ldots]$
     74 
     75 $b = [0, 3, 2, 5, 4, 7, 6,\ldots]$
     76 
     77 It can be shown that there isn't a positive integer $k$ such that the sequence $[k, k + 1]$ occurs in $b$ as a subsegment. So the answer is $1$.
     78 
     79 In the third test case, the first $20$ elements of sequences $a$ and $b$ are as follows:
     80 
     81 $a = [56, 59, 58, 61, 60, 63, 62, 49, 48, 51, 50, 53, 52, 55, 54, \textbf{41, 40, 43, 42}, 45, \ldots]$
     82 
     83 $b = [36, 39, 38, 33, 32, 35, 34, 45, 44, 47, 46, \textbf{41, 40, 43, 42}, 53, 52, 55, 54, 49, \ldots]$
     84 
     85 It can be shown that one of the longest common subsegments is the subsegment $[41, 40, 43, 42]$ with a length of $4$.