UVA - 11420 - Chest of Drawers

This article will explain my thought process to solve a problem called Chest of Drawers (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Permutation, Dynamic Programming

Problem Summary

Given:

Total drawers
Total secured drawers

We want to:

Total ways to configure the drawers

Glossary

Permutation — A mathematical concept that determines the number of possible arrangements for a specific set of elements.
Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.
Depth-first Search (DFS) — A graph traversal algorithm that starts from a source vertex and explores each path completely before backtracking and exploring other paths.

Observation

A drawer is either lock or unlocked. A secured drawer is either (1) A locked drawer that is followed by a locked drawer on top of it, or (2) A locked drawer located on the highest level of the drawers. We could explore every possible configuration of the drawers by creating a permutation of lock or unlock state for each drawer. For each drawer configuration, count the number of drawer that fulfill the criteria of a secured drawer and compare it against the desired number of secured drawers from the input. This will let us know the number of valid drawer configuration at the end of the iteration.

Next, after we’ve discovered the permutation solution, we need to further optimize the logic to avoid TLE. The permutation solution tries to explore every possible configuration, from the lowest-to-highest level. This iteration process is similar to DFS traversal.

Next, by observing the iteration process, we could see that each iteration is trying to find the number of valid configurations from the remaining unconfigured drawers. This structure can be transformed into DP, where the unconfigured drawers is the state and the number of valid configurations is the value. Unconfigured drawers can be expressed as a combination of the last configured drawer, remaining height of the drawers, and remaining number of secured drawers.

Algorithm

To explore permutation of every possible drawers, we could implement DFS which unlock and lock the drawer at each height. On each iteration, we keep track of the last configured drawer, the remaining height of the drawers, and the remaining number of secured drawers as the state of the DFS. To avoid re-computation, we store those state along with the number of secured drawers in the DP Memoization.

The time complexity of this problem is O({total drawers} * {total secured drawers}) or O(10^3).

Implementation

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;

/**
 * 11420 - Chest of Drawers
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2415
 */
public class Main {
    public static void main(final String... args) throws IOException {
        final BufferedIO io = new BufferedIO(System.in, System.out);
        final Process process = new Process();

        while (true) {
            final String[] lines = io.readLines(" ");

            final Input input = new Input();
            input.totalDrawers = Integer.parseInt(lines[0]);
            input.totalSecuredDrawers = Integer.parseInt(lines[1]);
            if (input.isEOF()) break;

            final Output output = process.process(input);
            io.write("%d\n", output.totalWays);
        }

        io.close();
    }
}

final class BufferedIO {
    private final BufferedReader in;
    private final BufferedWriter out;

    public BufferedIO(final InputStream in, final OutputStream out) {
        this.in = new BufferedReader(new InputStreamReader(in));
        this.out = new BufferedWriter(new OutputStreamWriter(out));
    }

    public String[] readLines(final String separator) throws IOException {
        final String line = readLine();
        return line == null ? null : line.split(separator);
    }

    public String readLine() throws IOException {
        String line = in.readLine();
        while (line != null && line.isEmpty()) line = in.readLine();
        return line;
    }

    public void write(final String format, Object... args) throws IOException {
        final String string = String.format(format, args);
        write(string);
    }

    public void write(final String string) throws IOException {
        out.write(string);
    }

    public void close() throws IOException {
        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int totalDrawers;
    public int totalSecuredDrawers;

    public boolean isEOF() {
        return totalDrawers < 0 && totalSecuredDrawers < 0;
    }
}

class Output {
    public long totalWays;
}

class Process {
    private static final int UNLOCKED = 0;
    private static final int LOCKED = 1;

    public Output process(final Input input) {
        final Output output = new Output();
        final Memoization memoization = new Memoization(input);
        output.totalWays = getTotalWays(memoization, UNLOCKED, input.totalDrawers, input.totalSecuredDrawers);
        return output;
    }

    private long getTotalWays(
        final Memoization memoization,
        final int lastDrawer,
        final int remainingHeight,
        final int remainingTotalSecuredDrawers
    ) {
        final boolean invalid = remainingHeight < 0 || remainingTotalSecuredDrawers < 0;
        if (invalid) {
            return 0;
        }

        final boolean topmost = remainingHeight == 0;
        if (topmost) {
            final boolean secured = lastDrawer == LOCKED;
            final boolean valid = 0 == remainingTotalSecuredDrawers - (secured ? 1 : 0);
            return valid ? 1 : 0;
        }

        final boolean computed = memoization.contains(lastDrawer, remainingHeight, remainingTotalSecuredDrawers);
        if (computed) {
            return memoization.get(lastDrawer, remainingHeight, remainingTotalSecuredDrawers);
        }

        long totalWays = 0;
        totalWays += getTotalWays(memoization, UNLOCKED, remainingHeight - 1, remainingTotalSecuredDrawers);
        final boolean secured = lastDrawer == LOCKED;
        totalWays += getTotalWays(memoization, LOCKED, remainingHeight - 1, remainingTotalSecuredDrawers - (secured ? 1 : 0));

        return memoization.set(lastDrawer, remainingHeight, remainingTotalSecuredDrawers, totalWays);
    }
}

class Memoization {
    private final long[][][] totalWays;
    private final boolean[][][] exists;

    public Memoization(final Input input) {
        totalWays = new long[2][input.totalDrawers + 1][input.totalSecuredDrawers + 1];
        exists = new boolean[2][input.totalDrawers + 1][input.totalSecuredDrawers + 1];
    }

    public long set(
        final int lastDrawer,
        final int remainingHeight,
        final int remainingTotalSecuredDrawers,
        final long totalWays
    ) {
        exists[lastDrawer][remainingHeight][remainingTotalSecuredDrawers] = true;
        return this.totalWays[lastDrawer][remainingHeight][remainingTotalSecuredDrawers] = totalWays;
    }

    public boolean contains(
        final int lastDrawer,
        final int remainingHeight,
        final int remainingTotalSecuredDrawers
    ) {
        return exists[lastDrawer][remainingHeight][remainingTotalSecuredDrawers];
    }

    public long get(
        final int lastDrawer,
        final int remainingHeight,
        final int remainingTotalSecuredDrawers
    ) {
        return totalWays[lastDrawer][remainingHeight][remainingTotalSecuredDrawers];
    }
}