TopCoder problem "MismatchedStrings" used in TCO09 Qual 3 (Division I Level Three)



Problem Statement

    

Well-parenthesized strings are defined using the following rules:

  • The empty string is well-parenthesized.
  • If S is a well-parenthesized string, then (S) is a well-parenthesized string.
  • If S and T are well-parenthesized strings, then ST is a well-parenthesized string.
  • Every well-parenthesized string can be created using the previous rules only.

In this problem we will deal with the complement of this set of strings: The strings that consist only of the characters '(' and ')', but are not well-parenthesized. We will call these strings mismatched.

You are given an int N and a long K. All mismatched strings of length N can be ordered lexicographically, and numbered sequentially, starting with zero. Return the string that will get the number K in this order. If there is no such string, return the empty string instead.

 

Definition

    
Class:MismatchedStrings
Method:getString
Parameters:int, long
Returns:String
Method signature:String getString(int N, long K)
(be sure your method is public)
    
 

Notes

-Given two different strings S and T of equal length, S is lexicographically smaller than T if it has a smaller character at the first position where they differ.
-The ASCII value of '(' is less than the ASCII value of ')'.
 

Constraints

-N will be between 1 and 50, inclusive.
-K will be between 0 and 2^N - 1, inclusive.
 

Examples

0)
    
4
0
Returns: "(((("
For any length, the lexicographically smallest mismatched string consists of '(' characters only.
1)
    
4
4
Returns: "())("
There are 14 mismatched strings of length 4. The first five are "((((", "((()", "(()(", "()((", and "())(". Note that we use a 0-based index, hence K=4 corresponds to the fifth mismatched string.
2)
    
6
63
Returns: ""
There are less than 64 mismatched strings of length 6.
3)
    
7
13
Returns: "((())()"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10326

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13758&pm=10326

Writer:

misof

Testers:

PabloGilberto , vorthys , ivan_metelsky

Problem categories:

Dynamic Programming