Statistics

Problem Statement for "ParenthesesDiv1Hard"

Problem Statement

Correct parentheses sequences can be defined recursively as follows:
  • The empty string "" is a correct sequence.
  • If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
  • If "X" is a correct sequence, then "(X)" is a correct sequence.
  • Each correct parentheses sequence can be derived using the above rules.
Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".


We can define the depth and the cost of a correct parentheses sequence recursively as follows:
  • The empty string "" has depth 0 and cost 0.
  • Suppose that "S" = "(A)", where A is a correct parentheses sequence. Then we have depth(S) = depth(A)+1 and cost(S) = cost(A) + depth(S)^2.
  • Suppose that "S" = "AB", where A and B are correct parentheses sequences. Then we have depth(S) = max(depth(A),depth(B)) and cost(S) = cost(A) + cost(B).
For example:
  • The depth of "(((())))" is 4, the depth of "()()()" is 1, and the depth of "(())()" is 2.
  • The cost of "(((())))" is 4^2 + 3^2 + 2^2 + 1^2 = 30, the cost of "()()()" is 1^2 + 1^2 + 1^2 = 3, and the cost of "(())()" is 6.
Note that the depth and the cost of each correct parentheses sequence is uniquely defined using the above rules. For example, when evaluating the depth and cost of "()()()" it does not matter whether we take X = "()" and Y = "()()" or we take X = "()()" and Y = "()", the results will be the same in both cases.


You are given a String s. You are going to split s into two disjoint subsequences s1 and s2. (Each character of s must be used in exactly one of s1 and s2, and the original order of characters must be preserved in the new sequences.)


Your primary goal is to make sure that both s1 and s2 are correct parentheses sequences. If this goal cannot be achieved, return -1.


Your secondary goal is to make cost(s1) + cost(s2) as small as possible. Compute and return the smallest possible value of cost(s1) + cost(s2).

Definition

Class:
ParenthesesDiv1Hard
Method:
minCost
Parameters:
String
Returns:
int
Method signature:
int minCost(String s)
(be sure your method is public)

Notes

  • Pay attention to the unusual time limit.

Constraints

  • s will contain between 1 and 150 elements, inclusive.
  • Each character in s will be '(' or ')'.

