Round 1C was the last chance to get to round 2, with the top 1000 advancing.

Problem A was an easy graph theory problem, and it was first finished in under 8 minutes! Any algorithm for counting paths between nodes sufficed to solve the problem.

Problem C was a dynamic programming problem, similar to the standard Longest Common Subsequence problem. The input strings each consisted of a small number of runs of equal letters, but each run could be very large. Since the strings can be so large, standard algorithms for solving the LCS problem had to be modified to take advantage of the special form of the input, making this problem much more challenging.

Problem B was a subtle physics problem that turned out to be the hardest in the set. It appears to require dynamic programming with a state that includes the position, velocity, and time of the car. But some careful reasoning shows that there's always an optimal strategy that consists of only two phases -- staying still for a period of time, then using the maximum acceleration, with no braking, until reaching the destination. This simplifies the mathematics considerably, as we only need to figure out how long to wait.

mystic won the round by a comfortable margin, finishing the whole set in under an hour. Congratulations to the 1000 advancers!

Cast

Problem A. *Diamond Inheritance* Written and prepared by Khaled Hafez.

Problem B. *Out of Gas* Written by Bartholomew Furrow. Prepared by Bartholomew Furrow and Yiu Yu Ho.

Problem C. *Box Factory* Written by David Arthur. Prepared by David Arthur and Luka Kalinovcic.

Contest analysis presented by John Dethridge, Onufry Wojtaszczyk, and John Dethridge again.

Solutions and other problem preparation by Igor Naverniouk, Adam Polak, Luka Kalinovcic, John Dethridge, Alexander Georgiev, Sean Henderson, Ahmed Aly, Muntasir Khan and Nikolay Kurtov.

You are asked to help diagnose class diagrams to identify instances of diamond inheritance. The following example class diagram illustrates the property of diamond inheritance. There are four classes: A, B, C and D. An arrow pointing from X to Y indicates that class X inherits from class Y.

In this class diagram, D inherits from both B and C, B inherits from A, and C also inherits from A. An inheritance path from X to Y is defined as a sequence of classes X, C_{1}, C_{2}, C_{3}, ..., C_{n}, Y where X inherits from C_{1}, C_{i} inherits from C_{i + 1} for 1 ≤ i ≤ n - 1, and C_{n} inherits from Y. There are two inheritance paths from D to A in the example above. The first path is D, B, A and the second path is D, C, A.

A class diagram is said to contain a diamond inheritance if there exists a pair of classes X and Y such that there are at least two different inheritance paths from X to Y. The above class diagram is a classic example of diamond inheritance. Your task is to determine whether or not a given class diagram contains a diamond inheritance.

The first line of the input gives the number of test cases, **T**. **T** test cases follow, each specifies a class diagram. The first line of each test case gives the number of classes in this diagram, **N**. The classes are numbered from 1 to **N**. **N** lines follow. The i^{th} line starts with a non-negative integer **M _{i}** indicating the number of classes that class

- If there is an inheritance path from X to Y then there is no inheritance path from Y to X.
- A class will never inherit from itself.

For each diagram, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is "Yes" if the class diagram contains a diamond inheritance, "No" otherwise.

Memory limit: 1GB.

Time limit: 40 seconds per test set.

1 ≤ **T** ≤ 50.

0 ≤ **M _{i}** ≤ 10.

1 ≤ **N** ≤ 50.

1 ≤ **N** ≤ 1,000.

Sample Input

3 3 1 2 1 3 0 5 2 2 3 1 4 1 5 1 5 0 3 2 2 3 1 3 0

Sample Output

Case #1: No Case #2: Yes Case #3: Yes

Your car is out of gas, and you want to get home as quickly as possible! Fortunately, your home is at the bottom of a hill and you (in your car) are at the top of it. Unfortunately, there is a car in front of you, and you can't move past it. Fortunately, your brakes are working and they are *very* powerful.

You *start* at the top of the hill with speed 0 m/s at time 0 seconds. Gravity is pulling your car down the hill with a constant acceleration. At any time, you can use your brakes to reduce your speed, or temporarily reduce your acceleration, by any amount.

How quickly can you reach your home if you use your brakes in the best possible way?

