codeforces-scrape

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

1931C.md (1710B)


      1 Source: https://codeforces.com/problemset/problem/1931/C
      2 
      3 C. Make Equal Again
      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 You have an array $a$ of $n$ integers.
     22 
     23 You can no more than once apply the following operation: select three integers $i$, $j$, $x$ ($1 \le i \le j \le n$) and assign all elements of the array with indexes from $i$ to $j$ the value $x$. The price of this operation depends on the selected indices and is equal to $(j - i + 1)$ burles.
     24 
     25 For example, the array is equal to $[1, 2, 3, 4, 5, 1]$. If we choose $i = 2, j = 4, x = 8$, then after applying this operation, the array will be equal to $[1, 8, 8, 8, 5, 1]$.
     26 
     27 What is the least amount of burles you need to spend to make all the elements of the array equal?
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of input test cases. The descriptions of the test cases follow.
     32 
     33 The first line of the description of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10 ^ 5$) — the size of the array.
     34 
     35 The second line of the description of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — array elements.
     36 
     37 It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output one integer — the minimum number of burles that will have to be spent to make all the elements of the array equal. It can be shown that this can always be done.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 8
     49 
     50 6
     51 
     52 1 2 3 4 5 1
     53 
     54 7
     55 
     56 1 1 1 1 1 1 1
     57 
     58 8
     59 
     60 8 8 8 1 2 8 8 8
     61 
     62 1
     63 
     64 1
     65 
     66 2
     67 
     68 1 2
     69 
     70 3
     71 
     72 1 2 3
     73 
     74 7
     75 
     76 4 3 2 7 1 1 3
     77 
     78 9
     79 
     80 9 9 2 9 2 5 5 5 3
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 4
     87 0
     88 2
     89 0
     90 1
     91 2
     92 6
     93 7
     94 ```