codeforces-scrape

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

2217B.md (2385B)


      1 Source: https://codeforces.com/problemset/problem/2217/B
      2 
      3 B. Flip the Bit (Easy Version)
      4 
      5 time limit per test
      6 
      7 1.5 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 This is the easy version of the problem. The difference between the versions is that in this version, there is exactly one special index ($k=1$). You can hack only if you solved all versions of this problem.
     22 
     23 You are given a binary array $a$ of length $n$ and $k$ special indices $p_1, p_2, \ldots, p_k$ ($1 \le p_i \le n$). It is given that the values $a_i$ of all elements at special indices are the same (i. e., $a_{p_1} = a_{p_2} = \ldots = a_{p_k}$).
     24 
     25 In one operation, you can choose a range $[l, r]$ ($1 \le l \le r \le n$) such that the range contains at least one special index ($l \le p_i \le r$) and flip all bits $a_j$ for $l \le j \le r$. Flipping a bit changes $0$ to $1$ and $1$ to $0$.
     26 
     27 Let $x$ denote the value at special indices before any operations are applied. Find the minimum number of operations required to make all elements of the array equal to $x$.
     28 
     29 Input
     30 
     31 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.
     32 
     33 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $k=1$) — the length of the array and the number of special indices.
     34 
     35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 1$) — the elements of the array.
     36 
     37 The third line contains $k$ integers $p_1, p_2, \ldots, p_k$ ($1 \le p_1 \lt p_2 \lt \ldots \lt p_k \le n$) — the special indices. It is guaranteed that $a_{p_1} = a_{p_2} = \ldots = a_{p_k}$.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the minimum number of operations required.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 3 1
     53 
     54 0 1 0
     55 
     56 2
     57 
     58 5 1
     59 
     60 1 1 1 1 1
     61 
     62 1
     63 
     64 6 1
     65 
     66 0 1 0 1 0 1
     67 
     68 3
     69 
     70 17 1
     71 
     72 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1
     73 
     74 5
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 2
     81 
     82 0
     83 
     84 4
     85 
     86 10
     87 ```
     88 
     89 Note
     90 
     91 For the first test case, you can choose the range $[1, 3]$ and flip all the bits to get $[1, 0, 1]$. Then you can choose the range $[2, 2]$ and flip the second bit to get $[1, 1, 1]$.
     92 
     93 For the second test case, all the bits already match the value at the special index. You do not need any operations.