codeforces-scrape

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

2248D.md (3810B)


      1 Source: https://codeforces.com/problemset/problem/2248/D
      2 
      3 D. Good Pair Queries
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 binary strings $s$ and $t$, both of length $n$.
     22 
     23 For two binary strings $a$ and $b$ of the same length, the pair $(a, b)$ is called good if both strings can be made empty by performing the following operation zero or more times:
     24 
     25 * Choose a non-empty set of positions $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le |a|$ and a character $c \in \{\mathtt{0}, \mathtt{1}\}$.
     26 * Let $x = a_{i_1}a_{i_2}\ldots a_{i_k}$ and $y = b_{i_1}b_{i_2}\ldots b_{i_k}$.
     27 * The character $c$ must be a mode$^{\text{∗}}$ of both $x$ and $y$.
     28 * Delete the characters at the chosen positions from both strings. The remaining characters are concatenated without changing their relative order.
     29 
     30 A binary string may have both $\mathtt{0}$ and $\mathtt{1}$ as modes.
     31 
     32 You need to answer $q$ queries. In each query, you are given two integers $l$ and $r$. Determine whether the pair of substrings $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ is good.
     33 
     34 The queries are independent.
     35 
     36 $^{\text{∗}}$For a binary string $z$, a character $c$ is a mode if it appears at least $\left\lceil \frac{|z|}{2} \right\rceil$ times in $z$. Here, $\lceil x \rceil$ denotes the smallest integer greater than or equal to $x$.
     37 
     38 Input
     39 
     40 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     41 
     42 The first line of each test case contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the length of each string and the number of queries.
     43 
     44 The second line of each test case contains the binary string $s$ of length $n$.
     45 
     46 The third line of each test case contains the binary string $t$ of length $n$.
     47 
     48 Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — a query.
     49 
     50 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     51 
     52 It is guaranteed that the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.
     53 
     54 Output
     55 
     56 For each query, output "YES" if the pair $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ is good. Otherwise, output "NO".
     57 
     58 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     59 
     60 Example
     61 
     62 Input
     63 
     64 ```
     65 3
     66 
     67 2 2
     68 
     69 01
     70 
     71 10
     72 
     73 1 1
     74 
     75 1 2
     76 
     77 5 1
     78 
     79 11111
     80 
     81 11111
     82 
     83 1 3
     84 
     85 5 1
     86 
     87 00011
     88 
     89 01111
     90 
     91 1 5
     92 ```
     93 
     94 Output
     95 
     96 ```
     97 NO
     98 
     99 YES
    100 
    101 YES
    102 
    103 YES
    104 ```
    105 
    106 Note
    107 
    108 In the first test case, for the first query, the pair is $(\mathtt{0}, \mathtt{1})$. No character is a mode of both strings, so no operation can be performed.
    109 
    110 For the second query, choose both positions and $c = \mathtt{0}$. Then $x = \mathtt{01}$ and $y = \mathtt{10}$, so $c$ is a mode of both strings and the whole pair is deleted.
    111 
    112 In the third test case, neither character is a mode of both $\mathtt{00011}$ and $\mathtt{01111}$, so the whole pair cannot be deleted in one operation. It can be emptied in three operations:
    113 
    114 * Choose positions $2$ and $4$ and $c = \mathtt{1}$. Then $x = \mathtt{01}$ and $y = \mathtt{11}$, so $c$ is a mode of both $x$ and $y$. After deleting the selected positions, the remaining characters are concatenated, giving the pair $(\mathtt{001}, \mathtt{011})$.
    115 * Choose positions $1$ and $2$ and $c = \mathtt{0}$. Then $x = \mathtt{00}$ and $y = \mathtt{01}$, so $c$ is a mode of both $x$ and $y$. After deleting the selected positions, the pair becomes $(\mathtt{1}, \mathtt{1})$.
    116 * Choose the remaining position $1$ and $c = \mathtt{1}$. Then $x = \mathtt{1}$ and $y = \mathtt{1}$, so $c$ is a mode of both $x$ and $y$. Deleting the selected position makes both strings empty.