Author: Tilps

Been a while since I last posted… I’ve fallen behind as was to be expected.

Q1) Given carrots are placed at locations 0 mod 1billion 7, and from any given location there are 2 options to go to, 4x+3 or 8x+7 and at most 100thousand movements are allowed, what is the minimum number of movements to get from starting position x, to a carrot.

A1) Obviously this problem is about transitions modulo 1 billion and 7.  The trick is needing to rule out trying all 2^100000 options.   1 billion and 7 is too large to compute all transitions, so a simple memotization won’t work.

The first step is to realise that order of application doesn’t matter. A(B(x)) == B(A(x)). That gets rid of almost all of the solution space.  Furthermore A(A(A(x)))=B(B(x)) and since we are trying to minimise moves the ideal solution will always choose 2 8x rather than 3 4x.  From there it is a simple matter of repeated application of B and trying 0 1 or 2 applications of A. (Technically you need to verify that another application of B isn’t equal of 2 appliations of A are equal given the statements made so far, but A(A(x))!=B(x) for all x so that is not a problem)

Another solution is to notice that all transition states available are of the form 2^(n)*(x+1)-1, and that every possible n is reachable except n=1.  Furthermore since the order of application doesn’t matter, and a greedy approach of using 8x as often as possible therefore is the ideal scenario. Therefore the answer is n/3 if n is a multiple of 3, or n/3+1 otherwise, for the first n which results in a 0 mod 1 billion and 7 answer. (if 2 mod 3 then apply 4x, if 1 mod 3 then apply 4x twice from one less 8x.)

Q2) Given up to 15 bottles each with capacity C and a list of initial contents levels (all integer), and a price list for how much a bottle with any specific content level is worth determine maximum profit given the ability to pour 1 bottle into another until it is empty or the other is full. Maximum C is 50 and maximum price is 1million.

A2) Each pouring operation either results in a bottle which is empty or one which is full (potentially both).  Empty and full bottles are of no interest for future pouring operations, so there are at most 14 pouring operations that will be performed. Giving a search space of 14! – which is too large.

A dynamic programming approach might seem like a good idea, all we have to do is determine the maximum for each subset and combine them.  But a closer look shows that it doesn’t make sense because we don’t know the contents levels in bottles as they may be neither full, empty nor their initial value.

So a different approach is required.  If a subset of the bottles all pour, one into another in some order.  They all end up either full or empty except for possibly 1.  Given we know the total contents and the capacity of each one, div gives you the number of full bottles, and mod gives you the capacity of the last possibly non-empty one, the rest are empty.  Presto we can trivially calculate the maximum for each subset where they all pour.  Therefore we can determine the maximum for a specific subset, it is the maximum for all partitions of pouring.  Number of partitions of 15 elements is still ~1billion so we can’t brute force those.

The maximum of n elements is therefore found by considering each possible non-empty subset as all pour, and the maximum of the rest.  This has a running time of less than 2^29, but it seems likely to time-out in the worst case.

Next approach – For each subset one of the elements will have content j, the rest are already sold.  You can generate a subset 1 larger by combining the unsold one with an unused one, or selling the unsold one and keeping the new one as unsold.  This has a state space of 2^15*50, but only an average of about 15 options to consider for each spot.  This gives running time <2^25 which is clearly going to run in time.

Q3) Given a list of the count of each type of apple in up to 50 boxes, determine the probability of selecting each specific apple type at random if you first randomly select a non-empty subset of the boxes to further select from randomly. (Up to 50 types of apple and each count is <200, no box is empty)

A3) The dual random selection is kind of annoying as the number of subsets is up to 2^50.  So obviously we can’t consider each scenario and average.

Dynamic programming might be a possibility. Maybe determine the probabilities using the first n boxes?  Except how do you expand from n boxes to n+1.  This appears to be impossible.  To modify the probabilities you need to know how many apples there were before.  Hmm, that <200 limitation is pretty small, gives a maximum of 500k apples in any subset.  Each transition only depends on the one before, so we don’t need to keep everything in memory.  So probabilities using the first n boxes with a total of k apples.  That is 2meg ram for just one probabilitiy, so we’ll have to do each probability separately, which I think is fine…

