Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look at the sample explanation to ensure that you understand the problem correctly.
Given a string S of length N consisting of two characters (open bracket) ( and (close bracket) ). We need to decompose S into K consecutive non-empty substrings such that every character is present in only one substring.
Say substrings are S[1],S[2],S[3],...,S[K]. Choose an array B and an array C, which is a permutation of 1 to K i.e. it is of size K and include every element from 1 to K. Also please note there should be atleast K/2 (rounded down) indices where B[i]≠C[i].
Now, form a new string V = S[B[1]]+S[B[2]]+....+S[B[K]] and V′ = S[C[1]]+S[C[2]]+....+S[C[K]] . A matching pair of brackets is not balanced if the set of brackets it encloses are not matched.
A string is said to be balanced if
For example : (())) is not balanced as last closing bracket is unmatched.
Suppose the number of balanced substrings in V is X and V′ is X′ (of length greater than 1).
Aim is to maximize Z=X+X′.
Input format
Output format
Verdict and scoring
Constraints
N=10350≤K≤102
Note: The sample provided is not a valid testcase as per the constraints, as N !=1000 and K does not lie in [50, 100]. Its just for simpler visualization.
Now,
Number of balanced substrings in V is 2 - () , (()) and in V' is 1 - ()