PROBLEM LINK:
Author: Jatin Yadav
Tester: tncks0121
DIFFICULTY:
EasyMedium
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 n2 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(k2) 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