Anonymous Informant
Contest: Codeforces Round 908 (Div. 1)
Difficulty rating: 1400
Tags: brute force, dfs and similar, graphs, implementation

You are given an array $$$b_1, b_2, \ldots, b_n$$$.

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:

1. A fixed point$$$^{\dagger}$$$ $$$x$$$ of the array $$$a$$$ was chosen.
2. Then, the array $$$a$$$ was cyclically shifted to the left$$$^{\ddagger}$$$ exactly $$$x$$$ times.

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.

$$$^{\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$$$.

$$$^{\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$$$.

Input format:
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.

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.

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$$$.

It is guaranteed that the sum of the values of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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$$$.

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]$$$.

In the third test case, it can be shown that there is no solution.

Example input:
6
5 3
4 3 3 2 3
3 100
7 2 1
5 5
6 1 1 1 1
1 1000000000
1
8 48
9 10 11 12 13 14 15 8
2 1
1 42

Example output:
Yes
Yes
No
Yes
Yes
No

Editorial:
The key idea is that after applying an operation with the number $$$x$$$, the last element of the resulting array will be equal to $$$x$$$. Since after $$$x$$$ cyclic shifts, the array $$$[a_1, a_2, \ldots, a_n]$$$ will become $$$[a_{x+1}, \ldots, a_n, a_1, \ldots, a_x]$$$, and $$$a_x = x$$$, as $$$x$$$ was a fixed point of the array $$$a$$$.
From this idea, we can deduce that the operation can always be undone in at most one way: we need to look at the last element ($$$a_n$$$), and if $$$a_n > n$$$, it is not possible to undo the operation. Otherwise, we need to cyclically shift the array to the right $$$a_n$$$ times.
Therefore, the solution to the problem will be to undo the operation on the array by $$$1$$$ step $$$k$$$ times. If at any point it becomes impossible to undo the operation, the answer is "No". Otherwise, the answer is "Yes".
To avoid explicitly shifting the array, we can store a variable $$$s$$$ representing the index of the initial element, indicating that the current array is equal to $$$[a_s, a_{s+1}, \ldots, a_n, a_1, \ldots, a_{s-1}]$$$. When cyclically shifting the array to the right by $$$x$$$, $$$s$$$ decreases by $$$x$$$, initially $$$s = 1$$$.
Also, since $$$k$$$ in the problem can be up to $$$10^9$$$, simulating $$$k$$$ undo operations would be very time-consuming. However, we can notice that if we manage to undo the operation $$$n$$$ times without breaking anything, we have entered a cycle. Therefore, if we successfully undo the operation $$$n$$$ times, the answer is definitely "Yes". In other words, it was sufficient to do k = min(k, n).
Time complexity: $$$O(n)$$$