We're trotting through the Round 1s one weekend at a time, and Round 1B
featured a lot of horsepower. Perhaps you used a test harness, or
accidentally started your Java program with
public static void mane, or tried to print in C++ using
colt << , or attempted to reserve memory in C using
gallop. At least we didn't give you a problem on the
Canter set or make you
write an
(e)quine!
Steed 2: Cruise Control riffed on a 1990s movie franchise; its author came up with it while stuck in slow traffic! It was a potentially complicated-looking problem that turned out to have a straightforward solution. In Stable Neigh-bors, figuring out how to arrange unicorns was only half the fun; the implementation was potentially tricky! Finally, Pony Express was a graph problem with an unconventional solution.
This round's hardest problem proved significantly easier than Round 1A's, allowing JAPLJ to claim first place really early with a perfect score with no wrong tries in under 40 minutes! When the dust settled, 347 contestants achieved perfect scores. About 800 other contestants managed to solve all problems except one Large, and most of them had enough points or a low enough penalty to qualify to Round 2.
Our top 1,000 from this round advance to Round 2, joining the 1,000 who advanced from Round 1A. There's still one more chance to advance in Round 1C next week!
Cast
Problem A (Steed 2: Cruise Control): Written and prepared by Ian Tullis.
Problem B (Stable Neigh-bors): Written and prepared by Ian Tullis.
Problem C (Pony Express): Written by Pablo Heiber. Prepared by Philipp Hoffmann.
Solutions and other problem preparation and review by Liang Bai, Shane Carr, Md Mahbubul Hasan, Taman (Muhammed) Islam, Lalit Kundu, Petr Mitrichev, Rohan Mukkamala, Igor Naverniouk, Chieu Nguyen, and Josef Ziegler.
Analysis authors:
Annie is a bus driver with a high-stress job. She tried to unwind by going on a Caribbean cruise, but that also turned out to be stressful, so she has recently taken up horseback riding.
Today, Annie is riding her horse to the east along a long and narrow one-way road that runs west to east. She is currently at kilometer 0 of the road, and her destination is at kilometer D; kilometers along the road are numbered from west to east.
There are N other horses traveling east on the same road; all of them will go on traveling forever, and all of them are currently between Annie's horse and her destination. The i-th of these horses is initially at kilometer Ki and is traveling at its maximum speed of Si kilometers per hour.
Horses are very polite, and a horse H1 will not pass (move ahead of) another horse H2 that started off ahead of H1. (Two or more horses can share the same position for any amount of time; you may consider the horses to be single points.) Horses (other than Annie's) travel at their maximum speeds, except that whenever a horse H1 catches up to another slower horse H2, H1 reduces its speed to match the speed of H2.
Annie's horse, on the other hand, does not have a maximum speed and can travel at any speed that Annie chooses, as long as it does not pass another horse. To ensure a smooth ride for her and her horse, Annie wants to choose a single constant "cruise control" speed for her horse for the entire trip, from her current position to the destination, such that her horse will not pass any other horses. What is the maximum such speed that she can choose?
The first line of the input gives the number of test cases, T; T test cases follow. Each test case begins with two integers D and N: the destination position of all of the horses (in kilometers) and the number of other horses on the road. Then, N lines follow. The i-th of those lines has two integers Ki and Si: the initial position (in kilometers) and maximum speed (in kilometers per hour) of the i-th of the other horses on the road.
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 constant speed (in kilometers per hour) that Annie can use
without colliding with other horses. y will be considered
correct if it is within an absolute or relative error of 10-6 of
the correct answer. See the
FAQ for an explanation of what
that means, and what formats of real numbers we accept.
1 ≤ T ≤ 100.
0 < Ki < D ≤ 109, for all i.
Ki ≠ Kj, for all i ≠ j. (No two
horses start in the same position.)
1 ≤ Si ≤ 10000.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ N ≤ 2.
1 ≤ N ≤ 1000.
3 2525 1 2400 5 300 2 120 60 60 90 100 2 80 100 70 10
Case #1: 101.000000 Case #2: 100.000000 Case #3: 33.333333
In Sample Case #1, there is one other (very slow!) horse on the road; it will reach Annie's destination after 25 hours. Anything faster than 101 kilometers per hour would cause Annie to pass the horse before reaching the destination.
In Sample Case #2, there are two other horses on the road. The faster horse will catch up to the slower horse at kilometer 240 after 2 hours. Both horses will then go at the slower horse's speed for 1 more hour, until the horses reach Annie's destination at kilometer 300. The maximum speed that Annie can choose without passing another horse is 100 kilometers per hour.
You are lucky enough to own N pet unicorns. Each of your unicorns has either one or two of the following kinds of hairs in its mane: red hairs, yellow hairs, and blue hairs. The color of a mane depends on exactly which sorts of colored hairs it contains:
You have R, O, Y, G, B, and V unicorns with red, orange, yellow, green, blue, and violet manes, respectively.
You have just built a circular stable with N stalls, arranged in a ring such that each stall borders two other stalls. You would like to put exactly one of your unicorns in each of these stalls. However, unicorns need to feel rare and special, so no unicorn can be next to another unicorn that shares at least one of the hair colors in its mane. For example, a unicorn with an orange mane cannot be next to a unicorn with a violet mane, since both of those manes have red hairs. Similarly, a unicorn with a green mane cannot be next to a unicorn with a yellow mane, since both of those have yellow hairs.
Is it possible to place all of your unicorns? If so, provide any one arrangement.
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with seven integers: N, R, O, Y, G, B, and V.
For each test case, output one line containing Case #x: y, where
x is the test case number (starting from 1) and y
is IMPOSSIBLE if it is not possible to place all the unicorns,
or a string of N characters representing the placements of unicorns in
stalls, starting at a point of your choice and reading clockwise around the
circle. Use R to represent each unicorn with a red mane,
O to represent each unicorn with an orange mane, and so on with
Y, G, B, and V. This
arrangement must obey the rules described in the statement above.
If multiple arrangements are possible, you may print any of them.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
3 ≤ N ≤ 1000.
R + O + Y + G + B + V =
N.
0 ≤ Z for each Z in {R, O, Y, G, B,
V}.
O = G = V = 0. (Each unicorn has only one hair color in
its mane.)
No restrictions beyond the general limits. (Each unicorn may have either one
or two hair colors in its mane.)
4 6 2 0 2 0 2 0 3 1 0 2 0 0 0 6 2 0 1 1 2 0 4 0 0 2 0 0 2
Case #1: RYBRBY Case #2: IMPOSSIBLE Case #3: YBRGRB Case #4: YVYV
Note that the last two sample cases would not appear in the Small dataset.
For sample case #1, there are many possible answers; for example, another is
BYBRYR. Note that BYRYRB would not be a
valid answer; remember that the stalls form a ring, and the first touches
the last!
In sample case #2, there are only three stalls, and each stall is a neighbor of the other two, so the two unicorns with yellow manes would have to be neighbors, which is not allowed.
For sample case #3, note that arranging the unicorns in the same color
pattern as the Google logo (BRYBGR) would not be valid, since a
unicorn with a blue mane would be a neighbor of a unicorn with a green mane,
and both of those manes share blue hairs.
In sample case #4, no two unicorns with yellow manes can be neighbors, and no two unicorns with violet manes can be neighbors.
It's the year 1860, and the Pony Express is the fastest mail delivery system joining the East and West coasts of the United States. This system serves N different cities. In each city, there is one horse (as in the expression "one-horse town"); each horse travels at a certain constant speed and has a maximum total distance it can travel before it becomes too tired to continue.
The Pony Express rider starts off on the starting city's horse. Every time the rider reaches a city, they may continue to use their current horse or switch to that city's horse; switching is instantaneous. Horses never get a chance to rest, so whenever part of a horse's maximum total distance is "used up", it is used up forever! When the rider reaches the destination city, the mail is delivered.
The routes between cities were established via complicated negotiations between company owners, lawmakers, union delegates, and cousin Pete. That means that the distances between cities do not necessarily follow common sense: for instance, they do not necessarily comply with the triangle inequality, and the distance from city A to city B might be different from the distance from city B to city A!
You are a time traveling entrepreneur, and you have brought a fast computer from the future. A single computer is not enough for you to set up an e-mail service and make the Pony Express obsolete, but you can use it to make optimal routing plans for the Pony Express. Given all data about routes between cities and the horses in each city, and a list of pairs of starting and ending cities, can you quickly calculate the minimum time necessary for each delivery? (You should treat all of these deliveries as independent; using cities/horses on one route does not make them unavailable on other routes.)
The first line of the input gives the number of test cases, T. T test cases follow. Each test case is described as follows:
For each test case, output one line containing Case #x: y1
y2 ... yQ, where x is the
test case number (starting from 1) and yk is the
minimum time, in hours, to deliver a letter from city Uk to
city Vk.
Each yk will be considered correct if it is within an
absolute or relative error of 10-6 of the correct answer. See
the FAQ for an explanation of
what that means, and what formats of real numbers we accept.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 100.
1 ≤ Ei ≤ 109, for all i.
1 ≤ Si ≤ 1000, for all i.
-1 ≤ Dij ≤ 109, for all i, j.
Dii = -1, for all i. (There are no direct routes from a city to itself.)
Dij ≠ 0, for all i, j.
Uk ≠ Vk, for all k.
It is guaranteed that the delivery from Uk to Vk can be
accomplished with the given horses, for all k.
Ul ≠ Um and/or Vl ≠ Vm,
for all different l, m. (No ordered pair of cities to investigate is repeated within a test case.)
Dij = -1, for all i, j where i + 1 ≠ j.
(The cities are in a single line; each route goes from one city to the next city in line.)
Q = 1.
U1 = 1.
V1 = N.
(The only delivery to calculate is between the first and last cities in the line).
1 ≤ Q ≤ 100.
1 ≤ Uk ≤ N, for all k.
1 ≤ Vk ≤ N, for all k.
3 3 1 2 3 2 4 4 4 -1 1 -1 -1 -1 1 -1 -1 -1 1 3 4 1 13 10 1 1000 10 8 5 5 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 10 -1 -1 -1 -1 1 4 4 3 30 60 10 1000 12 5 20 1 -1 10 -1 31 10 -1 10 -1 -1 -1 -1 10 15 6 -1 -1 2 4 3 1 3 2
Case #1: 0.583333333 Case #2: 1.2 Case #3: 0.51 8.01 8.0
Note that the last sample case would not appear in the Small dataset.
In Case #1 there are two options: use the horse in city 1 for the entire trip, or change horses in city 2. Both horses have enough endurance, so both options are viable. Since the horse in city 2 is faster, it is better to change, for a total time of 1/3 + 1/4.
In Case #2 there are two intermediate cities in which you can change horses. If you change horses in city 2, however, your new horse, while blazingly fast, will not have enough endurance, so you will be forced to change again in city 3. If you keep your horse, you will have the option to change horses (or not) in city 3. So, the three options, with their total times, are:
In Case #3, there are lots of alternatives for each delivery. The optimal one for the first delivery (city 2 to city 4) is to go to city 1 in time 10/1000, change horses, and then go to cities 2, 3 and 4, in that order, using the horse from city 1, which takes time (10 + 10 + 10) / 60.
For the second delivery (city 3 to city 2) you have no choice but to first go to city 4 which takes time 10/5. Your relatively fast horse does not have enough endurance to get anywhere else, so you need to grab the horse in city 4. You could use it to get directly to city 1 in time 15, but that would be slower than riding it to city 2 in time 6 and then using the blazingly fast horse in city 2 to get to city 1 in just 10/1000 extra time.
In the third delivery (city 3 to city 1) of Case #3 it is optimal to use the first two steps of the previous one, for a total time of 10/5 + 6 = 8.
Pop quiz, hotshots! This problem seems pretty complicated at first glance. What do you do?
One natural strategy is to try binary searching on Annie's speed, but it is difficult to directly determine whether a given speed avoids passing another horse; the input data alone does not tell us where each horse is at any given time, because horses might slow other horses down. In theory, we could figure out when faster horses catch up to slower horses and slow down, determine the exact path of each horse, and check whether our chosen speed crosses any of those paths. With only up to two horses in test set 1, this sort of calculation is feasible, but it would be laborious for test set 2.
However, we can avoid all of that work via some observations. To maximize cruising speed, Annie's horse should reach the destination at exactly the same time as the horse ahead of her (let's call it Horse A); there is no reason to leave a gap. Either Horse A will reach the destination without having to slow down (and so it will be the one that directly limits Annie's speed), or it will be slowed down at some point by the horse ahead of it (let's call it Horse B). The same is true for Horse B: either it will never have to slow down (and so it will be the one that ultimately limits Annie's speed), or it will be slowed down by the horse ahead of it, and so on. So there will be a single "limiting horse" on the road that ultimately determines how fast Annie's horse can reach the destination. We claim that this "limiting horse" is the only horse that matters, and we can disregard all of the others!
It is easy to see that we can ignore the horses to the east of the limiting horse; they will reach and pass the destination before the limiting horse gets there. What about the "intermediate horses" between Annie and the limiting horse? We know from the way we have defined the limiting horse that every intermediate horse will catch up to the limiting horse before reaching the destination. (If one did not, then it would be the limiting horse.) Suppose that Annie chooses a cruising speed that gets her to the destination at exactly the same time as the limiting horse. We certainly cannot go faster than this. Moreover, this speed is safe: it cannot possibly cause Annie to pass any of the intermediate horses. If she were going fast enough to overtake an intermediate horse, then she would definitely be going fast enough to pass the limiting horse, since every intermediate horse will catch up to the limiting horse. This would cause a contradiction. Therefore, we do not need to worry about the intermediate horses or their interactions with each other.
So, once we have identified the limiting horse, the strategy is simple: go at the exact speed that will cause Annie to reach the destination at the same time as the limiting horse. This speed can be found in constant time. We could identify the limiting horse directly via the argument in our third paragraph above, but even this would be unnecessary work. Instead, for each horse in turn, we can pretend that it is the limiting horse and calculate the cruising speed that it would force. Then the smallest of those speeds is our answer. (If any horse allows a faster cruising speed than another, it cannot be the limiting horse, because that cruising speed would cause Annie to pass the true limiting horse.) This takes O(N) time.
In the Small dataset, all of the unicorns have manes with only a single primary color: red, yellow, or blue. None of these manes share any primary colors, so our only restriction is that two unicorns with the same mane color cannot be next to each other. However, one color might be so common that it is impossible to avoid putting two unicorns with that color next to each other. If we space unicorns with the most common color out, with some other unicorn between each pair of them, then we can accommodate up to floor(N/2) of the most common color. If we have more than that number with any color, the case is impossible.
Otherwise, we can extend this "every other stall" strategy to work for any case. Start at some arbitrary position on the ring of stalls, and place unicorns in the first, third, fifth, etc. stalls, all the way around the ring. When you reach the starting point again, continue to place unicorns in the second, fourth, sixth, etc. stalls. As you do this, place all of the unicorns with the most common mane color, and then all the unicorns with the next most common mane color, and then all the rest. Because all of these colors have a frequency no greater than floor(N/2), it is not possible for this placement strategy to put two unicorns with the same color next to each other.
The Large dataset introduces more complications. Unicorns with a secondary-colored mane (orange, green, or violet) can only have one type of neighbor. An orange-maned unicorn must be next to two blue-maned unicorns; similarly, a yellow must be next to purples, and a red must be next to greens.
How many instances of a primary color do we need to "surround" all unicorns with the corresponding secondary-colored mane? If the secondary color and its primary neighbor are the only two colors available, then there must be equal numbers of those two colors. Otherwise, if there are S instances of the secondary color, we need at least S + 1 instances of the primary color.
Moreover, we might as well put all secondary colors of the same type together (separated by the primary color, of course) in a single chain. Any valid arrangement without that property can be rearranged to have that property. For instance, suppose that we have two separate R-G-R chains separated by two other valid chains Z and Z': R-G-R-Z-R-G-R-Z'-. We can just rearrange this to R-G-R-G-R-Z-R-Z'-, which must also be valid.
A final useful insight is that an R-G-R-G-R chain, for example, acts just like a single R in terms of what can neighbor it on either side. So one strategy for the Large is: first, check for the case mentioned above in which only one secondary color and its neighboring primary color are present. Otherwise, for each secondary color, check that there are enough primary-color unicorns to surround the secondary-color unicorns in a chain. Then pretend that each of these chains is just a single instance of the primary-colored mane from that chain; this reduces the problem to primary colors, and the algorithm for the Small dataset works. You can substitute each chain back in (for some arbitrary instance of the appropriate primary color) once that algorithm has finished.
These Small and Large solutions run in O(N) time, and they are bound by reading the input, checking color frequencies, and printing the output. Other, more complex solutions (e.g., dynamic programming) also exist.
In the Small dataset, we are given a line of cities and the distances between them, and we want to go from the first to the last city in the line. However, we need to minimize the time and not the distance, and the obvious way to transform between the two (divide by speed) does not work directly, because the horses we can use have different speeds. The solution, as in many minimization algorithms on a path that only moves forward, is to use dynamic programming.
Let us define f(i) as the quickest way to get from city i to the finish line, assuming we start using the horse at city i. Of course, f(1) is the answer to the only query.
We do not know where we need to change horses, but we can try every possible intermediate city j to change horses, thus completely defining f(i) by:
This solves the problem in O(N2) because the domain of f is of size N and the iteration to calculate each value of the domain takes time O(N) if we memoize the results. There are other dynamic programming approaches that also work in the same amount of time.
In the Large dataset, we are given a graph G of cities with distances between them instead of just a line, but the setup of the problem is otherwise the same.
As mentioned above, one relatively unusual feature of this graph problem is that the desired result (time) is not in the same units as the weights of the graph's edges (distance). Moreover, the obvious way to transform between the two (speed) is not a constant. This observation leads to a key insight: we should construct a new graph with weights of time instead of distance. That way, we can apply a shortest path algorithm to get the result we want.
We can do this by defining a graph G' that has the same nodes as G, but in which the weight of edge (i, j) is the time that it takes to go from city i to city j. As we said above, there is no fixed speed, but we can fix it. The edge (i, j) then represents the time it takes to go from city i to city j using a single horse, and the obvious choice is to use the horse at the departure city i. Let us call that horse h. In this way, the edge (i, j) on G' represents a path on G, traversed using a single horse. That means the edge (i, j) exists if and only if there is a path between i and j in G with distance less than or equal to h's endurance. Moreover, the weight (i, j) is a time now defined by a single speed, h's speed, and thus it is just the distance between i and j in G, divided by h's speed. You can see that a minimum path from a to b in G' represents a succession of edges in G', that is, a succession of single-horse paths in G, which is exactly what a solution looks like!
Since the limits are low enough, and we need all shortest paths in G to construct G', and many shortest paths in G' to answer many queries, the best option is to use an all-pairs shortest path algorithm. Floyd-Warshall is the easiest and fastest to implement, but others would work too. To also check for existence of paths, you can use the trick of setting weights to "infinity", that is, a distance too large for an actual shortest path (larger than maximum distance × number of total edges). Thus, an infinity distance simply means the edge or path does not exist in the graph.
To summarize, this pseudocode solves the problem:
This solution takes time O(N3). Both uses of Floyd-Warshall take time O(N3), and creating G' as an adjacency matrix only takes time O(N2).