codeforces-scrape

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

1867B.md (1832B)


      1 Source: https://codeforces.com/problemset/problem/1867/B
      2 
      3 B. XOR Palindromes
      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 a binary string $s$ of length $n$ (a string that consists only of $0$ and $1$). A number $x$ is good if there exists a binary string $l$ of length $n$, containing $x$ ones, such that if each symbol $s_i$ is replaced by $s_i \oplus l_i$ (where $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)), then the string $s$ becomes a palindrome.
     22 
     23 You need to output a binary string $t$ of length $n+1$, where $t_i$ ($0 \leq i \leq n$) is equal to $1$ if number $i$ is good, and $0$ otherwise.
     24 
     25 A palindrome is a string that reads the same from left to right as from right to left. For example, 01010, 1111, 0110 are palindromes.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).
     32 
     33 The second line of each test case contains a binary string $s$ of length $n$.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case, output a single line containing a binary string $t$ of length $n+1$ - the answer to the problem.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 5
     47 
     48 6
     49 
     50 101011
     51 
     52 5
     53 
     54 00000
     55 
     56 9
     57 
     58 100100011
     59 
     60 3
     61 
     62 100
     63 
     64 1
     65 
     66 1
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 0010100
     73 111111
     74 0011111100
     75 0110
     76 11
     77 ```
     78 
     79 Note
     80 
     81 Consider the first example.
     82 
     83 * $t_2 = 1$ because we can choose $l = $ 010100, then the string $s$ becomes 111111, which is a palindrome.
     84 * $t_4 = 1$ because we can choose $l = $ 101011.
     85 * It can be shown that for all other $i$, there is no answer, so the remaining symbols are $0$.