Author: Tilps

My first non-competing round of the season… will see how many of these I bother to write up – if previous years is anything to go by, not many!

Q1) Given a set of tasks which each have a time to complete, and percentage chance of failure, determine the order which minimises the expected time to completion if failure of any task means you have to restart your order from scratch.

A1) This was a sneaky question, not insanely difficult, but they set the restrictions on the small input that the time to complete of every task was identical.  In that scenario the solution is trivial, you sort by most likely to fail to least likely to fail (using a stable sort, or secondarily sorting based on original index).

The large input isn’t much more complicated, the only question is what is your sort operator look like when the times of the tasks are not identical.  Unfortunately my initial guess would have been length of task times the chance of failure, when the correct answer is length of time divided by chance of success. Fraction class works here, or you can define your sort operator as a.Time*(100-b.FailChance) < b.Time*(100-a.FailChance).  Pretty sure I’ve seen this question somewhere before…

Q2) Given a hexagonally shaped hexagonal grid and a series of ‘moves’ which fill in hexagons, determine the first point in time that either 2 corners are connected, 3 edges (which don’t include the corners) are connected, or a ring is formed. (A ring is a connected loop of hexagons where there is at least 1 empty hexagon inside.)

A2) The large input has a hex grid with side lengths of up to 3000, and 10k moves, so the implementation needs to be reasonably efficient.  Having written LoopDeLoop, I’ve had opportunity to consider similar problems in the past, so I think I had a chance of solving this problem if I had of been in the round.  We can solve the 3 sub-problems independently, but there will be a common theme.

Corners. if we use a union-find data structure and associate properties with each set representative (specifically the number of corners the set touches), we can do this in linear time. Each move is handled easily Each surrounding position is either empty or a member of a set.  Gather the number of corners for the distinct sets, union them all together, add in the new position and set the number of corners equal to the total (adding 1 if the move is in a corner).  If total exceeds 1 we are done.

Edges.  Almost identical to the corners, only instead of summing, we use a 6bit number to represent the edges touched, and use bitwise or to combine them.  And rather then checking total we do a pop-count.

Loops.  Here is the tricky bit.  Again we can use the union-find data structure, but this time rather than aiming to union things together and track status, we are looking to see if the current move has 2 neighbours which are already in the same set.  There is also the possibility that the move doesn’t create a loop, but just fills in the edge of a ‘blob’.  If precisely 2 of the neighbours are the same set, and they aren’t touching, we have definitely created a loop.  If 3 of the neighbours are the same set and they aren’t ‘sequential’, we’ve created a loop.  If 4, same applies.  If 5 or more there isn’t anyway to not have them sequential (and specifically 6 can never happen since it is already a loop).  Edge and corner placements don’t really change this logic, although you certainly can’t go all the way to 6.

Plenty of opportunity to screw up, but overall I think I had a better chance here than with the large input of the first question…

Q3) Given a delivery fee per delivery, and cost of types of food, and length of time until stale, how long can you eat delivered food given a certain amount of money.

A3) For a given number of days to survive on a single delivery, the answer is fairly obvious.  For each day take the cheapest food which would not be stale.

The problem comes in deciding how many days to go between deliveries.  Obviously if a type of food exceeds the cost of the cheapest food plus delivery fee, that type of food will never be selected, but since the delivery fee is averaged over multiple days the crossover point could be lower.  It wouldn’t be too hard to do an infinite money scenario maximum efficiency but for a finite amount of money the problem is trickier.

The large input is huge, 10^18 money and up to 10^18 stale time.  But the number of food types is much smaller, only 200.  I looked up some solutions, and the one which I think most matches where my thinking was heading is assuming that the solution consists of d day cycles or d-1 cycles to make up the total number of days achievable. Binary search to find the maximum number of days, and ternary search inside that to find the minimum cost to complete that many days.  If minimum cost is below the total amount of money, binary search goes up, otherwise it goes down.

Q4) Given a sequence of characters, some of which can be substituted with numbers, determine the length of the shortest string which contains every possible length k consecutive subsequence of the original sequence or any of its substituted variations.

A4) Large input has k up to 500, small input is only 2.  Small input we can build the list of distinct pairs, including substitutions.  Then you have to work out how short you can make the joining.  For each distinct pair you have to have at least 1 character in the output string, but do you need 2?  For each unique character in the input we can count how many pairs start with it, and how many end with it.  The difference (if positive) is how many times you can’t reuse that character.  Finally even if you could theoretically reuse everything, there is always the first character, so there has to be something which can’t be reused. (I read a solution because I wanted to finish writing this blog post before 1am… but I don’t think this is too hard to come up with…)

The large input, I have no clue!  Unlike with the size 2 input, you can have multiple different length overlaps to save you characters.  (Not to mention that 500 character sequence can have 2^500 versions using substitutions…) Only 1 person solved this during the competition, so I don’t feel to bad…  Turns out he used a mincost/maxflow, although I certainly am not going to read the pages of code to try and understand how mincost/maxflow solves this problem…

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.

So, this post is a bit delayed – I actually had to do this round from a hotel room on a 13inch macbook – with no mouse.  Far from ideal conditions and maybe they contributed to my just missing out on making it through to round 3.  9th placed Australian, in 543rd place.  Tikitiki and Aussie got great starts this round, I think they must have seen some of these kinds of questions recently or something…

I started by reading all of the problems first, thinking maybe it would be useful to have my mind mulling them over in the background while I worked on the first problem.  So my first problem submission time was not great.  Second problem had me stumped for a while, but I eventually got my head on straight and realised the solution was pretty easy after all.  But it only left me 30minutes to try to get one more small input.  I figured I needed to go for Q3 to be safe as it seemed easier and was worth more points.  It probably was a good decision, but an amazingly stupid mistake while solving an equation for x left me with code that was crashing with 2 minutes left on the clock.  I realised the problem at 1minute left, but wasn’t fast enough to fix it.  (Also there was one more issue which I didn’t realise until the next day, but it is possible my solution would have passed the small input tests anyway.  Getting it right would have been a top 250 placing, which would have been great.)

