# Google Kick Start Archive — Round C 2018 problems

## Overview

Thanks to everyone who participated!

Cast

Problem A (Planet Distance): Written and prepared by Anirudh GP.
Problem B (Fairies and Witches): Written by Akashdeep Nain and prepared by Satyaki Upadhyay.
Problem C (Kickstart Alarm): Written by Harshil Shah and prepared by Lalit Kundu.

Solutions and other problem preparation and review by Ian Tullis and Jonathan Irvin Gunawan.

Analysis authors:

Planet Distance: Anirudh GP
Fairies and Witches: Akashdeep Nain
Kickstart Alarm: Harshil Shah

## A. Planet Distance

### Problem

There are N planets in the universe, and Google's Space division has installed N vacuum tubes through which you can travel from one planet to another. The tubes are bidirectional; travelers may use a tube between two planets to travel from either of those planets to the other. Each vacuum tube connects two planets and no two vacuum tubes connect the same pair of planets. These tubes connect the planets such that it is possible to travel from any planet to any other planet using one or more of them. Some of these tubes are connected such that there exists exactly one cycle in the universe. Google has hidden gifts in all the planets that are part of this cycle. Now, Google wants to know how far away each of the planets in the universe is from the gifts.

Your task is to find the minimum distance (in terms of the number of vacuum tubes) between each planet and a planet that is part of the cycle. Planets that are part of the cycle are assumed to be at distance 0.

### Input

The first line contains an integer T, the number of test cases. T test cases follow. The first line of each test case contains an integer N, the number of planets and vacuum tubes. The planets are numbered from 1 to N.
N lines follow, the i-th of these lines contains two integers xi and yi, indicating that the i-th vacuum tube connects planet xi and planet yi.

### Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a list of N space-separated values in which the i-th value represents the minimum distance between the i-th planet and a planet in the cycle.

### Limits

1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ xiN, for all i.
1 ≤ yiN, for all i.
xiyi, for all i.
(xi, yi) ≠ (xj, yj), for all i ≠ j.

The graph in which planets are nodes and tubes are edges is connected and has exactly one cycle.

3 ≤ N ≤ 30.

3 ≤ N ≤ 1000.

### Sample

Sample Input
2
5
1 2
2 3
3 4
2 4
5 3
3
1 2
3 2
1 3

Sample Output
Case #1: 1 0 0 0 1
Case #2: 0 0 0


In Sample Case #1, the cycle consists of planets 2, 3, and 4. Therefore, the distances for planets 2, 3, and 4 are 0. There is a vacuum tube between 1 and 2, and another vacuum tube between 3 and 5. Thus, planets 1 and 5 are at a distance 1 from the cycle.

In Sample Case #2, all the planets are part of the cycle. Hence, their distances are 0.

## B. Fairies and Witches

### Problem

Pari is a powerful fairy who is fighting to protect Fairyland from evil witches. The witches are becoming more powerful every day, so Pari must use magical sticks to cast a protection spell. She can do this by arranging the sticks to form a convex polygon with non-zero area.

However, Pari cannot necessarily use whichever sticks she wants! All of the available sticks in Fairyland are packed together, forming a graph in which the edges are sticks and the nodes are endpoints of one or more sticks. (The sticks never touch each other except at endpoints; they are magical!) Whenever Pari removes a stick to use in her spell, all sticks that were adjacent to that stick (that is, that shared a node with that stick) disappear forever and cannot be used in the future.

Pari is wondering how many distinct subsets of sticks can be removed from the graph and used to form a convex polygon with nonzero area. All of the sticks are considered distinct, even sticks that have the same length. Two subsets of sticks are distinct if and only if there is at least one stick that is present in one subset but not the other. As stated above, a subset is only valid if there is a way to remove all of the sticks in that subset from the graph without any of them disappearing.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing one integer N: the number of nodes in the graph formed by the sticks. Then N lines follow; each contains N integers Li, j. The j-th value on the i-th line represents the length of the stick that has its endpoints at the i-th and j-th nodes, or 0 if there is no such stick.

### Output

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 valid subsets, as described above.

### Limits

