Statistics

Problem Statement for "TreesAndBrackets"

Problem Statement

This problem is about rooted trees in which the order of children matters. This type of trees is easily encoded using correct bracket sequences. The code of a tree rooted at r is constructed as follows:
  1. Write down the opening bracket '('.
  2. For each child c of r, in order, write down the code of the subtree rooted at c.
  3. Write down the closing bracket ')'.
For example, the code of a three-vertex tree in which the root has two children is "(()())". You are given the Strings t1 and t2 that represent two rooted trees using the encoding defined above. You want to transform t1 into t2.
The only operation you are allowed to perform is to remove a leaf from t1. (A leaf is a vertex with no children.) Note that removing the child of a parent does not change the relative order of the other children of that same parent.
Return "Possible" if there is a sequence of zero or more operations that transforms t1 into t2. Otherwise, return "Impossible".

Definition

Class:
TreesAndBrackets
Method:
check
Parameters:
String, String
Returns:
String
Method signature:
String check(String t1, String t2)
(be sure your method is public)

Constraints

  • t1 and t2 will contain between 2 and 100 characters, inclusive.
  • Each character in t1 and t2 will be either '(' or ')'.
  • Both t1 and t2 will represent a correct tree.

Examples

  1. "(())"

    "()"

    Returns: "Possible"

  2. "()"

    "()"

    Returns: "Possible"

  3. "(()()())"

    "((()))"

    Returns: "Impossible"

    Currently t1 is a tree of depth 2 in which the root has three children, while t2 is a tree of depth 3. Clearly, you cannot increase the depth of a tree by removing some of its vertices.

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

    "(()(())())"

    Returns: "Possible"

  5. "((())((())())())"

    "((()()()()()))"

    Returns: "Impossible"

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

    "(((()())()(()())(()())()()(())())()(())((())(()())(()())()(())()(())()(())()(()()()())))"

    Returns: "Impossible"

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

    "(((()())())()()(()()())((())(())))"

    Returns: "Impossible"

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

    "(()(()())(())())"

    Returns: "Impossible"

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

    "(()())"

    Returns: "Possible"

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

    "(((()))()()(()())()(())(()()(()(()))(()(((()))))(())()))"

    Returns: "Impossible"

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

    "(()()(())(())((()(())(())))(())()(()()))"

    Returns: "Impossible"

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

    "((())(())())"

    Returns: "Impossible"

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

    "(()()()(()((()(())())((()()()))((()))()(()(())())()()()((())())(()))())()())"

    Returns: "Impossible"

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

    "(()()((())))"

    Returns: "Possible"

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

    "(()()(())())"

    Returns: "Possible"

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

    "((())(()())(()()()()(()()())(((())))(()(())()(())()(()))())()()(())()())"

    Returns: "Possible"

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

    "((())()(()()))"

    Returns: "Possible"

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

    "(()((())()())(()(())(()))()((())())()()(()(()())()(()()))((()))(()))"

    Returns: "Impossible"

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

    "(()())"

    Returns: "Possible"

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

    "((())()(()()()())()()(())()(())()(()())(())((((()))))()(()()(())))"

    Returns: "Impossible"

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

    "((()()))"

    Returns: "Possible"

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

    "((()()()()())()()())"

    Returns: "Possible"

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

    "(()(()()()()))"

    Returns: "Impossible"

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

    "(((((()))())()())())"

    Returns: "Impossible"

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

    "(((()())))"

    Returns: "Impossible"

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

    "(()((()()()(())()()()((()()))())()))"

    Returns: "Impossible"

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

    "(()((())()))"

    Returns: "Possible"

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

    "((()()()())()()())"

    Returns: "Possible"

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

    "((()()()()((())(())()()(())())()()()(())()()((())))(())((())()()()()((()))())(()()))"

    Returns: "Impossible"

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

    "(()((()))())"

    Returns: "Impossible"

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

    "(((((((((())))))))))"

    Returns: "Possible"

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

    "((()(())))"

    Returns: "Possible"

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

    "((())())"

    Returns: "Impossible"

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

    "((((()))))"

    Returns: "Possible"

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

    "(((()(((()))))))"

    Returns: "Possible"

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

    "(((()(()))))"

    Returns: "Possible"

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

    "((()()((()()(()()(()))))))"

    Returns: "Possible"

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

    "((((()))))"

    Returns: "Possible"

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

    "(((((((()))))())))"

    Returns: "Possible"

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

    "((((()())()())()()))"

    Returns: "Possible"

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

    "((((()(()(((()()(()(((((((()))())())())()))))())()))))))"

    Returns: "Possible"

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

    "((()))"

    Returns: "Possible"

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

    "((((()))))"

    Returns: "Possible"

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

    "(((((((())))))))"

    Returns: "Possible"

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

    "((()()))"

    Returns: "Possible"

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

    "(())"

    Returns: "Possible"

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

    "((()))"

    Returns: "Possible"

  48. "((()(()()((()()(()(()((()(((()(())())()())()())())()())())()))()()))()))"

    "(((()(((((((()()())())())())()))))))"

    Returns: "Possible"

  49. "(((()()(()(()(()(()(((()())()())()())())())())()))()()))"

    "(((((()(((((()()))()))()))))()))"

    Returns: "Possible"

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

    "(()(((()))))"

    Returns: "Impossible"

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

    "((()()(()(()(((((()(()()(()())))()())())()())()()))())))"

    Returns: "Possible"

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

    "((()()))"

    Returns: "Possible"

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

    "((())())"

    Returns: "Impossible"

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

    "(())"

    Returns: "Possible"

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

    "((()))"

    Returns: "Possible"

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

    "((()()))"

    Returns: "Possible"

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

    "((((())))())"

    Returns: "Impossible"

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

    "((()))"

    Returns: "Possible"

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

    "((()()))"

    Returns: "Possible"

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

    "((((()))))"

    Returns: "Possible"

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

    "((()()(()()(()(()()(()(()((()()(((()()(()((()()(()(()())))()())()))())()()))()()))()))()))()))"

    Returns: "Impossible"

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

    "((()))"

    Returns: "Possible"

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

    "(()((())))"

    Returns: "Impossible"

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

    "(((((((())))))))"

    Returns: "Possible"

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

    "(((((()))())))"

    Returns: "Possible"

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

    "((((()))))"

    Returns: "Possible"

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

    "(((()))())"

    Returns: "Impossible"

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

    "(((())))"

    Returns: "Possible"

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

    "(()())"

    Returns: "Impossible"

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

    "((()))"

    Returns: "Possible"

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

    "(()())"

    Returns: "Impossible"

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

    "((((((((((()))))))))))"

    Returns: "Possible"

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

    "((()()))"

    Returns: "Possible"

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

    "(((((((())))))))"

    Returns: "Possible"

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

    "(((()))())"

    Returns: "Impossible"

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

    "((()(((()(()))))))"

    Returns: "Possible"

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

    "((((((()()))))))"

    Returns: "Possible"

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

    "((()()))"

    Returns: "Possible"

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

    "((()(((()((()()(()(())))()))()))))"

    Returns: "Possible"

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

    "(((())))"

    Returns: "Possible"

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

    "(((())))"

    Returns: "Possible"

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

    "(((())))"

    Returns: "Possible"

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

    "((()(())))"

    Returns: "Possible"

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

    "(((((((((()((()))))())))()))))"

    Returns: "Possible"

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

    "(((()((((())))))))"

    Returns: "Possible"

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

    "((()(())()()))"

    Returns: "Impossible"

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

    "(((())))"

    Returns: "Possible"

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

    "((((()(()(()(()((())())())()))())()())()()))"

    Returns: "Impossible"

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

    "((()))"

    Returns: "Possible"

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

    "(((((((()((())))()))))))"

    Returns: "Possible"

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

    "(()(())()(())((())(((())()((()))((((())))()(()))))())((()))((((()))))()()(())())"

    Returns: "Possible"

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

    "((()()))"

    Returns: "Possible"

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

    "((()))"

    Returns: "Possible"

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

    "(()(()))"

    Returns: "Impossible"

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

    "(((()))(((()())()))((())))"

    Returns: "Impossible"

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

    "((())(()))"

    Returns: "Possible"

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

    "()"

    Returns: "Possible"

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

    "((((()))())(()(())))"

    Returns: "Possible"

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

    "((()))"

    Returns: "Possible"

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

    "((())())"

    Returns: "Possible"

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

    "(()())"

    Returns: "Impossible"

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

    "((()()()))"

    Returns: "Impossible"

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

    "((()()()()()((((()))))))"

    Returns: "Impossible"

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

    "((()()))"

    Returns: "Impossible"

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

    "((())(((())())))"

    Returns: "Possible"

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

    "(()(()()))"

    Returns: "Impossible"

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

    "(((())))"

    Returns: "Possible"

  108. "((()))"

    "()"

    Returns: "Possible"

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

    "(())"

    Returns: "Possible"

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

    "(((((()()))((()))((()()))(())))(((())((()))((()()())))))"

    Returns: "Possible"

  111. "(((()))(()))"

    "(((())()))"

    Returns: "Impossible"

  112. "((()())(()((()))))"

    "((()()((()))))"

    Returns: "Impossible"

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: