codeforces-scrape

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

1913B.md (2170B)


      1 Source: https://codeforces.com/problemset/problem/1913/B
      2 
      3 B. Swap and Delete
      4 
      5 time limit per test
      6 
      7 1 second
      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$ (a string consisting only of 0-s and 1-s).
     22 
     23 You can perform two types of operations on $s$:
     24 
     25 1. delete one character from $s$. This operation costs $1$ coin;
     26 2. swap any pair of characters in $s$. This operation is free (costs $0$ coins).
     27 
     28 You can perform these operations any number of times and in any order.
     29 
     30 Let's name a string you've got after performing operations above as $t$. The string $t$ is good if for each $i$ from $1$ to $|t|$ $t_i \neq s_i$ ($|t|$ is the length of the string $t$). The empty string is always good. Note that you are comparing the resulting string $t$ with the initial string $s$.
     31 
     32 What is the minimum total cost to make the string $t$ good?
     33 
     34 Input
     35 
     36 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.
     37 
     38 The only line of each test case contains a binary string $s$ ($1 \le |s| \le 2 \cdot 10^5$; $s_i \in \{$0, 1$\}$) — the initial string, consisting of characters 0 and/or 1.
     39 
     40 Additional constraint on the input: the total length of all strings $s$ doesn't exceed $2 \cdot 10^5$.
     41 
     42 Output
     43 
     44 For each test case, print one integer — the minimum total cost to make string $t$ good.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 4
     52 
     53 0
     54 
     55 011
     56 
     57 0101110001
     58 
     59 111100
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 1
     66 1
     67 0
     68 4
     69 ```
     70 
     71 Note
     72 
     73 In the first test case, you have to delete a character from $s$ to get the empty string $t$. Only then $t$ becomes good. One deletion costs $1$ coin.
     74 
     75 In the second test case, you can, for example, delete the second character from $s$ to get the string 01, and then swap the first and second characters to get the string $t$ $=$ 10. String $t$ is good, since $t_1 \neq s_1$ and $t_2 \neq s_2$. The total cost is $1$ coin.
     76 
     77 In the third test case, you can, for example, swap $s_1$ with $s_2$, swap $s_3$ with $s_4$, swap $s_5$ with $s_7$, $s_6$ with $s_8$ and $s_9$ with $s_{10}$. You'll get $t$ $=$ 1010001110. All swap operations are free, so the total cost is $0$.