LTALL - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N prison cells, each with a light that may or may not work; represented by string S.
Each working light can face either left or right, and it will illuminate its own cell as well as one cell in its chosen direction.

Is it possible to choose directions and light up all the cells?

EXPLANATION:

Let’s look at this from the perspective of the cells.
In particular, look at the leftmost cell.

  • If S_1 = 1, i.e. there’s a light here, then this cell will always be lit up anyway.
    So, we might as well direct the light to the right and light up the next cell.
  • If S_i = 0, there’s no light here.
    Then, the only way to light up this cell, is if there’s a working light at cell 2.
    Further, the light at cell 2 would have to be directed left to achieve this.

This leads to a fairly simple greedy algorithm.
Consider positions from 1 to N in order.
When processing position i,

  • If there’s a light at position i,
    • If position i-1 is not lit up, we must direct this light left.
    • Otherwise, we can direct this light right and light up i+1 instead, giving us more options in the future.

This fixes the directions of all the lights, after which it’s easy to check if all cells have been lit up or not.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    
    mark = [0]*n
    for i in range(n):
        if s[i] == '0': continue

        mark[i] = 1
        if i == 0 or mark[i-1] == 1: # right
            mark[min(n-1, i+1)] = 1
        else: # left is forced
            mark[i-1] = 1
    print('Yes' if min(mark) == 1 else 'No')