Statistics

Problem Statement for "GoodCompanyDivOne"

Problem Statement

Shiny has a company. There are N employees in her company. The employees are numbered 0 through N-1 in order in which they joined the company.


Employee 0 is the only employee with no boss. Every other employee has precisely one direct boss in the company. You are given a int[] superior with N elements. Element 0 of superior will be -1 to denote that employee 0 has no boss. For each i between 1 and N-1, inclusive, element i of superior will be the number of the boss of employee i.


For each employee, their boss joined the company before them. Formally, for each i between 1 and N-1, inclusive, superior[i] will be between 0 and i-1, inclusive.


At the moment, the employees of Shiny's company cannot do anything useful. Shiny would like to change this. She decided that she will pay for the employees' training. More precisely, each employee will be trained to do two different types of work. (The two types of work may be different for different employees.)


There are K types of work for which training is available. You are given a int[] training with K elements. For each i, training[i] is the cost of training any single employee to do work of type i. If multiple employees are trained to do the same work type, Shiny must pay for each of them separately.


Each employee of the company has their own department. The department of employee x is formed by employee x and all the employees such that x is their boss. Formally, for any y different from x, employee y belongs into the department of employee x if and only if superior[y]=x. Note that if superior[z]=y and superior[y]=x, employee z does not belong into the department of employee x.


Shiny likes diverse departments. A department is diverse if:

  • Each employee in the department is doing something, and
  • no two employees in the department are doing the same type of work.


When Shiny comes to inspect a department, the employees in the department try to choose their work so that the department will be diverse. If they can do that, Shiny says that the department is good.


Shiny considers her company good if all N departments are good. (Note that the departments are not required to be diverse at the same time. A company is good as soon as each of its departments can be diverse at some point in time.)


Shiny now wants to choose, for each employee, the two work types they will be trained to do. Shiny wants to have a good company, and also to spend as little money as possible.


If it is possible for Shiny to have a good company, return the smallest possible total amount of money spent on training the employees. If it is impossible, return -1 instead.

Definition

Class:
GoodCompanyDivOne
Method:
minimumCost
Parameters:
int[], int[]
Returns:
int
Method signature:
int minimumCost(int[] superior, int[] training)
(be sure your method is public)

Notes

  • Each employee must learn to perform exactly two different work types (even though they might never need to do one of those two types of work).

Constraints

  • superior will contain between 1 and 30 elements, inclusive.
  • superior[0] will be -1.
  • For each valid i>0, superior[i] will be between 0 and i-1, inclusive.
  • training will contain between 2 and 30 elements, inclusive.
  • Each element of training will be between 1 and 100, inclusive.

