SRM 731, D1, 250-Pointer (TreesAndBrackets)

James S. Plank

• Problem Statement.
• A main() with the examples compiled in.
• A skeleton that compiles with main.cpp.

• Problem Given in Topcoder: March, 2018
• Competitors who opened the problem: 184
• Competitors who submitted a solution: 171
• Number of correct solutions: 97
• Accuracy (percentage correct vs those who opened): 52.7%
• Average Correct Time: 21 Minutes, 42 seconds.

In case Topcoder's servers are down

• You can define a tree with a string of parentheses -- "()" represents a leaf node, and "(ABC)" represents a tree with three subtrees, A, B and C.
• (And in case that's unclear, A, B and C are also strings of parentheses, and a tree can have any number of subtrees).
• You are given strings of two trees, t1 and t2.
• You want to decide whether you can convert t1 to t2 by repeatedly deleting leaf nodes from t1.
• If it's possible to do this conversion, return "Possible".
• Otherwise, return "Impossible".
• The strings that you are passed will be legal, and topcoder caps their size at 100. My tests cap their size at 200,000.

The examples

Testing yourself

Hints

Let's start off by looking at the examples. When it's "Possible", I show the nodes that you delete in blue. Make sure you see how examples 3 and 5 return "Possible". I've labeled some subtrees in those examples to help with the explanation.

Observations

Observation #1: While the problem description talks ./a.out deleting leaf nodes, in reality, you are deleting subtrees of T1 to match T2. Look again at example 5 -- there you should be able to see that repeatedly deleting leaf nodes is equivalent to deleting subtrees. I've labeled the subtrees in the first level of example 5, so that it is easier to talk ./a.out that example.

Observation #2: When you are matching t1 and t2, you cannot delete the root nodes. This is because you delete subtrees of t1. If you delete the root of t1, then you will have deleted the entire tree.

Observation #3: If t1 is a single node, and t2 is more than a single node, then t1 will not match t2. That is the case if you try to match a1 and b1 in example 5 above.

Observation #4: If t2 is a single node, then t1 will match t2. That's because you can delete all of t1 except for the root, and then it matches t2. That's what happens in example 0, and with subtrees c1 and d1 in example 3.

Observation #5: Let us suppose now that t1 and t2 are not single nodes. Each of them is the root of an ordered collection of subtrees. Let's call t1's subtrees x1, x2, ... and t2's subtrees y1, y2, ... If x1 matches y1, then you can delete both subtrees, and solve the problem on the remaining subtrees. You can see this best in example 3:

• You match c1 and d1, and then delete them.
• You match c2 and d2, and then delete them.
• You match c3 and d3, and then delete them.
• You're done.

• a1 and b1 don't match, so delete a1.
• a2 and b1 match, so delete both.
• a3 and b2 don't match, so delete a3.
• a4 and b2 match, so delete both.
• a5 and b3 don't match, so delete a3.
• a6 and b3 match, so delete both.
• At this point, t2 is a single node, so you can conclude that t1 and t2 match.

Turning the observations into a solution

class Node {
  public:
    int left_paren, right_paren;
    vector <class Node *> children;
    void Print();
};

And then I wrote a procedure to turn strings into trees. I represent a tree with a single pointer to the tree's root node:

Node *StringToTree(const string &s, int lp);

The parameters are as follows:

• s is the string of parentheses.
• lp is an index of a '(' character in the string.

a = StringToTree("()", 0)
b = StringToTree("(())", 1)
c = StringToTree("(())", 0)

Job #1

UNIX> ./a.out 0
Calling StringToTree on t1
STT("(())", 0) called.
STT("(())", 1) called.
STT("(())", 1) returning: left_paren=1, right_paren=2, children.size()=0
STT("(())", 0) returning: left_paren=0, right_paren=3, children.size()=1

Calling StringToTree on t2
STT("()", 0) called.
STT("()", 0) returning: left_paren=0, right_paren=1, children.size()=0

UNIX>

UNIX> ./a.out 2
Calling StringToTree on t1
STT("(()()())", 0) called.
STT("(()()())", 1) called.
STT("(()()())", 1) returning: left_paren=1, right_paren=2, children.size()=0
STT("(()()())", 3) called.
STT("(()()())", 3) returning: left_paren=3, right_paren=4, children.size()=0
STT("(()()())", 5) called.
STT("(()()())", 5) returning: left_paren=5, right_paren=6, children.size()=0
STT("(()()())", 0) returning: left_paren=0, right_paren=7, children.size()=3

Calling StringToTree on t2
STT("((()))", 0) called.
STT("((()))", 1) called.
STT("((()))", 2) called.
STT("((()))", 2) returning: left_paren=2, right_paren=3, children.size()=0
STT("((()))", 1) returning: left_paren=1, right_paren=4, children.size()=1
STT("((()))", 0) returning: left_paren=0, right_paren=5, children.size()=1

UNIX> 

And here is the program on example 2 -- the picture above should help you verify the output:

UNIX> ./a.out 2
Calling StringToTree on t1
STT("(()()())", 0) called.
STT("(()()())", 1) called.
STT("(()()())", 1) returning: left_paren=1, right_paren=2, children.size()=0
STT("(()()())", 3) called.
STT("(()()())", 3) returning: left_paren=3, right_paren=4, children.size()=0
STT("(()()())", 5) called.
STT("(()()())", 5) returning: left_paren=5, right_paren=6, children.size()=0
STT("(()()())", 0) returning: left_paren=0, right_paren=7, children.size()=3

Calling StringToTree on t2
STT("((()))", 0) called.
STT("((()))", 1) called.
STT("((()))", 2) called.
STT("((()))", 2) returning: left_paren=2, right_paren=3, children.size()=0
STT("((()))", 1) returning: left_paren=1, right_paren=4, children.size()=1
STT("((()))", 0) returning: left_paren=0, right_paren=5, children.size()=1

UNIX> 

Job #2

string TreesAndBrackets::check(string t1, string t2)
{
  Node *n1, *n2;

  n1 = StringToTree(t1, 0);
  n2 = StringToTree(t2, 0);

  printf("LP RP - Children\n");
  n1->Print();
  printf("\n");

  printf("LP RP - Children\n");
  n2->Print();
  printf("\n");

Here's the output on examples 0 and 2:

UNIX> ./a.out 0
LP RP - Children
 0  3 - 1
 1  2 -

LP RP - Children
 0  1 -

UNIX> ./a.out 2
LP RP - Children
 0  7 - 1 3 5
 1  2 -
 3  4 -
 5  6 -

LP RP - Children
 0  5 - 1
 1  4 - 2
 2  3 -

UNIX> 

Job #3

bool Match(const Node *n1, const Node *n2);

This returns true if the subtree rooted at n1 matches the subtree rooted at n2. Again, it will be recursive. Mine went through the following steps.

• First base case: If n2 has no children, then it's a match: return true.
• Second base case: If n2 has more children than n1, then a match will be impossible: return false.
• Now maintain two indices: c1 for the children of n1 and c2 for the children of n2. Start both at zero, and you're going to loop:
• If the subtree rooted at c1 matches the subtree rooted at c2 (this is where there is recursion), then increment both c1 and c2. Otherwise, there was no match, you need to only increment c1.
• At the end of the loop, if there are no more children in c2 to match, then you've succeeded! Return true.
• Otherwise, return false.

UNIX> ./a.out 0
Match(0,0) called.
Match(0,0) returns true.
Possible
UNIX> ./a.out 2
Match(0,0) called.
Match(1,1) called.
Match(1,1) returns false.
Match(3,1) called.
Match(3,1) returns false.
Match(5,1) called.
Match(5,1) returns false.
Match(0,0) returns false.
Impossible
UNIX> ./a.out 3
Match(0,0) called.
Match(1,1) called.
Match(1,1) returns true.
Match(5,3) called.
Match(6,4) called.
Match(6,4) returns true.
Match(5,3) returns true.
Match(13,7) called.
Match(13,7) returns true.
Match(0,0) returns true.
Possible
UNIX>