Well maybe a bit slow.

A faster way to do it is to break down the problem differently so you can accumulate the probabilities for each item simultaneously without requiring any additional ram.  One breakdown is to consider the answer as being the sum of count of apples of specific type in a box divided by total apples in subset, times number of ways to create that total with a subset that contains the specific box divided by total number of subsets, for each possible box and total number of apples in a subset.  Efficient calculation of number of ways to create total with a subset that contains the box means that running time is proportional to 500k times 50 worst case, as each apple type can be accumulated at the same time, because the part which requires the giant array is constant over each apple type.  Unlike the previous calculation where the giant array is specific to the apple type, which is 50 times slower. (Although apparently an efficient implementation can pass system tests… without this further optimization)

As is usual with SRM I didn’t do this one.  However, I figure I might keep writing up blogs until next years TCO.

Q1) Given a boolean rectangular array which maps to a hexagonal grid by shifting every second row half an entry to the right, determine the number of edges between true and false exist.

A1) This is easy enough, its a simple case of walking each cell and checking its 6 ‘neighbours’ and incrementing a counter if its not the same.  Once complete divide answer by 2.  The only difficulty is making sure you don’t screw up the determination of the 6 neighbours, which is different depending on whether the current cell is in an odd or even row.

Q2) Given a list of numbers, determine the greatest number of distinct pairs which can be selected such that all such pairs are the shorter sides of a integer sided right triangle and have a gcd of 1.  Numbers are all less than 1 million and worst case there might be 1250 numbers (less if they aren’t all single digit – maximum of 350 6 digit numbers).

A2) The constraints on the pairs are pretty significant, and could easily rule out most of the numbers entirely.  However 600 3s and 600 4s are a real possibility.  We can easily go through each pair of numbers and work out if they are compatible.  We can turn this into a graph with counts available for each number.  Not certain whether the graph can contain cycles.  If the graph can’t contain cycles, it is bipartite and we can perform a max flow to determine the answer.  If it can contain cycles we have a problem…

So I checked out some answers – and yes it does seem max matching is now considered a question 2 level algorithm, not question 3 as I thought it used to be.  However, whether there are cycles or not is not relevant, as 2 odd numbers apparently cannot satisfy the requirements (since the sum of their squares will be 2 mod 4), and 2 even numbers is ruled out by the gcd(a, b) == 1 requirement.  Hence the pairs are bipartite based on even or odd.

Q3) Given a weighted tree with up to 200 nodes, determine the minimum weight sum of a tour which starts and ends at node 0, visits every edge at least once, and can teleport for cost L up to K times.

A3) If K is 0, the answer is 2 times the sum of the edge weights as every edge will be traversed twice.  If K is 1, we can subtract the longest path and add L, and choose which is best. That is to say if the depth of the deepest node from any other node is > L we will teleport between those nodes.  However once K is > 1, it becomes a lot trickier…

Again looking at solutions.  The problem is a dynamic programming problem.  Recurse over the minimum tour length within a subtree if there are i teleport endpoints in that subtree.  This can be determined by considering that if a subtree has an even number of teleport endpoints, it will be both exited and entered, otherwise it will only be exited or entered, not both.  So there are n nodes, and up to 2k teleport endpoints, so the DP has O(nk) states.  Determining each recursion requires considering how to distribute the i teleport endpoints between a nodes children.  Considering every combination is too much, so we need to switch up the DP a bit.  If instead of thinking about each node, we consider each edge, we realise we only need to consider each possibility for i down a given edge, not in combinations with other edges out of a given node.  So we can instead either recurse to the left most child and all its outgoing edges, or to the ‘set of edges to the right of the left most child’  Since the number of edges equals number of nodes -1 in a tree, the DP states is still O(nk).  Number of possibilities to try for each case is O(k) giving O(nk^2) running time to populate the DP table.  Once the table is populated all we have to do is check for root of the tree, each even number of end points, modified by the cost of teleporting, and determine the best result.

