Petro Protsyk Professional software developer |
Facebook Hacker Cup 2012 – CheckpointYou are racing on a 2D lattice grid starting from the origin (0,0) towards a goal (M,N) where M and N are positive integers such that 0 < M <= N. There is a checkpoint that’s neither on the origin nor on the goal with coordinates (m,n) such that 0 <= m <= M and 0 <= n <= N. You must clear the checkpoint before you reach the goal. The shortest path takes T = M + N steps. At each point, you can move to the four immediate neighbors at a fixed speed, but since you don’t want to lose the race, you are only going to take either a step to the right or to the top. Even though there are many ways to reach the goal while clearing the checkpoint, the race is completely pointless since it is relatively easy to figure out the shortest route. To make the race more interesting, we change the rules. Instead of racing to the same goal (M,N), the racers get to pick a goal (x,y) and place the checkpoint to their liking so that there are exactly S distinct shortest paths. For example, given S = 4, consider the following two goal and checkpoint configurations Placing the checkpoint at (1, 3) and the goal at (2,3). There are 4 ways to get from the origin to the checkpoint depending on when you move to the right. Once you are at the checkpoint, there is only one way to reach the goal with minimal number of steps. This gives a total of 4 distinct shortest paths, and takes T = 2 + 3 = 5 steps. However, you can do better. Placing the checkpoint at (1, 1) and the goal at (2,2). There are two ways to get from the origin to the checkpoint depending on whether you move to the right first or later. Similarly, there are two ways to get to the goal, which gives a total of 4 distinct shortest paths. This time, you only need T = 2 + 2 = 4 steps. As a Hacker Cup racer, you want to figure out how to place the checkpoint and the goal so that you cannot possibly lose. Given S, find the smallest possible T, over all possible checkpoint and goal configurations, such that there are exactly S distinct shortest paths clearing the checkpoint. Input As input for the race you will receive a text file containing an integer R, the number of races you will participate in. This will be followed by R lines, each describing a race by a single number S. Lines are separated using Unix-style (“\n”) line endings. Output Your submission should contain the smallest possible length of the shortest path, T for each corresponding race, one per line and in order. Constraints 5 <= R <= 20 1 <= S <= 10000000 Example input 5 4 5 12 14 1 Example output Case #1: 4 Case #2: 6 Case #3: 6 Case #4: 9 Case #5: 2 Source:
Preliminaries Let’s start from the following problem. Given a lattice grid and a starting point (0,0), find how many there are ways to reach point (x,y) using no more than x steps to the left and y steps to the top. The problem is known as “Block walking”. The following picture shows two possible different ways to reach the point (2, 3) from the origin: It is easy to observe that the length of each such path consists of exactly x+y steps. Each path can be encoded as sequence of 0 and 1. Where, 0 means “move up” and 1 means “move right” respectively. For example, blue path might be encoded as 00011 and pink path 01100. Now, calculating the total number of different paths G(x,y) from (0,0) to (x,y) is equivalent to finding the number of different rearrangements of y zeros and x ones: G(x,y) = C(x, x+y) = C(y, x+y) = (n+k)!/(k!n!). (*) One important property of this equation is that G(x,y) = G(y,x). Now, for each (x,y) the value of G(x,y) might be easily calculated. The grid with actual values looks like: Naïve calculation of this grid using formula (*) will be extremely inefficient. Let’s investigate some important properties that might be used to calculate this grid efficiently:
These formulas lead to a very efficient algorithm for building such a table: for (int i = 0; i < max; i++) { for (int j = i; j < max; j++) { if (i == 0) { d[i, j] = 1; d[j, i] = 1; } else if (i == j) d[i, i] = 2 * d[i - 1, i]; else { d[i, j] = d[i - 1, j] + d[i, j - 1]; d[j, i] = d[i, j]; } } } The program doesn’t even have to store the complete grid, only the previously calculated row or column. There is no need to perform calculations when any of coordinates is equal to 0 or 1. This will be implemented in the final solution. It’s time to introduce checkpoint into consideration. And the next sub-task that should be solved is finding how many shortest paths S(m,n,M,N) exist from origin (0,0) to the goal (M,N) through checkpoint (m,n), such that (**):
Path from the origin through checkpoint towards the goal Combinatorial rule of product gives us the answer: S(m,n,M,N) = G(m,n) * G(M-m, N-n) So, the ultimate task is the following. Over all possible combinations of (m,n) and (M,N) find such that: S = S(m,n,M,N) T = argmin_{M,N}(M+N) where m,n,M,N satisfy conditions (**) There is one more sub-task left before we can formulate final algorithm to solve the problem: given an integer number S find all possible positive integers S1 and S2 such that:
This problem is a special case of integer factorization problem. The algorithm to factor any integer number into two multipliers is as simple as: int s1 = 1; int threshold = (int)Math.Sqrt(s) + 1; while (s1 < = threshold) { int ost = s % s1; if (ost == 0) { int s2 = s / s1; if (s2 < s1) break; // Output s1*s2 = s } s1++; } Problem solution It is time to formulate an algorithm that solves given task:
There is always a solution for any number S. If S is a prime, then there is only one factorization: S = 1*S and one possible solution: from origin (0,0) go to closest checkpoint (1,0) and to the point (1,S-1); T = 1+0+1+S-1 = S+1; Example: consider S = 9. 1) Factorization gives us two pairs (1,9) and (3,3).
2) The smallest found T_{0} is 6. There is no need to recalculate matrix G for each number S. Instead in the solution the rows of the matrix G will be built until numbers in the row are less than 10000000 (task constraint). Based on the matrix, a mapping from integer to a list of points < (x1,y1), (x2,y2), … > will be created, such that for each point (x,y) in the list of number N: N = G(x,y). Which means that step 2.a.i is no more than two lookups in such a mapping. The program can build a mapping once and reuse it while processing all test cases. Time complexity analysis The program should complete 20 test cases in less than 6 minutes. Building a mapping takes around 13 seconds on my laptop and ~1Gb of RAM which is acceptable. The rest is spent on factorizing and finding minimum values. There are two things I checked before I was convinced that my solution works fast enough to finish execution in 6 minutes:
So the worst possible input is 20 numbers equal to 8648640. Running the program on this input proves that on my machine it will take less than 15 seconds for any possible input. Most of that time spent on building the mapping. Results The initial solution was coded in C#, submitted and accepted by Facebook: The code that uses all above mentioned optimizations runs much faster and completes all test cases almost instantly. The code could be obtained by the following link: Final Checkpoint Solution or executed at Ideone.com Links
Code |
Last updated: 04.07.2014, created: 28.03.2012. |