codeforces-scrape

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

1893A.md (2913B)


      1 Source: https://codeforces.com/problemset/problem/1893/A
      2 
      3 A. Anonymous Informant
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array $b_1, b_2, \ldots, b_n$.
     22 
     23 An anonymous informant has told you that the array $b$ was obtained as follows: initially, there existed an array $a_1, a_2, \ldots, a_n$, after which the following two-component operation was performed $k$ times:
     24 
     25 1. A fixed point$^{\dagger}$ $x$ of the array $a$ was chosen.
     26 2. Then, the array $a$ was cyclically shifted to the left$^{\ddagger}$ exactly $x$ times.
     27 
     28 As a result of $k$ such operations, the array $b_1, b_2, \ldots, b_n$ was obtained. You want to check if the words of the anonymous informant can be true or if they are guaranteed to be false.
     29 
     30 $^{\dagger}$A number $x$ is called a fixed point of the array $a_1, a_2, \ldots, a_n$ if $1 \leq x \leq n$ and $a_x = x$.
     31 
     32 $^{\ddagger}$A cyclic left shift of the array $a_1, a_2, \ldots, a_n$ is the array $a_2, \ldots, a_n, a_1$.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     37 
     38 The first line of each test case contains two integers $n, k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^9$) — the length of the array $b$ and the number of operations performed.
     39 
     40 The second line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$) — the elements of the array $b$.
     41 
     42 It is guaranteed that the sum of the values of $n$ for all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output "Yes" if the words of the anonymous informant can be true, and "No" if they are guaranteed to be false.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 6
     54 
     55 5 3
     56 
     57 4 3 3 2 3
     58 
     59 3 100
     60 
     61 7 2 1
     62 
     63 5 5
     64 
     65 6 1 1 1 1
     66 
     67 1 1000000000
     68 
     69 1
     70 
     71 8 48
     72 
     73 9 10 11 12 13 14 15 8
     74 
     75 2 1
     76 
     77 1 42
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 Yes
     84 Yes
     85 No
     86 Yes
     87 Yes
     88 No
     89 ```
     90 
     91 Note
     92 
     93 In the first test case, the array $a$ could be equal to $[3, 2, 3, 4, 3]$. In the first operation, a fixed point $x = 2$ was chosen, and after $2$ left shifts, the array became $[3, 4, 3, 3, 2]$. In the second operation, a fixed point $x = 3$ was chosen, and after $3$ left shifts, the array became $[3, 2, 3, 4, 3]$. In the third operation, a fixed point $x = 3$ was chosen again, and after $3$ left shifts, the array became $[4, 3, 3, 2, 3]$, which is equal to the array $b$.
     94 
     95 In the second test case, the array $a$ could be equal to $[7, 2, 1]$. After the operation with a fixed point $x = 2$, the array became $[1, 7, 2]$. Then, after the operation with a fixed point $x = 1$, the array returned to its initial state $[7, 2, 1]$. These same $2$ operations (with $x = 2$, and $x = 1$) were repeated $49$ times. So, after $100$ operations, the array returned to $[7, 2, 1]$.
     96 
     97 In the third test case, it can be shown that there is no solution.