codeforces-scrape

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

1861B.md (2916B)


      1 Source: https://codeforces.com/problemset/problem/1861/B
      2 
      3 B. Two Binary Strings
      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 strings $a$ and $b$ of equal length, consisting of only characters 0 and/or 1; both strings start with character 0 and end with character 1.
     22 
     23 You can perform the following operation any number of times (possibly zero):
     24 
     25 * choose one of the strings and two equal characters in it; then turn all characters between them into those characters.
     26 
     27 Formally, you choose one of these two strings (let the chosen string be $s$), then pick two integers $l$ and $r$ such that $1 \le l \lt r \le |s|$ and $s_l = s_r$, then replace every character $s_i$ such that $l \lt i \lt r$ with $s_l$.
     28 
     29 For example, if the chosen string is 010101, you can transform it into one of the following strings by applying one operation:
     30 
     31 * 000101 if you choose $l = 1$ and $r = 3$;
     32 * 000001 if you choose $l = 1$ and $r = 5$;
     33 * 010001 if you choose $l = 3$ and $r = 5$;
     34 * 010111 if you choose $l = 4$ and $r = 6$;
     35 * 011111 if you choose $l = 2$ and $r = 6$;
     36 * 011101 if you choose $l = 2$ and $r = 4$.
     37 
     38 You have to determine if it's possible to make the given strings equal by applying this operation any number of times.
     39 
     40 Input
     41 
     42 The first line contains a single integer $t$ ($1 \le t \le 2000$)  — the number of test cases.
     43 
     44 Each test case consists of two lines:
     45 
     46 * the first line contains the string $a$ ($2 \le |a| \le 5000$), consisting of only characters 0 and/or 1.
     47 * the second line contains the string $b$ ($2 \le |b| \le 5000$), consisting of only characters 0 and/or 1.
     48 
     49 Additional constraints on the input:
     50 
     51 * in each test case, $|a| = |b|$ (the strings have equal length);
     52 * in each test case, both strings start with 0 and end with 1;
     53 * the total length of all strings $a$ in all test cases does not exceed $5000$.
     54 
     55 Output
     56 
     57 For each test case, print YES if it is possible to make the strings equal. Otherwise, print NO. You can print each letter in any register.
     58 
     59 Example
     60 
     61 Input
     62 
     63 ```
     64 7
     65 
     66 01010001
     67 
     68 01110101
     69 
     70 01001
     71 
     72 01001
     73 
     74 000101
     75 
     76 010111
     77 
     78 00001
     79 
     80 01111
     81 
     82 011
     83 
     84 001
     85 
     86 001001
     87 
     88 011011
     89 
     90 010001
     91 
     92 011011
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 YES
     99 YES
    100 YES
    101 NO
    102 NO
    103 NO
    104 YES
    105 ```
    106 
    107 Note
    108 
    109 In the first test case, we can perform the following operations:
    110 
    111 1. choose the string $a$, $l = 2$, $r = 4$; after this operation, $a$ is 01110001, $b$ is 01110101;
    112 2. choose the string $b$, $l = 5$, $r = 7$; after this operation, $a$ is 01110001, $b$ is 01110001.
    113 
    114 In the second test case, the strings are already equal.
    115 
    116 In the third test case, we can perform the following operations:
    117 
    118 1. choose the string $a$, $l = 4$, $r = 6$; after this operation, $a$ is 000111, $b$ is 010111;
    119 2. choose the string $b$, $l = 1$, $r = 3$; after this operation, $a$ is 000111, $b$ is 000111;
    120 
    121 In the fourth and fifth test cases, it's impossible to make the given strings equal.