Yet Another Balanced Parenthesis Problem
All submissions for this problem are available.A balanced parenthesis string is defined as follows: - The empty string is balanced - If P is balanced, (P) is also - If P and Q are balanced, PQ is also balanced You are given two even integers $n$ and $k$. Find any balanced paranthesis string of length $n$ that doesn't contain a balanced substring of length $k$, or claim that no such string exists. ### Input - First line will contain $T$, number of testcases. Then the testcases follow. - Each testcase contains of a single line containing $n$ and $k$. ### Output For every testcase, print on a new line, any balanced paranthesis string of length $n$ that doesn't contain a balanced substring of length $k$. If there doesn't exist any such string, print $-1$ instead. ### Constraints - $1 \leq T \leq 50000$ - $2 \leq k \leq n \leq 10^5$ - Sum of $n$ over all testcases doesn't exceed $10^5$. - $n$ and $k$ are both even integers. ### Example Input ``` 2 4 2 8 6 ``` ### Example Output ``` -1 (())(()) ``` ### Explanation In the first testcase, the only balanced strings of length $4$ are `(())` and `()()`, both of which contain `()` as a substring. In the second testcase, `(())(())` is a balanced string that doesn't contain any balanced substring of length $6$.
|Tags||cases, constructive, easy-medium, jtnydv25, maths, observations|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.