1 ≤ T ≤ 100.
Time limit: 40 seconds per test set.
Memory limit: 1 GB.
0 ≤ Li, j ≤ 1000 for all i, j.
Li, i = 0, for all i.
Li, j = Lj, i, for all i, j.

N = 6.

6 ≤ N ≤ 15.

### Sample

Note: there are additional samples that are not run on submissions down below.
Sample Input
4
6
0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
0 0 0 0 1 0
6
0 2 0 0 0 0
2 0 0 0 0 0
0 0 0 3 0 0
0 0 3 0 0 0
0 0 0 0 0 4
0 0 0 0 4 0
6
0 1 0 0 0 0
1 0 0 0 0 0
0 0 0 2 0 0
0 0 2 0 0 0
0 0 0 0 0 4
0 0 0 0 4 0
6
0 1 1 1 1 1
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0

Sample Output
Case #1: 1
Case #2: 1
Case #3: 0
Case #4: 0


In Sample Case #1, the packing graph contains 5 edges of equal length; representing these by the nodes they connect, these are 1-2, 2-3, 3-4, 4-5, and 5-6. To form a closed polygon, we need at least 3 sides, but the only way to remove 3 sticks is to select sticks 1-2, 3-4, and 5-6.

In Sample Case #2, the graph contains 3 sticks, 1-2, 3-4, and 5-6. Note that graph can be disconnected. We can form a triangle with side lengths of 2, 3, and 4.

In Sample Case #3, the graph contains 3 sticks, 1-2, 3-4, and 5-6. But we cannot form a closed polygon using sticks of lengths 1,2 and 4.

In Sample Case #4, we cannot remove more than 1 stick.

### Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.
Sample Input
1
8
0 5 0 0 0 0 0 0
5 0 0 0 0 0 0 0
0 0 0 5 0 0 0 0
0 0 5 0 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 5
0 0 0 0 0 0 5 0

Sample Output
Case #1: 5


In Sample Case #1, all 4 sticks are of the same length. There are 4 ways to form a triangle and one way to form a square.

## C. Kickstart Alarm

### Problem

Shil has a very hard time waking up in the morning each day, so he decides to buy a powerful alarm clock to Kickstart his day. This Alarm is called a Kickstart Alarm. It comes pre-configured with K powerful wakeup calls. Before going to bed, the user programs the clock with a Parameter Array consisting of the values A1, A2, ..., AN. In the morning, the clock will ring K times, with the i-th wakeup call having power POWERi.

To calculate POWERi, the alarm generates all the contiguous subarrays of the Parameter Array and calculates the summation of the i-th exponential-power of all contiguous subarrays. The i-th exponential-power of subarray Aj, Aj+1, ..., Ak is defined as Aj × 1i + Aj+1 × 2i + Aj+2 × 3i + ... + Ak × (k-j+1)i. So POWERi is just the summation of the i-th exponential-power of all the contiguous subarrays of the Parameter Array.

For example, if i = 2, and A = [1, 4, 2], then the i-th exponential-power of A would be calculated as follows:

• 2-nd exponential-power of  = 1 × 12 = 1
• 2-nd exponential-power of  = 4 × 12 = 4
• 2-nd exponential-power of  = 2 × 12 = 2
• 2-nd exponential-power of [1, 4] = 1 × 12 + 4 × 22 = 17
• 2-nd exponential-power of [4, 2] = 4 × 12 + 2 × 22 = 12
• 2-nd exponential-power of [1, 4, 2] = 1 × 12 + 4 × 22 + 2 × 32 = 35
so the total is 71.

Tonight, Shil is using his Kickstart Alarm for the first time. Therefore, he is quite worried about the sound the alarm might make in the morning. It may wake up the neighbors, or, worse yet, it may wake up the whole planet! However, calculating the power of each wakeup call is quite difficult for him. Given K and the Parameter Array A1, A2, ..., AN, can you help him by calculating the summation of power of each wakeup call: POWER1 + POWER2 + ... + POWERK?

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with nine integers N, K, x1, y1, C, D, E1, E2 and F. N is the length of array A, K is the number of wakeup calls. Rest of the values are parameters that you should use to generate the elements of the array A, as follows.