In any case I have a nice new t-shirt, which was the only prize I was going to get… in this competition anyway…

Q1) There are ropes hanging down from points.  Each rope has a given length and given position.  All hanging points are at the same level, which is the same level you start at, and the same level of your destination, which is a specified location past the last rope.  You start off holding the first rope.  You can swing out and grab any rope in your path.  Having grabbed a rope you can pull yourself back up level with the hanging points to any place between the two hanging points (limited by the length of the rope you grabbed).  Given this can you reach your destination?

A1) Key to this puzzle is realising that your best way to get to a rope, is from the rope closest to the beginning which allows you to reach it.  So you create an array which is the maximum length of rope for each rope which you are able to use.  First rope is easy, since you start off holding it.  It sweeps out a section ahead of it and you can fill in the maximum lengths for those.  Then repeat for the next rope and the next rope – until you either find a rope which you can’t reach, or are able to reach the destination.  By starting your search for the sweep from immediately after the last location filled in (which are all guaranteed to already be right due to the above explanation) and exiting as soon as you exceed the maximum length, you ensure that the running time is O(N), which is kind of important if you have a slow programming language as the large input has a maximum number of ropes of 10000 and the simplest approach can be O(N^2).

Q2) Given a list of circles of specified radii, determine how to place their centres in a provided rectangle such that they do not overlap.  The rectangle area is guaranteed to be at least 5 times the sum of the areas of the circles.

A2) With the large input being up to 1000 circles, and the circles being fairly large variability in radius, it seemed likely that some kind of brute force filling was probably going to be too slow.  In hindsight, I am not sure this is actually true.  O(N^2) with 1000 is trivial enough you could probably just place them in a row across the top long edge, and then try and fill new rows in, shifting towards the top long edge as far as possible based off an exhaustive test of the existing placed circles.  I don’t see any reason why this would have troubles with space given that there is about 4 times the space you need.  But I’ll include what I did for completeness.

First sort the circles from largest to smallest (something which would probably be important above anyway).  Then start rows just like as described before, but rather than trying to push them upwards, try to fill the rows height by stacking circles above one another within the row, if the circles are small enough.  This keeps the rows self contained and stops you from having to consider any circles other than the last one you placed in the current and last ‘column’.  This gives O(N) for the filling stage, so performance is dominated by the sort.  Packing density in this approach is at worst ~pi/8 which is far greater than 1/5.  To be safe I special cased long thin scenarios by just lining all the circles in a row, but I think my implementation actually handled them just fine.

I got 2 penalties on this problem, 1 because of some mistakes in my coding, but the other 1 was because the outputs had to be in the same order as the input, and I had forgotten that I had sorted the inputs…

Q3)There are a series of hills each exactly 1km apart.  From the peak of each hill, looking out towards the next hill (from ‘left’ to ‘right’), one of the hills has the greatest angle relative to straight down.  This hill ‘appears’ to be the highest, even though it may not actually be the highest.  Given for each hill which following hill appears to be the highest, determine a set of integer heights between 0 and 1 billion which satisfy these criterion.

A3)  The large input had up to 2000 hills which I determined was going to be problematic.  My approach was to work from right to left, determine the height range for each hill which caused it to satisfy the criterion and choose any point in that range.  The trick being that the range is not guaranteed to contain integers, or be positive.  The later is easily fixed, just shift every mountain upwards.  The former is of concern.  I figured that worst case the range might involve fractions where the basis was of the order of n! where is was the number of hills.  Which for n=10 was plausible, so I could just multiply the fractions up by their basis top make them all integers.  With a maximum of 1billion, that would be fine.  (And in fact the test cases I received only needed up to about 100k).  For 2000 hills this is very unlikely to work.  Finding the smallest fraction base in a range might have made it feasible, but I don’t know how to do that quickly.

My solution failed because solving for the range involves finding the minimum height such that the current point, its highest and a point behind that are co-linear.  And the maximum height for current point, its highest and a point in between.  I wrote out the equation for two lines having same slope, which with a common point means co-linear.  I then solved for the height, but somehow forgot that the height was in both sides.  At runtime this showed up as a divide by 0 error, because my height fraction was uninitialised on the right hand side and internally was equal to 0/0.  Kind of confusing trying to debug this with less than 3 minutes left on the clock.

The other bug I had was the minimum and maximum are technically inclusive and exclusive bounds, because the conditions state that in co-linear case you see the front-most.  But if you actually use that inclusive bound (and you don’t have to) you can later incorrectly decide that there is no valid option because the middle of that co-linear can no longer be the highest for any future point, but if you didn’t make them co-linear you could point at it directly just fine.  I think a few more minutes would have let me solve this one…

The large input…  I’ve had a few ideas, the best of which is as follows.  Every position which sees a given peak as the highest, can be given equal height.  Starting from the right, choose the minimum positive slope which lets all of them see that peak and nothing beyond and gives them an integer value.  By construction it should be fairly(?) obvious that this solves the problem as all the problematic cases are where its impossible to solve anyway…  The only question is whether the range of heights constructed exceeds the 1billion.  I think it can be shown that the worst case has a height difference of O(N^2).  Running time is theoretically O(N) if you first group them by which mountain they can see.  You also need to first validate the input that it doesn’t make impossible claims, which is that the ranges which claim a two different peaks as highest are mixed, not adjacent or fully contained.

