Google Code Jam: Egg Drop Solution

The problem definition could be found at Code Jam web site.

Dynamic programming:

1. The main idea is to understand dependency between current drop and next/prev drops.
2. Let F(D, B) - function returning Fmax number of floors in a building when Solvable(F, D, B) is true.
3. Let do a drop. We know the result for this drop: egg has been dropped or egg has not been dropped. So we covered +1 floor. Now we have D-1 drops left.
4. If egg has not been dropped then we still have B breaks left and for all floors from 1 to current egg will not be dropped as well. To get value of Fmax we only need to estimate how many floors upstairs we could cover to have Solvable(F, D, B) as true. We could think that we are on the ground and required value could be evaluated by F(D-1, B).
5. If egg has been dropped then we have B-1 breaks left. The situation below current floor is still unknown but to estimate how many floors downstairs we could cover and have Solvable(F, D, B) as true we could use F(D-1, B-1).
6. Taking all above into an account we have F(D, B) = 1 + F(D-1, B) + F(D-1, B-1)

Implementation:

1. Next facts could help to have efficient implementation.
2. F(D, 1) = D - because to have Solvable(F, D, B) = true we should start from 1-st floor and continue dropping from next floor one by one.
   
3. F(1, B) = 1 - because to have Solvable(F, D, B) = true we should start from 1-st floor and no more drops left after first attempt.
   
4. F(x, x) = 2^x -1 - because to have Solvable(F, D, B) = true and to have optimal solution we should use divide and conquer approach
   
5. F(x, y) = F(x, x), for all y > x - the same as for (4) and more possible breaks don't affect the result.
6. We need to calculate F(D, B) only for B=1..32, because all other values could be evaluated by (5) or will be -1, because they will be greater then 2^32 (4294967296)
7. It is enough to have array[1..Z][1..32], where F(Z, 2) > 4294967296 values to have fast, cache-based implementation of F(D, B).
   (I don't know how to calculate Z theoretically, but practically Z=10000 is not enough and Z=100000 is enough)
   

F(D, B) - Illustration of facts discussed above

My solution is published below.

Main functions:

• solve - solves the problem
• initFCache - inits F-cache
• getF - gets Fmax from F-cache
• getD - gets Dmin based on F-cache
• getB - gets Bmin based on F-cache

public class EggDrop {
   ...
   
    private Scanner scanner;
    private PrintWriter writer;
   
    public EggDrop(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
   ...
   
    private static final long MAX_F_VALUE = 4294967296l;
    private static final int LARGE_F_VALUE = -1;
    private static final int MAX_B_INDEX = 32;
   
    private static final int F_CACHE_SIZE = 100000;
    private long[][] fCache;
   
    /**
     * Solve the problem
     */
    public void solve() {
        fCache = new long[F_CACHE_SIZE][MAX_B_INDEX];
        initFCache();
   
        int n = scanner.nextInt();
   
        for (int i = 1; i <= n; i++) {
            // int is enough to store all numbers
            // see Integer.MAX_VALUE, 2,000,000,000 < 2,147,483,647
            int F = scanner.nextInt();
            int D = scanner.nextInt();
            int B = scanner.nextInt();
   
            writer.print("Case #");
            writer.print(i + ": ");
   
            long Fmax = getF(D, B);
            int Dmin = getD(F, B, D);
            int Bmin = getB(F, D, B);
   
            writer.printf("%1$d %2$d %3$d\n", Fmax, Dmin, Bmin);
        }
    }
   
    /**
     * Get Fmax from F cache
     *
     * @param d D
     * @param b B
     * @return Fmax
     */
    private long getF(int d, int b) {
        if (b > MAX_B_INDEX)
            b = MAX_B_INDEX;
   
        if (b == 1)
            return d;
   
        if (d > F_CACHE_SIZE)
            return -1;
   
        return fCache[d - 1][b - 1];
    }
   
    /**
     * Get Dmin based on F cache
     *
     * @param f F
     * @param b B
     * @param dMax D
     * @return Dmin
     */
    private int getD(long f, int b, int dMax) {
        for (int d = 1; d <= dMax; d++) {
            long maxF = getF(d, b);
            if ((maxF == LARGE_F_VALUE) || (maxF >= f))
                return d;
        }
        throw new IllegalStateException(String.format("D not found, F=%1$d, B=%2$d, Dmax=%3$d", f, b, dMax));
    }
   
    /**
     * Get Bmin based on F cache
     *
     * @param f F
     * @param d D
     * @param bMax B
     * @return Bmin
     */
    private int getB(long f, int d, int bMax) {
        for (int b = 1; b <= bMax; b++) {
            long maxF = getF(d, b);
            if ((maxF == LARGE_F_VALUE) || (maxF >= f))
                return b;
        }
        throw new IllegalStateException(String.format("B not found, F=%1$d, D=%2$d, max B=%3$d", f, d, bMax));
    }
   
    /**
     * Init F cache. DP.<BR>
     * F(D, B) = F(D-1, B) + 1 + F(D-1, B-1)<BR>
     * if F(D, B) > 4294967296 then F(D, B) = -1
     */
    private void initFCache() {
        Arrays.fill(fCache[0], 1);
   
        for (int d = 1; d < F_CACHE_SIZE; d++) {
            fCache[d][0] = d + 1;
            for (int b = 1; b < MAX_B_INDEX; b++) {
                if ((fCache[d - 1][b] == LARGE_F_VALUE) || (fCache[d - 1][b - 1] == LARGE_F_VALUE))
                    fCache[d][b] = LARGE_F_VALUE;
                else {
                    fCache[d][b] = fCache[d - 1][b] + 1 + fCache[d - 1][b - 1];
                    if (fCache[d][b] >= MAX_F_VALUE)
                        fCache[d][b] = LARGE_F_VALUE;
                }
            }
        }
    }
}

See also other posts in Code Jam