Use the recurrences below to generate xi and yi for i = 2 to N:

• xi = ( C × xi-1 + D × yi-1 + E1 ) modulo F.
• yi = ( D × xi-1 + C × yi-1 + E2 ) modulo F.
We define Ai = ( xi + yi ) modulo F, for all i = 1 to N.

### Output

For each test case, output one line containing Case #x: POWER, where x is the test case number (starting from 1) and POWER is the summation of POWERi, for i = 1 to K. Since POWER could be huge, print it modulo 1000000007 (109 + 7).

### Limits

1 ≤ T ≤ 100.
Time limit: 90 seconds per test set.
Memory limit: 1 GB.
1 ≤ x1 ≤ 105.
1 ≤ y1 ≤ 105
1 ≤ C ≤ 105.
1 ≤ D ≤ 105.
1 ≤ E1 ≤ 105.
1 ≤ E2 ≤ 105.
1 ≤ F ≤ 105.

1 ≤ N ≤ 100.
1 ≤ K ≤ 20.

1 ≤ N ≤ 106.
1 ≤ K ≤ 104.

### Sample

Sample Input
2
2 3 1 2 1 2 1 1 9
10 10 10001 10002 10003 10004 10005 10006 89273

Sample Output
Case #1: 52
Case #2: 739786670


In Sample Case #1, the Parameter Array is [3, 2]. All the contiguous subarrays are , , [3, 2].

For i = 1:

• 1-st Exponential-power of  = 3 × 11 = 3
• 1-st Exponential-power of  = 2 × 11 = 2
• 1-st Exponential-power of [3, 2] = 3 + 2 × 21 = 7
So POWER1 is 12.

For i = 2:

• 2-nd Exponential-power of  = 3 × 12 = 3
• 2-nd Exponential-power of  = 2 × 12 = 2
• 2-nd Exponential-power of [3, 2] = 3 + 2 × 22 = 11
So POWER2 is 16.

For i = 3:

• 3-rd Exponential-power of  = 3 × 13 = 3
• 3-rd Exponential-power of  = 2 × 13 = 2
• 3-rd Exponential-power of [3, 2] = 3 + 2 × 23 = 19
So POWER3 is 24.

## Planet Distance: Analysis

The problem statement explains that we have an undirected connected graph with N nodes and N edges, and exactly one cycle in it. Our task here is to first find the nodes that are part of the cycle, and then find the minimum distance from each of the other nodes to this cycle. From the input, we can form an adjacency list and use this to solve the problem.

### Small dataset

We can perform a DFS from every node, keeping track of visited and parent nodes, to get the nodes that are a part of the cycle. During the DFS for node i, if the first visited node we encounter (that is not the parent), is the node i, then node i is part of the cycle.
Time complexity for this method is O(N2).

Once we have identified all the nodes in the cycle, we can do a BFS from each of these cyclic nodes, keeping track of the number of edges we have travelled so far, to get the minimum distance to all the other nodes. We initially mark all the cyclic nodes as visited, to ensure that we dont traverse the cycle during the BFS.

The overall time complexity is O(N2).

### Large dataset

We can identify which nodes are part of the cycle in many ways. One way is to do a DFS, while keeping track of the parent node. If you encounter a node that is visited, and is not the parent of the previous node, it means that this node is part of the cycle. You can then backtrack using the parent nodes to get all the nodes of the cycle. The time complexity is O(N).

The second way is to recursively remove all vertices of degree 1. This can be done efficiently by storing a map of vertices to their degrees.

Initially, traverse the map and store all the vertices with degree = 1 in a queue. Traverse the queue as long as it is not empty. For each node in the queue, mark it as visited, and iterate through all the nodes that are connected to it (using the adjacency list), and decrement the degree of each of those nodes by one in the map. Add all nodes whose degree becomes equal to one to the queue. At the end of this algorithm, all the nodes that are unvisited are part of the cycle.
The time complexity for this method is O(N).