Q4) Given a rectangular grid of squares, some of which are ‘caves’, others are walls and others are just empty, determine two things.  Firstly which (how many) empty locations can reach each cave given down/left/right movement (no up) and secondly, does there exist a sequence of moves which moves every element which can reach the cave, to the cave.

A4) I am certainly glad that I choose to work on Q3, because even the small input of a 10×10 grid (which is 8×8 in practice because the outside edges are always walls) has solutions which are ~32 steps in length, and there are 3 possibilities at each step, and all of them can be possible.  So a pure brute force is something like O(n^2*3^(n^2/2)) which is insane.

I thought about this for quite a bit after the competition, and didn’t come up with anything which I was confident of.  So I consulted the contest analysis.  Key points are there is no need to back-track, you just need to ensure you don’t move in an invalid way. (Which gives a randomized solution, you randomly choose between valid moves until you win, but it could take a while…)  If you can move down, and there is something to move down, you might as well move down.  Moving left/right never take you outside the valid states, so you can move all left/all right to consolidate each row into a single value.  Then it just becomes a matter of moving those rows to some point where you can move down.

So, to recap.  First move everything full left, if you can move down usefully, then move down.  Otherwise step right and try again.  Keep trying until you hit a right wall on one row, then sweep left, remembering where you were, then go back to where you were and go right, and sweep left again, until you get to full right and a final sweep left.  This covers all the possible scenarios.  If you manage to go down, go back to the beginning until you win or fail to find progress.  What is the running time of this?  I think it is O(N^5) which should be fine for the large input which is N=30.

I got a successful challenge this round, don’t know how long it has been since that last happened… 347th before systests, I managed to move up to 292nd afterwards.  Quite a few failures in the second question, wish they had been in my room so I could have challenged them too… 😛

My TopCoder rating is now up to 1836, almost a personal best… (although still quite a ways short of where I want it…)

This is the second time I’ve scored as well as was needed for a t-shirt in previous years (292nd is a virtual 342nd after you allow for the 50 already through – although I got a higher score today than 3 of the 11 who bothered to compete in the parallel round for advancers).  If I make it 3 from 3 and don’t win a t-shirt I’ll be rather disappointed – and I didn’t even sneak a completely invalid solution past the system tests this time 😛

Q1) Given the numbers 1-N which are placed in some order where you only know where some of them are, what is the minimum number of picks of spots to guarantee you reach a target value. (Target value is large.)

A1) I think this problem is relatively greedy.  First up there are either 2 things you are going to do, pick the highest known value, or rotate through all the unknown values.  It never helps to choose an unknown value over and over, because it could be the minimum of the unknowns.  So I can see 3 strategies.  1) You simply use the highest value forever. 2) You simply rotate through the unknowns forever, presuming you get the smallest of the unknowns on your last rotation.  3) You rotate through the unknowns for as many full cycles as possible, then use the highest known value until finished, because the last cycle as partial, might have a lower worst case average than the highest known.

So try each of the 3 scenarios, and choose the best.  Handling corner cases like no unknowns or all unknown.

Q2) Given items of known weight, and the following game, determine the outcome if both players play optimally.  Each turn players can move a specific number of items from their pile to the opponents pile, these numbers are provided.  If their pile doesn’t contain that many items, all items are moved.  The first turn however is player 1 chooses which of the starting set of items (also provided) is placed into player 2’s pile.  Assume that the aim of the game is to maximise the weight of your opponents pile minus the weight of yours, and in equal situations both players aim to maximise the total weight. Items have a large weight range.

A2) I managed to solve this problem, but I didn’t get my implementation written in time.  This was also the problem I managed to get a successful challenge on.

First up is to realise that the game is entirely greedy and easily determined after the first player chooses the initial items.  At any point in the game you will always give your heaviest items to the opponent, there can be no benefit in giving the lighter ones.  So you can take a list of indexes for a virtual sorted array and simulate the game to see which indexes end up in each players pile.  Now player 1 has to maximise their score, and for equals maximise the total weight, by assigning individual items to these indexes in sorted order.

So start by sorting the provided items by weight- it is now a fairly standard DP on maximising a valuation of selecting an ordered subset.  However there is a small complication that some indexes cause negative value, and others positive.  But it doesn’t actually change the DP structure, you just want to build a lookup table of index to whether it is positive or negative multiplier.

Small tip I got from one of the solutions in my room was to make the DP table member type a custom class indicating the piles and write a custom comparator to compare the difference, or sum if equal.  This means you don’t have to reconstruct the piles from scratch after you have finished your DP like I was going to have to.

Q3) Given numbers of the form a*x+b from x=1 to x=n, concatenated in their minimal length binary representation, how many times does the sequence change from 1 to 0 or vice-versa. b and n are both huge, a, not quite so much.

A3)  This was only rated at 900 points, but I have no clue how that makes any sense…

The last digit is going to have a trivial sequence,  so tracking how the concatenation affects the result isn’t too crazy, but tracking the internal changes is still going to be problematic.  Definitely going to be some pattern, but it isn’t going to be trivial.

Looks like the correct approach is to process the multiples in sections of powers of 2, but from there it gets complicated and I definitely need some sleep.

So I didn’t have to do this round either, but it had some nice questions.

Q1) Given an acyclic directed graph determine whether there are any pairs of nodes with multiple paths between them.

A1) So the obvious approach is to depth first search starting from each node, and if any DFS ever sees the same node twice there is multiple paths.  This is O(N^2) since you have to run DFS over and over.  Given constraints that will be fast enough, but certainly isn’t optimal.  One sub-optimal improvement is to only run the DFS from nodes that have no nodes pointing to it. I think the optimal approach is to compare the sum of edges to the number of nodes  If it contains no multiple paths the number of edges will equal the number of nodes – 1. (But my graph theory is a bit rusty, but I think that criterion applies in this case.)

