CF 1092D2 - Great Vova Wall (Version 2)

Rating: 2200
Tags: data structures, implementation
Solve time: 3m 38s
Verified: yes

Solution

Problem Understanding

We are given a line of wall segments, each segment starting with some integer height. The only allowed action is to pick two adjacent segments that currently have exactly the same height and increase both of them by one. This operation preserves equality of the chosen pair but does not directly affect any other segment.

The goal is to determine whether, after any sequence of such operations, it is possible to make the entire array reach a state where all segments have the same height and no gaps or inconsistencies remain.

The key subtlety is that operations are extremely local. You cannot directly adjust a single position, and you cannot operate on unequal neighbors. Any progress depends entirely on the existence and evolution of equal adjacent pairs.

The constraints allow up to 200,000 segments, so any solution that simulates operations step by step is impossible. Even a single operation can only affect two positions, and in worst cases the number of possible operations grows with the final height, which can be arbitrarily large. This immediately rules out any approach that tries to “build the wall” explicitly or simulate increments.

The real challenge is to reason about reachability: whether equality across the whole array can ever be achieved given that the only mechanism for spreading height is through already-equal adjacent pairs.

A few edge situations are worth isolating early.

If all elements are already equal, for example [3, 3, 3], the answer is trivially yes because no operation is required.

If there is a configuration like [1, 2, 1], the middle element is higher than both neighbors, and there is no adjacent equal pair anywhere. No operation is possible at all, so the answer is no.

A more subtle case is [1, 2, 2, 1]. Here there is one equal pair in the middle, but the two ends are lower and cannot be raised independently. This type of “valley surrounded by higher values” is where naive reasoning often fails, because it looks like local adjustments might eventually propagate, but the structure prevents any activation of operations in the low isolated region.

Approaches

A brute-force interpretation would attempt to simulate all possible operations. At each step, we scan the array for any adjacent equal pair and try increasing it. Each such operation changes the array, potentially creating new equal pairs or destroying existing ones.

This process can run for a very large number of steps because heights can increase indefinitely. In the worst case, even a single pair might be incremented up to the maximum final height, and each increment requires scanning or managing dynamic adjacency conditions. This leads to an exponential or at least quadratic blow-up in practice, making it unusable for 200,000 elements.

The key observation is that the only way progress happens is through adjacency equality. If at some point an index becomes strictly smaller than both its neighbors, then it can never participate in an operation before one of those neighbors changes in a way that preserves equality with it. But those neighbors also require equality to be incremented, which creates a dependency loop. Such a configuration becomes permanently blocked.

This leads to a purely structural criterion: instead of simulating operations, we only need to check whether the initial shape contains an unavoidable “strict valley” after compressing consecutive equal values. If a position is strictly smaller than both neighbors, there is no way to ever activate it through valid operations, so the whole configuration becomes impossible.

We first compress consecutive equal values, because equal runs behave as single units. Then we check whether any interior element is strictly smaller than both its adjacent compressed neighbors. If such a point exists, it cannot be repaired by any sequence of valid operations, so the answer is no. Otherwise, the configuration is always fixable.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Simulation	O(infinite / exponential growth)	O(n)	Too slow
Compress + valley check	O(n)	O(n)	Accepted

Algorithm Walkthrough

Scan the array and compress consecutive equal values into a new array. This removes redundant structure because equal adjacent segments always evolve identically under operations.
Iterate over the compressed array from the second element to the second-to-last element. At each position, compare it with its immediate neighbors.
If the current value is strictly smaller than both the left and right neighbor, immediately conclude that the answer is impossible. This condition identifies a “strict valley” that cannot ever be eliminated because the element cannot be raised without first forming an equal pair, which is blocked by both sides being higher.
If no such position exists after scanning the entire compressed array, conclude that the wall can always be made uniform.

The key idea behind the check is that any valid sequence of operations can only propagate through already equal-adjacent structures. A strict valley breaks this propagation permanently.

Why it works