Once we have identified all the nodes in the cycle, we can do a BFS from each of these cyclic nodes, keeping track of the number of edges we have travelled so far, to get the minimum distance to all the other nodes. We initially mark all the cyclic nodes as visited, to ensure that we dont traverse the cycle during the BFS.

The overall time complexity is O(N).

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Fairies and Witches: Analysis

The problems asks us to choose a subset of edges of a graph such that no two edges share the same vertex and these edges can be used to form a convex polygon with non-zero area.

There are two key observations:

1. The number of ways to choose a subset of edges such that no two edges share same vertex is fairly small. In fact, for a complete graph with 15 nodes, the total number of such pairings is 10349536.
2. A convex polygon with non-zero area can be formed with sides of length l1,l2, ... ,lk if and only if k ≥ 3 and 2 * max(l1,l2, ... ,lk) < sum(l1,l2, ... ,lk).

Let's try to prove the upper bound on the total number of different pairings. Let's consider the case in which the total number of nodes (N) is even and we have exactly N/2 pairings; let us denote the total number of ways to create these N / 2 pairings as f(N).

If we try to generate all possibilities via brute-force code, then one strategy can be to choose the minimum numbered (starting from 1) unused vertex and try to pair it with all the remaining vertices (see code in later section). We can say that at every level when we are forming a new pairing we are choosing one vertex of the pairing in exactly one way (i.e. minimum numbered (starting from 1) unused vertex) and the other vertex of pairing can be any of the remaining vertices. For example, if the unused vertices are (2,5,6,8,9,10), then we start by choosing 2 (the minimum number) as one vertex, and then we try to pair it with all 5 of the remaining vertices. Whenever we choose a particular pair, we mark both vertices as used, and then we recursively pair up the rest. In mathematical terms, we can represent the total number of ways to form such pairings as follows:

f(N) = (N - 1) * (N - 3) .... * 1

But in our problem there can be any number of edges in final polygon, not just N/2. It might be a good idea to try to derive a more general expression before you keep reading!

So we can calculate the total pairings by choosing any set of an even number of vertices and pairing them all up, which gives us the total number as:

g(N) = Σ C(N, i) * f(i), where i is even and C(N, i) is the number of ways of choosing i objects out of N different objects.

### Small dataset

We can observe that for N = 6, we must use all 6 vertices so that we can have 3 edges, since a valid polygon must have at least 3 edges. All possibilities can be generated by enumerating all 6! permutations of arranging 6 numbers, and using the pairs of the first and second, third and fourth, and fifth and sixth numbers to get edges between those node numbers (if they exist).

Our C++ function for checking whether a polygon is valid can be something like this:

bool isGoodPolygon(const vector &edges) {
if(edges.size() < 3) {
return false;
}
int tot = 0;
int mx = 0;
for(int i = 0; i < edges.size(); i++) {
tot += edges[i];
mx = max(mx, edges[i]);
}
}


The overall time complexity is O(N!).

### Large dataset

The Large dataset uses the same overall strategy, but we need an efficient way to code the intended brute-force solution. One way of doing that is the following C++ code, which is using bit masks to store whether a vertex is used or not.

int n;
int L[N][N];
// Whether the i-th bit of mask is on.
int bit(int mask, int i) {
return (mask >> i) & 1;
}

int solve(int mask, vector &edges) {
int res = 0;
if(mask + 1 == (1 << n)) {
res = isGoodPolygon(edges);
return res;
}

for(int i = 0; i < n; i++) if(!bit(mask, i)) {
res += solve(mask | (1 << i), edges);
for(int j = i + 1; j < n; j++) if(!bit(mask, j) && L[i][j]) {
edges.push_back(L[i][j]);
res += solve(mask | (1 << i) | (1 << j), edges);
edges.pop_back();
}
break;
}
return res;
}


The overall time complexity is O(g(N) * N).

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Kickstart Alarm: Analysis

The overall time complexity is $$O(N^3 \times K)$$$. ### Large dataset The above solution will not work for Large dataset. To solve for Large dataset, let's iterate over every position $$x$$$ and calculate the contribution by $$A_x$$$to the result for all subarrays where this element is $$y$$$-th element in the subarray.

