TCO17 R1B

Less than 500 people turned up for this round, so of course positive scores advanced, of which there was 312.  Almost 100 of those solved the 1000pt question, with the 250pt question seeming to have a higher failure rate amongst the top competitors.

Q1) Given two amounts of two different types, and two rates of consumption and the ability to convert type 1 in to type 2 at rate of 2:1, determine the maximum time before one or the other type is exhausted.

A1) So there are two scenarios.  First determine the baseline time of exhaustion by dividing the amount by rate of consumption for each type.  If type 1 runs out first, there is nothing to be done, return that time.  Otherwise the aim is to find an exchange level which has type 1 and type 2 run out at the same time.  Since each increment we convert will lengthen the shortest and shorten the longest until that point.

Thus we need to solve (A1-x)/C1=(A2+x/2)/C2 to determine x, and then recalculate either side.  x =(C2A1-C1A2)/(C2+C1/2).  Note that x looks like it could be negative, but that is the same case as type 1 running out first.

Probable cause of failure is failing to account correctly for the input range.  C2*A1 will overflow 32 bit int if you haven’t converted to floating point.  C2A1-C1A2 being calculated with small precision float could be an issue as well, but I think using a 64 bit float might be sufficient, definitely fine with 80 bit float.  Obviously it could all be calculated using BigInteger fractions, but I’m pretty sure that is excessive.

Q2) Determine a set of positive integers such that the number of distinct sums which can be constructed from them (using each number at most once) is exactly k.  Maximum number of values in the set is 20 and k might be up to 1 million

A2) k=(2^N)-1 is an easy first scenario, just use powers of two between 0 and N-1 inclusive.

As an extension of this observation, it can be seen that given an existing set S, you can create a new set S2 which has double + 1 as many distinct output values, by adding a new value which is one more than the sum of the existing values.  If instead we add a new value which is equal to the sum, the number of distinct outputs doubles.  Now if we can work out a way to go from one set to another such that only 1 new value is added it would seem we are done.

If we can assume that the existing set of outputs when sorted forms the range 1 to x, then by adding the value 1, the new output is 1 to x+1, and we’ve added exactly one new value.  Helpfully the proposed doubling scheme above when given the range 1 to x creates 1 to 2x.

Thus we have increment and double operators, which lets us create any number in logarithmic number of steps.  However, with a target size of up to 1 million, its easy to construct a scenario where just double and increment take 38 values.  But we’re limited to 20.

So we need to be more greedy.  Note that we can actually extend our logic above to say that given a set of size x we can create any new size between x+1 and 2x+1, just by adjusting the new value added.  Or in reverse, given a current size x, we create it from any size between x-1 and floor(x/2).  So rather than building up to the target number, we could instead tear it down.  If the target is odd, choose a value for your output set which is half rounding up and solve for half rounding down, if the target is even choose the value equal to half and solve for half.  Repeat until target is 0.  Now you are done and its obvious that 20 values is sufficient!.

Q3) Given a tree with weighted nodes, determine the set of all sub-tree weights, then determine the sum of x raised to the power of each member of that set.  Return the answer modulo 1 billion and 7.  Weights of each node may be large, x itself may be large, but there is at most 50 nodes.

A3) Since the weight of each node can be large, and the tree could be very flat, the number of distinct subtree weights could be huge.  So enumerating them all is out of  the question.  So it would appear that the problem needs to be built up from the leaves.

As a simple starting point, consider a node with one child and an unknown number of sub children.  The answer consists of the answer ignoring the parent plus the answer including the parent added together.  Assume we have the answer for ignoring the parent (since we are planning on building up from leaves) the answer including the parent consists of, the parent on its own  (x^(parent weight)) and, the parent plus every subtree including the child (x^(parent weight + subtree weight) summed over every subtree).  We already have x^(sub tree weight) summed over every subtree, so this is (1+subtree answer)*x^(parent weight).

So we can now answer a linear tree, but that isn’t very interesting.  We need to handle branching.  So parent plus two children. (1+subtree1 answer + subtree 2 answer)*x*(parent weight) handles the scenarios of only choosing to include one of the children, but what about some subset of both.  Thinking for a bit this should be (subtree1 answer * subtree 2 answer)*x^(parent weight).  Subtree 1 is a sum of all the different subtrees, sub tree 2 answer is the sum of all those sub trees, so every combination of them can be formed by calculating the product, and each term of the product is correct as its x^weight we are trying to calculate so x^(weight1+weight2)=x^weight1*x^weight2.

This can obviously be expanded to an arbitrary number of children, but as written its got 2^(number of children) terms – which is far too many given tree branching factor can be as high as 49.  So we need to simplify.  1 + subtree1 + subtree2 + subtree1*subtree2 = (1+subtree1)*(1+subtree2).  And this pattern holds as number of children increases.  So now its a product of a linear number of terms – which can be easily calculated.

