codeforces-scrape

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

1631B.md (2331B)


      1 Source: https://codeforces.com/problemset/problem/1631/B
      2 
      3 B. Fun with Even Subarrays
      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 an array $a$ of $n$ elements. You can apply the following operation to it any number of times:
     22 
     23 * Select some subarray from $a$ of even size $2k$ that begins at position $l$ ($1\le l \le l+2\cdot{k}-1\le n$, $k \ge 1$) and for each $i$ between $0$ and $k-1$ (inclusive), assign the value $a_{l+k+i}$ to $a_{l+i}$.
     24 
     25 For example, if $a = [2, 1, 3, 4, 5, 3]$, then choose $l = 1$ and $k = 2$, applying this operation the array will become $a = [3, 4, 3, 4, 5, 3]$.
     26 
     27 Find the minimum number of operations (possibly zero) needed to make all the elements of the array equal.
     28 
     29 Input
     30 
     31 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. Description of the test cases follows.
     32 
     33 The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array.
     34 
     35 The second line of each test case consists of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$) — the elements of the array $a$.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 Print $t$ lines, each line containing the answer to the corresponding test case — the minimum number of operations needed to make equal all the elements of the array with the given operation.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 3
     51 
     52 1 1 1
     53 
     54 2
     55 
     56 2 1
     57 
     58 5
     59 
     60 4 4 4 2 4
     61 
     62 4
     63 
     64 4 2 1 3
     65 
     66 1
     67 
     68 1
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 0
     75 1
     76 1
     77 2
     78 0
     79 ```
     80 
     81 Note
     82 
     83 In the first test, all elements are equal, therefore no operations are needed.
     84 
     85 In the second test, you can apply one operation with $k=1$ and $l=1$, set $a_1 := a_2$, and the array becomes $[1, 1]$ with $1$ operation.
     86 
     87 In the third test, you can apply one operation with $k=1$ and $l=4$, set $a_4 := a_5$, and the array becomes $[4, 4, 4, 4, 4]$.
     88 
     89 In the fourth test, you can apply one operation with $k=1$ and $l=3$, set $a_3 := a_4$, and the array becomes $[4, 2, 3, 3]$, then you can apply another operation with $k=2$ and $l=1$, set $a_1 := a_3$, $a_2 := a_4$, and the array becomes $[3, 3, 3, 3]$.
     90 
     91 In the fifth test, there is only one element, therefore no operations are needed.