codeforces-scrape

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

1437B.md (1736B)


      1 Source: https://codeforces.com/problemset/problem/1437/B
      2 
      3 B. Reverse Binary Strings
      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$ of even length $n$. String $s$ is binary, in other words, consists only of 0's and 1's.
     22 
     23 String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones ($n$ is even).
     24 
     25 In one operation you can reverse any substring of $s$. A substring of a string is a contiguous subsequence of that string.
     26 
     27 What is the minimum number of operations you need to make string $s$ alternating? A string is alternating if $s_i \neq s_{i + 1}$ for all $i$. There are two types of alternating strings in general: 01010101... or 10101010...
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     32 
     33 The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$; $n$ is even) — the length of string $s$.
     34 
     35 The second line of each test case contains a binary string $s$ of length $n$ ($s_i \in$ {0, 1}). String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones.
     36 
     37 It's guaranteed that the total sum of $n$ over test cases doesn't exceed $10^5$.
     38 
     39 Output
     40 
     41 For each test case, print the minimum number of operations to make $s$ alternating.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 2
     50 10
     51 4
     52 0110
     53 8
     54 11101000
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 0
     61 1
     62 2
     63 ```
     64 
     65 Note
     66 
     67 In the first test case, string 10 is already alternating.
     68 
     69 In the second test case, we can, for example, reverse the last two elements of $s$ and get: 0110 $\rightarrow$ 0101.
     70 
     71 In the third test case, we can, for example, make the following two operations:
     72 
     73 1. 11101000 $\rightarrow$ 10101100;
     74 2. 10101100 $\rightarrow$ 10101010.