Connection Status:
Competition Arena > ParenthesesTree

ParenthesesTree

2016 TCO Algo Parallel 2B · 2016-03-24 · by cgy4ever

2016 TCO Algo Parallel 2B · 2016-03-24 · by cgy4ever · Graph Theory
Class Name: ParenthesesTree
Return Type: int
Method Name: minCost
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

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 have a rooted tree with n vertices. The vertices are labeled 0 through n-1. For each vertex v, the parent of v has a smaller number than v. (Hence, vertex 0 is the root: the only vertex with no parent.)

You are given the description of the tree: the int[] p with n-1 elements. For each valid i, vertex p[i] is the parent of vertex (i+1).

You are required to place a single parenthesis onto each edge of the tree. Once you do that, each walk on our tree will produce a sequence of parentheses. Note that the direction of walking will matter. For example, if the edge (x,y) has a label that reads '(' when we go from x to y, the same label reads ')' when we go from y to x.

Different labels may have different costs. You are given these costs in the int[]s L and R. For each valid i:
  • Using the label that reads '(' when we go from p[i] to (i+1) costs L[i].
  • Using the label that reads ')' when we go from p[i] to (i+1) costs R[i].
Note that you cannot leave an edge unlabeled, you must always choose one of the two available labels.

Finally, you are given a set of constraints. These are given in the int[]s a and b. For each valid i, consider the unique simple path from the vertex a[i] to the vertex b[i] in our tree. The string we'll read along this path must be a valid parentheses sequence.

Compute and return the minimal cost of choosing the n-1 labels in such a way that all constraints are satisfied. If it is impossible to satisfy all constraints, return -1 instead.

Constraints

  • n will be between 2 and 50, inclusive.
  • p, L and R will contain exactly n-1 elements.
  • For each valid i, 0 <= p[i] <= i.
  • Each element in L and R will be between 1 and 1,000, inclusive.
  • a will contain between 1 and 50 elements, inclusive.
  • a and b will contain the same number of elements.
  • Each element in a and b will be between 0 and n-1, inclusive.
Examples
0)
{0,1,2,3}
{1,2,3,4}
{10,20,30,40}
{0}
{4}
Returns: 64

There are 2 valid solutions: 0-(-1-(-2-)-3-)-4 0-(-1-)-2-(-3-)-4 In the first one, the cost is 1 + 2 + 30 + 40 = 73. In the second one, the cost is 1 + 20 + 3 + 40 = 64. So we should return 64.

1)
{0,1,2,3}
{1,2,3,4}
{10,20,30,40}
{0}
{3}
Returns: -1

When we read from 0 to 3 we will get a string with 3 characters and that can't be a valid parentheses sequence. So there is no solution.

2)
{0,1,2,3}
{1,2,3,4}
{10,20,30,40}
{2}
{2}
Returns: 10
3)
{0,1,1,3,4,4}
{1,2,3,4,5,6}
{100,200,300,400,500,600}
{0,0,2,2,1}
{5,6,5,6,4}
Returns: 1704
4)
{0,1,1,3,4,4}
{1,2,3,4,5,6}
{100,200,300,400,500,600}
{0,0,2,2}
{5,6,5,6}
Returns: 1605

Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ParenthesesTree with a public method int minCost(vector<int> p, vector<int> L, vector<int> R, vector<int> a, vector<int> b) · 80 test cases · 2 s / 256 MB per case

Submitting as anonymous