Q2) Given a car which has a maximum positive acceleration (spontaneous reductions in velocity are fine) and a lead car which cannot be passed, if the lead car travels at constant velocity between known points at known times, what is the earliest the first car can get to the end of the road.  Answer the same scenario for multiple different maximum accelerations.

A2) This question is a ‘simple’ simulation, checking for quadratic equations crossing linear equations of motion to know when the lead car is limiting the first car.  The large input is 2000 known points of time and 250 different maximum accelerations, and there are up to 100 test cases, but even so I don’t see there being a performance problem using brute force.

Update: Actually it isn’t as simple as I make out above, the most obvious approach is in fact incorrect, which is possibly why this question was the least commonly answered, and not just that the question text was presented in a way which seemed to maximise confusion.  If you try to move as quickly as possible at all times, you will in many scenarios end up slower then optimal.  The thing to optimise is not your forward position at each point in time, but instead your velocity at the time when the lead car increases speed.  If you catch up to the lead car you are guaranteed to be doing the same speed, when if you waited at the start, you could be travelling faster.  In fact the optimal strategy is to delay start for as long as needed, to maximise your use of acceleration to ensure you are always fast, but never hit the lead car.

Checked the solutions, I see brute force simulation.  The simulation can be simplified to tracking the maximum difference in arrival time at a point of the lead car and the time the other car would have gotten there if the lead car was not a problem.  Then just adding this to the minimum travel time for the car. But that isn’t significantly faster then the full simulation – the only question is whether you could get accuracy issues accumulating rounding error over 2000 segments doing the full simulation.

One other sneaky point is that the places and times for the lead car may include points beyond the ‘end of the road’, they need to be truncated appropriately to get it right.

Q3) There are two sequences of elements, which are very long, but only change element types at most 100 times, so there are very long runs of elements.  You start by taking the first element from both sequences, and proceed by either pairing matching item and taking 1 new from each sequence, or by throwing one item away and taking the next item in that sequence.  What is the maximum number of pairings you can perform?

A3) At first glance this appears to be a classic dynamic programming question, but it is not quite so trivial.  The trivial DP on index in each sequence, won’t perform usefully since the sequences are up to 10^18 elements long, and a DP purely on the segments isn’t going to work since one segment from the first sequence might match against 4 segments in the right sequence in the optimal solution.

So what can we do?  Well I think what we want is something in between.  Do a cached recursion based on index, but use acceleration to avoid the 10^36 running time that brings.  So no array cache, this will need a dictionary cache.  To simplify the logic the recursion parameters will be current segment and offset into the segment, since raw offsets will require searching the list to determine the segment details, which will likely cause performance to suffer by too much.

So what do I mean by ‘acceleration’?  We need some strategies that deal with a lot of elements in bulk, and do so in a consistent manner which doesn’t lose the optimal solution.  First up is if the current segments match, we will pair, we will never throw away, so we can accelerate forwards on both sequences to the end of whichever of the two segments has the least remaining.  If they don’t match there are 3 options, throw away every element of the left segment, or every element of the right segment, or both segments.  This later scenario can be ignored as it will be found by the other two unless it results in mandatory matching of elements, in which case it wasn’t the optimal solution anyway.  The reasoning here is that throwing away part of a segment now, is the same as not throwing them away and then throwing away the leftovers after doing some matching, just a different order of operations with the same outcome.

The running time of this algorithm isn’t immediately obvious, but I think it is no worse than O(N^4) where N is the number of changes in the sequences, which should be good enough.  You can even remove the first assumption that you always pair if available, although I think it is fine. Update: Actually it might be O(N^6) which would be a problem, for two reasons, one it would be too slow and two it would use more ram than my machine has available.  I did see a solution which passed which used a very similar approach, so I think the theoretical scenario I am thinking of may be practically impossible and the solution space is actually very sparse. Specifically if you do include the greedy match assumption, it probably makes it very difficult to break.

Another approach I found looking at solutions is to use the explicit DP on the segments, but to handle matching segments in a special manner.  Rather than storing an index into the segment to handle partial segments, realise that in order to use that segment to match against multiple other segments on the other side, you have to throw away any non-matching segments in between.  So whenever you have matching segments, you can try O(N^2) scenarios to skip both sides ahead gaining whatever matches of that type in the area skipped.  By trailing all these scenarios, you still get full coverage.  This solution is clearly O(N^4) which is likely a bit faster than my first solution, and definitely uses less memory for the cache.

So, I didn’t have to do this round, but looking at the scores it was very competitive.  Probably harder to advance than R1A.  Looking at the problems I think there were all theoretically in my grasp, except for Q3 large input, I might have missed the key insight, and probably wouldn’t have been game to try a solution based on random numbers.

Q1) If each item receives 2 scores – 1 fixed, and 1 a variable fraction of the total of the fixed scores, what is the minimum fraction for each item to guarantee that regardless of how the other items receive their fractional scores, that item will not have the distinctly lowest total.

A1)  I see a couple of options here.  But first some analysis of the question.

If we give a specific fraction to an item, what is the worst case competition for it?  Giving points to everything lower than it until they all equal the new value, and still having a non-zero fraction left. (Since that non-zero fraction can be divided amongst all equals to push them above.)  So, if we have the items sorted by their fixed values, we can go from smallest to largest, skipping the current item under consideration, subtracting from the available percentage as needed until we get to an item which is above the target sum.  This is O(N).

The above suggests we can use a floating point number binary search to find the threshold, giving about a 20*O(N^2) to get sufficient accuracy for all of them. This would be fast enough given the maximum constraint of N=200.