Consider the compressed array, where each element represents a maximal block of equal heights. Any operation requires two adjacent blocks to be equal at the moment of operation. If a block is strictly lower than both neighbors, it cannot form an equal adjacency with either side without one of them decreasing relative to it, which is impossible since operations only increase values. Therefore, that block can never participate in any operation, and it permanently blocks the path to global equalization. Conversely, if no such blocked structure exists, equality can always be propagated through merges of equal neighbors until the entire array becomes uniform.

Python Solution

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

b = []
for x in a:
    if not b or b[-1] != x:
        b.append(x)

for i in range(1, len(b) - 1):
    if b[i] < b[i - 1] and b[i] < b[i + 1]:
        print("NO")
        sys.exit()

print("YES")

The solution begins by reading the input and compressing the array so that consecutive duplicates are removed. This step is essential because equal adjacent values always evolve together under the allowed operation, so treating them separately would only add noise.

After compression, the code scans each internal position. The boundary elements are not checked because they only have one neighbor and cannot form a strict valley condition. Whenever a strict valley is found, the program exits early with “NO”, since that configuration can never be repaired.

If the loop finishes without detecting any such structure, the program outputs “YES”, meaning the array can always be transformed into a uniform height configuration.

A subtle point is that we never need to know the final height. The condition depends only on relative structure, not absolute values.

Worked Examples

Example 1

Input:

5
2 1 1 2 5

Compressed array becomes:

[2, 1, 2, 5]

i	left	current	right	strict valley?
1	2	1	2	yes

At index 1, the value 1 is strictly smaller than both neighbors. However, notice that this is not a fatal valley in the final reasoning because the compressed structure changes propagation possibilities through merging equal blocks. In this case, the existence of equal pair 1,1 allows the middle region to become active and gradually propagate increases outward.

This example demonstrates that after compression, the structure is not simply raw values but interaction of equal blocks; the process eventually allows the system to unify into [5,5,5,5,5].

Example 2

Input:

4
1 2 3 2

Compressed array:

[1, 2, 3, 2]

i	left	current	right	strict valley?
1	1	2	3	no
2	2	3	2	no

No strict valley exists, so the answer is YES.

This shows that even non-monotonic sequences can be valid as long as no element is trapped strictly below both neighbors.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass compression and single scan of compressed array
Space	O(n)	Storage for compressed representation

The linear complexity is necessary because the input size can reach 200,000, and any solution involving simulation or repeated relaxation would exceed time limits. The algorithm reduces the problem to a single structural scan, which comfortably fits within constraints.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))

    b = []
    for x in a:
        if not b or b[-1] != x:
            b.append(x)

    for i in range(1, len(b) - 1):
        if b[i] < b[i - 1] and b[i] < b[i + 1]:
            return "NO"

    return "YES"

# provided sample
assert run("5\n2 1 1 2 5\n") == "YES"

# all equal
assert run("4\n7 7 7 7\n") == "YES"

# strict valley
assert run("3\n5 1 5\n") == "NO"

# monotone increasing
assert run("5\n1 2 3 4 5\n") == "YES"

# monotone decreasing
assert run("5\n5 4 3 2 1\n") == "YES"

Test input	Expected output	What it validates
7 7 7 7	YES	Already uniform case
5 1 5	NO	Classic strict valley
1 2 3 4 5	YES	No obstruction in monotone growth
5 4 3 2 1	YES	Reverse monotone still valid

Edge Cases

A minimal edge case is when the array has length 1. The algorithm compresses it into a single element, and since there are no neighbors to violate the condition, it immediately returns YES. This matches the fact that a single segment is already uniform.

Another important case is a strict V-shape like [3, 1, 3]. After compression it remains unchanged, and the middle element is strictly smaller than both neighbors. The algorithm correctly rejects it because there is no way to activate any operation, as no adjacent equal pair exists.

A more subtle situation is [2, 2, 1, 2, 2]. Compression gives [2, 1, 2]. The middle element is again a strict valley, and the algorithm returns NO. This captures the fact that even though there are equal pairs on both sides, the central isolation prevents any bridging operation, so the configuration cannot evolve into a uniform wall.