UNBAL - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice

Author: Jatin Yadav

Tester: tncks0121

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Constructive algorithms, Mathematics

PROBLEM:

Given even n and k, construct a balanced paranthesis string of length n such that it has no balanced substring of length k

EXPLANATION:

First, lets see when the construction of such a string s is not possible:

  • k = n : Since the whole string is balanced, it must have itself as a balanced substring of size k

  • k = 2 : The first character of a balanced substring must be (. Find the first character equal to ). The character to its left must be (, and therefore there must be a substring of s equal to ().

  • k = 4 : If n = 4, this is obvious. If n \geq 6, we use induction. Say the smallest balanced prefix has length t. If t = n, the middle n-2 characters form a balanced substring of length n - 2, and by induction it must have a balanced substring of length 4. If t \neq n, either t \geq 4 or n - t \geq 4. In either case, we have a balanced paranthesis substring with size \geq 4 and < n. By induction, this substring must have a 4 sized balanced substring.

It turns out that in all other cases, we can construct such a string.

For an even t, let g(t) = \displaystyle \underbrace{ (( \ldots (( }_{ \frac{t}{2}} \text{ } \underbrace{ )) \ldots ))}_{\frac{t}{2}}.

Notice that any proper prefix of g(t) can’t occur as a suffix of a balanced string. Similarly, any proper suffix of g(t) can’t occur as a prefix of a balanced string. This means that g(t) must either be completely inside or completely outside a balanced substring of s.

Let r = n \pmod{k - 2} , p = \lfloor \frac{n}{k - 2} \rfloor .

Let X be the string formed by concatenating p copies of g(k - 2), and s be the string formed by concatenating X and g(r). In any balanced substring of s of length k, there can’t be two g(k-2) as 2 (k -2) = 2k - 4 > k, as k \geq 6. So, the only possible balanced substring of length k can be g(k - 2) g(r), which is only possible if r = 2. So, if r \neq 2, s is a valid answer.

If r = 2, let s' = (X). There was no balanced substring of length k in X. Also, there is no proper prefix or suffix of s' that is balanced. This is because any potentially balanced prefix would have to be a concatenation of ( and some copies of g(k - 2), making the total length odd, which is not possible. So, s' is a valid answer.

AUTHOR’S and TESTER’S codes:

The author’s code can be found here

The tester’s code can be found here

1 Like