codeforces-scrape

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

1969B.md (2064B)


      1 Source: https://codeforces.com/problemset/problem/1969/B
      2 
      3 B. Shifts and Sorting
      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 Let's define a cyclic shift of some string $s$ as a transformation from $s_1 s_2 \dots s_{n-1} s_{n}$ into $s_{n} s_1 s_2 \dots s_{n-1}$. In other words, you take one last character $s_n$ and place it before the first character while moving all other characters to the right.
     22 
     23 You are given a binary string $s$ (a string consisting of only 0-s and/or 1-s).
     24 
     25 In one operation, you can choose any substring $s_l s_{l+1} \dots s_r$ ($1 \le l \lt r \le |s|$) and cyclically shift it. The cost of such operation is equal to $r - l + 1$ (or the length of the chosen substring).
     26 
     27 You can perform the given operation any number of times. What is the minimum total cost to make $s$ sorted in non-descending order?
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     32 
     33 The first and only line of each test case contains a binary string $s$ ($2 \le |s| \le 2 \cdot 10^5$; $s_i \in$ {0, 1}) — the string you need to sort.
     34 
     35 Additional constraint on the input: the sum of lengths of strings over all test cases doesn't exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, print the single integer — the minimum total cost to make string sorted using operation above any number of times.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 5
     47 
     48 10
     49 
     50 0000
     51 
     52 11000
     53 
     54 101011
     55 
     56 01101001
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 2
     63 0
     64 9
     65 5
     66 11
     67 ```
     68 
     69 Note
     70 
     71 In the first test case, you can choose the whole string and perform a cyclic shift: 10 $\rightarrow$ 01. The length of the substring is $2$, so the cost is $2$.
     72 
     73 In the second test case, the string is already sorted, so you don't need to perform any operations.
     74 
     75 In the third test case, one of the optimal strategies is the next:
     76 
     77 1. choose substring $[1, 3]$: 11000 $\rightarrow$ 01100;
     78 2. choose substring $[2, 4]$: 01100 $\rightarrow$ 00110;
     79 3. choose substring $[3, 5]$: 00110 $\rightarrow$ 00011.
     80 
     81 The total cost is $3 + 3 + 3 = 9$.