Balance brackets

5

1 votes
String Algorithms, C++, String Searching, Algorithms
Problem

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](1iK) before form  new string V

Now, form a new string VS[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

  • Empty string is a balanced string.
  • if s is a balanced string, then (s) is also a balanced string.
  • if s and t are balanced strings, then st (concatenation of s and t) is also a balanced string.

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

  • First line contains two space-separated integers N K
  • Next line contains a string S.

Output format

  • In the first K lines, print 2 integers denoting end index of ith substring (indexes are 1 based) and whether it is reversed or not (0 for not reversed and 1 for reversed).
  • In next line print K space separated integers, denoting array B (permutation of 1 to K)
  • Note : End index of substrings should be in increasing order.

Verdict and scoring

  • Your score is equal to the sum of the values of all test files. The value of each test file is equal to the value of Z that you found.
  • If decomposition of string S is invalid, or array B is invalid you will receive a wrong answer verdict.

Constraints

N=10350K102

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

  • S1 = )
  • S2 = (()

Since we choose not to reverse any of the substrings, they remain the same. 

  • V = S2 + S1
  • V = (())

Number of balanced substrings is 2 - () , (()).
Number of not reversed substrings is 2.

  • Z = 2 * (2 + 1) = 6
Editor Image

?