The real trick here is disassociating the end points, realising the problem can be solved without caring about specific locations teleporting to specific others.

This is the second time I’ve seen the ‘dfs edge walk on a tree’ DP problem.  I should probably write up a solution to practice it.

So, as predicted by the odds I am out ;). I did at least score some points, so I came 125th. The question structure didn’t favour me, an easy first question jumping to a hard second question.  A fast time on the first question was sufficient to get through, or a couple of challenges and a terrible time.  However the first problem was so easy the challenges were hard to come by, and the second problem’s input requirements so obtuse that constructing a failing test case was next to impossible.

My time for the first problem was terrible  – I had the problem solved in the first minute, but a plus sign where I wanted a minus sign sent me down a warren of verifying things by hand, and quickly half an hour had vanished.  That being said I probably would not have gotten through even if I hadn’t screwed up badly, had to be fast.  Although an extra 20minutes and I might have actually had a serious attempt at the second question.

For a while I thought maybe I could do the 3rd question, thinking it was a well known computational geometry problem which I could just grab an algorithm off a textbook for.  However the closest related problem in the textbook told me the running time would be too slow.

Q1) Given a set of bank accounts with known values, where 1 dollar gets you one ticket in a lottery draw each week for a fixed amount, what is the expectation value of bank account 0 after n weeks. Limits: n up to 1000, winnings per week up to 1000, up to 50 bank accounts, each with a starting balance of up to 1million.

A1) I implemented this as a DP of probabilities of number of wins in a given number of weeks.  Note that the total amount of tickets in a given week stays the same regardless of who wins in the previous weeks, so only bank account 0 and the initial total of the incoming bank accounts is of interest.  Once DP is formed, simply multiply each probability in the final week by account balance for that many wins and return.

As it turns out the problem can be solved without the DP. It appears that simply using the expectation value of one week can be used to generate the expectation value of the next week.  Reducing O(N^2) down to O(N).

Q2) Given a sequence of numbers formed by multiplying the digits of each of up to 50 consecutive integers, determine the location of the first of those integers, assuming the sequence refers to the earliest such match. Limits: the input numbers will be less than 1 billion, output will be less than 2^63.

A2) After the competition I realised that this problem is not as hard as it looks.  I really might have worked this out if I had of made a serious attempt (and had that extra half hour :P). If the input is all 0’s you can return 10,100, 1000 depending on input length quickly.   In fact brute forcing for possible answers of 1-1000 takes care of some corner cases. Find the first non-zero number, brute force the last 3 non-zero digits and solve for the rest by trying as many 9s then 8s then 7s down to 2s going from right to left, then check against all other numbers in the input to see if it is right.  Return the smallest result.  For kicks I wrote this up and it failed test cases – but only because of a mistake in my code, fixed that and it now passes system tests.  My first thought was brute force 2 digits (well my real first thoughts were more complicated than that), but input size > 12 allows some control over the 3rd digit.  A number followed by 12 0s indicates that the last 3 digits were 9s for instance.  You can look at the input set and break it down in to all sorts of combinations, but in the end, simply brute forcing all last 3 digit scenarios is easier…

As an aside I was left wondering what checks the challenge system used, since the input limitations are significant.  Other than 0 no two consecutive numbers in the input can be equal. No input number can have a prime factor greater than 7. At least 5 of the inputs must be 0, and after the last consecutive 0 every 10th number must be a 0. Two consecutive non-zero numbers must be increasing and the difference must divide them.

Q3) Given up to 1200 points, where no 3 are co-linear and no 2 are coincident, determine the number of line segment intersections from choosing any 4 points of the points.

A3) Brute force is obviously no good. A look on Wikipedia indicates that even the best algorithm for enumerating all intersections of the complete set of line segments from n points is in the order of the number of intersections, and if the 1200 points form a convex hull the number of intersections is well over N^3 (Close to N^4 even I think).

