2225C.md (1561B)
1 Source: https://codeforces.com/problemset/problem/2225/C 2 3 C. Red-Black Pairs 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is a table of $2 \times n$ cells. Each cell of the table is colored either red or black. You want to repaint some cells of this table so that there exists at least one way to partition all cells into $n$ pairs such that the following conditions hold: 22 23 * the cells in each pair have the same color; 24 * the cells in each pair share a side. 25 26 What is the minimum number of cells that need to be repainted? 27 28 Input 29 30 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. 31 32 The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^{5}$). 33 34 The second and third lines of each test case describe the colors of the cells. Each line contains a string consisting of exactly $n$ letters "R" and/or "B". 35 36 Additional constraint on the input: 37 38 * the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 39 40 Output 41 42 For each test case, output one integer — the minimum number of cells that need to be repainted. 43 44 Example 45 46 Input 47 48 ``` 49 5 50 51 1 52 53 R 54 55 B 56 57 2 58 59 BR 60 61 BR 62 63 3 64 65 RBR 66 67 BRB 68 69 4 70 71 RRBB 72 73 BBRB 74 75 5 76 77 RBRBR 78 79 BBBRB 80 ``` 81 82 Output 83 84 ``` 85 1 86 87 0 88 89 3 90 91 1 92 93 4 94 ``` 95 96 Note 97 98 Consider the $3$rd example. One possible option is to color all cells in one color, which requires repainting $3$ cells. 99 100 In the $4$th example, one possible valid repainting is 101 102 ``` 103 RRBB 104 BBRR 105 ```