• If $$y>x$$$, there is no subarray such that $$A_x$$$ can be $$y$$$-th element. • For $$y \le x$$$, there is exactly one index where the subarray must start (i.e $$y-1$$$places before $$x$$$). Hence, all the subarrays starting at $$(n-(y-1))$$$and ending on or after index $$x$$$ will have $$A_x$$$at position $$y$$$ in the subarray. Therefore, the number of subarrays with element $$A_x$$$at $$y$$$-th position in the subarray will be $$(n-x+1)$$$. Contribution from this element as $$y$$$-th element in one subarray = $$A_x \times y^1 + A_x \times y^2 + \ldots + A_x \times y^K$$$. Let us denote with $$S(x,y)$$$ as the contribution from this element as $$y$$$-th element in all subarrays. Combining above observations, we can show that $$S(x,y) = (n-x+1) \times A_x \times (y^1 + y^2 + \ldots +y^K)$$$.
• $$S(x,y) = 0$$$for $$y > x$$$.
• $$S(x,y) = A_x \times K\times (n-x+1)$$$for $$y=1$$$.
• $$S(x,y) = \frac{(n-x+1) \times A_x \times y\times (y^K-1)}{(y-1)}$$$for $$y \le x$$$ and $$y>1$$$. Contribution by element at position $$x$$$ to the result (let us say $$C(x)$$$) = $$\sum S(x,y)$$$ for $$1 \le y \le n$$$$$= (n-x+1)\times A_x \times (K + \frac{2\times (2^K-1)}{(2-1)} + \frac{3\times (3^K - 1)}{(3-1)} + \ldots \frac{x\times (x^K-1)}{(x-1)})$$$.

So we can find the contribution by element at position $$x$$$in $$O(N\times \log(K))$$$. This gives us a $$O(N^2 \times \log(K))$$$solution to compute contribution of all the elements. Let us define $$G(x) = \frac{C(x)}{(A_x\times (n-x+1))} = K + \frac{2\times (2^K-1)}{(2-1)} + \frac{3\times (3^K - 1)}{(3-1)} + \ldots \frac{x\times (x^K-1)}{(x-1)}$$$.
Now if we look closely at $$G(x)$$$and $$G(x+1)$$$, we can observe that
$$G(x+1) = G(x) + \frac{(x+1)\times ((x+1)^K -1)}{x}$$$. Hence we can compute $$G(x+1)$$$ from $$G(x)$$$in $$O(\log(K))$$$ time. And subsequently $$C(x+1)$$$. Therefore the total time complexity = $$O(N\times \log(K))$$$.

Pseudocode for Large dataset:

  G = K
C = A * K * n
result = C
for(i in 2 to n){
// Using the formula derived above to get G[i] from C[i-1]
G[i+1] = G[i] + i * (i^K - 1) / (i - 1)
C[i] = G[i] * A[i] * (n - i + 1)
result = result + C[i]
result %= 1000000007
}

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Statistics — A. Planet Distance

### Test set 1: 640 correct solutions (94.7% solve rate)

First
Deemo 7:59
JWoong148 8:24
alex20030190 8:31
sdssudhu 8:45
nuip 9:29

### Test set 2: 569 correct solutions (84.2% solve rate)

First
Deemo 7:59
JWoong148 8:24
alex20030190 8:31
sdssudhu 8:45
nuip 9:29

## Statistics — B. Fairies and Witches

### Test set 1: 243 correct solutions (35.9% solve rate)

First
nuip 27:34
alex20030190 30:07
nhho 31:41
Calm orange sheep 32:51
pr3pony 36:20

### Test set 2: 118 correct solutions (17.5% solve rate)

First
nuip 27:34
alex20030190 30:07
nhho 31:41
Calm orange sheep 32:51
pr3pony 36:20

## Statistics — C. Kickstart Alarm

First
rkm0959 14:21
sdssudhu 27:02
rapel 31:57
phirasit 34:12
bohuss 34:26

### Test set 2: 192 correct solutions (28.4% solve rate)

First
rkm0959 14:21
rapel 31:57
nuip 40:53
thundercracker 41:13
teomrn 41:22