A more direct approach solve numerically.  In between each step from one distinct fixed score to the next, the problem is a linear equation.  If the answer for the linear equation lies outside the range, you move to the next step.  Again this is trivially O(N), for each item, making O(N^2).  In fact we can do a binary search on these segments, giving O(log N) for a total of O(N log N) for that component, but only if you can change the segments from one scenario to the next in O(log N) time or better as simply constructing the segments is O(N).  If you construct the segments for every item, then the segments for each individual scenario is either the same with the counts above a given point reduced by 1 or two adjacent segments are joined.  This later scenario can actually be ignored and treated like the first, the two linear equations  will be the same, but testing them both is no significant loss.  It is easy to embed the former logic into the linear equation, so we can indeed reuse the same segment list, giving us our O(N log N) running time.

Q2) Given a rectangular grid of cells where each cell has a floor and ceiling height, and a water level, and a requirement that to get from one cell to the next you can’t pass through an edge without at least a 50cm gap (either current ceiling/destination floor/water or current floor/water/destination ceiling or destination ceiling/floor) you want to get to the south east corner of the grid as fast as possible once the water starts dropping.  Every second at some future point the water level will drop 10cm.  It takes 1 second to move from cell to cell if there is 20cm of water above the ground in the current cell, otherwise it takes 10 seconds.  Starting from wherever is currently reachable from the north west corner of the grid, what is this shortest path? (No diagonal movement.)

A2) Ahh, interesting problem.  Especially since the large input makes the grid up to 100×100 in size.  Suggests a shortest path algorithm, but the edge cost changes as a function of arrival time.  Lets do some more thinking.

Firstly, it should be apparent that we never go back the way we came once we start.  More specifically because the best travel times only ever get worse the later we arrive, there is never any benefit to being somewhere at a later point in time then the earliest arrival.  This suggests shortest path will be fine, with some small modifications.  Finally there are no negative travel times, so we don’t have to worry about that complexity when it comes to shortest paths.

We can reach anywhere reachable from the start at time 0, so simply depth first search to determine what is reachable and initialise a grid with 0 at those locations and maxvalue at all others.  Add all reachable locations to an updateable priority queue.  Now we perform an earliest first search, at each location we determine how long to reach each of its 4 neighbours relative to the earliest arrival time for that cell which will either be wait+1 second or wait + 10seconds, where wait is how long until the water drops low enough to make it passable.  Wait could be 0 seconds if already passable, or infinite if it will never be passable.  If the new arrival time for the destination is lower than the current value, update the priority queue.

The code to calculate the wait isn’t exactly complicated, but it does have a number of criterion and would be a likely place to make a mistake.  It is also where you have to handle not leaving the edges of the grid.

This gives us the all points earliest arrival time, including the south east cell, which now contains the answer.  So what is the running time?  Initial search for starting points is O(N*M) or O(V) (V is total cells, or ‘vertexes’ in the graph.)  From there we run an earliest first search using a priority queue.  Lets assume we use the LookupHeap from TMD.Algo, this has O(log N) add/remove of any element.  The number of priority queue updates/adds/removes will be at most O(E).  E is the number of edges, which has an exclusive upper bound of 4V, effectively making it O(V) priority queue manipulations for a total of O(V log V).  Despite V being 10k this is quite reasonable.  The other component of running time the determination of wait, is easily O(1) per edge, so it is not significant.

Q3) Given a set of distinct positive integers, determine if there are 2 distinct subsets which have the same sum.

A3)  Pretty simple problem statement, but the large input has 500 integers each up to 10^12 in size.  Small input is more reasonable, 20 integers with 10^5 each.  Only up to 10 test cases in both scenarios, so plenty of cpu time available for each test case.

Small input approach.  The most(?) obvious brute force is going to be too slow, dividing into each possible set of 2 groups, then determining the intersection of every possible sum of those groups is something like 2^40.  However almost as obvious an approach is to break it into 3 groups, if the sum of all elements in group 1 equals all elements in group 2, we’ve found the solution.  Group 3 is ignored.  This can have a running time of O(3^N).  Which is quite high, but given only 10 test cases, and 4minutes to submit, it is plausible if optimised. Important part of the implementation is to not calculate the 2 sums directly for every scenario, instead, mutate them as the scenarios change, adding and subtracting.  This ensures the implementation isn’t O(N*3^N) which would almost certainly be too slow.

Large input approach… hrmm.  Well caching on the small input implementation gives us O(N*distinct number of sums) which doesn’t immediately give us anything, but we know the range of the sums which gives us an easy upper bound of O(N*(kN)^2) where k is the maximum value.  For the large input this is a considerable improvement over the O(3^N), but still longer than life of universe type processing times expected…  But it does tell us that as we get large inputs, the probability of there being a common sum approaches 1, maybe even is 1 by pigeon hole principle.  Maybe this will be useful.

So I looked up an answer to get a view into this question and I found a very important detail which I overlooked.  If you have 2 sets which are not equal which have the same sum, you can remove all the elements in common to get 2 new sets which are distinct and have the same sum!  Now we just have to find 2 distinct sets with the same sum.  This insight also allows the small input to be done in O(2^N) by using O(2^N) space as well as time.  It also lets us prove that the probability of common sum is 1.  2^500 is greater than 500*10^12, so there are at least 2 different subsets which have the same sum, and hence 2 disjoint non-empty subsets with same sum by removing any common elements.

Here is where the certainty comes in, if we do random guesses, and store the sums in memory until we find a collision we can get a very high likelihood of passing tests just by making enough guesses.  Birthday paradox means that despite the potential 10^14 different sums, the probability of collision is quite high with only 10million repetitions, and extremely high at 100million. (And even higher considering the difficulty of constructing a set of numbers which evenly spreads sums across the entire range.)

