I will try exemplify what I mean by providing a sample problem from the Google Code Jam 2018, Round 1C 2018, Written by Pablo Heiber and pprepared by Kevin Tran.
The problem description:
What is the maximum number of these ants that can form such a stack?
So how did I solve it?
First, let's recall the pipe of steps involved in building a dynamic programming solution, namely:
Recursion
This problem reminds us of the knapsack 0-1 problem whose dynamic programming solution is laid out as a decision tree. Similarily we try to establish a decision tree for this problem. At each node encoded as state [n,w] , we need to establish the appropiate weight and the value of the node which will represent the maximum number of ants up to this node.
We start with the maximal supported weight among all ants. For each child node, we apply the following logic :
We have n levels in our decision tree with 3 nodes children on each node. The complexity of this algorithm goes to 3n time units. Under a large n this algorithm will not finish, hence we need to find another way to span our state space.
Here is the solution:
Scott has an ant farm containing N ants. Each ant has a certain length and weight.
Today, as a challenge for the ants, Scott has placed some food at the top of the ant farm. The ants will try to reach it by arranging themselves into a vertical stack, with each ant in the stack directly holding the next on its back. In this way, each ant bears the weight of all ants above it. Scott's ants are very strong for their size and are able to carry up to 6 times their own weight. For example, an ant that weights 8 milligrams can carry two other ants weighing 24 milligrams each! Each ant also has a body length; the exact lengths are not important, except that they are all different.
- The stack must be linear. Each ant except for the top ant must be directly below exactly one ant, and each ant except for the bottom ant must be directly above exactly one ant.
- The lengths of the ants in the stack must be strictly decreasing from the bottom to the top of the stack; this ensures that each new ant that joins the stack will be able to climb up to the top.
- For each ant, the sum of the weights of all the ants above it in the stack must be no more than 6 times the weight of that ant.
What is the maximum number of these ants that can form such a stack?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with an integer N: the number of ants in the colony. Then, a second line follows containing N integers W1,W2, ..., WN, where Wi is the weight in milligrams of the i-th ant. The ants are listed in strictly increasing order of length. Notice that no actual length values are given; only the order is important.
Output
For each test case, output one line containing
Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of the given ants that can form a stack that obeys the rules above.Limits
7 ≤ T ≤ 100.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
Test set 1 (Visible)
For exactly 6 cases, N = 100; for the other T - 6 cases, 2 ≤ N ≤ 50.
1 ≤ Wi ≤ 1000, for all i.
1 ≤ Wi ≤ 1000, for all i.
Test set 2 (Hidden)
For exactly 6 cases, N = 105; for the other T - 6 cases, 2 ≤ N ≤ 500.
1 ≤ Wi ≤ 109, for all i.
1 ≤ Wi ≤ 109, for all i.
So how did I solve it?
First, let's recall the pipe of steps involved in building a dynamic programming solution, namely:
- Recursion
- Memoization
- Bottom-up
Recursion
This problem reminds us of the knapsack 0-1 problem whose dynamic programming solution is laid out as a decision tree. Similarily we try to establish a decision tree for this problem. At each node encoded as state [n,w] , we need to establish the appropiate weight and the value of the node which will represent the maximum number of ants up to this node.
We start with the maximal supported weight among all ants. For each child node, we apply the following logic :
pseudocode:
we compare the current ant weight to the current supported weight
If we cannot support the current ant
then we go one ant downwards
else
we calculate a potential new weight as min(6 * ants[i - 1], supported weight - ants[i - 1]);
node [i][w] = max(1 + node[i - 1][new weight], node[i - 1][supported weight]);
end else
We have n levels in our decision tree with 3 nodes children on each node. The complexity of this algorithm goes to 3n time units. Under a large n this algorithm will not finish, hence we need to find another way to span our state space.
import java.io.*;
import java.util.*;
/**
Copyright belongs to Dub Andrei-Manuel.
Please refer this author to any reference
**/
public class Solution {
static boolean logTime = false;
public static Map getLadder() {
Map map = new HashMap();
long top = (long) Math.pow(10, 9);
long load = 0;
long weight = 1;
int ants = 1;
while (weight < top) {
if (load <= (6 * weight)) {
load += weight;
map.put(ants, weight);
System.out.println(ants+" : "+
weight);
ants++;
} else {
weight++;
}
}
return map;
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
int t = in.nextInt();
for (int i = 1; i <= t; ++i) {
int antsNr = in.nextInt();
long[] ants = new long[antsNr];
for (int j = 0; j < antsNr; j++) {
int weight = in.nextInt();
ants[j] = weight;
}
long start = System.currentTimeMillis();
int maxAnts2 = solutionDP2(ants);
long end = System.currentTimeMillis();
System.out.println("Case #" + i + ": " + maxAnts2);
if (logTime)
System.out.println(end - start);
}
}
public static long getMaxWeight(long[] ants) {
long max = 0l;
for (long weight : ants) {
if (weight > max)
max = weight;
}
return max;
}
public static int solutionDP2(long[] ants) {
int max = searchDP2(ants, ants.length);
return max;
}
public static int solutionDP(long[] ants) {
long capacity = getMaxWeight(ants) * 7;
int max = searchDP(ants, ants.length, capacity);
return max;
}
public static int searchDP2(long[] ants, int n) {
int max = 0;
int k = 139;
long[][] g = new long[n + 1][k + 1];
for (int x = 0; x <= n; x++) {
for (int y = 0; y <= k; y++) {
if (y > x) {
g[x][y] = Long.MAX_VALUE;
} else if (x == 0 || y == 0) {
g[x][y] = 0;
} else if (x == 1 && y == 1) {
g[x][y] = ants[x - 1];
} else {
if (g[x - 1][y - 1] > 6 * ants[x - 1]) {
g[x][y] = g[x - 1][y];
} else {
g[x][y] = Math.min(g[x - 1][y - 1] + ants[x - 1], g[x - 1][y]);
}
}
}
}
for (int y = 0; y <= k; y++) {
if (y > max && g[n][y] < Long.MAX_VALUE) {
max = y;
}
}
return max;
}
public static int searchDP(long[] ants, int n, long availableCapacity) {
int[][] K = new int[n + 1][((int) availableCapacity) + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= availableCapacity; w++) {
if (i == 0 || w == 0) {
K[i][w] = 0;
} else {
long potentialCapacity = Math.min(6 * ants[i - 1], w - ants[i - 1]);
if (ants[i - 1] > w)
K[i][w] = K[i - 1][w];
else
K[i][w] = Math.max(1 + K[i - 1][(int) potentialCapacity], K[i - 1][w]);
}
}
}
return K[n][(int) availableCapacity];
}
}
