codeforces-scrape

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

2103B.md (3687B)


      1 Source: https://codeforces.com/problemset/problem/2103/B
      2 
      3 B. Binary Typewriter
      4 
      5 time limit per test
      6 
      7 1.5 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 $s$ of length $n$ and a typewriter with two buttons: 0 and 1. Initially, your finger is on the button 0. You can do the following two operations:
     22 
     23 1. Press the button your finger is currently on. This will type out the character that is on the button.
     24 2. Move your finger to the other button. If your finger is on button 0, move it to button 1, and vice versa.
     25 
     26 The cost of a binary string is defined as the minimum number of operations needed to type the entire string.
     27 
     28 Before typing, you may reverse at most one substring$^{\text{∗}}$ of $s$. More formally, you can choose two indices $1\le l\le r\le n$, and reverse the substring $s_{l\ldots r}$, resulting in the new string $s_1s_2\ldots s_{l-1}s_rs_{r-1}\ldots s_ls_{r+1}\ldots s_n$.
     29 
     30 Your task is to find the minimum possible cost among all strings obtainable by performing at most one substring reversal on $s$.
     31 
     32 $^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     37 
     38 The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of the binary string $s$.
     39 
     40 The second line of each test case contains a binary string $s_1s_2\ldots s_n$ ($s_i = \mathtt{0}$ or $s_i = \mathtt{1}$) — the characters of the binary string $s$.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output the minimum cost of string $s$ after performing at most one substring reversal.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 6
     54 
     55 3
     56 
     57 000
     58 
     59 3
     60 
     61 111
     62 
     63 3
     64 
     65 011
     66 
     67 3
     68 
     69 100
     70 
     71 5
     72 
     73 10101
     74 
     75 19
     76 
     77 1101010010011011100
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 3
     84 4
     85 4
     86 4
     87 8
     88 29
     89 ```
     90 
     91 Note
     92 
     93 In the first test case, we can choose not to reverse any substrings. We can do operation $1$ three times to type 000.
     94 
     95 In the second test case, we can choose not to reverse any substrings. We can do operation $2$ to move our finger to button 1. Then, we do operation $1$ three times to type 111.
     96 
     97 In the third test case, we can choose not to reverse any substring. We can do operation $1$ to type 0. Then, we do operation $2$ to move our finger to button 1. Finally, we do operation $1$ two times to type 11, resulting in the final string 011 using only $4$ operations.
     98 
     99 In the fourth test case, we can reverse the substring $s_{1\ldots 3}$, resulting in the string 001. We can do operation $1$ two times to type 00. Then we do operation $2$ to move our finger to button 1. Finally, we do operation $1$ once to type 1, resulting in the final string 001 using only $4$ operations.
    100 
    101 In the fifth test case, we can reverse the substring $s_{2\ldots 3}$, resulting in the string 11001. The cost of the string is $8$ as we can do the following sequence of operations:
    102 
    103 * Do operation $2$ to move our finger to button 1.
    104 * Do operation $1$ two times to type 11.
    105 * Do operation $2$ to move our finger to button 0.
    106 * Do operation $1$ two times to type 00.
    107 * Do operation $2$ to move our finger to button 1.
    108 * Do operation $1$ once to type 1.
    109 
    110 In the sixth test case, we can reverse the substring $s_{5\ldots 17}$, resulting in the string 1101111011001001000. It can be proven that the minimum number of operations needed to type the binary string is $29$.