codeforces-scrape

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

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 ```