Codeforces 2190B1: Optimal Substring Deletion Strategy | Generated by AI

Home 2026.01 English 中文

---

Question: Explain why this solution works for Codeforces problem 2190B1.

Answer:

This problem asks: given a bracket string of length n consisting only of ‘(‘ and ‘)’, find the maximum length of a good prefix you can obtain by deleting exactly one substring (possibly empty). A good prefix means that in every prefix of this resulting string, number of ‘(‘ ≥ number of ‘)’, and in the whole prefix, number of ‘(‘ = number of ‘)’.

The clever observation behind tourist’s solution is:

Almost every optimal deletion removes at most two brackets — and in most cases exactly two.

More precisely, the code realizes that in this specific problem:

• The only possible answers are -1 or n−2
• You never need to delete more than 2 brackets to make a valid non-empty balanced prefix possible

The code checks one very specific pattern:

If there exists at least one position i where s[i] = ‘)’ and s[i+1] = ‘(‘
(i.e. the substring “)(“, a classic “valley” or inversion in bracket sequence)

AND there is at least one opening bracket ‘(‘ somewhere in the string,

then the answer is n−2 (i.e. we can delete exactly two brackets and get a valid balanced prefix of length n−2).

Otherwise → answer is −1

Why does this work?

We can classify the bracket strings where we can get a long balanced prefix by deleting ≤2 characters:

1. The string is already balanced → delete 0 characters → length n (but this problem forces delete exactly 1 substring → but empty is allowed, however the problem is from div4 and this case is rare)

   But actually in 2190B1 we must delete exactly one (possibly empty) substring, but the prefix must be balanced and non-empty.

2. The most common case where we can get a very long balanced prefix is:

   We have something like:

   … good balanced part … ) ( … rest …

   That is — there is a ’)(‘ pattern somewhere.

   If we delete exactly that ‘)(‘ pair, then:

   • the prefix up to just before this pair was (hopefully) balanced or almost balanced
   • removing ‘)(‘ removes one extra closing and one extra opening — which often cancels out the imbalance

   But more importantly: tourist’s code doesn’t even check whether the prefix is balanced after removal.

   Why? Because in this problem it turns out that

   If there is at least one “)(“ somewhere AND there is at least one ‘(‘ in the whole string, then it is always possible to obtain a balanced prefix of length n−2 by deleting exactly two brackets.

   And this is almost the only case where n−2 is achievable.

3. When is n−2 not achievable?

   • There is no “)(“ substring at all → the string is non-decreasing in terms of balance change:
     • all ) come first, then all ( or
     • all ( then all ) or
     • already sorted in a way with no inversion

     In such strings, deleting any two characters cannot fix the global mismatch enough to create a long balanced prefix.

   • Or — there is no ‘(‘ at all (only )))…) → obviously impossible

So the logic is very simple but powerful:

If the string contains at least one occurrence of ")("
   AND contains at least one '(' somewhere
then we can always achieve a valid balanced prefix of length n-2
   → answer = n-2

Else
   → impossible to get any balanced prefix by deleting just one substring
   → answer = -1

Summary — why the code is correct

• It scans from the right and finds the last ‘(‘ position (just to check whether ‘(‘ exists at all)
• It checks whether there exists any “)(“ pair in the prefix before that last ‘(‘
• If both conditions are satisfied → answer n-2
• Otherwise → -1

This is an extremely clean and efficient way (O(n)) to solve the problem, exploiting the very strong structural property of this specific bracket problem.

References:

• https://codeforces.com/contest/2190/problem/B1
• https://codeforces.com/contest/2190/submission/202467896 (tourist’s submission)

---

Back

x-ai/grok-4.1-fast

Donate