Connection Status:
Competition Arena > MismatchedStrings

MismatchedStrings

TCO09 Qual 3 · 2009-02-24 · by misof

TCO09 Qual 3 · 2009-02-24 · by misof · Dynamic Programming
Class Name: MismatchedStrings
Return Type: String
Method Name: getString
Arg Types: (int, long long)
Problem Statement

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.

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: "((())()"
4)
49
562949953421311
Returns: ")))))))))))))))))))))))))))))))))))))))))))))))))"

Submissions are judged against all 181 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MismatchedStrings with a public method string getString(int N, long long K) · 181 test cases · 2 s / 256 MB per case

Submitting as anonymous