Statistics

Problem Statement for "MismatchedStrings"

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

  1. 4

    0

    Returns: "(((("

    For any length, the lexicographically smallest mismatched string consists of '(' characters only.

  2. 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.

  3. 6

    63

    Returns: ""

    There are less than 64 mismatched strings of length 6.

  4. 7

    13

    Returns: "((())()"

  5. 49

    562949953421311

    Returns: ")))))))))))))))))))))))))))))))))))))))))))))))))"

  6. 1

    0

    Returns: "("

  7. 1

    1

    Returns: ")"

  8. 47

    987654321987

    Returns: "((((((()))(()()))))()(())(()((())))()))()(((())"

  9. 50

    12345678

    Returns: "(((((((((((((((((((((((((()())))((())(((()()(()))("

  10. 50

    1121037960441172

    Returns: ""

  11. 50

    1121037960441171

    Returns: "))))))))))))))))))))))))))))))))))))))))))))))))))"

  12. 50

    1121036960441172

    Returns: "))))))))))))))))))))((()((())(()()(())())((((((((("

  13. 38

    52133126321

    Returns: "(())((())()())))()(())()(()))))(()(())"

  14. 2

    0

    Returns: "(("

  15. 2

    1

    Returns: ")("

  16. 2

    2

    Returns: "))"

  17. 2

    3

    Returns: ""

  18. 3

    0

    Returns: "((("

  19. 3

    7

    Returns: ")))"

  20. 3

    5

    Returns: ")()"

  21. 4

    13

    Returns: "))))"

  22. 4

    12

    Returns: ")))("

  23. 6

    16

    Returns: "()()(("

  24. 7

    42

    Returns: "()()()("

  25. 8

    81

    Returns: "()()))))"

  26. 12

    3532

    Returns: ")))(()()(((("

  27. 34

    2343251535

    Returns: "(()((()))))())())()))(())())))(((("

  28. 49

    562949953421311

    Returns: ")))))))))))))))))))))))))))))))))))))))))))))))))"

  29. 50

    1121037960441171

    Returns: "))))))))))))))))))))))))))))))))))))))))))))))))))"

  30. 3

    7

    Returns: ")))"

  31. 3

    6

    Returns: "))("

  32. 4

    13

    Returns: "))))"

  33. 4

    14

    Returns: ""

  34. 4

    2

    Returns: "(()("

  35. 5

    31

    Returns: ")))))"

  36. 5

    5

    Returns: "(()()"

  37. 6

    58

    Returns: "))))))"

  38. 6

    59

    Returns: ""

  39. 6

    38

    Returns: ")()())"

  40. 7

    127

    Returns: ")))))))"

  41. 7

    99

    Returns: "))((())"

  42. 8

    241

    Returns: "))))))))"

  43. 8

    242

    Returns: ""

  44. 8

    125

    Returns: ")((()())"

  45. 9

    511

    Returns: ")))))))))"

  46. 9

    261

    Returns: ")((((()()"

  47. 10

    981

    Returns: "))))))))))"

  48. 10

    982

    Returns: ""

  49. 10

    935

    Returns: "))))()((()"

  50. 11

    2047

    Returns: ")))))))))))"

  51. 11

    1322

    Returns: ")()(()()()("

  52. 12

    3963

    Returns: "))))))))))))"

  53. 12

    3964

    Returns: ""

  54. 12

    1135

    Returns: "()(()))(()()"

  55. 13

    8191

    Returns: ")))))))))))))"

  56. 13

    6752

    Returns: "))()(())((((("

  57. 14

    15954

    Returns: "))))))))))))))"

  58. 14

    15955

    Returns: ""

  59. 14

    1273

    Returns: "((()()())(((()"

  60. 15

    32767

    Returns: ")))))))))))))))"

  61. 15

    14426

    Returns: "()))(((()())()("

  62. 16

    64105

    Returns: "))))))))))))))))"

  63. 16

    64106

    Returns: ""

  64. 16

    57797

    Returns: ")))(()))()())())"

  65. 17

    131071

    Returns: ")))))))))))))))))"

  66. 17

    94158

    Returns: ")())())))))(()))("

  67. 18

    257281

    Returns: "))))))))))))))))))"

  68. 18

    257282

    Returns: ""

  69. 18

    73694

    Returns: "()(())(((()())(())"

  70. 19

    524287

    Returns: ")))))))))))))))))))"

  71. 19

    358750

    Returns: ")()())))(()()())))("

  72. 20

    1031779

    Returns: "))))))))))))))))))))"

  73. 20

    1031780

    Returns: ""

  74. 20

    208694

    Returns: "(())()()))()))()()(("

  75. 21

    2097151

    Returns: ")))))))))))))))))))))"

  76. 21

    532385

    Returns: "()(((((())))))()(((()"

  77. 22

    4135517

    Returns: "))))))))))))))))))))))"

  78. 22

    4135518

    Returns: ""

  79. 22

    77596

    Returns: "((((()(()))())((()()))"

  80. 23

    8388607

    Returns: ")))))))))))))))))))))))"

  81. 23

    3289644

    Returns: "())(()((())(()((()())(("

  82. 24

    16569203

    Returns: "))))))))))))))))))))))))"

  83. 24

    16569204

    Returns: ""

  84. 24

    15874689

    Returns: "))))()()())(()))(((())()"

  85. 25

    33554431

    Returns: ")))))))))))))))))))))))))"

  86. 25

    18578504

    Returns: ")((())())()))))((()(()((("

  87. 26

    66365963

    Returns: "))))))))))))))))))))))))))"

  88. 26

    66365964

    Returns: ""

  89. 26

    58066138

    Returns: ")))(((((()()())()())(()))("

  90. 27

    134217727

    Returns: ")))))))))))))))))))))))))))"

  91. 27

    28638036

    Returns: "(())())()(()))))())()()()(("

  92. 28

    265761015

    Returns: "))))))))))))))))))))))))))))"

  93. 28

    265761016

    Returns: ""

  94. 28

    123755856

    Returns: "())))((()(()(()())((()())((("

  95. 29

    536870911

    Returns: ")))))))))))))))))))))))))))))"

  96. 29

    373288042

    Returns: ")())((()))))))))())((())()()("

  97. 30

    1064046978

    Returns: "))))))))))))))))))))))))))))))"

  98. 30

    1064046979

    Returns: ""

  99. 30

    44182399

    Returns: "(((()()())))(()(((()))))(((())"

  100. 31

    2147483647

    Returns: ")))))))))))))))))))))))))))))))"

  101. 31

    2126177797

    Returns: "))))))()()))()()))(())(((((()()"

  102. 32

    4259609625

    Returns: "))))))))))))))))))))))))))))))))"

  103. 32

    4259609626

    Returns: ""

  104. 32

    4033078742

    Returns: "))))(()(()))))))())()(())())))(("

  105. 33

    8589934591

    Returns: ")))))))))))))))))))))))))))))))))"

  106. 33

    2006845483

    Returns: "(()))())))(())))((((()((((()()())"

  107. 34

    17050224393

    Returns: "))))))))))))))))))))))))))))))))))"

  108. 34

    17050224394

    Returns: ""

  109. 34

    3437302584

    Returns: "(())()(()(())())()))()())))()((((("

  110. 35

    34359738367

    Returns: ")))))))))))))))))))))))))))))))))))"

  111. 35

    6343774756

    Returns: "(()())))()(((())))(()()(()((()(()(("

  112. 36

    68241838035

    Returns: "))))))))))))))))))))))))))))))))))))"

  113. 36

    68241838036

    Returns: ""

  114. 36

    48612272768

    Returns: ")())())())()))))))(()(())()()()())(("

  115. 37

    137438953471

    Returns: ")))))))))))))))))))))))))))))))))))))"

  116. 37

    111288982727

    Returns: "))(())))()(()()()()))((()))(())((()))"

  117. 38

    273110643753

    Returns: "))))))))))))))))))))))))))))))))))))))"

  118. 38

    273110643754

    Returns: ""

  119. 38

    171283343091

    Returns: ")()(((()(()()()(())))()())(()())(()(()"

  120. 39

    549755813887

    Returns: ")))))))))))))))))))))))))))))))))))))))"

  121. 39

    49546981629

    Returns: "((()()))((()(()(()))()())))(((())))))()"

  122. 40

    1092947507355

    Returns: "))))))))))))))))))))))))))))))))))))))))"

  123. 40

    1092947507356

    Returns: ""

  124. 40

    150232777539

    Returns: "(()((())))(()()()(()()(()()((()(()())((("

  125. 41

    2199023255551

    Returns: ")))))))))))))))))))))))))))))))))))))))))"

  126. 41

    591845441298

    Returns: "()((()(()))(())(()())))(()())))))((()(()("

  127. 42

    4373580244083

    Returns: "))))))))))))))))))))))))))))))))))))))))))"

  128. 42

    4373580244084

    Returns: ""

  129. 42

    2327012505344

    Returns: ")((()((())()))))))(((()))()(()(()()((())(("

  130. 43

    8796093022207

    Returns: ")))))))))))))))))))))))))))))))))))))))))))"

  131. 43

    8324114891022

    Returns: "))))(()(()(((())()))))()(()()((((()(((()))("

  132. 44

    17500703480775

    Returns: "))))))))))))))))))))))))))))))))))))))))))))"

  133. 44

    17500703480776

    Returns: ""

  134. 44

    12853336518715

    Returns: ")())))((()()))))(())()()()))))()()((()))(())"

  135. 44

    1750070348077

    Returns: "((())()((((()(()((())(()()()())()))))))()()("

  136. 44

    15750633132697

    Returns: ")))(())()((()(((())))()())())())())())()((()"

  137. 44

    3500140696155

    Returns: "(())(()))))((()(((()))(()(()))(())))(())((()"

  138. 44

    14000562784620

    Returns: "))(())()((()(((())))()())())())())())()(()(("

  139. 45

    35184372088831

    Returns: ")))))))))))))))))))))))))))))))))))))))))))))"

  140. 45

    11371277174381

    Returns: "()()(()()())))(()()(()))())))))((())(())())()"

  141. 46

    70025684564013

    Returns: "))))))))))))))))))))))))))))))))))))))))))))))"

  142. 46

    70025684564014

    Returns: ""

  143. 46

    38722739321678

    Returns: ")((()))(((())))())()))((()((())((((())(()((((("

  144. 46

    7002568456401

    Returns: "((())()((((((()()(()(()((()((())(()))((()))())"

  145. 46

    63023116107611

    Returns: ")))(())()(((())(()())(())(()()((((()))(()())()"

  146. 46

    14005136912802

    Returns: "(())(())))()()))()))))((())))()((())()))())((("

  147. 46

    56020547651210

    Returns: "))(())()(((())(()())(())(()()((((()))(()()))(("

  148. 47

    140737488355327

    Returns: ")))))))))))))))))))))))))))))))))))))))))))))))"

  149. 47

    58292720851782

    Returns: "())()()((((()((()()()(()))()())()())())()((())("

  150. 48

    280185072563331

    Returns: "))))))))))))))))))))))))))))))))))))))))))))))))"

  151. 48

    280185072563332

    Returns: ""

  152. 48

    134391745160144

    Returns: "())))())())(())())())((()((((()(())())))()(())(("

  153. 48

    28018507256333

    Returns: "((())(()))))))(())(((((())))(()))(()())())(())()"

  154. 48

    252166565306997

    Returns: ")))(())()(((()((())()))())()(()))))())()))))((()"

  155. 48

    56037014512666

    Returns: "(())(())))(())())))(()((()())))))((())(((()))((("

  156. 48

    224148058050664

    Returns: "))(())()(((()((())()))())()(()))))())()))))(()(("

  157. 49

    562949953421311

    Returns: ")))))))))))))))))))))))))))))))))))))))))))))))))"

  158. 49

    205024144367704

    Returns: "()()))()(()))())))))(()))()(()()))()(((((()())((("

  159. 50

    1121037960441171

    Returns: "))))))))))))))))))))))))))))))))))))))))))))))))))"

  160. 50

    1121037960441172

    Returns: ""

  161. 50

    241754441533282

    Returns: "(())()))))((())))))(((()())))()()))((()))()(()(()("

  162. 50

    112103796044117

    Returns: "((())(()))))()))()))))(())())(())()()(()(()(())(()"

  163. 50

    1008934164397053

    Returns: ")))(())()((((()()())(())()(((())))(((()))()()()(()"

  164. 50

    224207592088234

    Returns: "(())(())))((()()(())((()))())()(((((((()())()((()("

  165. 50

    896830368352936

    Returns: "))(())()((((()()())(())()(((())))(((()))()()()()(("

  166. 50

    999999999999999

    Returns: ")))(()((())))()()()()(()))()()))()((()(()()()()())"

  167. 50

    1073741824

    Returns: "((((((((((((((((((()((((((((((((()))((((())(()))()"

  168. 50

    562949953421312

    Returns: ")(((((()((())())(((((((()()(()())()(()(()()()())(("

  169. 50

    1125899906842622

    Returns: ""

  170. 50

    4294967296

    Returns: "((((((((((((((((()(((((((((()(()())((()(((((()(((("

  171. 50

    936489623

    Returns: "(((((((((((((((((((())()))))()(()(())(())))(((()(("

  172. 50

    1099513627778

    Returns: "((((((((()(((((()))))))())((((()()()())(()())((()("

  173. 50

    3284224

    Returns: "(((((((((((((((((((((((((((())(()(((()))()(((((((("

  174. 50

    1000000000000

    Returns: "(((((((((()))())((()((())())(((()(((((())())()(())"

  175. 50

    587272728

    Returns: "(((((((((((((((((((()((())((((((()())((((())(()((("

  176. 50

    562949953421311

    Returns: ")(((((()((())())(((((((()()(()())()(()(()()()()())"

  177. 50

    1021037960441171

    Returns: ")))()(()()(((())(()))()))))(((()())())))))))))))))"

  178. 50

    11258999068

    Returns: "(((((((((((((((()()(()))))))(()()())))())())))((()"

  179. 50

    1121037960441164

    Returns: ")))))))))))))))))))))))))))))))))))))))))))))))((("

  180. 4

    7

    Returns: ")(()"

  181. 49

    100002

    Returns: "(((((((((((((((((((((((((((((((())(((())()()((()("

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: