WOLFDOWN - 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 animals on consecutive positions of the x-axis.
Each animal is either a wolf or a bird.

Each second, if a wolf has a bird immediately to its right, it will move one step right and eat the bird.
Find the number of birds that will never be eaten.

EXPLANATION:

Wolves only eat birds immediately to their right.
From the bird’s perspective, this means a bird can only get eaten from its left side.

In particular, this means that if some bird has no wolves at all anywhere to its left, then it can surely never be eaten.
That is, if there’s a bird at position i, and there are no wolves at any positions \lt i, then surely the bird at position i is safe.

That leaves the question of: what happens if a bird does have a wolf somewhere to its left?
It’s easy to see that in this case, the bird will definitely be eaten.
To see why: suppose the bird is at position i, and let j \lt i be the position of the nearest wolf.
Since there are birds at all of positions j+1, j+2, \ldots, i-1, i, every second, the wolf at position j will eat the next bird and move one step forward; till eventually it eats the bird at position i.

So, the solution is to simply count the number of birds that have no wolves to their left.

This can be done easily in quadratic time; and can also be done in linear time by finding the first position that contains a wolf, and taking the number of birds before it to be the answer.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    ans = 0
    for i in range(n):
        if s[i] == '1': break
        ans += 1
    print(ans)
1 Like