Therefore we can’t enumerate the actual intersections we have to count them in batches.  Specifically the time needed needs to be about O(1) for every line segment. O(log n) would be sufficient.

I had a quick look at one solution, and it considers each point, and sorts the other points by angle relative to that point, then for each of those segments in order, mystically calculates the intersection count really quickly. … going to have to read it again after some sleep.

Edit: Post sleep update.

I had a look at some more solutions.  General approach seems to be assume everything crosses.  Then for every point, sort the other points around it by angle.  If you can get 180 degree separation in the sorting, all the points on the left will not form crosses with the points on the right. So you subtract these scenarios away.  However there is over-counting which you have to adjust for.  Looks like the over-counting adjustment is probably the hardest bit.

Q1) Given a dictionary and a mapping of numbers to sets of letters, and an input sequence consisting of numbers, ‘try alternate’ button pushes and ‘spaces’, determine the output.  Assume dictionary is processed in alphabetical order.

A1) Easy enough, make a dictionary of number sequences to list of words that match, sort each list, then process input to produce output…

Q2) Given a graph with a line of nodes each connecting from one to the next, determine the minimum time to get from the first node to the last.  Subject to some special conditions.  Each edge has two time options for its travel.  The first is always available, but the second can only be used if there are less than k contiguous sections where second option has already been used, or you used the second option for the last edge. The number of nodes n is up to 400thousand, and k is up to n or 40, whichever is lower.  The first and second times for each travel option are generated using a pseudo-random number generator with specified parameters.

A2) While writing my question text above I may have made this question even easier due to my phraseology.  Its a DP problem, 3 parameters, number of contiguous sections of second option so far, boolean if last was second option and how many nodes passed already.  Very easy, only problem is that it requires 64meg ram in the default dp table.  Luckily every entry only depends on the ones at one less nodes passed.  Lucky because that means we can get rid of the memory problem, and also because if it depended on all of them the processing time would have been excessive.

Q3) Given a k-partite graph where each ‘layer’ only connects to its neighbours (arranging the k layers in a circle), determine the maximum independent set.  Limits: Maximum vertices is 100, k between 10 and 50.

A3) When I first saw this problem I was shocked, a question 3 which maybe I can actually do.  (The original question isn’t phrased as given, but still it was obvious this was the real question.)  I unfortunately pretty quickly came to the realisation that the graph itself didn’t have any limitations which guaranteed it was bipartite. If k was even, I was good to go, but when k is odd, I had a problem.  I thought about it for quite a while, and along the way I had the idea that I could try all the possibilities for one of the layers, and do the rest pretending it was a bipartite graph.  Unfortunately I threw this thought away because I didn’t remember that k was at least 10, and so I decided that worst case would be 33 vertices as the smallest layer and 2^33 scenarios is too many to consider.  With k at least 10 (or we might as well say 11 since 10 is trivial and a maximum vertices of 100, the worst case scenario is when the 100 vertices are distributed in layers of 10 or 9.  Select one of the rows with only 9 in it, and try all 2^9 scenarios.  For a given layer if we are trialling a vertex as being in the independent set, we can remove it, and any immediate neighbour vertexes.  If not we just remove it.  This removes the entire layer, leaving us with a bipartite graph which we can solve via the dual maximum matching problem using simple maxflow on a graph with capacities which are all 1.  Add in the number of ‘independent’ vertexes in the current trial and choose maximum over all trials and done.  Probably one of the easier question 3’s I’ve seen recently.

Q1) Given a n rows of m seats, and a list of specific taken seats, return how many ways 2 people can sit next to each other. Limits: n and m up to 1 billion and number of taken seats up to 50.

A1) Very very easy.  Use long long to avoid overflow.  For each row with taken seats get the sorted taken seats in that row, then for each gap greater than 1, add gap-1 to the total.  Finally add number of empty rows times m-1.

Not my favourite kind of question, simply because I am not uber-speed code writer.

