oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

enumeratingbrackets Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

enumeratingbrackets.html

Enumerating Brackets

A balanced bracket sequence is a string consisting only of the characters “(” (opening brackets) and “)” (closing brackets) such that each opening bracket has a “matching” closing bracket, and vice versa. For example, “(())()” is a balanced bracket sequence, whereas “(())(()” and “())(()” are not.

Given two bracket sequences A and B of the same length, we say that A is lexicographically smaller than B (and write A < B) if:

  1. A and B differ in at least one position, and
  2. A has a “(”, and B has a “)” in the left-most position in which A and B differ

For example “(())()” < “()()()” because they first differ in the second position from the left, and the first string has an “(” in that position, whereas the second string has a “)”. For a given length N, the “<” operator defines an ordering on all balanced bracket sequences of length N. For example, the ordering of the sequences of length 6 is:
  1. ((()))
  2. (()())
  3. (())()
  4. ()(())
  5. ()()()

Given a length N and a positive integer M, your task is to find the M-th balanced bracket sequence in the ordering.

Input

You will be given an even integer N, and a positive integer M. It is guaranteed that M will be no more than the number of balanced bracket sequences of length N.

Output

Output the M-th balanced bracket sequence of length N, when ordered lexicographically.

Limits

  • 2 ≤ N ≤ 2000
  • 1 ≤ M ≤ 1018
  • M ≤ number of balanced bracket sequences of length N

Sample Input 1

6 4

Sample Output 1

()(())

Tags

Waterloo Programming Contest 2016-10-01, Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100161s256MBMinimum
2011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o enumeratingbrackets -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.