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

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

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.

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 **x _{i}** and

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.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1 GB.

1 ≤ **x _{i}** ≤

1 ≤

(

3 ≤ **N** ≤ 30.

3 ≤ **N** ≤ 1000.

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.

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.

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 **L**_{i, 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.

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.

1 ≤ **T** ≤ 100.

Time limit: 40 seconds per test set.

Memory limit: 1 GB.

0 ≤ **L**_{i, j} ≤ 1000 for all i, j.

**L**_{i, i} = 0, for all i.

**L**_{i, j} = **L**_{j, i}, for all i, j.

**N** = 6.

6 ≤ **N** ≤ 15.

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.

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.

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 **A _{1}**,

To calculate POWER_{i}, 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 **A _{j}**,

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] = 1 × 1
^{2}= 1 - 2-nd exponential-power of [4] = 4 × 1
^{2}= 4 - 2-nd exponential-power of [2] = 2 × 1
^{2}= 2 - 2-nd exponential-power of [1, 4] = 1 × 1
^{2}+ 4 × 2^{2}= 17 - 2-nd exponential-power of [4, 2] = 4 × 1
^{2}+ 2 × 2^{2}= 12 - 2-nd exponential-power of [1, 4, 2] = 1 × 1
^{2}+ 4 × 2^{2}+ 2 × 3^{2}= 35

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 **A _{1}**,

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, x _{1}, y_{1}, C, D, E_{1}, E_{2}** and

Use the recurrences below to generate x_{i} and y_{i} for i = 2 to **N**:

- x
_{i}= (**C**× x_{i-1}+**D**× y_{i-1}+**E**) modulo_{1}**F**. - y
_{i}= (**D**× x_{i-1}+**C**× y_{i-1}+**E**) modulo_{2}**F**.

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 POWER_{i}, for i = 1 to **K**.
Since `POWER`

could be huge, print it modulo 1000000007 (10^{9} + 7).

1 ≤ **T** ≤ 100.

Time limit: 90 seconds per test set.

Memory limit: 1 GB.

1 ≤ **x _{1}** ≤ 10

1 ≤

1 ≤

1 ≤

1 ≤

1 ≤

1 ≤

1 ≤ **N** ≤ 100.

1 ≤ **K** ≤ 20.

1 ≤ **N** ≤ 10^{6}.

1 ≤ **K** ≤ 10^{4}.

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], [3, 2].

For i = 1:

- 1-st Exponential-power of [3] = 3 × 1
^{1}= 3 - 1-st Exponential-power of [2] = 2 × 1
^{1}= 2 - 1-st Exponential-power of [3, 2] = 3 + 2 × 2
^{1}= 7

For i = 2:

- 2-nd Exponential-power of [3] = 3 × 1
^{2}= 3 - 2-nd Exponential-power of [2] = 2 × 1
^{2}= 2 - 2-nd Exponential-power of [3, 2] = 3 + 2 × 2
^{2}= 11

For i = 3:

- 3-rd Exponential-power of [3] = 3 × 1
^{3}= 3 - 3-rd Exponential-power of [2] = 2 × 1
^{3}= 2 - 3-rd Exponential-power of [3, 2] = 3 + 2 × 2
^{3}= 19

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.

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(N^{2}).

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^{2}).

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

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

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:

- 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.
- A convex polygon with non-zero area can be formed with sides of length l
_{1},l_{2}, ... ,l_{k}if and only if**k**≥ 3 and 2 * max(l_{1},l_{2}, ... ,l_{k}) < sum(l_{1},l_{2}, ... ,l_{k}).

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.

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]); } return tot - mx > mx; }

The overall time complexity is O(N!).

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

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

The problem asks us to calculate the summation of power of each wakeup call: $$$POWER_1 + POWER_2 + \ldots + POWER_K $$$, where $$$POWER_i$$$ is just the summation of the $$$i$$$-th exponential-power of all the contiguous subarrays of the Parameter Array.

For Small dataset, we can iterate over every subarray of the given array and calculate the summation of $$$POWER_i$$$ for all $$$i \le K$$$. Thus, the simplest brute solution will work for Small dataset.

Pseudocode for Small dataset:

result = 0 for(k in 1 to K) { for(L in 1 to N) { for(R in L to N) { for(j in L to R) { result = result + A[j] * pow(j-L+1,k) result %= 1000000007 } } } }

In the above pseudcode, we can precompute all the $$$pow(a,b)$$$ values for $$$1 \le a \le n$$$ and $$$1\le b \le k$$$.

The overall time complexity is $$$O(N^3 \times K)$$$.

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[1] = K C[1] = A[1] * K * n result = C[1] 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

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