Another approach I saw in solutions with less random in it…  If we sort the input then break it into sections of length 20, then determine every subset sum, then choose the 2 closest sums we end up with 25 sets of distinct subsets where we can use the sum difference as individual values to calculate every subset sum.  If we find a collision then we can construct the subset.  The idea here appears to be that we’ll end up working with a much smaller size numbers by finding the smallest difference in each section, so the probability of 0 sum is increased significantly in the second set of summations.  Again this really seems to be a probabilistic approach, but apparently good enough that you don’t need to randomise the data.

So, I thought I knew my way around a red-black tree, maybe not great, but I’ve implemented it a few times now.

The contest analysis for Q3 in GCJ12 R1A states that the question can be performed in O(N^2 log N) time, but leaves how as an exercise to the reader.  I decided to take up this challenge, and came to the conclusion that what I needed was a data structure which took items which have an order, and could join/split subsets of that order in log(N) time.

I actually thought I could do such a data structure with O(1) join/split – but then I realised that I needed to associate state with the joined groups, and hence the split operations were becoming O(N) or accessing the state would take O(N) if I started from the wrong node.  So I went back to the drawing board. As is often the case when you see a solution with O(1) for some operations and O(N) for others, there is a way to do somewhere in between for all operations and it often involves trees…

So, if I represented each connected section as a binary tree, I could get from any element to the root of its section, and associate the state with that root, giving O(log N) lookups.  Good start.  But what about the joins and splits?  Could I join a binary search tree with another adjacent one in O(log N) time, or even worse, can I split a binary search tree at an arbitrary point in O(log N) time?  I felt the answer was going to be yes, and not just because of the Contest Analysis suggestion of a O(N^2 log N) lower bound.

This called for some research, and it didn’t take long to find a couple of papers describing how to do concatenate and split in red-black trees.  The first one was confusing me, it kept adding nodes to the tree, or removing them and not putting them back. (And the PDF had the pages in reverse order!)  But the second one was much clearer, and explained that the former was using a variant of red-black trees where only leaf nodes contained values, and how to augment these algorithms to work with what I considered a more standard red-black tree approach.

So, off to implement I went.  For my new data structure I decided to reuse a single memory allocation containing all the tree nodes, and perform the splits/joins and manage the multiple trees all in the one array.  This held promise of best performance, something of a target considering I am going to make this part of TMD.Algo’s next release.  But… it did mean I had to write my red-black tree logic from scratch, since my other red-black tree implementations all use heap allocated nodes and pointers and sentinel nodes.  This took a while on its own, and since my data structure only has 3 API members (Add, Union, Split) – and I had only written 1 (Add), it was not very favourable to testing yet…

Union was up next.  Union requires the Insertion fix-up logic from a standard red-black tree, but is otherwise not actually that hard.  First, remove the left-most element of the right tree.  Then spend another O(log N) steps to find the black-height of both trees, and the black node on the higher tree which is the same height as the smaller tree.  Then you take that left-most element you removed, make it red, and add the two nodes with equal black-height you have identified as children, then add it back in to the taller tree where you just stole a sub-tree to use as a child. (Unless they trees are of equal height, then there is nothing to add it back to.)  Pretty simple, but still you end up with 3 code paths, and having to handle corner cases like the right tree being a single node to start with, or either of the trees being entirely empty.  At this point my code got its first real test-case, but it was hardly capable of stressing much.  I was probably a couple of hours in to writing code at this point.

Split.  When I first started this journey, I didn’t expect split to be all that much worse than Union.  But it certainly was!  The description starts out simple… Walk the tree from the root to the split location.  At each node you visit, you are either at the target node, or the target node is to the left or right.  If the target node is left, union the right sub-tree with the right split result (starts as null) and store the current node to use as a pivot for the next union rather than having to take the left most element out of the right tree.  Similar (but reversed) for if the target node is right.  And if the target node is equal, do both, but then add the current node to the left tree (or right if you want) rather than storing it to use as the next pivot.

The devil is of course in the details.  In order for this Split algorithm to be O(log N) the unions have to be performed in O(1) time.  But the Union implementation takes O(log N) time?!?  Also not mentioned is that you have to handle cases where you’ve stored a node as a pivot, but when you get to the point where you would use it the current node has no right sub-tree, or you have no accumulated result tree, or both…

But back to the performance problem – how do we do Union in O(1) time?  Well it gets mentioned that if you augment your tree with black height information in each node, and keep it updated through all the insertions and stuff you can do Union in time equal to the difference in the height of the trees.  Because when it comes down to it, Union is O(1), you just have to find where to perform the union itself.  But keeping track of the black height as part of the nodes isn’t exactly trivial, and so I went with the approach suggested in the paper I was reading, which was to track the relative heights between the items which you are merging.  You can even start by saying that the original root node of the tree is height 0, since it is only the relative heights that matter and a red-black tree starts with the property of every path having the same black height.

This is still easier said than done! Black height of the current node, that is easy, you just decrement it by 1 each time you leave a black node.  So you know the black height of that right (or left) sub-tree you want to concatenate with the (right or left) result easily enough.  But what is the effective black height of the (left or right) result, and how can we be sure that the difference in heights is effectively O(1)?  It was at this point that I had to do some actual thinking, because it wasn’t expanded upon in the paper.  The first sub-tree was easy enough, we knew its black height when we got it, so we just stored it, and the height difference between it and the next sub-tree is going to be at most equal to the number of steps between sub-trees being on the same side.  This isn’t O(1), but clearly the sum of these O(steps) is at most O(log N), which is the goal.  This however will only work if we can move between the first sub-tree and the next in O(steps).

