BLREACH - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

N people stand in a row. The i-th person has strength A_i, which is either 1 or 2.
Person i can throw a ball to person j if |i - j| is a multiple of A_i.

Does there exist a pair of people (i, j) such that if the ball is initially with i, it can never reach j?

EXPLANATION:

First, note that if A_i = 1, then person i can directly throw the ball to anyone else.
On the other hand, if A_i = 2, person i can throw the ball only to people at the same parity - that is, if i is even then the ball can only be thrown to other even-index people; and if i is odd the ball can only be thrown to other odd-index people.

So, let’s look at some person i with A_i = 2, and see if we can find some j that they cannot reach via a sequence of throws.
Suppose i is even, and there also exists an even index j such that A_j = 1.
Then, i can throw the ball to j, and j can then throw the ball to anybody - so i can reach anybody.

That leaves us with the case of A_j = 2 for all even indices j.
In this case, it’s easy to see that if the ball is initially at index i, it can only travel to other even indices - there’s no way to move it to an odd index.

The situation is similar for the odd indices: if there’s an odd index containing a 1, any odd index can reach it first and from there all other indices; and otherwise if all the odd indices contain 2's there’s no way for the ball to travel from an odd index to an even index.

This gives us a pretty simple criterion for the answer:

  • If there exists a 1 at some even index and at some odd index, any person can reach any other person.
  • Otherwise, some pair will be unreachable - for example if there’s no 1 at an even index then 2 cannot reach 1; and if there’s no 1 at an odd index then 1 cannot reach 2.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    even, odd = 0, 0
    for i in range(n):
        if a[i] == 1:
            if i%2 == 0: even = 1
            else: odd = 1
    
    if even == 1 and odd == 1: print('No')
    else: print('Yes')
1 Like
3

wdym? where did you even get this testcase from?
where is it mentioned that for your given testcase the answer is “No” ?

for your testcase, the answer would be “Yes”
as for all odd indices j with Aj=2, there doesn’t exist a Aj=1 where j is even
so pairs like (i, j) = (1, 2) exist where you can’t make the ball reach to j from i

1 Like
4

According to editorial, this is a yes [2,1,2,1]

See the line where it specifies how to print yes and no
Yes if there exists a valid pair (i,j) such that the ball starting with i means it can never reach j, and No otherwise.