BOUNCE_BALL - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: detective_dots
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Prefix sums

PROBLEM:

There are N positions, each either contains a wall with height A_i or is empty.
You can place a ball at an empty index and push it either left or right.
When the ball hits a wall, it will reduce the wall’s height by 1 and then move in the opposite direction.
If a wall’s height reaches 0, it’s considered destroyed, and the ball can then pass over it.

Find the number of starting moves that result in every wall eventually being destroyed.

EXPLANATION:

Suppose we place a ball at index i, and push it left.
Observe that the ball will first hit a wall to the left of index i, then a wall to the right of index i, then a wall to the left, then a wall to the right, and so on - that is, it will alternate between hitting a wall to the left and to the right of index i.

Let L be the total height of all walls to the left of index i, and R be the total height of all walls to the right.
The ball’s bounce then alternately reduces L and R by 1.
When either L or R reach 0, there are no more walls on that side - so the ball will not hit anything and go out of bounds.

Our aim is to destroy every wall. This means both L and R should be 0 when the ball goes out of bounds.
Since we push the ball left from index i, and L and R decrease by 1 alternately, this is possible if and only if L = R, or L = R+1.

Similarly, if we initially push the ball right instead, it will destroy every wall if and only if L = R or L+1 = R.

Both cases are easy to check if we know L and R.
Note that L is simply the sum of all A_j for 1 \leq j \lt i, while R is the sum of A_j for indices i \lt j \leq N.
Both of these can be computed in constant time using prefix sums.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    pref = a[:]
    for i in range(1, n):
        pref[i] += pref[i-1]
    
    ans = 0
    for i in range(1, n-1):
        if a[i] != 0: continue
        if pref[i-1] - (pref[n-1] - pref[i]) == 0: ans += 2
        elif abs(pref[i-1] - (pref[n-1] - pref[i])) == 1: ans += 1
    if sum(a) == 0: ans += 4 # account for 1 and N
    print(ans)
2

The question framing was not clear enough, IMO. ‘Find all the ways in which the ball could be thrown out of bounds’ and ‘find all the ways in ways to bring down the walls’ are not quite the same, are they?
5
0 0 0 0 0

why would one even consider the left-wards direction when one is at index 1 (1 - base) for example?

3 Likes
3

The Question was not framed properly… The question says- “Determine the number of ways to place and push the ball so that the walls are destroyed”. So if there are no walls, the number of ways must be 0… I had solved it that way… Either this thing should be mentioned in the question or I should get rating points for my solution…

1 Like