Single Round Match 492
Tuesday, December 28th, 2010
Match summary
Ahem. How time flies, we are at the end of year 2010. Looking back in time, we remember the good ol' days of TopCoder Open 2010 and other contests alike. Travelling back in time, that's what we find in this set.
Bird-eye view
The level of activity in both divisions is low. The number of submitted solutions / coder in division two is 1.17 and worse in division 1 : 0.95. The system test was not forgiving either, the number of systest survivors (people who solved at least one problem) is only around 54% in division two and 65% in division one. Truly this is a low number, contrast to the second-latest SRM that I authored: SRM 480.
Division 2
Division 2 coders are faced with three problems of balanced difficulty. The easy problem is supposedly easy, but the success rate is very low compared to a usual division2-250 problem (for a reason that I have yet to know). They have the Division1-250 problem as their Division2-550 problem. Finally, they have an ordinary 1000 problem that some claim to be easier than the 550, just like in SRM 470 (coincidentally, both 1000 problems are solved using the same algorithm).
Despite this, there are 7 coders who managed to solve all three problems. Amongst them, vector9x and jimison become the third and second place winners, respectively. Newcomer lg5293 becomes the winner and is promoted to yellow.
Division 1
You see, it's not that I don't want to give a higher score for the problems. It's just, problem scores are relative (i.e., if all the problems are hard or all of them are easy then it'll be the standard 250-500-1000). The point is, all three problems of this set are considered to be difficult, so instead of putting 275-600-1050, we downgrade all of them to 250-550-1000. it4.kp said something funny about my suggested constraints, something like this: Making the 1000 into a 1050 is really mean, coders are given 'no safe route' after solving the 250 :).
The difficulty of all three problems is reflected by the number of correct solutions. From 549 participants, only 360 managed to solve the easy problem, 31 for the medium problem, and 1 for the hard problem. Indeed I wouldn't object if someone called them the medium, very hard, and the impossibly hard problems instead :).
Nobody managed to solve all three problems correctly. 10 coders submitted the hard problem using scary Dijkstra algorithms (which are so scary that no coder actually tried to challenge them) and amongst them, lyrically is the only person* who solved the hard problem correctly. He becomes the second place winner, losing the first place to jialin and her extremely fast submission for the medium problem. The third place goes to Petr.
Some Random Thoughts
The problem texts are heavy. Even so, only two people asked for clarification, which amazes me. Perhaps the texts were so heavy that people were busy to read than to clarify.
This problem asks for max(profit[i] - decay[j], i != j).
The brute force approach
Brute force over all pairs of <i,j> where i != j, count profit[i] - decay[j], and maximize that value. Newcomer-winner lg5293 implements this solution.
Another approach?
The approach above works in O(N^2). There's an O(N) solution which works though. Can you find it guys? (Hint below in white)
If we have chosen a cellar as i in the pair <i,j>, can we find j in O(1)?
Thoughts
It is guaranteed that this profit will be positive.
Did you guys find that helpful? I wonder if the number of incorrect solutions would be higher if the answer could be negative. Oh well, it's surprising already that the success rate is so low.
This is a geometry problem. Fortunately, a simple one.
The general idea
There are two possible cases:
We can always solve the problem by choosing N-1 trees. Indeed, we can decrease the heights all trees but the shortest tree to the height of the shortest tree.
Otherwise, there will be at least two trees that are not shortened. If we know these two trees, the line that corresponds to the collinearity of all the trees becomes fixed.
So, the algorithm works by brute forcing over all pairs of trees as two trees that are fixed, and then checking the other trees. For each other tree T we let projected_height be the height that T should be so that T is collinear with the two fixed trees. If projected_height is less than zero or more than the height of T, then this is impossible, so we simply mark our pair of fixed trees as 'impossible'. Otherwise, we check if projected_height is not equal to the height of T, in which case T needs to be shortened. So, this way, for each pair of trees that are fixed, we will find either 'impossible' or the number of other trees that needs to be shortened. We then simply find the least number of shortened trees and return that as our answer.
You see, some part of the algorithm is dedicated for calculating projected_height. Let's discuss two approaches. Let's start with the easy-risky approach: we call this
The (risky) double approach
The idea is simple and is expressed in the picture above. It can be explained in many ways, I'll try to explain one of them. Suppose we have two fixed trees T1 and T2. Let's say T1's top point is (x1,y1) and T2's is (x2,y2). The line L (the diagonal line in the picture above) that passes through T1 and T2 has a constant dy/dx (the difference of y compared to the difference of x) that is equal to (y2-y1) / (x2-x1) (note that x2-x1 won't be zero for distinct trees - we won't have division by zero). So, for another tree T3 that is located at (x3,y3), y3 can be computed by dy/dx * (x3-x1) + y1 (since we 'offset' the y by y1 as the picture suggests).
Indeed this approach will work (as shown by LayCurse in his solution), as long as you supply your computations with epsilon. Otherwise, rounding error may fail your solution.
In light of rounding errors, some coders like to search for a more-elegant non-double non-risky solution. We call this
The exact approach
You see, projected_height as suggested by the (risky) double approach is simply (y2 - y1) / (x2 - x1) * (x3 - x1) + y1. So we divide some value by a constant value of (x2 - x1) (constant - since we fix both T1 and T2). So, let's try to remove the division.
To illustrate how this work, we will illustrate how we check whether projected_height is more than the height of T3. Checking whether projected_height is equal to the height of T3 or checking whether it is less than zero is similar.
Which is true if (x2 - x1) is positive (we can enforce this by strictly picking T2 to the right of T1), and Voila, we have no more doubles to mess with our code :).
A geometry in D1-250 is indeed uncommon. Let's see, the last time Geometry appears as a D1-250 was in SRM 449. Hey, that's a long-time-ago ;).
Aside from that, do you guys find images helpful? I like images, they make the problem more 'interesting'. It's just, sometimes I think putting lots of images in a statement makes it harder to read. Perhaps if you guys think images are helpful, I should add more to the problems :).
Now that we finished talking about those two problems, we are left with three graph problems. And so, without further ado..
Let's solve this problem!
Which some claim to be easy. Indeed, all you need is a simple-looking observation which says that:
This problem is equivalent to finding the minimum spanning tree in the graph that covers all nodes..
Perhaps I should've made the font bigger, since the problem is just that. You can learn more about minimum spanning trees here, and so the rest of our discussion will talk about why and not how.
So, why? Clearly if there does not exist such spanning tree, it means that the graph is disconnected, which means that you cannot reach some of the cities from city 0, in which case the answer is certainly -1. Otherwise, we will prove this in similar fashion as how we proved ActivateGame here.
Lemma 1: The set of roads that is traversed by any solution will span the graph.
Indeed, the first time we reach a city that wasn't reached before, we will need to traverse a road. The set of these roads will be a spanning tree (formal proof by induction).
Lemma 2: For any spanning tree, there exists a solution that traverses each of those roads once and no other road.
The proof is by construction. We start at city 0 and regard it as the root. If we have reached all other cities, then we're done. Otherwise, we pick one of the roads that is in the spanning tree that is adjacent to this city. We traverse that road, and we remove that road from our tree. Now, we have two trees, the tree that we're currently in and the remaining tree that contains city 0. Now, we let our current city as the root and continue the recursion (with the basis case that we end up at a node with no adjacent roads). This will terminate since we have a finite number of roads and each recursion deletes a road. If we're done, and we're not at the original city 0, we 'travel back in time' to the previous city where we came from. It is easy to see that every road that this algorithm traverses, it'll traverse only once. Furthermore, to see that we will eventually traverse all roads in the graph, we'll use contradiction. We let the depth of a city as the number of roads traversed from city 0 to the city in the spanning tree. If we haven't traversed all roads, then there is this road R whose depth-of-one-of-the-two-cities-named-C-adjacent-to-it is minimum (in case of a tie, pick any of them). If C is city 0, then we arrive at a contradiction. Otherwise, there's some other road that connects city C to a city D which is closer to the root. This edge will have been traversed, since we pick R in the way we did. Hence, at some point, city D will be regarded as a root. The fact that R is not traversed is then a contradiction. Finally, it is easy to see that if we traverse each of those roads, then we will visit all of the cities.
Hence, a direct consequence from Lemma 1 and Lemma 2 is the set of roads that is traversed in an optimal solution will be a spanning tree with the property that each of those roads is traversed exactly once. The minimum of such is called the minimum spanning tree, and our proof is finished.
I did my best to make the MST obscure this time. The last time, the MST was so easily found that the number of correct submissions reached 62. We only have 26 now, so I think it's more obscure :).
Around 5.5% coders managed to solve this problem. Hey, that's a small number, let's investigate why!
The problem?
is a Dynamic Programming problem at heart which uses some Graph algorithm.
The idea
So, first, we are at city 0, we need to survey cities[0]..cities[M-1]. Can we actually represent this as our state? I.e, a triple (C,u,v) which means that we're at city C and need to survey cities[u]..cities[v]? Let's investigate!
So what happens now is that we move to another city, suppose city D. So now, we're at city D, we need to survey cities[0]..cities[M-1]. If cities[0] is city D, then we survey the city and update into cities[1]..cities[M-1]. However, if we represent this as triple (D,u,v), we lose the fact that we can travel back in time to city C. So it appears that we can't forget about city C. But there lies the key to the problem.
Suppose we travel back in time to city C. Can we now forget about city D? We can, since we can't reverse back to city D and so aside from its effect on u and v, it leaves no other trace.
Let's revisit the triple (D,u,v). If we will never reverse back in time to city C, then this triple will be sufficient. Otherwise, we will at some time reverse back to city C. The question is when? We will need to travel back in time to city C because we want to survey some city cities[i] in cities[u]..cities[v]. So the idea is that we will at some point reverse the time back to city C to survey some cities[i]..[v] (to v because once we go back in time, we effectively forget about D and all cities we traversed afterwards). This also implies that during our trip to survey cities[u]..cities[i-1], we will never return back in time to city C (Except if we revisit city C through 'traversing' and not 'going back in time' - but in this case we will ultimately be able to travel back in time to city C that we first visit). Hey, now we seem to have a solid ground to step on!
Indeed, during our trip to visit cities[u]..cities[i-1], the fact that we will never return back in time to city C enables us to forget city C during that course, i.e., it can be conveniently represented by the tuple (D,u,i-1). And then, since we will never travel back in time when we're already at city C, we can also represent the other part as a tuple (C,i,v) (since we won't need to remember D).
So what's the conclusion of our discussion so far? We can represent our state as a triple (C,u,v), and we can solve a triple by breaking it into two other triples. Now, we if we treat each triple like how we treat the triple above, then we get a recursive solution!
Solution the First
So, how do we solve a triple (C,u,v)? In other word, what should a triple return? Well, let's define the triple again.
(C,u,v) is the minimum cost required such that we're now at city C, we're not allowed to go back in time
further than this city, and we need to survey cities[u]..cities[v].
And now, the recursion will be presented in a pseudocode
//#PART 1#
if (u > v) {
//basis step, we have finished surveying all required cities
return 0;
}
if (cities[u] == C) {
//we survey city C
return (C, u+1, v);
}
answer = huge number;
//#END OF PART 1#
//#PART 2# NOT INCLUDED IN THE ALGORITHM FOR REASONS BELOW
//for each city D {
// //Perhaps we won't go back in time to city C, in which case...
// answer = min(answer, dist[C][D] + (D, u, v));
//}
//#END OF PART 2#
//#PART 3#
for each city D {
for i = u to v {
//we go to city D, and we'll return to C at i
answer = min(answer, (D, u, i-1) + (C, i, v) + dist[C][D])
}
}
//#END OF PART 3#
return answer;
PART 2 is not included to avoid cyclic call. If you want this algorithm to be able to work even without the presence of PART 2, we add a slight modification: we add 0 as the last city that we need to survey, if it's not there already. Seeing why this algorithm work is a bit subtle. First, we observe that for the initial case, we're fine since we can revisit this city as our last member in the cities that we need to survey. Otherwise, we can move only to important cities: cities that we're going to survey and cities that we're going to revisit through time reversal.
This 50^5 solution is risky to submit (since 50^5 is huge). However, we note that each of the computation is very simple and the actual complexity is somewhere near 50^5 / 4. So it's pretty fast and Maksay's solution which implements this idea passes the system test.
Solution the Second
So you're one of those programmers who seeks efficiency. Well, I know some said that we should look for the-stupidest-solution-that-work, but well, efficiency and elegancy are like aesthetics, yes? So don't worry, I'm going to guide you through the 50^4 solution.
Solution the Second has the same idea, but we notice that the bottleneck lies when we 'choose a city' and 'separate u,v' at the same time. So, this solution basically separates those two steps. Instead of choosing both simultaneously, when we're at a tuple (C, u, v), we separate that tuple into (C, u, i) and (C, i+1, v) first, then transform the first (or sometimes, both) into (D, u, i).
We create two triples, (C, u, v) and {C, u, v}. (C, u, v) is responsible for breaking down (C, u, v) into {C, u, i-1} and (C, i, v), while {C, u, v} is responsible for transforming into (D, u, v) (D may be the same as C). Both has the same stop condition as #PART 1# above. {C, u, v} is solved like the omitted #PART 2# above. (C, u, v) is solved like the inner loop of #PART 3# above. This works in exactly the same way as Solution the First.
And there you have it, our first 50^4 which, unfortunately, use two states. those implements this in his solution. But we haven't discussed about the most commonly-found algorithm in the contest, which is our final algorithm. It has a 50^4 time complexity and only one state!
Solution the Third
This idea combines both Solution the First and Solution the Second. The state is the same as in Solution the First, but uses the idea presented in Solution the Second. From each state (C, u, v), we can either go to (D, u, v) or break it into (C, u, i) and (C, i+1, v). Seems simple enough.
However, the transformation (C, u, v) to (D, u, v) makes our state cyclic. We need to stop that.
There are several ways to do that, perhaps the easiest is by constructing the state bottom-up with respect to v minus u. At each pair (u,v), we first break at each city (C, u, i-1) and (C, i, v) for every i. Next, we try to move from a city to other in the same (u,v), i.e., (C, u, v) = min( (C, u , v), (D, u, v) + distance[C][D]).
And this concludes our (short?) dicussion. The elegancy of this solution can be seen in rng_58's solution.
Solution the Fourth Thoughts
Only 31 coders survived this problem. The examples are not weak, but not strong either. The statement, however, was very 'challenging'.
Actually, I wonder if you guys found out the similarity of this problem with the Google Code Jam 2010 finals problem A. The 'time travel' stuff (as also found out by neal_wu near the end of the match) can actually be represented by a stack. Adding an element(city) to the stack has a cost that depends on the top element of the stack and the new element. Removing an element incurs no cost. What we want is to 'stamp' a sequence of elements using the top of this stack, while incurring the least possible cost.
That's a pretty long statement. So what's this problem about?
Dijkstra-s. And a lot of them. The solution below will be partially based on the description provided by ivan_metelsky.
Key Ideas
So, you guys have read the long statement. Clearly this is a shortest-path problem, but what are the nodes? We clearly can't use the pair (House, Time) since Time can go as far as 1,000,000,000. As usual, perhaps there's just a small number of important ones.
Let's move away from this and think of an optimal solution. This optimal solution will be a sequence of actions: traverse a road, traverse a road, go back in time, traverse a road, ... . It'll be a sequence of road traversal and turning back time. (Waits are implicit, we wait where it is necessary.)
Let's try to find the so-called 'basic states'. Each state will be a pair (H, s), where H is a house and s is either an element of sunnyEnd or 0 (this makes the number of states small). So a basic state means that we're at House H at time s. The key observation is that there exists an optimal solution that:
We will start at a basic state. (trivial)
At some point between two time reversal, we will be at a basic state. (proof below)
At some point between the last time reversal and house N-1, we will be at a basic state. (proof below)
Sketches of proofs (2). Suppose it's false. Then, for some pair of consecutive time reversal (for example reversal in house A and house B), the time at the end of traversing all the roads that we traversed between them is not one of sunnyEnd. Hence, we can reduce the time we reversed at house A by 1 and we 'shift' our journey by adding 1 to the times. We'll arrive at B 1 minute later but that's not a problem. The extra cost that we pay in B is the same as the less cost that incurred at A. Continuing to do this, (2) can be obtained. (note that this uses the fact that the times in some optimal solution will all be integral - which can be established fairly easily)
The sketch of proof for (3) is similar to (2) (but we gain profit instead of the costs 'cancelling' each other).
So, solving this problem is equivalent to moving between basic states. Movement between two basic states is either without time reversal or with a single time reversal performed at a house. We find the minimum cost required to reach each reachable basic state, and after finding that, we can count from all those basic states the time required to reach house N-1 without reversing time - the answer is the minimum of which. So we have bootstrapped the problem into this problem of moving between two basic states. This is our first Dijkstra.
And then we continue...
Before we solve the problem we just mentioned, let's precompute things. First, we would like to precompute the earliest possible time to reach a house HK from a basic state (H, s) without going back in time. This is simple Dijkstra (our second), for each triple HK, H, and s, we compute the time required to reach all other cities by initially setting min_time[H] = s. We can enquiry whether or not we're allowed to traverse a road without getting wet by simply traversing the list of sunny intervals. A Dijkstra implementation allows a complexity of N^2 * S^2 (N = number of houses, S = number of intervals). Let's call this Go(H, s, HK).
Weird as it seems, we also need to precompute another thing: the latest possible time from which we can reach state (H,s) from city HK (some call this a reverse-Dijkstra - our third Dijkstra). We can compute this similarly like how we compute the calculation above. We'll refer to this as RGo(H, s, HK).
Suppose we're going to find the minimum time to go from a basic state to another, say, from (H1, s1) to (H2, s2). The algorithm simply picks another house H3, where we're supposed to reverse back time in. First of all, we can simply not reverse back time, in which we can use the value of Go(H1, s1, H2) and mutate the value correspondingly (i.e., wait an appropriate amount of time). Otherwise, we brute force H3 and we compute the minimum time that we need to reverse in H3. How? Clearly we should reach H3 as quickly as possible from H1 without reversing time (since otherwise we can always wait at H3). And then, to reach the state (H2, s2) from H3, it's best to depart as late as possible (since otherwise we can always wait at H3). The amount of time that needs to be reversed can then be computed, Go(H1, s1, H3) - RGo(H2, s2, H3). We have precomputed all of these numbers, so this step should take N^3 * S^2 time.
And there we have it. The algorithm is surprisingly easy to describe. Implementing it is somewhat harder (I mean, three Dijkstras in a problem), but it's possible! lyrically succesfully solved this problem during the contest, an amazing feat!
Thoughts
So we have a 550 and a 1000. Some coders will then jump to the 1000 (since 550 are often deadlier-than-they-look). However, the 1000 this time is just as deadly and, well, some coders stumbled (out of the frying pan and into the fire). Perhaps we really should've signal that the 1000 is also harder than usual, perhaps using a score of 1025.
Many thanks to gojira_tc for pointing out the cities-but-should-be-houses mistake in the constraints so early in the match (anyone noticed that some parts of the constraints for the last three problems are similar?). It was fixed immediately and we received no other complaints!
Alternative solutions and additional comments.
rng_58 posted a very interesting approach which is much faster in this thread :).
No. A very simple case is a graph with three nodes as follows :
0 to 1 length 3
1 to 2 length 3
0 to 2 length 5
Posted by dolphinigle
at Dec 31, 2010 22:08Updated by dolphinigle
Thank you very much for such detailed editorial.
I do like problems by other authors too but some of them don't prepare editorials after the matches and this is sad.
If we have chosen i, we should pick j such that j != i and decay[j] is minimum right? So, what's wrong with simply picking the least value of decay? It's because maybe j == i. But then, how about the second minimum?
Hi, thanks for replying to my previous query.I have another question.
According to problem TimeTravellingTour:
"He wishes to survey city cities[0], city cities[1], ..., city cities[M-1] in this exact order (i.e., before surveying city cities[i], he must have finished surveying cities cities[0], ..., cities[i-1] in this order)."
Suppose I can only visit cities[i] by going through cities[j], where i < j. Does that mean that i should output -1?
Posted by dolphinigle
at Dec 31, 2010 22:08Updated by dolphinigle
Wondering, for TimeTravellingSalesman, is a shortest-path-spanning tree possible? Thanks!