Examples

  1. {-1}

    {1, 2}

    Returns: 3

    There is only one employee (employee 0) and two work types. Employee 0 has to be trained to do both work types. This costs 1+2 = 3. After the training, the company is clearly good.

  2. {-1, 0, 0}

    {1, 2, 3}

    Returns: 10

    One optimal solution: Employee 0 learns work types 0 and 1 which costs 1+2 = 3. Employee 1 learns work types 0 and 1 which costs 1+2 = 3. Employee 2 learns work types 0 and 2 which costs 1+3 = 4. The total cost is 3+3+4 = 10. The company is now good because: The department of employee 0 is formed by employees 0, 1, and 2. This department is good because they can choose work types 0, 1, and 2, respectively. The department of employee 1 is formed only by employee 1 and it is clearly good. The department of employee 2 is formed only by employee 2 and it is clearly good.

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

    {1, 2, 3}

    Returns: -1

    There are only three work types, but there are four employees in employee 0's department. Therefore, this department can never be good.

  4. {-1, 0, 0, 2, 2, 2, 1, 1, 6, 0, 5, 4, 11, 10, 3, 6, 11, 7, 0, 2, 13, 14, 2, 10, 9, 11, 22, 10, 3}

    {4, 2, 6, 6, 8, 3, 3, 1, 1, 5, 8, 6, 8, 2, 4}

    Returns: 71

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

    {10, 20, 20, 32, 30}

    Returns: 160

  6. {-1, 0, 1, 2, 3, 4, 3, 3, 4}

    {21, 2, 11, 16, 12, 20, 1, 7}

    Returns: 41

  7. {-1, 0, 1, 1, 1, 1, 1, 1, 1, 6, 5, 4, 9, 6, 4, 2, 11, 9, 9, 1, 11, 8, 11, 14, 13, 2, 7}

    {9, 45}

    Returns: -1

  8. {-1, 0, 1, 2, 2, 0, 0, 5, 2, 0, 8, 5, 2, 7, 13, 12}

    {3, 5, 2, 3, 3, 6, 4, 4}

    Returns: 82

  9. {-1, 0, 0, 0, 3, 2, 3, 6}

    {17, 15, 3, 16, 26}

    Returns: 147

  10. {-1, 0, 1, 0, 1, 1, 2, 5, 4, 4, 9, 10, 11, 2, 0, 6, 2, 1, 6, 0, 12, 2, 9, 5, 4, 5}

    {36, 19, 48, 53, 47, 39, 5, 68}

    Returns: 828

  11. {-1, 0, 1, 0, 3, 2, 2, 2, 5, 1, 5, 2, 11}

    {35, 44, 86, 68, 81, 27, 72, 15, 29, 41, 18, 18, 79}

    Returns: 449

  12. {-1, 0, 1, 1, 3, 0, 2, 2, 3, 0, 8, 1, 5, 5, 3}

    {13, 18, 8, 1, 11, 18, 20, 1, 17}

    Returns: 71

  13. {-1, 0}

    {9, 9, 12, 9, 10, 7}

    Returns: 32

  14. {-1, 0, 1, 0, 3, 0, 4, 1, 6, 1, 2, 3, 11, 10, 9, 5, 10, 1, 5, 16, 12}

    {70, 74, 8, 9, 86, 32}

    Returns: 575

  15. {-1, 0, 1, 0, 3, 2, 2, 3, 7, 0, 5, 3, 11, 12, 6, 0, 5, 11, 7, 14, 19, 7, 4, 9, 23, 4, 14, 22, 11, 11}

    {19, 16, 35, 10, 2, 37, 23, 9, 8, 38, 21, 14, 5}

    Returns: 250

  16. {-1, 0, 1, 0, 2, 2, 0, 2, 5, 1, 6, 7, 4, 8, 12, 1, 1, 4, 14, 1, 17, 10, 10, 4}

    {48, 6, 65, 45, 15, 60, 64, 24, 49, 23, 20, 56, 44}

    Returns: 578

  17. {-1, 0, 1, 0, 1, 4, 0, 3, 5, 3, 3, 10, 9, 7, 6, 1, 0, 2, 16, 12, 10, 12, 2, 16, 6, 10, 22, 1, 0, 17}

    {6, 12, 1, 8, 11, 17, 11, 8, 15}

    Returns: 234

  18. {-1, 0}

    {52, 61}

    Returns: 226

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

    {5, 17}

    Returns: -1

  20. {-1, 0, 1, 1}

    {10, 18, 9, 1}

    Returns: 41

  21. {-1, 0, 0, 1, 0, 1, 1, 3, 6, 2, 9, 3, 3, 9, 7, 2, 13, 4, 9}

    {5, 5, 20, 19, 17, 20, 14, 8, 1, 9, 9, 19, 17}

    Returns: 123

  22. {-1, 0, 1, 1, 0, 3, 0, 6, 2, 7, 0, 4, 4, 12, 13, 6, 1, 11, 10, 18, 15, 9}

    {9, 29}

    Returns: -1

  23. {-1, 0, 0, 2, 3, 3, 4, 4, 2, 4, 9, 7, 8, 2, 3, 12, 8, 3, 8, 11, 7, 10, 11, 11, 7, 9, 3, 8}

    {1, 20, 2, 16, 7, 16, 24, 4, 3, 4, 21, 21, 7, 26, 7}

    Returns: 105

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

    {18, 1, 7, 1, 29, 15, 11, 13, 12, 29, 7, 29, 17, 15, 10}

    Returns: 16

  25. {-1, 0, 1, 0, 2, 1, 1, 6, 0, 2, 8, 10, 7, 4, 4, 11, 9, 8, 7, 8, 4, 18, 19, 1, 21, 13, 7, 5, 0}

    {4, 8, 4, 9, 10, 13, 9, 1, 10, 12, 7, 8, 5, 11, 2}

    Returns: 108

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

    {4, 25, 20, 1}

    Returns: 57

  27. {-1, 0, 0, 2, 2, 1, 0, 3, 4, 4, 0, 10, 5, 6}

    {13, 23, 18, 2}

    Returns: -1

  28. {-1, 0, 0, 2, 3, 4, 2, 0, 6, 1, 5, 6, 2, 10, 11, 9, 3, 3, 13, 0, 14, 12, 12, 22, 20, 20}

    {2, 2, 1, 2, 2, 1}

    Returns: 60

  29. {-1, 0, 0, 1, 0, 4, 4, 5, 5, 2, 3, 7, 3, 11, 9, 1, 0, 8, 16, 16, 11, 4, 4, 22, 18, 20, 17, 10, 7, 28}

    {8, 40}

    Returns: -1

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

    {63, 55, 53, 19}

    Returns: 290

  31. {-1, 0, 1, 2, 0, 3, 4, 3, 5, 3, 5, 3, 11, 8, 6, 1, 7, 15, 6, 13, 17, 16, 13}

    {38, 39, 17, 21, 4, 27, 47, 40}

    Returns: 530

  32. {-1, 0, 0, 0, 1, 3, 5, 1, 2, 8, 3}

    {19, 81}

    Returns: -1

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

    {6, 26, 21, 3, 20}

    Returns: -1

  34. {-1, 0, 0, 2, 3, 2, 1, 3, 0, 4, 9, 10, 8, 0, 6, 7, 12, 5, 16, 3, 17, 2, 20, 13, 12, 2, 13, 22}

    {23, 19, 56, 48, 64, 21, 59, 7}

    Returns: 773

  35. {-1, 0, 1, 2, 2, 0, 2, 6, 1, 6, 8, 5, 9, 9, 3, 2, 6, 6}

    {70, 15, 16, 24}

    Returns: -1

  36. {-1, 0, 0, 0, 3, 0, 3, 0, 0, 1, 6, 4, 6, 5, 0, 8}

    {36, 16, 9, 43, 21, 48, 31, 30, 11}

    Returns: 436

  37. {-1}

    {29, 15, 16, 25, 22, 30}

    Returns: 31

  38. {-1, 0, 1, 1, 3, 1, 3, 1, 4, 4}

    {25, 59, 44, 14}

    Returns: -1

  39. {-1, 0, 0, 0, 3, 1, 2, 5, 4, 5, 2}

    {52, 4, 16, 33, 22}

    Returns: 249

  40. {-1, 0, 0, 2, 3, 2, 4, 5, 0, 3, 9, 3, 1, 11, 5, 0, 14, 11, 11, 11, 3, 14, 9, 0, 15, 17, 14, 8, 15}

    {19, 3, 18, 9, 26, 15, 1, 3, 15, 12, 28, 26, 8, 24, 12}

    Returns: 157

  41. {-1, 0, 0, 2, 0, 4, 5, 5, 4, 6, 2, 6}

    {23, 20, 40, 6, 34, 8, 25, 43, 16, 36, 23, 28}

    Returns: 196

  42. {-1, 0, 0, 1, 0, 4, 0, 0, 0, 2, 7, 7, 6, 10, 7, 13, 5, 11, 14, 17, 18, 3, 19, 22, 22, 20, 9}

    {39, 23, 31, 48, 72, 26, 28, 5}

    Returns: 819

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

    {29, 50, 16, 36, 21, 28, 35, 25}

    Returns: 233

  44. {-1, 0, 1, 0, 3, 1, 2, 4, 1, 3, 8, 4, 10, 9, 11, 4}

    {23, 21}

    Returns: -1

  45. {-1, 0, 1, 1, 2, 0, 3, 4, 7, 8, 5, 3, 9, 0, 4, 1, 10, 16, 5, 1, 8, 4, 17, 6}

    {3, 43, 28, 9, 34}

    Returns: 448

  46. {-1, 0, 0}

    {2, 21, 3, 38, 25, 21, 16, 11, 15, 35, 17}

    Returns: 23

  47. {-1, 0, 1, 0, 3, 3, 5, 5, 6, 8, 0, 0, 11, 12, 8, 0, 5, 15, 8, 1, 5, 19, 15, 15, 10, 15, 7, 26, 1, 15}

    {17, 10, 6, 2, 6, 6, 5, 10, 1, 1, 5, 19, 7, 3, 14}

    Returns: 89

  48. {-1, 0, 1, 0, 1, 3, 4, 3}

    {1, 1, 1, 1}

    Returns: 16

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

    {29, 31}

    Returns: -1

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

    {22, 4, 10, 44, 20, 9}

    Returns: 130

  51. {-1, 0, 0, 0, 0, 1, 1, 1, 0, 8, 8, 5, 1, 1, 5, 10, 9, 9, 14, 2, 8, 19}

    {15, 16, 12, 11, 6, 7, 19, 13, 19, 15, 5, 15, 6, 4, 20}

    Returns: 213

  52. {-1, 0, 1, 1, 3, 4, 0, 1, 2, 1, 8, 0}

    {8, 13, 12, 2, 10, 15, 11, 14, 20, 21, 19, 11}

    Returns: 130

  53. {-1, 0, 0, 2, 0, 4, 5, 6}

    {8, 36, 52, 77, 78, 25}

    Returns: 302

  54. {-1, 0, 1, 1, 0, 1, 1, 1, 6, 0, 7}

    {13, 31, 5}

    Returns: -1

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

    {3, 4, 3, 5, 2, 5, 3, 2, 2, 1, 2}

    Returns: 15

  56. {-1, 0, 1, 2, 1, 3, 3, 2, 3, 8, 7, 9, 11, 2, 13, 7, 6, 15, 9, 15, 3, 1, 10, 8, 3}

    {9, 13, 46, 36, 72, 29, 74, 64}

    Returns: 744

  57. {-1, 0, 1, 0, 1, 1, 4, 1, 1, 6, 0, 1, 0, 6, 11, 13, 13, 3, 9, 11, 17, 7, 14, 0, 11, 6, 18, 6, 23, 15}

    {13, 37, 1, 3, 18, 4, 4, 13, 32, 11, 28, 7, 38, 35, 10}

    Returns: 154

  58. {-1, 0, 0, 2, 0, 2, 3, 0, 7, 6, 0, 6, 10, 4}

    {38, 11, 62, 40, 12, 27}

    Returns: 456

  59. {-1, 0}

    {14, 28, 12, 8, 6, 34, 4, 10}

    Returns: 20

  60. {-1, 0, 1, 1, 0, 0, 5, 4, 3, 0, 4, 8, 6, 3, 4, 2, 10, 9, 4, 14, 7, 17, 4}

    {36, 10, 39, 7, 10, 16, 25}

    Returns: 444

  61. {-1}

    {1, 6}

    Returns: 7

  62. {-1, 0}

    {13, 21, 34, 1, 39, 43, 35, 44}

    Returns: 28

  63. {-1, 0, 0, 2, 3, 2, 4, 4, 2, 5, 4, 10, 8, 0, 11, 14, 3, 10, 6, 2, 2, 12, 17, 5, 19, 0}

    {10, 11, 13, 21, 26}

    Returns: -1

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

    {38, 10, 37, 15, 59, 58, 65, 61, 58, 30, 6}

    Returns: 69

  65. {-1, 0, 0, 2, 1, 4, 3, 1, 4, 7, 1, 2, 6, 11}

    {3, 2, 3, 6, 7, 10}

    Returns: 73

  66. {-1, 0, 0, 2, 2, 1, 1, 2, 0, 2, 4, 1, 9, 3, 11, 2, 1, 6, 1, 10, 2, 7}

    {3, 15, 6, 15}

    Returns: -1

  67. {-1, 0, 1, 1, 3, 1, 5, 2, 2, 4, 6, 0, 8, 9, 10}

    {42, 11, 25, 43, 34}

    Returns: 566

  68. {-1, 0, 0, 0, 2, 2, 2, 2, 2, 7, 6, 3, 7, 7, 3, 10, 10, 2, 12, 5, 14, 16, 5, 9, 17, 9}

    {11, 10, 17, 4, 4, 7, 17, 5, 4, 2}

    Returns: 166

  69. {-1, 0, 1, 0, 1, 4, 1, 3, 7, 7, 5, 0, 2, 11, 9, 6, 8, 0, 17, 8, 15, 3, 17, 18, 10, 1, 19, 4}

    {10, 46, 15, 52, 51, 28, 17}

    Returns: 763

  70. {-1, 0, 0, 0, 2, 4, 4, 5, 2, 2, 3, 5, 11, 7, 0, 2, 12, 9}

    {6, 11, 8, 1, 25, 23, 8, 9, 14}

    Returns: 139

  71. {-1, 0, 1, 1, 0, 4, 5, 4, 7, 4, 7, 2, 11, 12, 10, 11, 3, 5}

    {6, 7, 20, 9, 2, 10, 11}

    Returns: 150

  72. {-1}

    {6, 4}

    Returns: 10

  73. {-1, 0, 1}

    {3, 3, 3, 1, 3, 1, 2, 1, 1, 3, 2}

    Returns: 6

  74. {-1, 0, 1}

    {42, 58, 12, 60, 11, 71, 57, 74, 18, 62, 51}

    Returns: 69

  75. {-1, 0, 0, 1, 1, 3, 3, 5, 1, 3, 0, 5, 9, 6, 2, 6, 2, 9}

    {39, 30, 4, 4, 16, 7, 16, 21, 4, 23, 10, 20, 12, 25, 40}

    Returns: 150

  76. {-1, 0, 1, 2, 1, 3, 1, 4, 5, 3, 6, 9, 8}

    {81, 78, 48, 51, 3, 68, 49, 85, 32, 69, 25}

    Returns: 401

  77. {-1, 0, 0, 1, 0, 1, 2, 1, 7, 5, 4, 8, 9, 0, 13, 11, 2, 11, 15, 17}

    {6, 29, 32, 32, 37, 24, 12, 49, 35}

    Returns: 433

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

    {6, 26, 16, 32, 39}

    Returns: 120

  79. {-1, 0, 0, 2, 0, 0, 3, 1, 6}

    {1, 5, 5, 1, 5, 5, 10, 5, 1, 4, 7}

    Returns: 25

  80. {-1, 0, 1, 2, 3, 2, 5}

    {56, 20, 47, 44, 40, 22, 25, 45, 51}

    Returns: 297

  81. {-1, 0, 0, 2, 3, 3, 5, 5, 0, 6, 7, 4, 6, 4, 5, 6, 3, 4, 12, 3, 2, 12, 4, 10, 6}

    {34, 23, 17, 11, 16, 37, 8, 44, 45}

    Returns: 543

  82. {-1, 0, 1, 2, 3, 2, 3, 0, 6, 7, 5, 8, 4, 2, 6, 11}

    {15, 18, 22, 9}

    Returns: 400

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

    {2, 5, 3, 2}

    Returns: 24

  84. {-1, 0, 1, 2, 3, 4, 4, 3, 7, 0, 2, 9, 5, 2, 1, 9, 13, 15, 2, 15, 5, 6, 6}

    {2, 32, 24, 46, 4, 50, 70, 53}

    Returns: 308

  85. {-1, 0, 0, 2, 0, 0, 4, 1, 5, 2, 9, 0, 6, 9, 5, 11, 14, 4, 1, 17, 13, 4, 7, 5, 8, 15, 18}

    {21, 62, 77, 85}

    Returns: -1

  86. {-1, 0, 0, 2, 3, 2, 3, 4, 5, 4, 6, 2, 5, 10, 6, 6, 12, 0, 8, 5, 0, 10, 18, 8, 18, 9, 1, 11, 6}

    {11, 22}

    Returns: -1

  87. {-1, 0, 1, 2, 1, 2, 0, 2, 7, 0, 8, 7, 10, 11, 0, 5, 14}

    {16, 26, 55, 58, 32, 17, 20, 20}

    Returns: 582

  88. {-1, 0, 0, 1, 3, 1, 2, 5, 7, 2, 5, 1, 4, 2, 9, 14, 5, 7, 3, 18, 17, 4, 15, 22, 15, 13, 16, 8, 16, 4}

    {8, 1, 8, 2, 4, 8, 1, 1, 7, 8, 8, 8}

    Returns: 63

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

    {27, 38, 37, 31, 6, 39, 36, 4}

    Returns: 81

  90. {-1, 0, 0, 0, 2, 3, 1, 1, 3, 2, 5, 5, 11, 1, 9, 4, 1, 10, 2, 4, 0, 14, 7}

    {17, 11, 1, 4, 17, 23, 2, 17, 7}

    Returns: 96

  91. {-1, 0, 1, 2, 0, 1, 4, 6, 3, 4, 8, 3, 8, 3}

    {21, 29, 15, 18, 12, 2, 6, 17, 2}

    Returns: 78

  92. {-1, 0, 1, 2, 3, 1, 5, 4, 6, 3, 8, 0, 7, 4, 9, 11, 13, 0, 4, 7, 14, 6, 10, 12}

    {15, 16}

    Returns: -1

  93. {-1, 0, 1, 1, 2, 1, 1, 6, 6, 6, 5, 3, 3, 1, 9, 4}

    {1, 1, 3, 2, 3, 2, 2, 3, 3}

    Returns: 38

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

    {45, 13, 35, 44}

    Returns: -1

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

    {3, 35, 25}

    Returns: -1

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

    {27, 2, 22, 5}

    Returns: -1

  97. {-1, 0}

    {53, 2, 26}

    Returns: 56

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

    {3, 1, 3, 7, 3, 3, 2, 5, 1, 10, 6, 4, 1}

    Returns: 30

  99. {-1, 0}

    {34, 11, 49, 51, 4, 32, 47, 33}

    Returns: 30

  100. {-1, 0, 0, 0, 0}

    {48, 34, 68, 24, 80, 54, 45, 18}

    Returns: 265

  101. {-1, 0}

    {47, 91, 94, 13}

    Returns: 120

  102. {-1, 0, 0}

    {13, 30, 52}

    Returns: 151

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

    {6, 2, 5, 6}

    Returns: -1

  104. {-1, 0, 1, 2, 3, 4, 4, 6, 4, 4, 8, 7, 1, 11, 9, 8, 5, 12, 3, 16, 8, 18, 9, 13, 23}

    {3, 13, 2, 5, 5, 7, 12, 15, 4, 10, 4, 1, 8, 12, 10, 1, 6, 10, 4, 11, 7, 14, 2, 10, 6}

    Returns: 56

  105. {-1, 0, 1, 1, 2, 3, 3, 4, 6, 3, 1, 2, 9, 12, 13, 12, 0, 13}

    {3, 32, 44, 21, 13, 15, 11, 8, 37, 13, 8, 37, 30, 7, 44, 6, 32, 45, 43, 18}

    Returns: 168

  106. {-1, 0, 1, 1, 2, 3, 5, 0, 2, 1, 4, 4, 1, 9, 8, 13, 6}

    {2, 20, 7, 2, 1, 5, 15, 8, 3, 4, 2, 10, 3, 3, 1, 14, 20, 16, 4, 17, 13, 13, 15, 6, 20, 12, 12, 12, 6}

    Returns: 38

  107. {-1, 0, 0, 2, 0, 1, 5, 3, 7, 0, 4, 10, 4, 7, 9}

    {81, 3, 78, 15, 46, 68, 15, 36, 1, 28, 9, 1, 67, 64, 27, 86, 33, 12, 27, 36, 12, 22}

    Returns: 53

  108. {-1, 0, 0, 2, 0, 1, 0, 0, 1, 0, 5, 7, 5, 6, 7, 9, 10, 0, 13, 16, 17, 1, 6, 14, 11, 21, 1, 26, 26}

    {27, 15, 11, 18, 9, 4, 27, 13, 16, 4, 12, 2, 8, 5, 11, 28, 25, 29, 12, 28, 14, 19, 20, 16, 22, 30, 13}

    Returns: 199

  109. {-1, 0, 0, 2, 3, 3, 2, 2, 5, 5, 5, 2, 6, 1, 3, 2, 5, 15, 2, 13, 13, 0, 19, 14, 22, 6, 16, 2, 3, 15}

    {45, 11, 9, 49, 26, 45, 64, 40, 44, 11, 45, 36, 65, 43, 33, 12}

    Returns: 708

  110. {-1, 0, 1, 1, 2, 4, 2, 0, 7, 2, 0, 1, 4, 12, 6, 6, 12, 15}

    {40, 38, 60, 99, 50, 25, 37, 24, 92, 55, 10, 22, 83, 68, 77, 46}

    Returns: 588

  111. {-1, 0, 1, 0, 1, 4, 2, 2, 3, 4, 2, 3, 3, 7, 4, 12, 5, 6, 5, 14, 2, 13, 6, 4, 13, 2, 1, 4}

    {31, 29, 37, 11, 3, 19, 27, 10, 7, 32, 35, 20, 4, 13, 12, 12, 2, 23, 10, 18, 36, 7, 12, 13}

    Returns: 178

  112. {-1, 0, 0, 0, 2, 4, 3, 1, 2, 1, 0, 8, 1, 7, 1, 6, 10}

    {1, 2, 2, 8, 8, 6, 13, 15, 3, 1, 6, 3, 10, 13, 14, 12, 7, 4}

    Returns: 40

  113. {-1, 0, 0, 2, 0, 0, 1, 3, 4, 5, 9, 9, 4, 7, 8, 3, 10}

    {11, 21, 44, 21, 21, 3, 56, 66, 12, 37, 65, 60, 65, 39, 3, 16, 10, 25, 65, 31, 15, 13, 47, 49, 29, 24, 6}

    Returns: 126

  114. {-1, 0, 1, 0, 3, 4, 0, 0, 3, 6, 2, 8, 5, 12, 13}

    {6, 4, 5, 6, 2, 5, 4, 3, 1, 3, 2, 6, 4, 1, 1, 2, 3, 6, 2, 2, 1, 4, 6, 4, 1, 2, 5, 5}

    Returns: 30

  115. {-1, 0, 1, 2, 3, 1, 3, 4, 2, 4, 5, 6, 8, 12, 0, 2, 1, 13, 17, 15, 9, 4, 11, 22, 8, 17, 2}

    {21, 7, 26, 34, 12, 44, 7, 51, 59, 48, 25, 60, 18, 22, 10, 24, 1, 17, 43, 3, 13, 44, 54}

    Returns: 139

  116. {-1, 0, 1, 2, 0, 2, 1, 1, 2, 7, 3, 1, 3, 2, 7, 8, 3, 3, 4, 0, 7}

    {32, 19, 33, 22, 17, 26, 2, 11, 18, 4, 18, 35, 16, 24, 17, 14, 19, 4, 5, 8, 39, 9, 38, 33, 15, 29, 30, 28, 34, 10}

    Returns: 137

  117. {-1, 0, 1, 1, 1, 4, 3, 1, 2, 6, 8, 0, 6, 5, 6, 13, 2, 11, 5, 0, 7, 0, 14, 11, 22}

    {3, 1, 3, 2, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 3, 1, 1, 1, 3, 1, 1}

    Returns: 50

  118. {-1, 0, 1, 0, 3, 0, 4, 6, 2, 7, 8, 1, 3, 11, 9, 10, 9}

    {4, 5, 6, 3, 1, 5, 6, 5, 6, 1, 4, 6, 1, 4, 3, 5, 7, 6, 5, 4, 6, 5, 6, 5, 4, 2, 7, 1}

    Returns: 34

  119. {-1, 0, 1, 1, 1, 4, 0, 3, 4, 1, 4, 1, 7, 5, 9, 7, 10, 12, 1}

    {3, 2, 1, 3, 7, 6, 5, 1, 4, 2, 5, 3, 2, 6, 2, 1, 1, 5, 6, 3, 5, 1, 4, 2}

    Returns: 40

  120. {-1, 0, 1, 2, 1, 3, 5, 2, 6, 1, 1, 8, 7, 5, 3, 12, 3, 14, 10, 13, 19, 8, 0, 15}

    {39, 10, 44, 23, 36, 22, 40, 39, 19, 7, 7, 2, 1, 2, 23}

    Returns: 87

  121. {-1, 0, 1, 1, 2, 4, 2, 5, 3, 0, 0, 5, 7, 8, 3, 14, 3, 9}

    {1, 5, 3, 6, 9, 3, 4, 9, 9, 5, 2, 6, 1, 3, 1, 5, 2, 8, 3, 7, 3, 4, 8, 6, 5, 9}

    Returns: 38

  122. {-1, 0, 0, 0, 3, 2, 0, 1, 3, 3, 5, 10, 2, 3, 3, 0, 13, 0, 13, 6, 7, 14, 21, 10, 0, 11, 1, 18, 23}

    {16, 1, 8, 5, 2, 5, 1, 9, 15, 5, 15, 11, 13, 6, 8, 6, 1, 7, 11, 3, 4}

    Returns: 75

  123. {-1, 0, 1, 0, 2, 0, 0, 1, 6, 3, 8, 5, 2, 7, 13, 1, 3, 4, 0, 12, 12}

    {11, 31, 51, 70, 63, 35, 1, 26, 33, 19, 38, 7, 54, 41, 39, 44, 40, 5, 20, 39, 31, 22, 50, 60, 21, 12, 1, 57, 62}

    Returns: 81

  124. {-1, 0, 1, 2, 2, 4, 5, 3, 4, 3, 9, 10, 3, 7, 5, 4, 10, 11, 5, 5, 7, 17}

    {3, 17, 32, 28, 23, 20, 2, 23, 1, 6, 26, 7, 34, 8, 9, 9, 6, 26}

    Returns: 82

  125. {-1, 0, 0, 2, 1, 4, 3, 3, 4, 2, 3, 9, 1, 7, 7, 14, 9, 10, 12, 16, 13, 19, 5}

    {9, 43, 14, 63, 10, 15, 13, 65, 16, 12, 21, 59, 62, 13, 63, 22, 40, 16, 8, 22, 31, 26, 45, 62}

    Returns: 398

  126. {-1, 0, 1, 2, 2, 1, 1, 6, 5, 2, 5, 2, 9, 10, 8, 11, 10, 13, 5}

    {38, 2, 16, 4, 22, 4, 1, 7, 6, 43, 13, 28, 51, 21, 2, 18, 51, 23, 23, 42, 25, 24, 16, 44, 10, 6}

    Returns: 63

  127. {-1, 0, 1, 0, 2, 4, 5, 3, 6, 2, 7, 4, 7, 0, 4, 3, 12, 1, 1, 2, 5, 8, 7, 15, 11, 0, 24, 16, 9}

    {24, 78, 2, 46, 6, 75, 9, 6, 57, 59, 8, 21, 61, 79, 18, 70}

    Returns: 241

  128. {-1, 0, 0, 1, 2, 2, 3, 4, 6, 8, 1, 8, 6, 0, 5}

    {15, 68, 50, 21, 15, 46, 39, 51, 69, 42, 72, 22, 14, 28, 52, 7, 34, 52, 67, 34, 53, 66, 68, 12, 2, 31, 5}

    Returns: 116

  129. {-1, 0, 1, 0, 0, 3, 0, 1, 0, 5, 8, 7, 0, 5, 5, 5, 7, 4, 2, 3, 18, 4, 6}

    {22, 23, 21, 3, 24, 3, 10, 27, 16, 11, 14, 19, 23, 23, 28, 28, 29, 17}

    Returns: 224

  130. {-1, 0, 0, 0, 0, 3, 1, 0, 0, 2, 7, 7, 3, 5, 7, 7, 4, 10, 5, 5, 18, 1, 13}

    {5, 9, 1, 4, 3, 6, 10, 10, 7, 10, 7, 6, 2, 5, 1, 8, 7, 6, 9, 10, 7, 7, 5, 9, 3, 6}

    Returns: 64

  131. {-1, 0, 0, 2, 0, 0, 0, 1, 5, 8, 6, 2, 8, 11, 7, 0, 9, 6, 14, 9, 0, 19, 16}

    {9, 27, 15, 8, 30, 18, 14, 9, 15, 30, 8, 20, 23, 27, 29, 26, 29, 7, 31, 7, 24, 30, 22, 16}

    Returns: 344

  132. {-1, 0, 0, 2, 3, 4, 4, 2, 4, 6, 0, 1, 9, 11, 2, 3, 9, 4, 2}

    {3, 14, 7, 19, 2, 8, 18, 7, 16, 2, 4, 16, 9, 16, 3, 13, 2, 21, 14, 19, 17, 17, 5, 9, 13, 2, 14}

    Returns: 78

  133. {-1, 0, 0, 1, 2, 4, 1, 6, 5, 6, 5, 3, 11, 0, 9, 6, 2, 4, 1, 14, 0, 2}

    {36, 86, 84, 82, 70, 22, 32, 80, 24, 59, 77, 33, 2, 70, 25, 58, 6, 23, 25, 9, 59}

    Returns: 237

  134. {-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {19,10,16,19,81,33,90,84,72,77,44,37,94,68,66,47,59,17,23,54,56,52,8,97,21,51,86,95,93,36}

    Returns: 1847

  135. {-1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,0,1,1,1,0,1,0,1,1,1,0}

    {81,29,27,7,37,85,2,87,81,52,42,63,12,62,80,34,67,47,89,20,27,49,1,46,92,66,62,33,9,15}

    Returns: 737

  136. {-1, 0, 0, 2, 2, 2, 1, 1, 6, 0, 5, 4, 11, 10, 3, 6, 11, 7, 0, 2, 13, 14, 2, 10, 9, 11, 22, 10, 3 }

    {4, 2, 6, 6, 8, 3, 3, 1, 1, 5, 8, 6, 8, 2, 4 }

    Returns: 71

  137. {-1, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 6, 6, 6, 7, 7, 7, 8, 8, 8 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }

    Returns: 72

  138. {-1, 0, 0, 0, 0, 0, 0 }

    {1, 2 }

    Returns: -1

  139. {-1, 0, 0, 0 }

    {1, 2, 3, 4 }

    Returns: 15

  140. {-1, 0, 0, 1, 1, 2, 2 }

    {1, 2, 3 }

    Returns: 23

  141. {-1, 0, 1, 1, 0, 4, 4, 5, 6, 7, 4, 7, 5, 11, 13, 1, 11, 3, 8, 1, 16, 9, 18, 15, 9, 17, 6, 6, 12, 13 }

    {3, 5, 7, 11, 13, 17, 19, 23 }

    Returns: 270

  142. {-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    {2, 8, 9, 10 }

    Returns: 120

  143. {-1, 0, 0, 1, 1, 2, 2, 6, 1, 5, 3, 5, 1, 6, 12, 6, 5, 5, 12, 12, 15, 10, 6, 5, 2, 14, 15, 7, 11, 7 }

    {72, 34, 38, 61, 84, 10, 16, 37, 58, 46, 84, 70, 70, 41, 36, 46, 50, 66, 63, 82, 10, 90, 15, 7, 26, 85, 53, 28, 65, 90 }

    Returns: 559

  144. {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 13, 15, 14, 20, 20, 20, 20 }

    {1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6 }

    Returns: 80

  145. {-1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4 }

    {50, 40, 30, 20, 10 }

    Returns: 640

  146. {-1, 0, 0, 1, 1, 2, 2 }

    {1, 5, 20 }

    Returns: 72

  147. {-1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 }

    {1, 3, 4, 5 }

    Returns: 112

  148. {-1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6 }

    {10, 20, 30, 40, 50, 60, 70, 80 }

    Returns: 640

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

    {1, 1, 100 }

    Returns: 216

  150. {-1, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12, 12 }

    {1, 3, 6, 10, 15, 21, 28 }

    Returns: 181

  151. {-1, 0, 0, 1, 1, 3, 4, 4, 7 }

    {1, 2, 4, 8, 16 }

    Returns: 31

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: