From Local Comparisons to Prefix Invariants: A Pattern in Div.2 A Problems

Recently I solved A – Simons and Making It Beautiful from a Div.2 contest.

Instead of discussing the code directly, I want to highlight the pattern recognition involved — because this pattern appears frequently in A/B problems. 1. The Real Question Behind the Problem

We are given a permutation p.

We need to count positions where the array stops behaving like a “clean growing prefix”.

At first glance, it may look like we need to compare each element with many previous elements.

That instinct leads toward an O(n²) mindset.

But that is unnecessary.

1. Reframing the Condition

The problem statement condition:

If there exists a previous element greater than p[i], this position contributes to ugliness.

This can be reformulated more precisely:

For index i, we need to check:

∃ j < i such that p[j] > p[i]

Now observe:

Instead of checking all previous elements, we only need the maximum of the prefix.

Because:

If max_prefix > p[i], then such a j must exist.

If max_prefix <= p[i], then no such j exists.

This transforms a quantifier condition into a simple invariant check.

1. The Core Pattern

This is a classic:

“Replace many comparisons with a maintained prefix invariant.”

The invariant here is:

max_prefix = max(p[0], p[1], ..., p[i-1])

Then each step becomes:

if p[i] < max_prefix: ugly++

This reduces the complexity to O(n).

1. Why This Pattern Matters

This idea appears in many problems involving:

Inversions (partial detection)

Prefix constraints

Detecting disorder

Checking monotonicity violations

Greedy validation

Whenever you see:

“Check if some previous element satisfies a condition”

Ask:

Can I maintain a prefix aggregate (max / min / sum / gcd) instead?

That mental shift is the real takeaway.

1. Implementation t = int(input())

for _ in range(t): n = int(input()) p = list(map(int, input().split()))

max_val = 0
ugly_count = 0

for x in p:
    if x < max_val:
        ugly_count += 1
    max_val = max(max_val, x)

print(ugly_count)

Time Complexity: O(n) Space Complexity: O(1)

1. A Small Extension Thought

Notice that this logic effectively counts elements that are not part of the longest increasing prefix starting from index 0.

So another way to interpret the solution:

We are counting elements that break the prefix maximum structure.

Thinking in structural terms instead of procedural comparisons often simplifies implementation.

1. What I’m Practicing Now

At ~800 rating, I’m focusing on:

Recognizing reusable patterns

Replacing nested loops with maintained invariants

Reducing implementation noise

Target: build consistency and move toward 1000+.

Key Lesson

Before writing nested loops, ask:

“Is there a prefix invariant that captures this condition?”

Often, that question alone converts O(n²) thinking into O(n).