Q1) Given a sequence of step, turn left and turn right commands, which are repeated infinitely, determine whether you will stay in a constrained (but not specified) area, or drift off in to the distance. Maximum command sequence length is 50.
A1) There are 4 scenarios. 1. You come back to where you started. 2. You end up facing the opposite way you started, and so the second run you end up back where you started. 3. You end up facing 90 degrees to where you started, in which case after 4 runs you trace a ‘square’ and end up where you started. 4. You end up facing the same direction as where you started, but not where you started, in this case you drift away. In any case, simulate 4 runs and if you are back where you started, you don’t drift. Case 1 will hit the same place 4 times, case 2 will come back twice, case 3 will come back once, but all 3 will be at the starting position after 4 runs.
Q2) Given n points equally distributed around the edge of a circle, and a ‘pseudo randomly’ generated subset k of those points which are marked, determine how many right angled triangles can be created using only the marked points. n is up to 1 million but k is limited to 100 thousand. Also the input is guaranteed not to result in an answer greater than 2^64.
A2) Seems kind of tough for a second question at first glance. First we need to identify how to create right triangles. If n is even, this is easy, possible pair of edges corresponds to a mirror pair, and either of those mirror pair will make a right triangle. If n is odd, no right triangles can be created… (A right angled triangle has its hypotenuse as a diameter of a circle, and 2 different circles can only have at most 2 crossing points, not 3.) However even with O(1) dictionary lookup and considering every pair of marked points to determine if either of the matching mirror locations is way too much. So we need a solution which comes from considering the points one at a time. The trick is in the logic we used to get rid of all the cases where n is odd. The hypotenuse must be a diameter, so from each marked point we can determine immediately the location across the diameter and verify that it is a marked point. If it is a marked point we then have a second trick, every single other marked point other than the 2 consumed will make a valid right triangle with the diameter. So for every marked point in one half of the circle, if there exists the matching point then add k-2 to the sum. Not so hard after all… (Although implementing the pseudo randomness itself had risks…)
Q3) Given a n x m board and k varieties of pieces each with its own count, determine how many ways exist to layout the pieces such that every row and column has at most 1 variety. n and m have a maximum of 30 and k has a maximum of 10. Return result modulo 1 billion and 9.
A3) Hmm, as usual Q3 seems beyond me. Even just trying to generate canonical arrangements which can then be boosted to the actual answer applying combinatorial multipliers, seems difficult. After thinking about it for a while I gave up. Turns out canonical arrangement approach is no good, you need to boost as you go along.
From a solution. Define dynamic program over number of ways to populate the board using i rows and j columns to contain the first l varieties. This is equal to the number of ways to populate the board with l-1 varieties in i-di rows and j-dj columns, times n-i-di choose di, times m-j-dj choose dj times the number of ways to arrange count of l in di rows and dj columns. That second arrangement can be done using dynamic programming up front, or memotized, since it will be repeated a lot. Firstly l has to fit into the area of di*dj, and must be greater than or equal to both di and dj in order for there to be an arrangement. I would have thought x*y choose c would have been the answer at this point but I would have been wrong, as it doesn’t consider the case where a row or column is left entirely empty. So we subtract off the number of ways to arrange c in to each possible scenario of less rows or columns, each multiplied by the number of ways to arrange the rows or columns into the full x and y size.
Not as bad as I first thought, but still pretty tricky.