The first line of the input gives the number of test cases, **T**. **T** test cases follow. The first line of each test case contains three space-separated numbers: a real-valued number **D**, the distance in meters to your home down the hill; and two integers, **N** and **A**. The distance **D** will be given in *exactly 6 decimal places*.

**N** lines follow, each of which contains two space-separated, real-valued numbers: a time **t**_{i} in seconds, and a position **x**_{i} in meters. The **t**_{i} and **x**_{i} values will be given in *exactly 6 decimal places*.

One line follows, with **A** space-separated, real-valued numbers **a**_{i}, which are accelerations in `m/s`

. The accelerations will be given in ^{2}*exactly 2 decimal places*.

The other car's position is specified by the (**t**_{i}, **x**_{i}) pairs. The car's position at time **t**_{i} seconds is **x**_{i} meters measured from the top of the hill (i.e. your initial position). The car travels at constant speed between time **t**_{i} and **t**_{i+1}. The positions and times will both be given in increasing order, with **t**_{0}=0.

For example, if t_{5}=10, x_{5}=20, t_{6}=20, x_{6}=40, then 10 seconds after the *start*, the other car is 20 meters down the hill; 15 seconds after the *start*, the other car is 30 meters down the hill; and 20 seconds after the *start*, the other car is 40 meters down the hill.

For each test case, output one line containing "Case #c:", where c is the case number (starting from 1). Then output **A** lines, the i^{th} of which contains the minimum number of seconds it takes you to reach your home if your acceleration down the hill due to gravity is **a**_{i}, and you use your brakes in the best possible way. Answers within an absolute or relative error of 10^{-6} of the correct answer will be accepted. There should be no blank lines in the output.

**Position and Acceleration:** An object with a constant acceleration `a m/s`

and starting speed of ^{2}`v`

will move a distance of v_{0} m/s_{0}*t + 0.5*a*t^{2} after `t`

seconds.

`2 m/s`^{2}

with an initial speed of `0 m/s`

, and the other car is stopped at x=1, it will take exactly 1 second to reach the other car.
**The other car:** You may never pass the other car, which means that at no time shall your distance down the hill be greater than that of the other car. It may be equal. The cars should be considered as point masses.

**Output values:** You can print as many decimal places as you like in the output. We will read and compare your answers with ours, and at that time we will be using 10^{-6} as a threshold for inaccuracy. So 25, 25.0 and 25.000000 are the same from our perspective. Trailing zeros after the decimal point does not matter.

Memory limit: 1GB.

1 ≤ **T** ≤ 20.

1.0 ≤ **D** ≤ 10^{4}.

1.0 ≤ **a**_{i} ≤ 9.81.

0.0 ≤ **t**_{i} ≤ 10^{5}.

0.0 ≤ **x**_{i} ≤ 10^{5}.

**t**_{i} < **t**_{i+1}.

**x**_{i} < **x**_{i+1}.

**t**_{0} = 0

**x**_{N-1} ≥ **D**.

Time limit: 60 seconds.

1 ≤ **N** ≤ 2.

1 ≤ **A** ≤ 10.

Time limit: 120 seconds.

1 ≤ **N** ≤ 2000.

1 ≤ **A** ≤ 250.

Sample Input

3 1000.000000 2 3 0.000000 20.500000 25.000000 1000.000000 1.00 5.00 9.81 50.000000 2 2 0.000000 0.000000 100000.000000 100.000000 1.00 1.01 10000.000000 3 1 0.000000 0.000000 10000.000000 0.100000 10000.100000 100000.000000 1.00

Sample Output

Case #1: 44.7213595 25.000000 25.0 Case #2: 50000.0 50000.0 Case #3: 10140.974143

You own a factory with two assembly lines. The first assembly line makes boxes, and the second assembly line makes toys to put in those boxes. Each type of box goes with one type of toy and vice-versa.

At the beginning, you pick up a box from the first assembly line and a toy from the second assembly line. You then have a few options.

- You can always throw out the box and pick up the next one.
- You can always throw out the toy and pick up the next one.
- If the box and toy are the same type, you can put the toy in the box, and send it out to customers.

Warning: The two assembly lines make a *lot* of boxes and toys. However, they tend to make one kind of thing for a long period of time before switching.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.

Each test case begins with a line contains two integers **N** and **M**. It is followed by a line containing 2 * **N** integers **a _{1}**,

