Anonymous Informant (Codeforces 1894C)
Tags: Implement, graphs

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: A fixed point$$$^{\dagger}$$$ $$$x$$$ of the array $$$a$$$ was chosen. 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: 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: 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.

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.

Sample Inputs:
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

Sample Outputs:
Yes
Yes
No
Yes
Yes
No

Solution (Python):
List = list

class Solution:

    def cf(self):
        (n, k) = map(int, input().split())
        b = list(map(int, input().split()))
        if max(b) <= n:
            print('Yes')
        else:
            ans = 'Yes'
            ind = n
            for _ in range(min(n, k)):
                if b[ind - 1] > n:
                    ans = 'No'
                    break
                ind -= b[ind - 1]
                if ind < 0:
                    ind += n
            print(ans)
t = int(input())
for i in range(t):
    res = Solution().cf()

Solution (Python):
readint = lambda : int(input())
readlst = lambda : list(map(int, input().split()))

def main():
    for t in range(readint()):
        (n, k) = readlst()
        ar = readlst()
        print(solve(ar, k))

def solve(ar, k):
    d = 0
    n = len(ar)
    for i in range(min(n, k)):
        ai = ar[(d - 1) % n]
        if not 1 <= ai <= n:
            break
        d += n - ai
    else:
        return 'Yes'
    return 'No'
main()

Solution (Python):
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 'Yes'
    index = -1
    for i in range(min(n, k)):
        curr = a[index]
        if curr > n:
            ans = 'No'
            break
        else:
            index = (index - curr) % n
    print(ans)