Facebook Hacker Cup 2012 Round 1 Solutions: Checkpoint

Problem:

You 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

Solution:
Note that the racer will only take steps to the right or top. This leads us to a number of conclusions about the number of possible paths to a point in the lattice grid:

• the number of distinct shortest paths for every point situated on (x, 0) and (0, y) is 1;
• the number of distinct shortest paths for every target point on the lattice grid is exactly the sum of the number of distinct shortest paths leading to point at the target's immediate left, and point at the target's bottom.  This arrangement is very similar to the way binomial coefficients are calculated.

For each arrangement of the goal and checkpoint, the number S of distinct shortest paths leading to the goal through the checkpoint is number of shortest paths to the checkpoint Sc multiplied by the number of shortest paths from the checkpoint to the target St. Note that both these numbers can be found independently - for the number of paths to the checkpoint, the bottom left corner of the lattice grid represents the starting position; for the number of paths from the checkpoint to the target, the bottom left corner of the lattice grid represents the checkpoint.

The minimum number of steps needed to reach a point with coordinates [X, Y] in the lattice grid is obviously X+Y.

So, my algorithm has the following steps:

1. Pre-calculate the number of paths leading to each point in the lattice grid. The values are used to fill a vector P that maps number of distinct shortest paths to least possible amount of steps needed to reach a point in a lattice grid that has this exact number of distinct shortest paths leading to it from the starting corner. With a decent amount of constraints, this pre-calculation takes approximately ~500ms.
2. Set T to some large number (+inf)
3. Find all the possible pairs of factors F1, F2 for S (F1*F2=S). For each pair, check the sum P[F1]+P[F2], and, if the sum is less than T, store this sum as T.
4. Output T.