Thank you for participating in Kick Start 2019 Round F.
Cast
Flattening: Written by Yossi Matsumoto and prepared by Zhang Chen.
Teach Me: Written and prepared by Jonathan Irvin Gunawan.
Spectating Villages: Written by Yossi Matsumoto and prepared by Sadia Atique.
Solutions, other problem preparation, reviews and contest monitoring by Ciprian Olariu, Himanshu Jaju, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu, Reyno Tilikaynen, Sadia Atique, Stéphane Henriot, Vivek Dhiman, Yang Xiao, and Zhang Chen.
Analysis authors:
Blotch has built a wall. The wall is made up of N sections, numbered from 1 to N from left to right. Since he had built the wall in a hurry, not all the sections are of the same height. The i-th section of wall is Ai metres tall.
Blotch would like to fix his wall by rebuilding some of the sections. Blotch can set the height of each section he rebuilds to any height he chooses.
Blotch will be happy if the number of indices i (1 ≤ i < N) where Ai ≠ Ai+1 is not more than K.
What is the fewest sections of the wall Blotch needs to rebuild so that he will be happy?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and K, the number of sections of wall and the maximum number of changes in height between adjacent sections, respectively.
The second line contains N integers. The i-th integer is Ai, the height of the i-th section of wall.
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and
y is the fewest sections that Blotch has to rebuild so that he will be happy.
Time limit: TBD seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ai ≤ 1000, for all i.
0 ≤ K ≤ N.
2 ≤ N ≤ 20.
2 ≤ N ≤ 100.
4 8 2 300 100 300 300 200 100 800 500 5 3 100 100 100 100 3 7 3 10 20 40 10 10 30 30 10 2 30 30 60 60 90 90 60 60 30 30
Case #1: 3 Case #2: 0 Case #3: 1 Case #4: 2
In the first sample case, there are N = 8 sections of wall, and Blotch will be happy if there are at most K = 2 changes in height between adjacent sections. Blotch can:
In the second sample case, there are N = 5 sections of wall, and Blotch will be happy if there are at most K = 3 changes in height between adjacent sections. Blotch is already happy with this wall, so he does not need to rebuild any sections.
In the third sample case, there are N = 7 sections of wall, and Blotch will be happy if there are at most K = 3 changes in height between adjacent sections. Blotch can:
In the fourth sample case, there are N = 10 sections of wall, and Blotch will be happy if there are at most K = 2 changes in height between adjacent sections. Blotch can:
Here at Google we love teaching new skills to each other! There are N employees at Google, numbered from 1 to N. There are a total of S different skills, numbered from 1 to S. Each employee knows up to 5 different skills.
The i-th employee can mentor the j-th employee if there is a skill that the i-th employee knows that the j-th employee does not know. How many ordered pairs (i, j) are there where the i-th employee can mentor the j-th employee?
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case gives the two integers N and S, which are the number of employees and the number of skills respectively.
The next N lines describe the skills that each employee knows. The i-th of these lines begins with an integer Ci which is the number of skills the i-th employee knows. Then, Ci integers follow on the same line. The j-th of these integers is Aij indicating that the i-th employee knows the skill Aij.
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is
the number of ordered pairs (i, j) where the i-th employee can mentor the j-th employee.
Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ S ≤ 1000.
1 ≤ Ci ≤ 5 for all i.
1 ≤ Aij ≤ S for all i and j.
Aij ≠ Aik for all j ≠ k.
2 ≤ N ≤ 500.
2 ≤ N ≤ 5 × 104.
2 4 100 4 80 90 100 5 1 90 1 80 3 80 90 100 3 30 4 10 11 12 13 4 10 11 12 13 5 25 26 27 28 29
Case #1: 7 Case #2: 4
In Sample case #1:
In Sample case #2:
The countryside of Kickstartia consists of V villages (labelled from 1 to V), connected by V-1 bidirectional roads (labelled from 1 to V-1). The i-th road connects village Xi to village Yi. Each road connects exactly two villages, and no two roads connect the same two villages. Furthermore, there is exactly one sequence of roads that connects any two villages in Kickstartia.
Some villages are more beautiful than others. The i-th village has a beauty value of Bi. Note that it is possible for a village to have a negative beauty value!
You are going to build lighthouses in some of the villages. A village is illuminated if there is a lighthouse built in it, or there is a lighthouse built in a village that is directly connected to it by a road.
You may build as many or as few (even zero) lighthouses as you like. What is the maximum possible sum of beauty values of illuminated villages you can obtain?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer V, the number of villages. The second line contains V integers. The i-th of these is Bi, the beauty value of the i-th village.
Then, V-1 lines follow. The i-th line gives Xi and Yi, indicating the i-th road connects village Xi to village Yi.
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is
the maximum possible sum of beauty values of illuminated villages you can obtain.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ V ≤ 105.
-105 ≤ Bi ≤ 105 for all i.
1 ≤ Xi, Yi ≤ V for all i.
Xi ≠ Yi for all i.
(Xi, Yi) ≠ (Xj, Yj) for all i ≠ j.
There is exactly one sequence of roads connecting every pair of villages.
1 ≤ V ≤ 15.
1 ≤ V ≤ 105.
3 9 -10 4 -10 8 20 30 -2 -3 7 1 4 2 4 4 3 9 4 9 8 7 5 6 7 7 9 4 -2 20 20 20 1 2 1 3 1 4 5 -5 -10 8 -7 -2 5 4 4 3 3 2 2 1
Case #1: 67 Case #2: 58 Case #3: 0
In Sample Case #1, you can place a lighthouse in villages 2 and 7. This illuminates villages 2, 4, 5, 6, 7 and 9, for a total beauty of 4 + 8 + 20 + 30 + (-2) + 7 = 67. There are other possible ways to place lighthouses to achieve this total beauty.
In Sample Case #2, you can place a lighthouse in villages 1, 2 and 3. This illuminates villages 1, 2, 3 and 4, for a total beauty of (-2) + 20 + 20 + 20 = 58. There are other possible ways to place lighthouses to achieve this total beauty.
In Sample Case #3, the best you can do is to place no lighthouses at all! This illuminates no villages for a total beauty of 0.
We can start with an interesting observation, whenever we rebuild a section of the wall, it is equivalent to removing that section. So we can follow two steps,
There are 2N possible sets of sections, and for each set, checking if the remaining sections will make Blotch happy or not will take O(N) time. So the time complexity of this approach is O(2N × N), which is fast enough for test set 1.
We need to approach the problem a bit differently for test set 2. We can start with observing the amount of walls we need to remove for a particular range of consecutive wall sections[i...j]. The most optimal way of making a set of consecutive wall sections have same height would be to figure out which height appeared the most, and remove all sections with a different height.
So for each consecutive set of walls, we can calculate number of wall removals needed. Let's say, R(i, j) defines number of removals necessary to have all wall sections from i to j have the same height.
We can define a solution based on a function F(x, k), where F(x, k) denotes the number of the walls we need to remove so that the sections from 1 to x in the input has Ai ≠ Ai+1 in at most k places. We can define the recurrence relation as, F(x, k) = min(F(i, k-1) + R(i+1, x)) for all 1 ≤ i ≤ x-1. The minimum number of walls that we need to remove for given N and K is F(N, K). We can compute this function using dynamic programming, which will have O(N2 × K) time complexity, which is fast enough for test 2.
We can have a faster solution, if we decompose the problem from a slightly different angle. We can think about running binary search on number of removals needed to satisfy the condition. In each iteration of binary search, we need to calculate if it is possible to have k or less number of positions where Ai ≠ Ai+1 if we have at most x removal, x being the value of binary search value of that iteration. That can be also calculated with another dynamic programming, leading us to a solution with time complexity of O(N2 × log(N)).
We can solve this test set by considering all ordered pairs of employees. For an ordered pair (i, j), we can check whether there is a skill that the i-th employee knows that the j-th employee does not know with a simple O(Ci × Cj) check using nested loops.
This solution runs in O(52 × N2).
We can solve this test set by defining m(i) as the number of employees who can mentor the i-th employee. If we can compute m(i), the answer to the problem is the sum of all m(i).
To compute m(i), we can count the number of employees who cannot mentor the i-th employee instead. We can observe that the j-th employee cannot mentor the i-th employee if and only if the set of skills known by the j-th employee is a subset of the set of skills known by the i-th employee. Therefore, we would like to count the number of employees whose set of skills is a subset of the set of skills known by the i-th employee.
To count this, we can consider every subset of {Ai1, ..., AiCi}. For a subset B, we can count the number of employees whose set of skills is exactly B. Taking the sum of all subsets gives us the number of employees whose set of skills knowledge is the subset of the set of skills known by the i-th employee. m(i) is simply the number of employees subtracted by this value.
To be able to compute the number of employees whose set of skills is exactly a given set, we can preprocess the set of skills into an occurences hashmap. In other words, we can keep a hashmap that takes a set of skills as its key and returns the number of employees who knows the exact same set of skills as its value.
For each employee i, we need to consider every subset of {Ai1, ..., AiCi}. Since there can be up to 25 subsets, this solutions runs in O(25 × N).
Since there are very few villages for this set, we can calculate the sum of beauty values of illuminated villages for every possible set of villages we choose to build lighthouses in and then take the maximum among these.
For each such set, we have to find which villages will be illuminated. So, for each village, we see if it is in the set or if any of its neighbours are in the set and add its beauty value accordingly.
Since there will be 2V such sets and for each such set we are taking O(V) time to figure out what is the corresponding total beauty value for the set, the overall complexity of this approach is O(V2V)
The the graph formed by taking the villages as nodes and roads as edges is a tree. Let's root this tree at node number 1.
Now, let us define a function maxBeauty(K, P, Q) which represents the maximum beauty value we can obtain from nodes in the subtree of node K (including itself) such that P is a boolean indicating whether the parent node of K has a lighthouse and Q is a boolean indicating whether K itself has a lighthouse. The solution to our problem is simply max(maxBeauty(1, 0, 1), maxBeauty(1, 0, 0)). We consider a few cases to evaluate maxBeauty(K, P, Q).
If Q = 1, then we have a lighthouse placed at K. Which means all of its children will be illuminated irrespective of them having a lighthouse or not. Therefore, in this case,
maxBeauty(K, P, Q) = BK + sum of max(maxBeauty(C, 1, 0), maxBeauty(C, 1, 1)) for all children C of node K.
If Q = 0 and P = 1, then irrespective of whatever we choose for the children of K, they are not going to recieve light from K but K itself is going to be illuminated. Therefore, in this case,
maxBeauty(K, P, Q) = BK + sum of max(maxBeauty(C, 0, 0), maxBeauty(C, 0, 1)) for all children C of node K.
Else, we have Q = 0 and P = 0. This means that the children of K are not going to recieve light from K but the illumination of K depends on whether we place a lighthouse in at least one of the children of K.
This case can be handled using a dynamic programming approach. We define dp[i][j] as maximum sum of beauty values of all illuminated nodes in the first i subtrees of node K such that, if j = 0 then we have not placed a lighthouse in any of the first i children of K and if j = 1 then there is at least one node among the first i children of K with a lighthouse.
Therefore, dp[i][0] = dp[i-1][0] + maxBeauty(Ci, 0, 0) and
dp[i][1] = max(dp[i - 1][1] + max(maxBeauty(Ci, 0, 0), maxBeauty(Ci, 0, 1)), dp[i - 1][0] + maxBeauty(Ci, 0, 1)).
(Here, Ci represents the ith child of K)
Finally, for this case, maxBeauty(K, P, Q) = max(dp[M][1] + BK, dp[M][0]) where M is the total number of children of K.
Since for every node K we can get maxBeauty(K, P, Q) for all values of P and Q in O(M) time, overall complexity of this approach is O(N).