So what happens when we union these trees?  We know there is a pivot, we know that the pivot’s black height starts as the same as the smaller tree (and the trees that we are joining are in non-increasing height sequence, so that is always the newer tree for which the black-height is easy to calculate), since the pivot is always red to start with.  Will this pivot always be on the outside edge of the tree once we have run the insertion fix-up, and will it always have that same black height?  The answers to this is yes and no respectively.  Most scenarios just recolour, but there can be rotations.  However, these rotations all occur at the parent or grand parent level.  With the parent level rotating to push the pivot down the outside and the grand parent level to pull it up the outside.  The recolouring also occurs at parent levels and above, so you might think the black height won’t change either.  However there is one exception, if the pivot is or becomes the root of the tree, it gets forced to black to maintain the root node is black requirement.  This increases the black height by 1.  This increase by one is worst case going to double the cost of walking to the next join point (1 step becomes 2), so the order of magnitude hasn’t changed.

So, we can use the pivot point, and we can track its black height efficiently.  All that remains is to put it all together, handle the black heights in the corner cases where there is no sub-tree and trying not to make too many errors writing almost the same rather complicated logic 4 times.

Now that I had ‘Split’ I could write some real stress tests.  I like to have a random (with fixed seed) test which runs a large number of repetitions for cases like this, because manually identifying all the corner cases to write test cases for is harder than writing the code!  I started out with 1000 elements and 100k random operations.  The first time I ran my test case it crashed on operation 1.  (I hadn’t handled splitting something which wasn’t unioned.) and it wasn’t long before I realised that 1000 elements was too many to debug all the problems in my code, so I dropped it down to 3.  It passed! (Yay! My code could handle some trivial cases!)  I stepped up to 4.  Fail.  Fix, fix fix. Works, 5, Fail. Fix, fix fix. Works, 6, Fail.  At 7 the only failure was for splitting the perfectly balanced tree.  At 8 I found I had implemented the algorithm incorrectly.  Not a typo or off-by-one or similar like all my previous bugs, I had implemented the wrong thing.  Specifically I had missed the requirement that union could only work if the nodes at same black level were both black.  You couldn’t use a red parent of the equal black level nodes from the larger tree.  I wondered why only my split implementation failed, then I realised that my union walked down to the leaves then walked back up to find equal height, so stopping early was always stopping in the right place.  For Split, I was always walking down from the last pivot point, which in this case was red and started with the right black height.  I fixed that and it works.  9, 10, 20, 30, 60, 130.  All works.

One last thing I want to mention was my test assertions.  After each operation, union or split, I could trivially assert that the union had joined or the split has split.  But a failure at one step might not get noticed for dozens of steps later.  So I ran a full suite of compliance tests after each step as well.  Significantly slowed down execution, since they were O(n^2) and each step was O (log N) otherwise, but I tested the following and every one of them helped me find a bug.

1. Each root node was black. (red black tree requirement 0)
2. Each node was only in one tree, and no cycles.
3. Each red node only has black children (red-black tree requirement 1)
4. The black distance from each node with 0 or 1 children to root is the same as the black distance from root to left most child. (red-black tree requirement 2)
5. At each point in each tree, every node to the left is smaller and every node to the right is larger. (I originally only checked that immediate children satisfied this property, but found my tree mangling was sometimes too subtle to get picked up.)
6. For every pair of root nodes, that the left most edge of one tree isn’t on the same side of the right-most edge of the other as its root, or vice versa.

All in all I think I spent almost 10 hours to get this to work.  Certainly glad I wasn’t trying to do it during a programming competition! (And I haven’t even written the solution to the actual problem…)

Now this is more like it… 44th! (Sure the time of this round was pretty bad for all of europe, but still…)

I finished the first 2 problems in about an hour, leaving 90 minutes for the 3rd problem.  However, I could not see how to formulate the DP (or greedy) to pass the large input after a good long while thinking, so I decided to just do the brute-force possible small input.  Even the small input had its corner cases, but my Fraction class came to my rescue once again and after realising a stupid mistake on my first submission, I got a correct on my second attempt.

Luckily I didn’t make any mistakes in the large input for the first two problems, as failing the second of the two would have dropped my score below the 1000th place cut-off, even with my submission of the 3rd problem small input. (Points were 10,10 15,18 17,30 and the pass cut-off was 53 points in a time of 2h 15 or better.)

Q1) Given that you are typing a k character string, and you have typed m characters, and each of those characters has an individual probability of being correct (which is provided) but every character you type from now on will be correct, what is the expected number of keystrokes to get your password correct if you choose the best strategy.  You can press delete 0 or more times to clear some of the existing characters and then fill in the rest and have to press the enter key each time you submit. Alternatively you can press enter immediately and start again.

A1) So the enter immediately scenario is trivial, 2 + k.  Its what we need to beat.  This leaves k+1 scenarios, with probabilities.  We can walk through these easily.

First scenario is delete everything and type it out.  Probability of success is 1.  Cost is m+k+1 on success.  Second scenario is delete all but 1, probability of success is the probability of success for the first letter.  Cost is m+k+1-(2) on success and m+k+1-(2)+k+1 on failure.  Next scenario is the same, but the number in brackets is 4 (2 more than before) and probability of success is multiple of the first 2 probabilities.  Just loop through them all and return the best.

Q2) Given a list of tasks which you get either 2 or 1 points depending on how good your best effort is, and a minimum number of points before you are capable of performing a 1 or 2 point effort (where this minimum is specified individually for every task and point outcome), determine the minimum number of task attempts required to get a 2 point effort on every task.

A2) It took me a little bit of thinking before I worked out exactly how, but this seemed like a problem with a greedy solution.  And my solution passed, so that is promising.

The approach is to sort the tasks in order of least to greatest points required to get a 2 point result.  Then you take turns performing all tasks you are capable of getting 2 points on, then 1 task that you can get 1 point on.  The first part is obvious, the list is sorted we can just work our way up it.  But how to choose that 1 task to potentially unlock some more 2 points?  The greedy approach is to say that you want to choose the task which is hardest to get 2 points on, its the one you are going to try last, so we maximise the opportunity to get 2 points in a single go.  So, just walk the sorted list from the other end, choosing the first task which you haven’t already scored 1 point or more, and are capable of scoring 1 point on.  You don’t have to worry about checking whether you can score 2 points, because you already greedily took all of those before you started your search for a potential 1 point task.