Q2) Given a counter which ticks down every minute, and a set of k items which each have a time length, but increase the counter by j at a specific time within that time length, determine the maximum number of items which can be processed completely before the counter drops below 0.  If there are multiple ways to achieve this goal, return the order which prefers lower numbered items first. Limits: k up to 20.

A2) Each item has a minimum requirement, and a net effect. If there is a non-negative net effect which we can meet the minimum requirement for, we want to use it. If there are only negative net effects, which we can meet the minimum requirements for, we will never be able to use anything which is currently not at minimum requirement.  However, the order of the things left is non-trivial.

With a limit on k of only 20, every possible subset is a valid consideration if we can process it quickly. This provided a hint, but I needed to look at a solution to get the rest. If we divide the input into start and end sections, we can determine which of the end section can be placed immediately after the start section.  This lets us create a DP of maximum number which can be processed from a set which appear after the rest not in the set (regardless of whether the rest not in the set can actually all be processed before it).  That final condition may sound crazy, but once you get to the full set,  the not-in set becomes empty set and the condition is fine, so the rest doesn’t matter.

Once the DP is done, you just have to do the ‘reverse dp walk’ to construct the output.

Q3) Given a list of items and 2 queues to put them in, where each item has a processing time, which depends which queue it is in, and after processing is placed into the other queue, unless it has already been processed by that queue, determine how many different ways to place the items in the 2 queues subject to 2 conditions.  1) The items have to be added to the queues in the same order as the input. 2) Neither queue must ever be empty before the other queue has finished its initial list. Limits: up to 47 items and each processing time is between 1 and 20.

A3) No clue – the processing time limit seems suspiciously small though. Maybe a dp on the number of solutions with an initial queue time of n?  Let me look at a solution.

Rather than solving the problem as given, solve a different problem, number of ways for queue 1 to run out before queue 2 is done its initial list.  Then switch queues and use the same logic again.  Subtract both from number of possible distributions.

So, how to count the number of ways for it to run out. Each time we put something on to queue 1, it makes it harder to run out, each time we put something on queue 2 it is easier to run out.  Some analysis is required to work out the DP.  The definition of fail is if total queue 1 time + total time of first i-1 from queue 2 processed at queue 1 speed – total time of first i from queue 2 processed at queue 2 speed < 0 for any i.  We want to know what the minimum of the left for any i is, for each possible distribution in order to know whether it has failed, if that minimum is less than 0, then it is a fail.  As each new item is added to the pile this function changes.  If we add one to queue 1, all possible left hand sides increase by the processing time, thus also increasing the minimum.  If we add one to queue 2, the inequality doesn’t change except for the new i=new length of queue 2 case.  In that case the inequality equals the previous scenario where all were processed minus the new addition as a possible new minimum.  So we can minimize between that and the old minimum.  The only problem is we need to know that previous scenario as well.  So ‘previous scenario’ and ‘minimum’ are 2 parameters to the DP, the 3rd being number of items en-queued.

Now that we have this new parameter we need to know how it changes.  If we add to the first pile, it goes up exactly the same as the minimum does, adding the queue 1 processing time.  If its added to the second queue, that causes a subtraction of the queue 2 processing time, and an addition of the queue 1 processing time.

Potential range on previous scenario and minimum are pretty large so memory is an issue if the entire dp was kept in memory.  Helpfully each case only depends on the previous number of items en-queued, and the final summation is only on the full list of items en-queued, so we can throw away memory as we go. (Avoid garbage collection issues and alternate arrays, don’t keep allocating.)  Additionally with the inequality range being +/- ~900, that is close to 200million dp locations filled without any optimisation.  Running with c++ this is probably reasonable, but with Java further trimming helped.  For instance minimums only ever get smaller and we are only interested in the negative ones, so treat all positive minimums as 0, and we save half the state space.  Furthermore the area of the DP increases by +/- 20 in both dimensions with each step, taking this into account can save another factor of ~3 rather than blindly checking every spot.

Again out of my range, but useful to sit down and understand how it works.