Statistics

Problem Statement for "ActivateTree"

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:

  1. He chooses some vertex V from target and some tree T from trees. The pair (V, T) can only be chosen once overall.
  2. He chooses a subtree T' from target that is rooted at V and is isomorphic to T (see notes for a definition if required).
  3. 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

  1. {"-1 0","-1 4 4 4 0","-1 0 0","-1 0 0 0","-1 0"}

    "-1 0 0 2 3 4 3 1 4 4 0 3 11 6 7 4"

    {19574,960,641,20810,17151}

    Returns: 122299

  2. {"-1 0 0 1 1","-1 3 3 0","-1 0 1","-1 0 1","-1 0"}

    "-1 0 0 13 2 0 5 2 2 7 8 3 3 7 6 1"

    {19457,9631,15335,17890,3036}

    Returns: 53899

  3. {"-1 0 0","-1 0 0 2 2","-1 0 1","-1 0 0","-1 0"}

    "-1 0 1 0 1 3 3 5 4 7 2 10 1 5 6 8"

    {14113,18372,22680,32448,31376}

    Returns: 176232

  4. {"-1 0 1 1","-1 0 0 2","-1 0","-1 0 1 1","-1 0"}

    "-1 0 1 1 3 3 5 4 1 3 1 5 0 6 11 10"

    {19676,26524,27717,5642,3307}

    Returns: 36768

  5. {"-1 0","-1 0 0 2 2","-1 0 0 2","-1 0","-1 0"}

    "-1 0 0 1 3 3 4 5 3 8 7 1 0 9 5 3"

    {13261,11182,15798,22900,13088}

    Returns: 90514

  6. {"-1 0","-1 0","-1 0 0","-1 0 1 1 2","-1 0 1 0"}

    "-1 0 0 1 0 1 3 5 3 7 7 2 11 10 8 10"

    {32445,23763,4696,25392,3985}

    Returns: 66517

  7. {"-1 0 1","-1 0 0 2 1","-1 0 0","-1 0 0 1 3","-1 0 0"}

    "-1 0 1 0 2 2 0 1 5 8 3 4 7 6 8 7"

    {7855,7730,22174,22020,16532}

    Returns: -1

  8. {"-1 0 1 0","-1 0 0 0","-1 0 1 1","-1 0 1 1 2","-1 0 1"}

    "-1 0 0 2 3 0 2 6 7 6 6 1 1 5 3 2"

    {12005,11121,28218,30324,9165}

    Returns: 92451

  9. {"-1 0 0 2","-1 0 0 2 1","-1 0 0","-1 0 1 2 0","-1 0 1"}

    "-1 0 0 0 0 2 2 1 2 1 2 9 7 0 10 14"

    {8344,28493,19666,9739,10999}

    Returns: 69486

  10. {"-1 0 1 0","-1 0","-1 0 0 0 1","-1 0 1 1","-1 0 0 2"}

    "-1 0 1 2 3 2 2 0 2 6 5 6 6 3 12 6"

    {15431,31521,4447,23120,4492}

    Returns: 40998

  11. {"-1 0 0","-1 0 1 1","-1 0 0 1 1","-1 0 1 1 3","-1 0"}

    "-1 0 1 1 2 2 1 3 3 3 7 7 1 0 11 8"

    {548,2903,15044,24517,7953}

    Returns: 31309

  12. {"-1 0","-1 0 0 1 3","-1 0 0 0 0","-1 0 1","-1 0 1 2 2"}

    "-1 0 1 0 3 2 3 5 4 7 8 9 7 1 6 8"

    {21715,18470,4498,9371,5616}

    Returns: 73642

  13. {"-1 0 1","-1 0 1","-1 0 0 0","-1 0 1 2","-1 0"}

    "-1 0 1 2 2 3 5 4 1 5 5 6 9 0 13 7"

    {21604,13052,21360,3173,28042}

    Returns: 70279

  14. {"-1 0 1 2","-1 0","-1 0 1 0","-1 0","-1 0 1 2"}

    "-1 0 1 1 3 4 5 2 2 0 1 3 11 3 6 1"

    {30995,15730,15767,10615,12751}

    Returns: 88881

  15. {"-1 0 1 1","-1 0 1 2 2","-1 0 0 2 2","-1 0 0","-1 0 1 0"}

    "-1 0 0 1 2 1 0 4 6 3 1 5 1 7 11 14"

    {19341,15915,1701,147,21550}

    Returns: -1

  16. {"-1 0 0","-1 0 0 2 2","-1 0 1 2","-1 0","-1 0"}

    "-1 0 1 1 0 2 4 1 4 2 8 10 9 1 8 7"

    {4733,4439,15302,6612,3306}

    Returns: 23235

  17. {"-1 0 0 0 1","-1 0 1 0 2","-1 0 0 1","-1 0 1 0","-1 0"}

    "-1 0 0 2 1 0 3 3 6 2 4 6 5 7 7 1"

    {18205,16541,30815,18262,24124}

    Returns: 143642

  18. {"-1 0 1 2 2","-1 0 0 2","-1 0 0","-1 0","-1 0 0 2 1"}

    "-1 0 1 0 3 3 4 1 1 2 8 2 4 12 12 3"

    {12174,9947,15508,24063,30273}

    Returns: 73031

  19. {"-1 0 0","-1 0 1","-1 0 0 1 2","-1 0 1","-1 0"}

    "-1 0 1 2 3 4 3 6 1 4 1 9 2 12 9 6"

    {890,1089,12215,12464,32121}

    Returns: 38550

  20. {"-1 0 1 1","-1 0","-1 0 1 1","-1 0 1 2 1","-1 0 1 1 3"}

    "-1 0 1 1 1 2 3 0 4 1 0 7 4 10 12 11"

    {19531,26178,29596,894,23847}

    Returns: -1

  21. {"-1 0 1 0","-1 0 0 2 3","-1 0","-1 0 0 0 3","-1 0 1"}

    "-1 0 1 1 1 2 4 0 1 2 7 8 0 10 10 2"

    {13742,16119,31824,23928,156}

    Returns: 139543

  22. {"-1 0 1 0 1","-1 0","-1 0 0 1 3","-1 0 0 0","-1 0 0 2 3"}

    "-1 0 1 1 2 0 3 1 1 1 9 8 5 7 6 3"

    {1366,11952,7567,6947,32753}

    Returns: 81391

  23. {"-1 0 1 1","-1 0 1","-1 0","-1 0 0 0 0","-1 0 0"}

    "-1 0 1 1 3 0 5 1 5 3 7 2 3 6 2 6"

    {23904,825,4196,7901,29474}

    Returns: 51555

  24. {"-1 0 0 0","-1 0 1","-1 0","-1 0 0 0 0","-1 0 1 0 0"}

    "-1 0 1 0 1 1 3 3 2 4 0 4 10 0 9 5"

    {30319,8118,27126,15969,28537}

    Returns: 154688

  25. {"-1 0 0 0 2","-1 0 1","-1 0 1 0","-1 0 0 1","-1 0 0"}

    "-1 0 1 2 2 1 3 5 4 5 7 9 4 4 2 6"

    {5423,5009,19542,22801,29299}

    Returns: 74300

  26. {"-1 0 1","-1 0 0 1 1","-1 0 1 0","-1 0 0 1 0","-1 0 0 1"}

    "-1 0 0 1 0 3 0 1 3 5 7 1 11 10 8 0"

    {8780,13801,23172,11550,23173}

    Returns: 118957

  27. {"-1 0 1","-1 0 0","-1 0","-1 0 1 2","-1 0"}

    "-1 0 0 0 1 1 5 6 2 5 4 9 7 7 11 6"

    {8565,2650,10567,19538,21067}

    Returns: 40947

  28. {"-1 0 0 0 2","-1 0","-1 0 0 2 0","-1 0","-1 0 0"}

    "-1 0 1 1 3 3 5 1 0 6 4 8 8 4 1 8"

    {19953,2248,7545,2256,5032}

    Returns: 32825

  29. {"-1 0 1 2","-1 0","-1 0 1 2","-1 0 1 0","-1 0 1 0"}

    "-1 0 0 2 2 1 4 5 0 4 1 2 2 9 6 9"

    {32498,747,27793,3792,2111}

    Returns: 12179

  30. {"-1 0 1 1","-1 0 1","-1 0","-1 0","-1 0 1"}

    "-1 0 0 2 1 2 2 4 2 0 0 7 1 5 8 5"

    {22762,31091,10461,25414,32747}

    Returns: 164795

  31. {"-1 0 0 1 2","-1 0 1","-1 0 1 0 2","-1 0 0 2 3","-1 0 1 1 2"}

    "-1 0 0 0 3 4 5 2 0 3 8 3 8 6 10 14"

    {17670,19323,31039,21654,15700}

    Returns: -1

  32. {"-1 0 0","-1 0","-1 0 1","-1 0 0 0 2","-1 0 1 1 3"}

    "-1 0 1 2 1 2 2 4 1 2 7 10 0 9 10 9"

    {7946,4265,14476,30371,3610}

    Returns: 35907

  33. {"-1 0 0 1 0","-1 0","-1 0 1 2","-1 0 1 0","-1 0"}

    "-1 0 1 2 3 2 4 2 6 3 4 5 10 0 10 13"

    {12048,24891,8610,22329,2985}

    Returns: 49710

  34. {"-1 0 0","-1 0 1","-1 0 0","-1 0 0 1 2","-1 0 1 0"}

    "-1 0 0 2 0 0 2 2 6 3 9 8 3 4 1 10"

    {21557,20678,19630,31367,15618}

    Returns: 127601

  35. {"-1 0 1 1 2","-1 0 0","-1 0 1 2","-1 0 1 0","-1 0"}

    "-1 0 0 2 2 1 5 4 4 4 0 9 8 7 6 8"

    {9973,30469,4512,22673,8407}

    Returns: 71005

  36. {"-1 0 0 0","-1 0","-1 0","-1 0 0","-1 0 1 0 2"}

    "-1 0 1 0 0 4 4 5 7 0 5 7 5 5 5 13"

    {14223,26993,3031,19692,11268}

    Returns: 54869

  37. {"-1 0","-1 0 1 0","-1 0 1","-1 0 0 0 2","-1 0 0 1"}

    "-1 0 0 0 0 2 4 1 4 2 6 2 3 2 0 5"

    {27080,31650,7844,13203,5045}

    Returns: 49385

  38. {"-1 0","-1 0","-1 0 1","-1 0 0 1","-1 0 0 1"}

    "-1 0 0 0 0 0 5 2 1 4 3 6 6 7 13 11"

    {3588,8094,21116,4445,26057}

    Returns: 56475

  39. {"-1 0 0 1 3","-1 0 1 2","-1 0 1 0 0","-1 0 0 0","-1 0"}

    "-1 0 0 1 0 0 3 3 3 6 2 2 9 0 13 10"

    {8381,20471,20493,14345,25253}

    Returns: 97324

  40. {"-1 0 0","-1 0 0 1","-1 0","-1 0 1 0 2","-1 0 1"}

    "-1 0 0 1 3 2 4 3 2 1 6 7 7 4 8 10"

    {18549,24443,3149,1240,27058}

    Returns: 13167

  41. {"-1 0 0 1","-1 0 1","-1 0 0","-1 0 1 0","-1 0 0 0"}

    "-1 0 0 0 0 4 0 3 3 8 8 2 4 9 12 9"

    {31823,5253,13123,18349,19834}

    Returns: 81347

  42. {"-1 0 1 0","-1 0 0","-1 0 0 2 0","-1 0 0 2 2","-1 0 1"}

    "-1 0 0 2 3 2 1 3 6 7 0 1 11 9 1 13"

    {24312,11718,5018,6118,7003}

    Returns: 55357

  43. {"-1 0 0 2 0","-1 0 1 0","-1 0 0 1","-1 0","-1 0 1 2 1"}

    "-1 0 1 0 2 3 3 4 2 1 0 5 10 8 13 10"

    {14933,8162,29516,17868,23243}

    Returns: 110891

  44. {"-1 0 0 2","-1 0 0 2 3","-1 0 1 0 3","-1 0","-1 0"}

    "-1 0 0 2 2 0 4 2 1 1 8 5 1 6 7 2"

    {1515,12616,4711,23480,16614}

    Returns: 36971

  45. {"-1 0 0 1 3","-1 0","-1 0 1 1 3","-1 0 0 0","-1 0 0 1 1"}

    "-1 0 1 1 0 2 3 4 3 6 2 6 7 11 6 4"

    {9622,32046,28293,26242,7088}

    Returns: 114132

  46. {"-1 0 1","-1 0","-1 0 0","-1 0","-1 0"}

    "-1 0 0 2 1 4 2 4 2 4 9 0 5 4 11 9"

    {3173,29971,7294,16630,29588}

    Returns: 55325

  47. {"-1 0 1","-1 0","-1 0 1 1 1","-1 0","-1 0 0 0 0"}

    "-1 0 0 2 0 2 1 4 0 6 4 1 10 8 6 8"

    {8491,1857,26259,21919,16609}

    Returns: 75143

  48. {"-1 0 1 2","-1 0 0 0","-1 0 1","-1 0","-1 0 1 1"}

    "-1 0 1 0 0 1 1 2 0 5 1 8 0 10 13 6"

    {22907,9802,23501,8054,10704}

    Returns: 90835

  49. {"-1 0","-1 0 1","-1 0 1 0 3","-1 0 0 1 1","-1 0 0 0"}

    "-1 0 0 1 1 0 2 1 1 2 1 0 6 10 6 14"

    {1869,11446,24495,28998,30877}

    Returns: 85730

  50. {"-1 0 0","-1 0","-1 0","-1 0","-1 0"}

    "-1 0 1 2 1 4 0 4 4 4 0 7 6 11 12 8"

    {18586,3628,7232,6723,4517}

    Returns: 66881

  51. {"-1 0 1 1","-1 0 1 0","-1 0 1 1","-1 0","-1 0"}

    "-1 0 1 1 1 0 4 3 0 6 4 10 6 9 0 4"

    {20202,10619,5220,24123,4100}

    Returns: 65682

  52. {"-1 0","-1 0 1 0 3","-1 0 0 0","-1 0","-1 0 1 0"}

    "-1 0 0 2 1 1 5 4 6 4 7 7 10 0 9 7"

    {15717,21794,6491,8268,4579}

    Returns: 43120

  53. {"-1 0","-1 0 0 0 2","-1 0 0","-1 0 1 1 2","-1 0 0"}

    "-1 0 1 0 1 2 0 4 6 8 2 6 1 1 3 13"

    {10767,5593,6023,32282,17093}

    Returns: 55533

  54. {"-1 0","-1 0","-1 0","-1 0","-1 0"}

    "-1 0 1 0 0 2 0 2 6 8 6 8 4 11 1 10"

    {12546,473,10434,25105,9854}

    Returns: 76034

  55. {"-1 0","-1 0","-1 0 0 2","-1 0","-1 0 1 1 3"}

    "-1 0 1 0 3 2 2 3 7 6 5 10 5 8 6 4"

    {25505,28289,9956,636,11399}

    Returns: 33684

  56. {"-1 0 1","-1 0 0 0","-1 0 0","-1 0 0 1 0"}

    "-1 0 0 2 2 1 5 6 7 7 8 2"

    {21131,2987,13381,8708}

    Returns: 79761

  57. {"-1 0","-1 0 1 0 0","-1 0","-1 0","-1 0 1"}

    "-1 0 0 1 3 2 5 2 1 3 4 1 7 7"

    {15070,16130,22060,27966,27871}

    Returns: 144953

  58. {"-1 0 0 1","-1 0","-1 0 0 1 3","-1 0 1 1"}

    "-1 0 0 2 1 1 1 1 6 5 0 8 6 10 7"

    {454,16167,1512,16317}

    Returns: 50013

  59. {"-1 0 1 1","-1 0 0","-1 0"}

    "-1 0 1 1 1 2 2 3 4 3 2 2 9 10 11 2"

    {31604,13851,5224}

    Returns: 104501

  60. {"-1 0 0","-1 0 0 0","-1 0","-1 0 1","-1 0 1 1 0"}

    "-1 0 1 1 2 1 5 6 5 8 3"

    {17072,25761,22597,107,3556}

    Returns: 90709

  61. {"-1 0","-1 0","-1 0","-1 0 0 1 1"}

    "-1 0 1 2 0 2 5 5 6 1 5"

    {22251,3099,7538,14142}

    Returns: 34482

  62. {"-1 0 0 1 2","-1 0 1","-1 0 1","-1 0 1"}

    "-1 0 1 0 0 0 1 5 3 8 6"

    {21181,19542,4531,15676}

    Returns: -1

  63. {"-1 0","-1 0","-1 0 0 0 0","-1 0 0 2","-1 0 1 1 0"}

    "-1 0 1 1 2 0 3 4 5 7"

    {25905,1720,11800,8930,1533}

    Returns: 10133

  64. {"-1 0 0 2 2","-1 0 1","-1 0 0 1 0","-1 0 1 1","-1 0 1"}

    "-1 0 1 1 3 4 3 1"

    {23887,3451,20146,28738,10941}

    Returns: 35640

  65. {"-1 0","-1 0 1 0","-1 0 0 2","-1 0"}

    "-1 0 1 1 0 0 2 4 0"

    {8437,8670,13769,26}

    Returns: 17211

  66. {"-1 0 1 1 3","-1 0 0 2","-1 0 0 2"}

    "-1 0 1 0 2 1 5 0 4 6 4 5 0"

    {16553,12892,9646}

    Returns: -1

  67. {"-1 0 0 0","-1 0 0","-1 0 1","-1 0 0 1 0","-1 0 0 0"}

    "-1 0 0 0 1 1 2 3"

    {4083,13505,24472,120,21808}

    Returns: 55685

  68. {"-1 0","-1 0 1 1","-1 0"}

    "-1 0 0 2 0 2 4 6 6 1 0 9 1"

    {27312,17544,12658}

    Returns: -1

  69. {"-1 0","-1 0 0 1","-1 0 1 2","-1 0 1"}

    "-1 0 0 0 1 4 3 5 7"

    {9636,3215,11439,4232}

    Returns: 18886

  70. {"-1 0 1 0 2","-1 0","-1 0 1 0","-1 0 1","-1 0 0"}

    "-1 0 0 2 3 3 5 5"

    {26072,2439,5512,11636,11690}

    Returns: 13463

  71. {"-1 0 0 1","-1 0 0 0","-1 0"}

    "-1 0 0 1 0 3 4 6 5 7 4 8 4 8"

    {15368,12745,11128}

    Returns: -1

  72. {"-1 0 1","-1 0","-1 0 1 1 3","-1 0 1 1 1","-1 0 0"}

    "-1 0 0 1 2 1 3 5"

    {22484,381,12420,32289,16355}

    Returns: 13563

  73. {"-1 0 1 0","-1 0 1"}

    "-1 0 0 2 1 1 3 6 4 3 3 4 7 1 1 9"

    {67,5249}

    Returns: -1

  74. {"-1 0 0 2","-1 0 0 1","-1 0","-1 0 1","-1 0 1 2 1"}

    "-1 0 0 1 2 1 3"

    {17924,21294,24578,1639,9795}

    Returns: 11434

  75. {"-1 0 1","-1 0 0 2 2","-1 0","-1 0 1 2 1","-1 0 0"}

    "-1 0 1 0 1 4 4"

    {20409,9345,20806,10249,25337}

    Returns: 34682

  76. {"-1 0","-1 0 0 0 3"}

    "-1 0 1 1 0 3 4 0 6 8 1 6 0 10 11"

    {21238,14660}

    Returns: -1

  77. {"-1 0 1 2 3","-1 0","-1 0 1","-1 0 0 2","-1 0 1 0 2"}

    "-1 0 1 1 1 2 2"

    {15628,5038,2787,6102,2713}

    Returns: 13927

  78. {"-1 0","-1 0 1 1"}

    "-1 0 1 1 0 1 1 3 0 7 4 0 9 1 9"

    {3984,10517}

    Returns: -1

  79. {"-1 0 1","-1 0"}

    "-1 0 0 1 2 1 2 0 4 4 1 0 3"

    {5234,23455}

    Returns: -1

  80. {"-1 0 1 2","-1 0 1 0","-1 0 1","-1 0 0"}

    "-1 0 0 2 1 2 4"

    {2588,11692,29846,27326}

    Returns: 71452

  81. {"-1 0 0","-1 0 1 1 0"}

    "-1 0 1 2 0 4 3 6 1 3 5"

    {13315,13306}

    Returns: -1

  82. {"-1 0 1 1 1","-1 0 0 2 2","-1 0 1 1","-1 0","-1 0 1 1 2"}

    "-1 0 1 0"

    {31302,24166,27032,19195,7437}

    Returns: -1

  83. {"-1 0","-1 0 1"}

    "-1 0 1 2 3 1 3 4 2"

    {17930,12595}

    Returns: 50380

  84. {"-1 0 1","-1 0 0","-1 0","-1 0 1 0 2"}

    "-1 0 0 0 2"

    {3885,13122,31377,21317}

    Returns: 17007

  85. {"-1 0 1","-1 0 1 0 1","-1 0 1 2","-1 0"}

    "-1 0 1 0 0 1"

    {9471,12133,28646,8467}

    Returns: 20600

  86. {"-1 0 1"}

    "-1 0 0 1 0 0 0 2 4 2 7 6 9 5"

    {7495}

    Returns: -1

  87. {"-1 0 1 0 1","-1 0 1","-1 0 0","-1 0 0 2"}

    "-1 0 0 1 1"

    {2044,17882,2403,10765}

    Returns: 2044

  88. {"-1 0","-1 0 0","-1 0 0 0","-1 0 0"}

    "-1 0 1"

    {32308,26975,19752,13593}

    Returns: 64616

  89. {"-1 0 1 0","-1 0"}

    "-1 0 1 0 2 1 1 0 1"

    {21815,18431}

    Returns: 80492

  90. {"-1 0","-1 0 1 0"}

    "-1 0 0 1 0 1 4"

    {21007,14530}

    Returns: 77551

  91. {"-1 0 1","-1 0","-1 0 0","-1 0 1","-1 0 0"}

    "-1 0 0"

    {20398,7178,29315,30533,7531}

    Returns: 7531

  92. {"-1 0"}

    "-1 0 1 0 2 2"

    {20955}

    Returns: -1

  93. {"-1 0 1 1 0","-1 0 0 1 2","-1 0 0 2","-1 0 0 0 1","-1 0 1"}

    "-1 0"

    {6870,28598,20477,25200,25966}

    Returns: -1

  94. {"-1 0 0 0","-1 0 0 0 2"}

    "-1 0 0 2 3"

    {8024,28696}

    Returns: -1

  95. {"-1 0 0 0","-1 0"}

    "-1 0 0 0 0 0"

    {15919,9387}

    Returns: -1

  96. {"-1 0","-1 0 0 0 0"}

    "-1 0 1 2 1"

    {19945,29293}

    Returns: -1

  97. {"-1 2 0 0 0"}

    "-1 0 1 1 3 2 5 4"

    {18334}

    Returns: -1

  98. {"-1 0","-1 0 1 1 0","-1 0","-1 0 0 0 1","-1 0 0 1 3"}

    "-1 0"

    {8215,22755,6944,24357,4444}

    Returns: 6944

  99. {"-1 0","-1 0 1","-1 0 0 1 3","-1 0 0 1"}

    "-1 0"

    {12892,20714,20815,23193}

    Returns: 12892

  100. {"-1 0 1 2"}

    "-1 0 1 1 3 4 2 5 5 1"

    {541}

    Returns: -1

  101. {"-1 0 1 0 2","-1 0"}

    "-1 0 1 1"

    {19096,5522}

    Returns: -1

  102. {"-1 0 1","-1 0 0 2 3","-1 0 0"}

    "-1 0"

    {32145,11921,18961}

    Returns: -1

  103. {"-1 0 1 0 1","-1 0 0 2"}

    "-1 0"

    {28923,15592}

    Returns: -1

  104. {"-1 0 0 2"}

    "-1 0 0"

    {12323}

    Returns: -1

  105. {"-1 0","-1 0","-1 0","-1 0","-1 0"}

    "-1 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7"

    {1,2,3,4,5}

    Returns: 22

  106. {"-1 0 0","-1 0 0","-1 0 0","-1 0","-1 0"}

    "-1 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7"

    {1,2,3,4,5}

    Returns: 11

  107. {"-1 0 0 1 1","-1 0 0 1 1","-1 0 0 1 1","-1 0 0 1 1","-1 0 0 1 1"}

    "-1 9 10 10 11 11 12 12 13 13 14 14 15 15 0 0"

    {1,2,3,4,5}

    Returns: -1

  108. {"-1 0"}

    "-1 0"

    {5}

    Returns: 5

  109. {"-1 0"}

    "-1 0 0"

    {5}

    Returns: -1

  110. {"-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.

  111. {"-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.

  112. {"-1 0 1","-1 0 0","-1 0","-1 0 1 0 2"}

    "-1 0 0 0 2"

    {3885,13122,31377,21317}

    Returns: 17007

  113. {"-1 2 0 0 3", "-1 4 0 0 2", "-1 3 4 0 0", "-1 0 0 0", "-1 0" }

    "-1 14 9 8 13 9 14 2 13 13 1 4 10 0 13 10"

    {45802, 20000, 23207, 8447, 65000 }

    Returns: 258207

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: