Low attendance for this round, out of 1900 potentials, less than 1100 turned up. Apparently some people were having difficulty reaching the topcoder site just before it started so they delayed the start by 10minutes. I lost connection twice, once during debugging the first question and again during the challenge phase (I think it was my own modem even, not top-coder). But I don’t think it affected my performance significantly.
Writer solution for the 900pt problem was wrong… so it took a very long time to get any results…
346th before system tests – but I missed a corner case in my answer to question 1 and ended up with 0 points. Which dropped me down to 525th. I wasn’t going to advance or get a t-shirt in either case, so not a large drama.
Q1) Given a fully connected directed graph where you can change 1 edge value, determine the longest path taken by a greedy algorithm which always chooses to move to the closest remaining destination, starting at 0 with tie breaking based on order of input.
A1) I made my code more complicated than it needed to be, so my submission time was a bit slow (but apparently not complicated enough). Brute force is O(kN^4) (k being the maximum range of each edge value), which is too slow. However it can easily be seen that there are only a few interesting values to change an edge to. First is the maximum – this either eliminates the edge from consideration, or increases the maximum distance. Next is the highest value which makes the edge be selected. If the edge is already selected, this may still be higher than its current value. So at each point you can choose the second shortest path if the edge being modified is under consideration and try the value equal or immediately below, whichever is the highest value which makes it selected.
There are a few corner cases, making maximum doesn’t rule the edge out of consideration if there all other edges are higher index and maximum length and you can’t have an edge with length less than 1, so you can’t always make an edge selected either.
Specific case I missed was when forcing the maximum, the scenario where it increases the maximum distance rather than forcing a different option doesn’t just include where it is already maximum or it is the only option. It also covers the case where all other options are higher index and also maximum length.
Q2) Given a large number of points in a 2 dimensional plane where no x or y co-ordinates are in common, determine how many ways you can select 3 points such that if x coordinates are in order 1 2 3 the y coordinates are in order 1 3 2.
A2) The number of points is up to 30k, which rules out O(N^2) algorithms. Evidently the solution is O(N log N). I don’t think I’ve seen a problem like this one before, and the solution is kind of interesting. I certainly wasn’t going to guess it during the comp though… As a bonus, I completely misread the question and thought the x and y coordinates were in the same order (despite the question having a sentence explicitly calling out the fact that they were not…)
First do some range reduction, sort the x-coordinates and re-number them to be consecutive integers from 0. Then switch to sorting by the y coordinates.
Now we need to actually solve the problem… So we consider each point in reverse y order, first checking to see how many points already added have higher x then the current. Then we add the current point. At any point in time all points already added have greater y, so greater x is the criterion of interest. Then we add the new point.
The first trick being that we need to answer the question regarding the number of points already added with higher x, quickly. For this we use a range tree. Since we renumbered the x-coordinates, we know the full range, and can do a trivial sideways binary tree to cover up to the next power of 2 greater than the range. When an element is added, we increase the value of each segment which contains it. When we need to know how many elements are we look into the tree, summing any right branches whenever we take the left.
The second trick being all I’ve said so far only helps with choosing 2 points, how do we choose 3? Well we can take the number of values with greater x and do a choose 2, but while we know they have greater y values and x values, we don’t know if they actually are ordered correctly themselves. So we need to keep track of how many pairings greater than a given are the wrong order. Since the wrong order is that they are sorted, and we know how to count the number of elements greater, this is not too hard. Just have another segment tree, but rather than giving unit weight to each number as it is added, weight it by the number of entries strictly greater then itself at the time it was added. Thus the total of these is a count of all pairings in sorted order, which we can subtract from the choose 2 to get the correct answer.
Don’t think I’ve seen a question involving a segment tree before at all even – I’ll have to keep them in mind in future.
Q3) Given a list of heights, and the rule that at each time step positive heights shift 1 unit of height to the next entry in the list (circular so last moves to first), determine the new list of heights after a very long time.
A3) I think I should have put more effort into this question, because it certainly seems easier than Q2… The solution is to simulate it, but jump forward in time by the largest step you can at any point.
At any point if everything is 0 or negative, you are done. If everything is positive, you are done. If everything is 0 or 1, you can rotate the solution to finish. If everything is 0 or greater, a few simple simulation steps will either make everything positive, or just 0 and 1.
So the only interesting scenarios are the ones which involve a mix of negative and positive numbers. In these scenarios, you can jump ahead, so long as you don’t fill any holes or clear any mountains, since that changes the dynamics of the scenario.
We can rule out a few corner cases by forcing step by step simulation if the number of turns remaining is smallish. Also if there are any 0’s between a mountain and a hole, some manual simulation will take care of that. Then, for each hole we follow left to find the left-most contiguously positive position, and skip ahead a number of steps equal to the minimum of what fills the hole or reduces the height to 0. The minimum of all these minimums is the number of steps to simulate, which can be done just by subtracting the number of turns off of the left-mountains and adding them to the connected holes.
I think the worst case runtime of this algorithm is something like O(N^3) – finding the connected mountains is linear, but the manual simulation sections might be O(N^2). However since one mountain or hole is eliminated in each step, there shouldn’t be more than O(N) such sections.