codeforces-scrape

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

2266C.md (1940B)


      1 Source: https://codeforces.com/problemset/problem/2266/C
      2 
      3 C. AND, OR, Sort!
      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 binary string$^{\text{∗}}$ $s$ of length $n$.
     22 
     23 You may perform the following operation any number of times (possibly zero):
     24 
     25 * choose an integer $i$ ($1 \le i \le n$), and replace $s_i$ with either the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) or the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of $s_1, s_2, \ldots, s_i$.
     26 
     27 Note that the bitwise AND or bitwise OR of a single element is equal to the element itself.
     28 
     29 Your goal is to make $s$ sorted in non-decreasing order$^{\text{†}}$.
     30 
     31 Find the minimum number of operations required to sort $s$ in non-decreasing order.
     32 
     33 $^{\text{∗}}$A binary string only contains characters $\texttt{0}$ and $\texttt{1}$.
     34 
     35 $^{\text{†}}$If $s$ is in non-decreasing order, then $s_1 \leq s_2 \leq \ldots \leq s_n$.
     36 
     37 Input
     38 
     39 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     40 
     41 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the binary string $s$.
     42 
     43 The second line of each test case contains the binary string $s$ of length $n$. Each character of $s$ is either 0 or 1.
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     46 
     47 Output
     48 
     49 For each test case, print a single integer — the minimum number of operations required to sort $s$ in non-decreasing order.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 6
     57 
     58 4
     59 
     60 0011
     61 
     62 4
     63 
     64 1000
     65 
     66 5
     67 
     68 01000
     69 
     70 8
     71 
     72 01001101
     73 
     74 7
     75 
     76 0101010
     77 
     78 7
     79 
     80 0111101
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 0
     87 
     88 3
     89 
     90 1
     91 
     92 2
     93 
     94 3
     95 
     96 1
     97 ```
     98 
     99 Note
    100 
    101 In the first test case, the string is already sorted, so no operations are required.
    102 
    103 In the second test case, we can use bitwise OR to change the last three characters to 1, obtaining 1111 in $3$ operations.