codeforces-scrape

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

1257C.md (2252B)


      1 Source: https://codeforces.com/problemset/problem/1257/C
      2 
      3 C. Dominated Subarray
      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 call an array $t$ dominated by value $v$ in the next situation.
     22 
     23 At first, array $t$ should have at least $2$ elements. Now, let's calculate number of occurrences of each number $num$ in $t$ and define it as $occ(num)$. Then $t$ is dominated (by $v$) if (and only if) $occ(v) \gt occ(v')$ for any other number $v'$. For example, arrays $[1, 2, 3, 4, 5, 2]$, $[11, 11]$ and $[3, 2, 3, 2, 3]$ are dominated (by $2$, $11$ and $3$ respectevitely) but arrays $[3]$, $[1, 2]$ and $[3, 3, 2, 2, 1]$ are not.
     24 
     25 Small remark: since any array can be dominated only by one number, we can not specify this number and just say that array is either dominated or not.
     26 
     27 You are given array $a_1, a_2, \dots, a_n$. Calculate its shortest dominated subarray or say that there are no such subarrays.
     28 
     29 The subarray of $a$ is a contiguous part of the array $a$, i. e. the array $a_i, a_{i + 1}, \dots, a_j$ for some $1 \le i \le j \le n$.
     30 
     31 Input
     32 
     33 The first line contains single integer $T$ ($1 \le T \le 1000$) — the number of test cases. Each test case consists of two lines.
     34 
     35 The first line contains single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array $a$.
     36 
     37 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the corresponding values of the array $a$.
     38 
     39 It's guaranteed that the total length of all arrays in one test doesn't exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 Print $T$ integers — one per test case. For each test case print the only integer — the length of the shortest dominated subarray, or $-1$ if there are no such subarrays.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 1
     52 1
     53 6
     54 1 2 3 4 5 1
     55 9
     56 4 1 2 4 5 4 3 2 1
     57 4
     58 3 3 3 3
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 -1
     65 6
     66 3
     67 2
     68 ```
     69 
     70 Note
     71 
     72 In the first test case, there are no subarrays of length at least $2$, so the answer is $-1$.
     73 
     74 In the second test case, the whole array is dominated (by $1$) and it's the only dominated subarray.
     75 
     76 In the third test case, the subarray $a_4, a_5, a_6$ is the shortest dominated subarray.
     77 
     78 In the fourth test case, all subarrays of length more than one are dominated.