codeforces-scrape

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

1605B.md (2676B)


      1 Source: https://codeforces.com/problemset/problem/1605/B
      2 
      3 B. Reverse Sort
      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 Ashish has a binary string $s$ of length $n$ that he wants to sort in non-decreasing order.
     22 
     23 He can perform the following operation:
     24 
     25 1. Choose a subsequence of any length such that its elements are in non-increasing order. Formally, choose any $k$ such that $1 \leq k \leq n$ and any sequence of $k$ indices $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$ such that $s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}$.
     26 2. Reverse this subsequence in-place. Formally, swap $s_{i_1}$ with $s_{i_k}$, swap $s_{i_2}$ with $s_{i_{k-1}}$, $\ldots$ and swap $s_{i_{\lfloor k/2 \rfloor}}$ with $s_{i_{\lceil k/2 \rceil + 1}}$ (Here $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$, and $\lceil x \rceil$ denotes the smallest integer not less than $x$)
     27 
     28 Find the minimum number of operations required to sort the string in non-decreasing order. It can be proven that it is always possible to sort the given binary string in at most $n$ operations.
     29 
     30 Input
     31 
     32 The first line contains a single integer $t$ $(1 \le t \le 1000)$  — the number of test cases. The description of the test cases follows.
     33 
     34 The first line of each test case contains an integer $n$ $(1 \le n \le 1000)$  — the length of the binary string $s$.
     35 
     36 The second line of each test case contains a binary string $s$ of length $n$ containing only $0$s and $1$s.
     37 
     38 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.
     39 
     40 Output
     41 
     42 For each test case output the following:
     43 
     44 * The minimum number of operations $m$ in the first line ($0 \le m \le n$).
     45 * Each of the following $m$ lines should be of the form: $k$ $i_1$ $i_2$ ... $i_{k}$, where $k$ is the length and $i_1 \lt i_2 \lt ... \lt i_{k}$ are the indices of the chosen subsequence. For them the conditions from the statement must hold.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 7
     54 0011111
     55 5
     56 10100
     57 6
     58 001000
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0
     65 1
     66 4 1 3 4 5 
     67 1
     68 3 3 5 6
     69 ```
     70 
     71 Note
     72 
     73 In the first test case, the binary string is already sorted in non-decreasing order.
     74 
     75 In the second test case, we can perform the following operation:
     76 
     77 * $k = 4:$ choose the indices $\{1, 3, 4, 5\}$
     78 
     79   $\underline{1}$ $0$ $\underline{1}$ $\underline{0}$ $\underline{0}$ $\rightarrow $ $\underline{0}$ $0$ $\underline{0}$ $\underline{1}$ $\underline{1}$
     80 
     81 In the third test case, we can perform the following operation:
     82 
     83 * $k = 3:$ choose the indices $\{3, 5, 6\}$
     84 
     85   $0$ $0$ $\underline{1}$ $0$ $\underline{0}$ $\underline{0}$ $\rightarrow $ $0$ $0$ $\underline{0}$ $0$ $\underline{0}$ $\underline{1}$