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.


Leave a Reply

Your email address will not be published. Required fields are marked *