[SOLUTION] Anonymous Informant solution codeforces

Anonymous Informant
time limit per test

3 seconds

memory limit per test

512 megabytes


standard input


standard output

You are given an array b1,b2,,bn�1,�2,…,��.

An anonymous informant has told you that the array b was obtained as follows: initially, there existed an array a1,a2,,an�1,�2,…,��, after which the following two-component operation was performed k times:

  1. A fixed point x of the array a was chosen.
  2. Then, the array a was cyclically shifted to the left exactly x times.

As a result of k such operations, the array b1,b2,,bn�1,�2,…,�� was obtained. You want to check if the words of the anonymous informant can be true or if they are guaranteed to be false.

A number x is called a fixed point of the array a1,a2,,an�1,�2,…,�� if 1xn1≤�≤� and ax=x��=�.

A cyclic left shift of the array a1,a2,,an�1,�2,…,�� is the array a2,,an,a1�2,…,��,�1.


Each test contains multiple test cases. The first line contains an integer t (1t1041≤�≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n,k�,� (1n21051≤�≤2⋅1051k1091≤�≤109) — the length of the array b and the number of operations performed.

The second line of each test case contains n integers b1,b2,,bn�1,�2,…,�� (1bi1091≤��≤109) — the elements of the array b.

It is guaranteed that the sum of the values of n for all test cases does not exceed 21052⋅105.


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.


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


In the first test case, the array a could be equal to [3,2,3,4,3][3,2,3,4,3]. In the first operation, a fixed point x=2�=2 was chosen, and after 22 left shifts, the array became [3,4,3,3,2][3,4,3,3,2]. In the second operation, a fixed point x=3�=3 was chosen, and after 33 left shifts, the array became [3,2,3,4,3][3,2,3,4,3]. In the third operation, a fixed point x=3�=3 was chosen again, and after 33 left shifts, the array became [4,3,3,2,3][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][7,2,1]. After the operation with a fixed point x=2�=2, the array became [1,7,2][1,7,2]. Then, after the operation with a fixed point x=1�=1, the array returned to its initial state [7,2,1][7,2,1]. These same 22 operations (with x=2�=2, and x=1�=1) were repeated 4949 times. So, after 100100 operations, the array returned to [7,2,1][7,2,1].

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


def can_be_true(n, k, b):
if k % n != 0:
return “No”
for i in range(n):
if b[i] == b[(i – k // n) % n]:
return “Yes”
return “No”

t = int(input())
for _ in range(t):
n, k = map(int, input().split())
b = list(map(int, input().split()))
result = can_be_true(n, k, b)

Leave a Comment