Examples

  1. "(())"

    Returns: 2

    The optimal solution is to split s into s1 = s2 = "()". (For example, s1 will be the characters at indices 0 and 2 and s2 will be the characters at indices 1 and 3.) For this split we have cost(s1) = cost(s2) = 1.

  2. "((())())(()()())"

    Returns: 11

    One optimal solution is: s = ((())())(()()()) s1 = () () ()()() s2 = (( ) )( ) Cost(s1) = 5, Cost(s2) = 6.

  3. "())(()"

    Returns: -1

    This s cannot be split into two correct sequences.

  4. "(((((((((())))))))))"

    Returns: 110

  5. "()"

    Returns: 1

  6. "(((())()()()((((()))))(((())))()()()))(()(()))"

    Returns: 69

  7. "()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()(()())()(())()()()()()()()()()(())"

    Returns: 75

  8. "()()()()()()()()()()()()()((())())()()()(())(()(()))()()()(())()(())()()(()((()))())()(())()()()(())()()()((()))()(()()())()()()()()()(())()((())())()"

    Returns: 93

  9. "(((((((((()(()((((((((((((((()(((((((()())(((((((((((((((((((()(((()()(())()))()((())((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 17133

  10. "((((()(((((((((((((((()((((((()((((((((((((((((((((((((((((((((((())(()((((((((()())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 27377

  11. "(())()()()()(())()()()()()(()())()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()"

    Returns: 75

  12. "((()()(())((((((()(((()(((()(()(()(()((()))(()(()()((((())((())()(())()()((((((()((((()()))())(())((((()((()())))))(()))))))))))))))))))))))))))))))))"

    Returns: 4626

  13. "(()())()()(())()(())()()()()()()()()()()((()())()(())())()()(())()(((()()())))()()(()(()))()(())(())()(()())()()(())()()((()))()()(()()())()(())()()()"

    Returns: 90

  14. "((()(()(((()(()(((((()(((()(()(((((((()(((()(((((((((((()((((()((((())((((((()))((((((()(()(()))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 16290

  15. "()()()()()(())()()()()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()(())()(())()()()"

    Returns: 75

  16. "()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()"

    Returns: 75

  17. "(())()(())()((()))()()(())((()))(()())()(((((())()))))()(()((()))())()()()((()(())))()()(())(()(()))()()(())()()()()()()((())(())((()))()(()))(())()()"

    Returns: 124

  18. "((((((((()))((()(((((()((((((((()((()((()((()((((())()))()((())((((())(((((((()((()((()()((()(((((()))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 11759

  19. "(((()(()(((((((((((()((((((((((((((((()((((((((((((((()((((((((((()(((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 28601

  20. "()((())()())()()(()())((((()))(()(()()()))(()))(()))()()(())((()()(()()()))()())()()(((()()())()))()()(()(()((()(((()))()((()()((()((()()())))))))))))"

    Returns: 280

  21. "()()()()()(())()()()()()()()()()(())((()))()()()()()(()())(())(())()()(())()()()(())()()()()()()()()(()()())()((()))()()()()(())()()((()))()()((()))()"

    Returns: 87

  22. "(()((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 35151

  23. "(())()()(()(()((()()((())())))))()((()))()()(())(())()()(()((())(()))())()((()))(())()(((((())))))()()((())())()()()()()()((()())()(())()(()())())()()"

    Returns: 152

  24. "(())(())()(()(()()(()()()((())()()())()))()(()))(())(())()()((()))((())()(()))()(())()()()()(())()(()())()()()()((())()(()))()(())()(()())()()(())()()"

    Returns: 106

  25. "()(((((()())))()()))()(()()(())(((())))())((())())()(()()())((((()(())(()))((()())))()))()()()()()()()()()()()()(()(()((((((())))())(()((((())))))))))"

    Returns: 253

  26. "(((((((((((((()(()((((()(()))((((((((((((())(()(((((((()(((((((((((((((((((()((())(((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 20848

  27. "(())(((())((())())()()))((()(((())(())))))"

    Returns: 57

  28. "((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 18010

  29. "()()()()()()(())(())()()()()()()()()()()()()()(())()()()()()()()()(())()()()()(())()()()()()()()()()()()()()()(())()()()((())())()(())(())()"

    Returns: 73

  30. "()()()((((((())))(()((((((()((((((()(((()()(((((()((((((((((((())())())(()((()()((()))))))))))))))))))))))))))))))))))))))"

    Returns: 5374

  31. "((((((((((()()(((((((((()(((()((((((((()((((((((((((((((()((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 14650

  32. "()()()(())()((())())(())()((()))"

    Returns: 22

  33. "()(((((()((()(())(((()())))((((((()()()()())))))))))))))"

    Returns: 300

  34. "(()()(((((()(((((((((((((()((((())))))))))))))))))))))))"

    Returns: 1304

  35. "()(())()()()()()()()()"

    Returns: 11

  36. "()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()"

    Returns: 30

  37. "()()()()(())()()"

    Returns: 8

  38. "()()(())((())(())(())(()(())(((()(((((()())((())()((())((()(())))()()(()()((()(((((((()))))(())((())(((())(()(())())(()(()))))))))))))))))))))))"

    Returns: 1228

  39. "()()((()())()(())(())(()()))(()(()((()((())()((((()())(()((((((((())(((((((((((()(((((()))))))))))))))))))))))))))))))))"

    Returns: 3311

  40. "(()()(()))(())"

    Returns: 10

  41. "()()()()()()(())()()()()()()()()()()()()()()"

    Returns: 22

  42. "()()()()()()()(())()()()()(())()()()(())(())()()()()()()()(())()()(()())(())()()()()"

    Returns: 42

  43. "((()(())()))"

    Returns: 12

  44. "()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()"

    Returns: 68

  45. "()()()()()()()()()()()((()(())(((()))))()(()()))"

    Returns: 46

  46. "()()()()()()()()()()()()()()()()()"

    Returns: 17

  47. "((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 36594

  48. "("

    Returns: -1

  49. ")"

    Returns: -1

  50. "()))()()))())(()()))())()))))((())())))())(()(()()())))(()))))"

    Returns: -1

  51. ")(())((("

    Returns: -1

  52. "(())(()((((((((((((((((((((("

    Returns: -1

  53. "))()))))())()))))(())(()))()))()))()()()()("

    Returns: -1

  54. "()(())())))())(((((()))(((())())(((())((()()))((()))((()"

    Returns: -1

  55. "())))()())))(()()))))()))())())()))))))))()())()))((((())(())(()()))))))((()))))()())()))))))(()((()"

    Returns: -1

  56. "(())))()()((()(((()))()(()())(())()))()))))()())())))((((((()()())()())))))()(())(()(((()()(())())()()()()((()))("

    Returns: -1

  57. ")())())()"

    Returns: -1

  58. "((((((((((((((((()(((((((((((((((((((((("

    Returns: -1

  59. "(()((((()((((()((((((((((((()(((()(((()(())((())(((())()()"

    Returns: -1

  60. "))())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: -1

  61. "))()))(((())))))(())))))())))))(()))((()))))(())())(()()))))()))())(((())"

    Returns: -1

  62. "()()))))(())))))()())))()))))))()()())))))))()))())())))()))))))))))()))))()))))()))()(())))))())())))))())))))())))))))))))()))))))"

    Returns: -1

  63. "(((((((()((((((((("

    Returns: -1

  64. ")))()((()((()()())))(((())))((((((()())((())(()(((()))())))))))()()()())))())((()()((()(((()()())())))))())()))(()(())((((()())()"

    Returns: -1

  65. "((((((((()((((()()((((((()())))((())"

    Returns: -1

  66. "(((()(()((()()()((((((((()(((((((((((((((((("

    Returns: -1

  67. "(((()()))((((((((((((((((((((((((((((((()(((((((((((((((()(()(((((((((()((((((((((()(((("

    Returns: -1

  68. "((()(((((((((((((((((((((((((((((()(((()((((((()((((((((((()((((()((((((((((((((((((((()(()((((((((((((((((("

    Returns: -1

  69. "((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()(((((((((((((((((((((()(((((((("

    Returns: -1

  70. "()()()()(()())()()()()()(())()()(()())()()()()()()()()((()(()())))()(()(()()))()((()()))()()()(()()())(((())()))(())(())(((((()())()())()()))((())))()"

    Returns: 118

  71. "()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()(())()()()(())()()()()()()()()()()()(())()()()()()()()(())()()()()()()()()()()()"

    Returns: 75

  72. "()(()(()(()((((())))()(()())))((()()((()()))))()(())))()(()(())())(())()()(((()))(()(((()((())()))())))())()()()()(())(()(()))(())()(())()(())()(())()"

    Returns: 202

  73. "(())()()()(((()())))()(((()((())((()(((()(((()()()()(((())(()(((())(((((((()()(()((()()()(((())(((((())))()(((()(())))))))))))))))))))))))))))))))))))"

    Returns: 4269

  74. "()()()(()(()()()))((()((())))((()()((()(()())))))(()(()((()((((((((()((())()()))((())(()(()))))(())()())(()(((()())))))())()))(())))()))))()()()()()()"

    Returns: 518

  75. "((())())(()())()((()))()(()(()()))(()())()(()())()()()(()(()))((((()))()))((()(()())(((((()()))))(((((()))(())())))())()))(())()(())(())(()())((()()))"

    Returns: 194

  76. "()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()"

    Returns: 75

  77. "(())(()())(()())()()(()(()))(())(())()()()()()()()()()()(())()()(((())))()((()(()())))((()))()()()(())()()()()()((()))()()()(()())(())()()()()()()()()"

    Returns: 96

  78. "(((((()(())))()))())()()(())((())())()()()((()))()()(())(())()()(())()()(()(()()((())(())())())())(()((((()()))))(()()()(()()))(((())())(()))(((()))))"

    Returns: 169

  79. "(()(()(())()))()()((()(()(()((((((()())((())((((()))()))((((()()()()()()((((((((())())(()())(()))(((()))()((((())))((())(())(())))))))))))))))))))))))"

    Returns: 1551

  80. "(())((((((())(()((((()((((())())(((((()(())((()))(()))((((()(())(((()(((())))((()(((((((((((()()()(((())(((())))))))))))))))))))))))))))))))))))))))))"

    Returns: 6670

  81. "()()()()()()()()(())()()()()()()()()()()()()()(())(()())(())()()()()()(())()()()()()(())()()()()(())()(())()()()()()()()(())(()(()))((()(()))())()(())"

    Returns: 84

  82. "()(((((((((((((((((((((((((((((((((((((((((((((((((((((((()(((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 33783

  83. "()(((((((((((((((((((((((((((((((()(((((((((((((((((((((()(((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 32415

  84. "()(()()())((())())()()()()()()()()()()()()()()((()))()(()(()())())()(())()()()()()()()()()(())()()()()((()))()()()()(())((()))((()))()()()(())()(()())"

    Returns: 93

  85. "(())()(())(((((((()))(()()))()(()(()(()((((((((()(()(()(()))()(((((((((((())())())()(((((()((((((()())(()()(((()))))))))))))))))))))))))))))))))))))))"

    Returns: 5391

  86. "(())()()()()()()(())()(())(())()()()(())()()()()()()()()(())()()(())((())()())()()()(())(())()()(())()()()()(())()()()()()()(())()()()()()()()()()()()"

    Returns: 78

  87. "()()()()()(())()()()()()()()((())((()())))(()())()()((()))()(())(()())(()())(())()()()()(())()()()()()()(()()(()()))()()(())()()(()(()(())))()()()()()"

    Returns: 93

  88. "((((((((((((((((((()(((((())((((((((()(()((((((((((((()((((((((((((((())((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 26222

  89. "(((((((((((((())((((((((((((((((((((()((((((((((((()((((((((((((((((((()(((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 29825

  90. "()(()(()))()(((())(((((())(()()()()((())()(()))(()()())))(()()(()())())()))))(()()(()()((()))((()(()(((()((()(()()))())))()))))((())()))()))()()()(())"

    Returns: 381

  91. "((()()(())))(())()(())()(())()(())(()())()(()()(((()(()))))((((()())))(())()))()((()))(()((()))(()))()()()(())()()()()(())()(()())()()(()((()(()))))()"

    Returns: 140

  92. "(()(()(((()())))))()((()(()(((()(((())((()((())))))))(((())(((((())()((()((()()(()(())))))(((((()(((()(()()())()))()(())(((())))())())))))))))))))))))"

    Returns: 1167

  93. "()()()()(())()()()()()()()(())()()()()()()()()()()()()()()()()()()()(())(())()()(())()()()(((())))()()(()())()(())((())())((())((()))())()()()()()(())"

    Returns: 90

  94. "()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()()()()()()()()()"

    Returns: 75

  95. "(())()()()()((()))()()()()()((()))()(()(()))(())()()((())(()))()(())(())()()()()()()()(())()()()()()()((()()))()()()()()()(()(())())()()(()(())(()))()"

    Returns: 96

  96. "()(()((()(((()))((()())())))))(()((())(()())))(((()())()))((()))()()()(()())((((()(()()()()))())))()()()((())()()(((()(()())))))(()()((())()))()()()()"

    Returns: 180

  97. "(())(()(()((())())()()(((()))((((()()()(()(()((()))()((()()((()))(()()))(()))(((())(()(()))()(((()))()(())())(()()(((()(((((((()))))))))))))))))))))))"

    Returns: 1240

  98. "()(((()(((((((()(((((((((((((((((((((((((((((((((((((())(((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 29825

  99. "()()()()()()()()(()())()()()((()))()()(()(()))()()()()()(())()(((()(()()))))()()()()()()()()()()()(())()()((()()))(())()()()()()(())(())(()())()()()()"

    Returns: 98

  100. "(())()()()(((()()())))()()()()((()))()(((())))()()(())()()()()()()((()(()()())()))((()))()()(()()()()()()(()))()()((()((()))))(())()()()()()(())()()()"

    Returns: 116

  101. "((((((()((((()((()()((((()(((()((((((()(((((()()((((()((()(())((())(((())()((((())(())(()()(((()((()()))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 10451

  102. "(())()()()()()()()((()))()(())((()))((()()))(())(())()()(())(()())()(())(()())()((()))()()()(())()()()(())()()()()()()()()()()()(()(()))()()()(())()()"

    Returns: 90

  103. "()((((((((()(()(()(((((()()(()((()((())(()(((((()(()()((()())(((((((()((()())(((()(()())(((()()())(((((())))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 8677

  104. "(())(()())()(()((((((()(((()(())((()))((()())(())()))()())()(()((()(()(()()(()(())))())()()))())())(((())))((((((())(()()(()))()))))()(((())))))))))))"

    Returns: 548

  105. "()(((((((((((((((((((((((((((()((((((((((((((((((((((((((((((((((((((((()()(((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 31120

  106. "()()()()((())()())((()())())(())()(())()()()(()(()))()()()()()()((()))(())()(()(((())))(()(()()())))()((()))()()()()(((())))(()()()()((())))(())()()()"

    Returns: 119

  107. "((()(((((((((((((((((((((((((((((((((((((((((((((()((((((()(((((((((((((())((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 29825

  108. "((((((((((((((((((((((((((((((((((((((((((((()(((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 35151

  109. "()()(())()(())()()(())()()()()(())()()(()())()()()()()()()()()()()()(())()()()()()()()(()())()()()(()())()()()((()))()()()(())()()()(())()()()(()(()))"

    Returns: 81

  110. "(((((((((()()())())())()(()()()()())(((()())))(())(()()))((((())(())))(()((()(((((())()()(((())))())()())(()())()))(()))()((())(())((()()))())))))))))"

    Returns: 579

  111. "((()"

    Returns: -1

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: