codeforces-scrape

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

1837C.md (1985B)


      1 Source: https://codeforces.com/problemset/problem/1837/C
      2 
      3 C. Best Binary String
      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 a string $s$ consisting of the characters 0, 1 and/or ?. Let's call it a pattern.
     22 
     23 Let's say that the binary string (a string where each character is either 0 or 1) matches the pattern if you can replace each character ? with 0 or 1 (for each character, the choice is independent) so that the strings become equal. For example, 0010 matches ?01?, but 010 doesn't match 1??, ??, or ????.
     24 
     25 Let's define the cost of the binary string as the minimum number of operations of the form "reverse an arbitrary contiguous substring of the string" required to sort the string in non-descending order.
     26 
     27 You have to find a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 3 \cdot 10^4$) — the number of test cases.
     32 
     33 The first and only line of each test case contains the string $s$ ($1 \le |s| \le 3 \cdot 10^5$) consisting of characters 0, 1, and/or ?.
     34 
     35 The sum of the string lengths over all test cases does not exceed $3 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, print a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 
     48 ??01?
     49 
     50 10100
     51 
     52 1??10?
     53 
     54 0?1?10?10
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 00011
     61 10100
     62 111101
     63 011110010
     64 ```
     65 
     66 Note
     67 
     68 In the first test case of the example, the cost of the resulting string is $0$.
     69 
     70 In the second test case, the cost of the resulting string is $2$: we can reverse the substring from the $1$-st character to the $5$-th character, and we obtain the string 00101. Then we reverse the substring from the $3$-rd to the $4$-th character, and we obtain the string 00011, which is sorted in non-descending order.