This means that the first assembly line will make **a _{1}** boxes of type

A toy can be matched with a box if and only if they have the same type number.

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the largest number of boxed toys that you can send out to customers.

Memory limit: 1GB.

Time limit: 30 seconds per test set.

1 ≤ **T** ≤ 100.

1 ≤ **a _{i}**,

1 ≤

1 ≤ **N** ≤ 3.

1 ≤ **M** ≤ 100.

1 ≤ **N, M** ≤ 100.

Sample Input

4 3 3 10 1 20 2 25 3 10 2 30 3 20 1 3 5 10 1 6 2 10 1 5 1 3 2 10 1 3 2 5 1 3 5 10 1 6 2 10 1 5 1 6 2 10 1 6 2 5 1 1 1 5000000 10 5000000 100

Sample Output

Case #1: 35 Case #2: 20 Case #3: 21 Case #4: 0

We are given a directed graph, and have to determine if there is a pair of nodes (X,Y) such that there are two or more paths from X to Y.

For each node, we do a depth-first search with that node as the root. If during the depth-first search we reach the same node twice, then we must have followed two different paths to get to that node from the root node, so we have found a pair (X,Y). Conversely, if there are two paths between X and Y, we will reach Y at least twice when doing a DFS from X. So if this algorithm finds no pair (X,Y), then none exists in the graph.

If there are V nodes and E edges in a graph, then a DFS is O(V+E) in general. But each DFS will never follow more than V edges, because after following that many edges, some node will have been reached twice, so we can stop at that point. Therefore this algorithm is O(V^{2}).

We can also just use a variation of Floyd's algorithm, which is O(V^{3}), but very simple to write. With only 1000 nodes in the graph, a fast implementation will finish within the time limit.

Test Data

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

This was a hard problem to wrap your head around, as evidenced by the results. The final solution was, however, surprisingly simple (although the argumentation for it is not).

Let us first consider a single case, with a single acceleration value **a**, and an arbitrarily large **N**. Suppose some strategy *S _{1}* takes you home in time

We can propose an alternate strategy *S _{2}*: first stop and wait for time

We have to prove that if *S _{1}* did not collide with the other car, neither will

Assume *S _{1}* was at some point

So, now we only need to consider strategies such as *S _{1}*. We now just need to determine how long do we need to wait on the top of the hill.

One last thing to notice is that if the other car moves at constant speed between **x _{i}** and

With this reasoning complete, we now have two possible algorithms. One is a binary search: To check if a given waiting time **T** is long enough, we just need to check all the **N** points at which the other car can change its speed. To achieve a precision of 10^{-6}, we will need around 40 iterations in the binary search. This means we solve each test case in O(**N A**) time, with the constant 40 hidden in the big-O notation — fast enough.

If we are worried about the constant factor of 40, we can also iterate over all points **x _{i}**, and for each calculate the minimum waiting time needed not to intercept the other car at this point:

`t`_{i} - sqrt(2x_{i}/a)

for all i such that `x`_{i} < D

(you also have to include the moment where the other car reaches your house). This will make our solution run in O(Test Data

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

This problem is a variation of the Longest Common Subsequence problem, which is to find the longest string of characters which occurs as a subsequence of each of two strings (a string S is a subsequence of a string T if S occurs in T, possibly with more characters inserted between the elements of S.) In this case, the first "string" is the sequence of types of each box produced by the factory, and the second "string" is the sequence of types of each toy produced by the factory.

A dynamic programming algorithm for this problem is to find the maximum number of toys that could be placed in boxes using the first x boxes and the first y toys. Let this value be f[x][y]. Then f[x][y] is equal to the maximum of:

- f[x-1][y]
- f[x][y-1]
- f[x-1][y-1]+1

Unfortunately, even though the number of runs of boxes and toys is small, the total number of boxes and toys can be very large, so this algorithm is not practical. But we can modify it so that f[x][y] will be the maximum number of toys that could be placed in boxes using the first x **runs** of boxes and the first y **runs** of toys. Now f[x][y] is the maximum of:

- f[x-1][y]
- f[x][y-1]
- f[a][b]+g(a,b,x,y), for all a<x, b<y

This algorithm is O(n^{4}). Another improvement can reduce this again to O(n^{3}), which we leave as an exercise to the reader!

Test Data

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