Problem Statement |
| | Petya likes oriented graphs, especially rooted trees. He has such a tree described in a String target. Every edge may be in an active or inactive state. Initially every edge is in an inactive state. Petya wants to change the states of all the edges so that they are all active. To do so he has some trees described in a String[] trees in which each element describes a single tree. Initially, every edge in target is inactive and he must activate them by repeating the following process:
- He chooses some vertex V from target and some tree T from trees. The pair (V, T) can only be chosen once overall.
- He chooses a subtree T' from target that is rooted at V and is isomorphic to T (see notes for a definition if required).
- The state of every edge in T' is toggled (i.e., if it was active, it becomes inactive; if it was inactive it becomes active).
Each time he follows the process he incurs a cost that depends on which tree he selected. If he selects trees[i] it costs him costs[i]. Petya also likes the number 5 and so no vertex in target will have more than 5 children. Return the minimum cost of activating all the edges in target or -1 if it is impossible to do so.
target and the trees in trees will be described using the same format:
- The vertices are indexed sequentially starting with the root as vertex 0.
- The parent of each vertex in index order is then written in a space-separated list. I.e., if the i-th number written (zero-indexed) is p[i],
it means that there is a directed edge from vertex p[i] to vertex i in the tree. Since the root has no parent, the first number in the list will
be -1 instead.
|
| |
Definition |
| | | Class: | ActivateTree | | Method: | minCost | | Parameters: | String[], String, int[] | | Returns: | int | | Method signature: | int minCost(String[] trees, String target, int[] costs) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Two trees T and T' are isomorphic if there exists a 1-to-1 mapping between the vertices of T and T', such that for each pair of vertices V1 and V2 in T, there is an edge (V1, V2) if and only if and edge exists between the corresponding vertices of T'. I.e., one tree can be transformed into the other simply by relabelling the vertices. |
| |
Constraints |
| - | target will contain between 1 and 46 characters, inclusive. |
| - | trees will contain between 1 and 5 elements inclusive. |
| - | Each element of trees will contain between 4 and 10 characters. |
| - | target and each element of trees will be single-space delimited lists of integers formatted without leading zeros, with no leading or trailing spaces. |
| - | target will contain between 2 and 16 integers, inclusive. |
| - | Each element of trees will contain between 2 and 5 integers, inclusive. |
| - | The first integer in target and in each element of trees will be -1. |
| - | target and each element of trees will describe valid trees as specified in the problem statement. |
| - | No vertex in the tree represented by target will have more than 5 children. |
| - | costs will contain the same number of elements as trees. |
| - | Each element of costs will be between 0 and 65536, inclusive. |
| |
Examples |
| 0) | |
| | |
| 1) | |
| | |
| 2) | |
| | {"-1 0","-1 0"} | "-1 0 0" | {1,101} |
| Returns: 102 | | Petya can not use the first tree twice in the same position so he has to pay once for each of the trees. |
|
|
| 3) | |
| | {"-1 0","-1 0","-1 0 3 0"} | "-1 0 3 0" | {5,10,21} |
| Returns: 20 | | Here it is cheaper to use the first tree twice and the second tree once than to use only the third tree. |
|
|
| 4) | |
| | {"-1 0 1","-1 0 0","-1 0","-1 0 1 0 2"} | "-1 0 0 0 2" | {3885,13122,31377,21317} |
| Returns: 17007 | |
|