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, which is a permutation of 1 to K i.e. it is of size K and include every element from 1 to K.
Also, along we can choose to keep every substring as it is or in reverse order. That means you can reverse S[i](1≤i≤K) before form new string V.
Now, form a new string V = S[B[1]]+S[B[2]]+....+S[B[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 number of balanced substrings in V is X (of length greater than 1) and number of substrings among S[1],S[2],S[3],...,S[K] which were not reversed are Y.
Aim is to maximize Z=X×(Y+1).
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.
Since we choose not to reverse any of the substrings, they remain the same.
Number of balanced substrings is 2 - () , (()).
Number of not reversed substrings is 2.