The Europe, Middle East and Asia regional semifinal round turned out to be the easiest of the three semifinals, with seven contestants solving all four problems. The top three spots went to bmerry, dzhulgakov and gawry. Coders from Eastern Europe dominated by taking 9 of the top 10 spots. The competition was fierce, and the bar of advancing to the finals ended up at an unprecedented 50 points. For most of the top 43 contestants, that meant solving at least problems A, B and D-small. The problem set was a mix of different flavours of linear algebra and dynamic programming.
Credits
Problem A. Scaled Triangle Written and prepared by Cosmin Negruseri.
Problem B. Painting a Fence Written by John Dethridge. Prepared by Bartholomew Furrow and Daniel Rocha.
Problem C. Rainbow Trees Written by Petr Mitrichev. Prepared by Frank Chu and Xiaomin Chen.
Problem D. Bus Stops Written and prepared by Marius Andrei.
Contest analysis presented by Cosmin Negruseri, Igor Naverniouk, Xiaomin Chen, and Marius Andrei.
You are given two triangle-shaped pictures. The second picture is a possibly translated, rotated and scaled version of the first. The two triangles are placed on the table, with the second one placed completely inside (possibly touching the boundary of) the first one. The second triangle is always scaled by a factor that is strictly between 0 and 1.
You need to process the picture, and for that you need a point in the picture which overlaps with the same point of the scaled picture. If there is more than one solution, you can return any of them. If there are no solutions, print "No Solution" (without the quotes) for that test case.
The first line of input gives the number of cases, N. Then for each test case, there will be two lines, each containing six space-separated integers -- the coordinates of one of the triangles -- in the format "x1 y1 x2 y2 x3 y3". The point (x1, y1) in the first triangle corresponds to the same corner of the picture as (x1, y1) in the second triangle, and similarly for (x2, y2) and (x3, y3).
For each test case, output one line containing "Case #x: " followed two real numbers representing the coordinates of the overlapping point separated by one space character, or the string "No Solution". Answers with a relative or absolute error of at most 10-5 will be considered correct.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ N ≤ 10.
The coordinates of the points will be integer numbers between -10 000 and 10
000. The three points in each triangle will not be collinear.
All tests will contain isosceles right-angle triangles. (i.e., the triangle's angles will be 45 degrees, 45 degrees, and 90 degrees.)
The triangles can have any shape.
2 0 0 0 2 2 0 0 0 0 1 1 0 10 0 0 10 0 0 3 3 1 1 3 1
Case #1: 0.000000 0.000000 Case #2: 2.692308 1.538462
You need to hire some people to paint a fence. The fence is composed of 10000 contiguous sections, numbered from 1 to 10000.
You get some offers from painters to help paint the fence. Each painter offers to paint a contiguous subset of fence sections in a particular color. You need to accept a set of the offers, such that:
If it is possible to satisfy these two requirements, find the minimum number of offers that you must accept.
For each test case, there will be:
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 50
1 ≤ N ≤ 10
1 ≤ N ≤ 300
5 2 BLUE 1 5000 RED 5001 10000 3 BLUE 1 6000 RED 2000 8000 WHITE 7000 10000 4 BLUE 1 3000 RED 2000 5000 ORANGE 4000 8000 GREEN 7000 10000 2 BLUE 1 4000 RED 4002 10000 3 BLUE 1 6000 RED 4000 10000 ORANGE 3000 8000
Case #1: 2 Case #2: 3 Case #3: IMPOSSIBLE Case #4: IMPOSSIBLE Case #5: 2
In the first test case, accepting both offers will exactly paint the whole fence, 5000 sections each, with no overlap.
In the second case, the painters will overlap, which is acceptable.
In the third case, accepting all four offers would cover the whole fence, but it would use 4 different colours, so this is not acceptable.
In the fourth case, section 4001 cannot be painted.
In the fifth case, we can accept just the first and second offer and successfully paint the fence.
In graph theory, a tree is a connected, undirected simple graph with no cycles. A tree with n nodes always has n - 1 edges.
A path in a tree is a sequence of distinct edges which are connected (each pair of consecutive edges in the path share a vertex).
Consider a tree with n vertices and n-1 edges. You can color each edge in one of k colors.
An assignment of colors to edges is a rainbow coloring if in every path of 2 or 3 edges, the colors of the edges are different. (i.e., every two consecutive edges have different colors, and every three consecutive edges have different colors).
Given a tree and the number of colors k, find the number of rainbow colorings modulo 1000000009.
The first line of input gives the number of test cases, C. Then for each of the C cases, there will be:
For each test case, output one line. That line should contain "Case #X: Y", where X is 1-based number of the case, and Y is the answer for that test case.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ k ≤ 1000000000
All the node numbers are between 1 and n, inclusive.
1 ≤ C ≤ 100
2 ≤ n ≤ 20
1 ≤ C ≤ 40
2 ≤ n ≤ 500
2 4 10 1 2 1 3 1 4 5 3 1 2 2 3 3 4 4 5
Case #1: 720 Case #2: 6
In the first case, the tree has four nodes. There are edges from one node to each of the other three. Each pair of these edges are adjacent, so for there to be a rainbow coloring, all the edges must have different colors. There are therefore 10 x 9 x 8 = 720 rainbow colorings.
In the second case, the tree itself is a path of 4 edges, and there are 3 colors. The first three edges must all have different colors, so there are 3 x 2 x 1 colorings for these, and then there is only one choice for the fourth edge, so there are 6 rainbow colorings.
In the First City of Mars there are N bus stops, all aligned in a straight line of length N-1 km. The mayor likes to keeps things simple, so he gave the bus stops numbers from 1 to N, and separated adjacent stops by exactly 1 km.
There are also K buses in the city. The mayor has to plan the bus schedule and he would like to know in how many ways that can be done. This number can be very large. Luckily there are a few constraints:
Help the mayor evaluate the number of schedules. However try not to give him very bad news (a lot of schedules) so just output the real number modulo 30031.
The first line in the input file is the number of cases T.
Each of the next T lines contains 3 integers separated by one space:
N, K and P.
For each case output the number of ways to plan the bus schedules (modulo 30031) in the format "Case #t: [number of ways modulo 30031]" where t is the number of the test case, starting from 1.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 < T ≤ 30
1 < P ≤ 10
K < N
1 < K ≤ P
1 < N < 1000
1 < N < 109
3 10 3 3 5 2 3 40 4 8
Case #1: 1 Case #2: 3 Case #3: 7380
Let's name the buses: A, B, C...
For the first case there is only one possible way of planning the schedule:
A → 1, 4, 7, 10. B → 2, 5, 8. C → 3, 6, 9.
For the second case the possible ways of planning are:
(A → 1,3,5. B → 2,4),
(A → 1,3,4. B → 2,5),
(A → 1,4. B → 2,3,5).
In this problem we are given a triangle and another triangle obtained by applying an affine transformation on the first one -- translation, rotation and scaling. We are asked to find a fixed point for this transformation.
This is actually a particular case of "Bannach's fixed point theorem" which guarantees the existence and uniqueness of fixed points of certain self maps of metric spaces, though knowing the theorem was not a requirement.
To solve this problem, we need to find the parameters of the transformation.
Such transformations are familiar to anyone who has ever played with computer graphics. To view the transformation as a linear operator, it is convenient to use homogeneous coordinates, where our plane is embedded as the plane z=1 in 3D space. i.e., consider each point (x, y) as (x, y, 1). (Note: As usual, all the vectors corresponding to points are considered column vectors, in spite of the horizontal way we write them here.) In this setting, rotating a point by an angle alpha around the point (0, 0) corresponds to multiplying the vector v = (x, y, 1) by the matrix R = [[cos alpha sin alpha 0] [-sin alpha cos alpha 0] [0 0 1]]. Translating a point x, y by (dx, dy) corresponds to multiplying v by T = [[1 0 dx] [0 1 dy] [0 0 1]], and a scaling transform centered at 0 corresponds to multiplying a point v = (x, y, 1) by the matrix S = [[S 0 0] [0 S 0] [0 0 1]]. The total transform looks like this
v' = T R S v = M v.
Note that above we focused on the effect of the transformation on the plane z=1. The interested reader can verify that it maps every horizontal plane z=z0 to itself.
To get the matrix M, we may solve separately for the matrices T, R, and S. There is an easier way. From the input constraints, we know that point A is mapped to A', B to B' and C to C'. View each point as a vector in the plane z=1, so that A, B, C are linearly independent. So the 3 by 3 matrix [A B C] is invertible. Therefore,
M [A B C] = [A' B' C']
has a unique solution for M.
From here, there are still two solutions to our problem. One observation is that if we apply the transformation and we have a point that doesn't change, we can apply it again on the resulting triangle and the point will remain the same. So we apply this transformation until the triangle becomes very small. The fixed point will still be inside the triangle so we can stop when the side lengths of the current triangle get smaller than the needed precision.
The more algebraic solution looks at the equation again. We know there is a
unique point v = (x, y, 1) such that M v = v. From here we know that
(i) 1 must be an eigen-value for the matrix M; (ii) the space of the
eigen-vectors corresponding to 1 must be one-dimensional.
So we can just solve the equation [M - I] v = 0, and find the intersection of
the solution space (a line) and the plane z=1.
Banach fixed point theorem - Homogeneous coordinate - Eigen value, eigenvectors, and more
This was meant to be the easiest problem in the match. A straightforward brute force solution suffices.
Step 1. Pick a set C of (up to) three colors to be used. There are N different colors, so O(N3) such choices.
Step 2. From the offers, filter out the ones where the color is not in the set C. We want to figure out whether the remaining offers can cover the whole fence, and if so, what the minimum required number of offers is.
Step 2 is a classical problem with a greedy scanline solution. We sort the offers (intervals) by their left endpoint, and scan from left to right, considering the offers one by one. At any moment, if we have covered the fence from section 1 to k, we always pick the next offer so that it starts before k and ends as far to the right as possible.
If we sort all the offers by their left endpoing in the beginning, then step 2 takes time O(N), and the whole algorithm runs in time O(N4).
Pick any vertex r. We view the tree as rooted at r, and -- as usual -- draw the tree with the root at the top, and draw the nodes of depth d at the same level, d units below the root.
By a partial coloring on a subset of edges we mean the assignment of
colors to the edges in the subset so that the "rainbow coloring" constraint is
satisfied on that subset. We do not care about the coloring of the edges that
are not in the subset.
For each node x, we define the value
f(x) := number of ways to color the subtree rooted at x, given any partial coloring for the set of edges that are incident to the parent of x.
It is not at all obvious that f(x) is well defined. (Why would the number always be the same for any given partial coloring?). To see that f(x) is indeed well defined, let's look at an algorithm for computing it.
Suppose z is the parent of x, and the degree of z is D. Note that the rainbow constraint is a very local condition -- the color of any edge other than those incident to z does not affect the coloring for the subtree rooted at x.
Assume that x has t children -- y1, y2, ..., yt. To color all the edges in the subtree rooted at x, we do the following.
Indeed, the computation only depends on D, the degree of the parent of x. f(x) is the product of the numbers above.
There is nothing very special about the root r, except that we need to agree D = 0 in that case. And the solution to our problem is just f(r).
The problem can be solved by using dynamic programming and matrix multiplication for solving linear recursive sequences.
Consider a configuration of buses that are within a window of width P and advance the leftmost bus in such a way that all of the buses are still within a (shifted) window of width P.
Now we can define a state as the position of the buses within P units. For
instance if we have P = 10 and K = 5 buses, then we have 252 possible states
(10 choose 5). Let NS be the number of states.
To be sure we don't count the same state in different windows we can required
that there always be a bus at the leftmost position in the window.
To advance the window of size P we move the leftmost bus. There is always a bus there. Now remember that the new state has to have a bus at the leftmost position, so the window might move to the right by more than one spot.
We compute all the possible state transitions. Let C be the matrix of state
transitions having Ca,b be the number of ways we can go from state
a to state b.
For each state j, with the window in the position i we will have something
like:
A[Sj][i+1] = C1,jA[S1][i] + C2,jA[S2][i] + ... + CNS,jA[SNS][i]
A[s][p] is the number of ways we can get into state s while having the window in position p.
This would be enough to solve the small input. For the large input we need to speed things up, so we are going to compute that linear recurrence of order NS by using matrix multiplication. Let's look instead at a much simpler example of a linear recurrence -- Fibonacci numbers.
FN = FN-1 + FN-2
This can be rewritten as:
(1 0) * (FN-2) = (FN-1) (1 1) (FN-1) (FN )
In a shorter form we have:
M * VN-1 = VN
This says that to compute VN = (FN, FN-1) from VN-1 = (FN-2, FN-1) we need to multiply with M. Now we can apply this recursively:
MX * V0 = VX
MX can be computed using an algorithm called successive squaring in time that is logarithmic in X.