Finally you need to terminate this loop if you stop making any progress or finally get 2 points on all tasks.  If the former, the problem isn’t possible, and you return as such.

Q3) Given a 2 lane road with cars initially in 1 lane or the other, and having initial speed and initial rear-bumper position relative to some start line, determine the maximum time before a car has to change speed to avoid a collision, presuming instantaneous car lane switches and a car length of 5 metres.  Cars can touch bumper-to-bumper without problem, so long as the cars have same speed or the faster car is in front.

A3) So the speeds and positions and car length are all integers, but the answer is not.  Using double risks incorrectly deciding that a car cannot switch lanes, but some epsilon usage is probably feasible to get it right.  However since I had my Fraction class, I used it to ensure I didn’t have to worry about getting the epislons correct.

The small input size was a maximum of 6 cars, the large was a maximum of 50.  In either case I expect the first step is to determine the points in time which are of interest.  Sorting the cars by speed, determine the point in time where the front of a faster car meets the back of a slower car.  For 6 cars, this is at most 18 points.  And at each of these 18 points, there is only 2 options of interest, showing a very plausible brute force search space.

So brute force approach, you walk through the points of interest in time order, at each one there are 2 scenarios.  If the two cars are in the same lane, one of them has to swap.  If the 2 cars are in different lanes, either they can both swap, or they can stay where they are.  This both swap case is important because future seemingly unavoidable collisions might be avoided by trying it.  Recursively search swapping car lanes and moving on to next interesting point in time, and undoing the swaps when the recursion returns, is not too complicated at all.  The important bit being ensuring that you don’t swap a car when it can’t be swapped.  This is easy enough, you just consider each car, move it to the point in time under consideration check if it is in the target lane and would overlap the target car position.  This is where I think the greatest risk from using double and epsilons would be, but fractions handle it easily.

The above brute force approach however has a problem.  If two events happen simultaneously, what do you do?  Indeed one of the sample inputs fails if you don’t handle this.  Thinking about how it can fail you come to the conclusion that it is where there are 3 cars which are in bumper alignment at once.  In this case the recursion will decide to move the one moveable car, but then further down the recursion, it moves it back, inadvertently returning to where you were, but not reconsidering the scenario.  One solution is to change the recursion to handle this, and you probably could, but I found it simpler to instead walk every pair of points of interest up front, and determine if they were at the same time and if so whether they shared the same fast or slow car (I only handled same slow car in my first submission… oops).  If you find a match the answer cannot be greater than that time point.  So choose the smallest of all matches and cap any returned value from the brute force, to that.  This is a bit simpler to implement, and returns the identical result.

So what about the large input?  Well, the solution is in caching I am sure, but what is your key for the DP table or memotization lookup?  Since we are moving cars between lanes, and there are up to 50 cars, the naive cache ends up with 1225*2^50 slots (1225 being the maximum number of points of interest) and not being very sparse.  Just as the competition ended I realised that at any point you only need to consider the cars which are involved in future points of interest.  Defining what that actually means, obviously includes both cars at the point, but also up to 2 more cars which might be blocking the ability to switch lanes.  But I don’t know if this reduces the search space enough, but it should be very significant at the leaves, and even before the leaves I think the actual state usage will probably be pretty sparse and so it might be possible.

Or maybe a completely different approach is required, I haven’t checked anyone solutions to see.

Contest analysis is up – and they do indeed use a quite different approach for solving the large input. Looks like the trick is to gather the cars together into groups.  When two cars are passing, they are locked, they cannot switch lanes.  This locking cascades.  If you track both events regarding 2 cars travelling at different speeds meet and pass, you can work out when to split or join these groups.  When they aren’t in a group, they are free to change at will, so the only way you can get a collision is if the two groups join and they are both fixed, which is to say they started the simulation locked. Fixed is contagious, but when a group size returns down to one it loses its fixed state.  So we just need to consider the N^2 events, updating the joined status and returning the time if we get an unsolvable collision. Each update can easily be performed in O(N^2) which with N=50 brings the total running time quite high, but still feasible.  It also isn’t too hard to make it perform better than that.

This solution is nice, wish I had thought of it 😛

So, since its Google code jam time, I figure I’ll do another TMD.Algo release.  Still the same licensing as before.

New features: (Beware bugs due to insufficient testing… especially in the first 2)

1. MaxFlowMinCost algorithm for Graph.
2. Generic TernarySearch extension for lists.
3. SortedDictionary2  – a sorted dictionary with ‘near’ lookup support. Finds the element equal or less than the search element and then you can enumerate from that position.
4. Pattern support.  Algorithms for efficiently finding the sum or value at index in a repeating pattern with optional non-repeating start. Uses sequence generation state as a key to detect loops.
5. Memotizer – a simple function adapter to automatically cache results – not exactly nice to use if the function needs to be recursive…
6. LookupQueue – amortized O(1) lookup/remove/append queue using a dictionary augmented linked list.  Presumes queue elements are all distinct. (Internal implementation uses arrays to avoid the GC and random location dereferencing penalties of a normal linked list.)

Improvements:

1. Fraction improvements: Truncate to closest integer in direction of 0, explicit cast for integer to fraction, <= and >= operators added, absolute value function.

Bug fixes:

1. Corner case in reverse comparer (if base comparer returned int.MinValue it would fail).
2. One of the error messages in LookupHeap had a typo.

 

Link: http://www.themissingdocs.net/downloads/TMD.Algo.0.0.5.0.zip