Arrange Brackets

0

0 votes
String Algorithms, Algorithms, String Searching
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 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 VS[B[1]]+S[B[2]]+....+S[B[K]] and  VS[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

  • 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 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

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

Output format

  • In the first line print K integers, which denotes the end index of ith substring (indexes are 1 based).
  • In next line print K space separated integers, denoting array B (permutation of 1 to K)
  • In next line print K space separated integers, denoting array C (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,C is invalid you will receive a wrong answer verdict.

Constraints

N=10350K102

 

Sample Input
4 2
)(()
Sample Output
1 4
2 1
1 2
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 = (()

Now, 

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

Number of balanced substrings in V is 2 - () , (()) and in V' is 1 - ()

  • Z = 2 + 1 = 3
Editor Image

?