Finally once we build all the way up the tree, we then need to sum all the values over the tree, as each node is only calculating the sum for subtrees which are rooted at that location.

Of course the answer can be huge, so we need to consider how the modulo comes in to play.  Obviously adding two values is easy.  Multiplying two values needs care to avoid 32 bit overflow.  But the raw values of x^(current node weight) where both x and weight might be large requires both care for 32 bit overflow, and to perform accelerated exponentiation.  But those 3 scenarios cover all the operations needed.  No division or subtraction to be handled.  Pretty easy as 1000pt questions go.

TCO17 R1A

I got to see 2 am twice staying up for this round, since it was scheduled for the hour when DST ended…

Positive scores advanced, only about 1000 people registered.  Only 17 people got all 3 questions out.  I think I was close on solving all 3, just ran out of time on the fiddly implementation for Q3, but given how many submissions for Q3 failed system tests, maybe I wasn’t as close as I thought…

Q1) For a table tennis tournament with people with distinct skill levels where greater skill always wins and only one table at which everyone queues, and after n consecutive wins the winner joins the end of the queue after the loser.  Determine who wins/loses in the Kth round.

A1) K was only at most 1000, so this was a simple simulation, even if you don’t have a queue data structure handy it’ll trivially run in time.  Just need some care tracking how many wins the players have had and be sure to add the retiring winner to the queue after that rounds loser.  I guess maybe input sizes of 2 and 3 would also present a potential corner case to some implementations.

Q2) Determine the maximum sum of products of the longer 2 dimensions of rectangular prisms which are made from an original rectangular prism of integer dimensions A,B,C by slicing parallel to a face to create 2 rectangular prisms of integer dimensions, where the pieces have to have a minimum dimension of each S in order to count.

A2) A,B,C could all be up to 100, and S could be 1, so the number of ways to break it down rules out brute force.  Instinct suggested a greedy solution was the way forward.  Options to consider are slicing in half, or slicing off a slice of size S.  Slicing in half gives you two smaller problems, but you can clearly see that you get less slices than slicing off S at a time if you repeatedly try to slice in half.  Once you decide to slice off S at a time, you could switch to dynamic programming – state space is at worst size 100^3, with 3 options to check from each state, that will easy run in time.

However I still liked this problem for greedy, so with a little bit of math, you can show that slicing from the smallest dimension is strictly better than slicing from a larger dimension.  But if the smallest dimension is less than 2*S, slicing on that dimension has no gain, and slicing in a the next longest dimension is actually a win.  Again once the two smallest dimensions are less than 2*S, you slice the longest dimension instead.  So first loop summing the product of the longest two dimensions until you get the shortest to less than 2*S, then repeat for until the second shortest is also less than 2*S, then again for the final dimension, and then finally add the product of the two longest remaining dimensions.

Simple mistake that could be made here is that when you are slicing the second or third longest dimensions to get them down to less than 2*S, you may end up with your 3 dimensions changing sort orders.  If you don’t resort your array after each run of slicing, you might end up start summing the product of the shortest and longest sides, rather than the two longest sides.  I sorted every time I changed the value, just to be safe, sorting 3 values is cheap 😛

Q3) Given a strictly convex polygon with the maximum and minimum y valued coordinates on the y axis, determine the volume of revolution around the y axis.

A3) This question was quite unclear, since given the polygon in most cases crosses the y axis, a full 360 degree rotation will cause the shape to sweep over itself.  So I did for a moment wonder if they meant the volume of 180 degree rotation – but the first example created a full cylinder out of a square with one edge on the y axis.  So I presume that the answer is the union volume from the 360 degree sweep.  I think I might have seen an answer which calculated volume of each half, doubled and added together and subtracted the intersection volume – so I think I was right about that.

So the final shape will be a stack of truncated cones, and the formula for volume of a truncated code is pretty simple.  The trick becomes determining the coordinates where each truncated code outside edge starts and stops.  Since its a union shape we’re trying to determine the volume of, take each segment on the left of the y-axis and reflect it to the right, and then we need to determine the outside edge of the combined set of segments.  Walking the segments in pairs advancing the segment which ends first, there are 3 possibilities for the overlap y range of the two segments.  Either one or the other is completely to the left or right of the other, or they could cross.  Turn each segment in to a line equation, allows the substitution of the y range min and max to check the maximum x-coordinates for the top and bottom of the range, if they belong to different segments do a segment intersection calculation to find the cross point.  Then you get 2 truncated cones instead of one by adding the cross point in between the 2 calculated maximum x coordinates for the start and end of the range..

Corner case – horizontal segments.  There can be up to 2 horizontal segments which are at the top and bottom since its convex.  These two segments can be ignored, and should be since otherwise you can have both horizontal and vertical segments which makes line equations difficult (without them you can construct the line equations as x = ay+b, otherwise vertical lines are annoying), and you also have segment overlaps with 0 extent in y axis which is confusing.