codeforces-scrape

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

1546B.md (4226B)


      1 Source: https://codeforces.com/problemset/problem/1546/B
      2 
      3 B. AquaMoon and Stolen String
      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 AquaMoon had $n$ strings of length $m$ each. $n$ is an odd number.
     22 
     23 When AquaMoon was gone, Cirno tried to pair these $n$ strings together. After making $\frac{n-1}{2}$ pairs, she found out that there was exactly one string without the pair!
     24 
     25 In her rage, she disrupted each pair of strings. For each pair, she selected some positions (at least $1$ and at most $m$) and swapped the letters in the two strings of this pair at the selected positions.
     26 
     27 For example, if $m = 6$ and two strings "abcdef" and "xyzklm" are in one pair and Cirno selected positions $2$, $3$ and $6$ she will swap 'b' with 'y', 'c' with 'z' and 'f' with 'm'. The resulting strings will be "ayzdem" and "xbcklf".
     28 
     29 Cirno then stole away the string without pair and shuffled all remaining strings in arbitrary order.
     30 
     31 AquaMoon found the remaining $n-1$ strings in complete disarray. Also, she remembers the initial $n$ strings. She wants to know which string was stolen, but she is not good at programming. Can you help her?
     32 
     33 Input
     34 
     35 This problem is made as interactive. It means, that your solution will read the input, given by the interactor. But the interactor will give you the full input at the beginning and after that, you should print the answer. So you should solve the problem, like as you solve the usual, non-interactive problem because you won't have any interaction process. The only thing you should not forget is to flush the output buffer, after printing the answer. Otherwise, you can get an "Idleness limit exceeded" verdict. Refer to the [interactive problems guide](https://codeforces.com/blog/entry/45307) for the detailed information about flushing the output buffer.
     36 
     37 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.
     38 
     39 The first line of each test case contains two integers $n$, $m$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 10^5$) — the number of strings and the length of each string, respectively.
     40 
     41 The next $n$ lines each contain a string with length $m$, describing the original $n$ strings. All string consists of lowercase Latin letters.
     42 
     43 The next $n-1$ lines each contain a string with length $m$, describing the strings after Cirno exchanged and reordered them.
     44 
     45 It is guaranteed that $n$ is odd and that the sum of $n \cdot m$ over all test cases does not exceed $10^5$.
     46 
     47 Hack format:
     48 
     49 The first line should contain a single integer $t$. After that $t$ test cases should follow in the following format:
     50 
     51 The first line should contain two integers $n$ and $m$.
     52 
     53 The following $n$ lines should contain $n$ strings of length $m$, describing the original strings.
     54 
     55 The following $\frac{n-1}{2}$ lines should describe the pairs. They should contain, in the following order: the index of the first string $i$ ($1 \leq i \leq n$), the index of the second string $j$ ($1 \leq j \leq n$, $i \neq j$), the number of exchanged positions $k$ ($1 \leq k \leq m$), and the list of $k$ positions that are exchanged ($k$ distinct indices from $1$ to $m$ in any order).
     56 
     57 The final line should contain a permutation of integers from $1$ to $n$, describing the way the strings should be reordered. The strings will be placed in the order indices placed in this permutation, the stolen string index will be ignored.
     58 
     59 Output
     60 
     61 For each test case print a single line with the stolen string.
     62 
     63 Example
     64 
     65 Input
     66 
     67 ```
     68 3
     69 3 5
     70 aaaaa
     71 bbbbb
     72 ccccc
     73 aaaaa
     74 bbbbb
     75 3 4
     76 aaaa
     77 bbbb
     78 cccc
     79 aabb
     80 bbaa
     81 5 6
     82 abcdef
     83 uuuuuu
     84 kekeke
     85 ekekek
     86 xyzklm
     87 xbcklf
     88 eueueu
     89 ayzdem
     90 ukukuk
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 ccccc
     97 cccc
     98 kekeke
     99 ```
    100 
    101 Note
    102 
    103 In the first test case, "aaaaa" and "bbbbb" exchanged all positions, and "ccccc" is the stolen string.
    104 
    105 In the second test case, "aaaa" and "bbbb" exchanged two first positions, and "cccc" is the stolen string.
    106 
    107 This is the first test in the hack format:
    108 
    109 ```
    110 3  
    111 3 5  
    112 aaaaa  
    113 bbbbb  
    114 ccccc  
    115 1 2 5 1 2 3 4 5  
    116 2 1 3  
    117 3 4  
    118 aaaa  
    119 bbbb  
    120 cccc  
    121 1 2 2 1 2  
    122 2 1 3  
    123 5 6  
    124 abcdef  
    125 uuuuuu  
    126 kekeke  
    127 ekekek  
    128 xyzklm  
    129 1 5 3 2 3 6  
    130 2 4 3 2 4 6  
    131 5 4 1 2 3
    132 ```