Class 08 - Dynamic Programming, Bottom-Up

Main00673Parenthesis.java

package class08;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

// Parenthesis 00673

public class Main00673Parenthesis {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(in.readLine());
		
		while (N-- > 0) {
			String line = in.readLine();
			
			Stack<Character> stack = new Stack<Character>();
			
			boolean okay = true;
			
			loop: for (int i = 0; i < line.length(); i++) {
				char ch = line.charAt(i);
				
				switch (ch) {
				case '(':
				case '[':
					stack.push(ch);
					break;
					
				case ')':
					if (stack.isEmpty()) {
						okay = false;
						break loop;
					} else {
						char match = stack.pop();
						if (match != '(') {
							okay = false;
							break loop;
						}
					}
					break;
					
				case ']':
					if (stack.isEmpty()) {
						okay = false;
						break loop;
					} else {
						char match = stack.pop();
						if (match != '[') {
							okay = false;
							break loop;
						}
					}
				}
			}
			
			if (okay) {
				if (!stack.isEmpty()) {
					okay = false;
				}
			}
			
			System.out.println(okay ? "Yes" : "No");
		}
	}
	
}

Main10131IsBiggerSmarter.java

package class08;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Stack;


// Is Bigger Smarter? UVa 10131

public class Main10131IsBiggerSmarter {

	public static void main(String[] args) throws Exception {
		new Main10131IsBiggerSmarter().run();
	}
	
	public class Elephant {
		int w, s, idx;
		
		public Elephant(int w, int s, int idx) {
			this.w = w;
			this.s = s;
			this.idx = idx;
		}
		
		public String toString() {
			return String.format("%d %d", w, s);
		}
	}
	
	// Elephants sorted by weight
	ArrayList<Elephant> elephants = new ArrayList<Elephant>();
	
	public void run() throws Exception {
		Scanner in = new Scanner(System.in);
		
		int idx = 1;
		
		while (in.hasNextInt()) {
			Elephant e = new Elephant(in.nextInt(), in.nextInt(), idx++);
			elephants.add(e);
		}
		
		// Sort the elephants by weight, increasing
		Collections.sort(elephants, new Comparator<Elephant>() {
			@Override
			public int compare(Elephant o1, Elephant o2) {
				if (o1.w < o2.w) {
					return -1;
				} else if (o1.w > o2.w) {
					return 1;
				} else if (o1.s > o2.s) {
					return -1;
				} else if (o1.s < o2.s) {
					return 1;
				} else {
					return 0;
				}
			}
		});
		
		int N = elephants.size();
		
		// Perform longest decreasing subsequence in the following steps
		
		int dp[] = new int[N+1];
		int backtrack[] = new int[N+1];
		Arrays.fill(backtrack, -1);
		int max = 0;
		
		for (int i = 1; i < N; i++) {
			dp[i] = 1;
			Elephant e1 = elephants.get(i);
			for (int j = 0; j < N; j++) {
				Elephant e2 = elephants.get(j);
				
				if (e1.s < e2.s && e1.w > e2.w && dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
					backtrack[i] = j;
					max = Math.max(max, dp[i]);
				}
			}
		}
		
		// Now backtrack through the longest decreasing subsequence and print out the elephants in it
		
		Stack<Integer> stack = new Stack<Integer>();
		
		for (int i = N-1; i >= 0; i--) {
			if (dp[i] == max) {
				do {
					stack.push(i);
					i = backtrack[i];
				} while (i != -1);
				
				break;
			}
		}
		
		System.out.println(max);
		
		while (!stack.isEmpty()) {
			System.out.println(elephants.get(stack.pop()).idx);
		}
	}
	
}

Main10192Vacation.java

package class08;
import java.io.BufferedReader;
import java.io.InputStreamReader;

// Vacation UVa 10192

public class Main10192Vacation {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int count = 1;
		
		while (true) {
			String S1 = in.readLine();
			
			if (S1.equals("#")) {
				break;
			}
			
			String S2 = in.readLine();
			
			int dp[][] = new int[S1.length()+1][S2.length()+1];
			
			for (int i = 1; i <= S1.length(); i++) {
				char ch1 = S1.charAt(i-1);
				for (int j = 1; j <= S2.length(); j++) {
					char ch2 = S2.charAt(j-1);
					
					if (ch1 == ch2) {
						dp[i][j] = 1 + dp[i-1][j-1];
					}
					
					dp[i][j] = Math.max(dp[i][j], Math.max(dp[i-1][j], dp[i][j-1]));
				}
			}
			
			System.out.printf("Case #%d: you can visit at most %d cities.\n", count++, dp[S1.length()][S2.length()]);
		}
	}

}

Main10564PathsThroughTheHourglass.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

// WA because DP must be recursive in order to print out the proper lexicographical sequence

public class Main10564PathsThroughTheHourglass {
	
	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		
		while (in.hasNextInt()) {
			int N = in.nextInt();
			int S = in.nextInt();
			
			if (N == 0 && S == 0) {
				break;
			}
			
			// parse the input and make sure the hourglass is surrounded by -1s
			
			int hourglass[][] = new int[2*N+1][N+2];
			
			for (int[] h : hourglass) {
				Arrays.fill(h, -1);
			}
			
			for (int r = 1; r <= N; r++) {
				for (int c = 1; c <= (N-r+1); c++) {
					hourglass[r][c] = in.nextInt();
				}
			}
			
			for (int r = N+1, rr = 2; r <= 2*N-1; r++, rr++) { // rr keeps track of the width of the row
				for (int c = 1; c <= rr; c++) {
					hourglass[r][c] = in.nextInt();
				}
			}
			
			int dp[][][] = new int[500][2*N+1][N+2];
			boolean prevUpRight[][][] = new boolean[500][2*N+1][N+2];
			
			for (int d[][] : dp) {
				for (int dd[] : d) {
					Arrays.fill(dd, -1);
				}
			}
			
			for (int i = 1; i < N+2; i += 2) {
				dp[0][0][i] = 1;
			}

			for (int r = 1; r <= 2*N-1; r++) {
				for (int c = 1; c <= N; c++) {
					if (hourglass[r][c] < 0) {
//						System.out.printf("NOPE r %d c %d\n", r, c);
						continue;
					}
					
					int upLeft = r <= N ? 0 : -1;
					int upRight = r <= N ? 1 : 0;
					
					// fill in with the up and right cell
					for (int i = 0; i < 500 - hourglass[r][c]; i++) {
						if (dp[i][r-1][c+upRight] >= 0) {
							if (dp[i + hourglass[r][c]][r][c] < 0) {
								dp[i + hourglass[r][c]][r][c] = 0;
							}
							dp[i + hourglass[r][c]][r][c] += dp[i][r-1][c+upRight];
							prevUpRight[i + hourglass[r][c]][r][c] = true;
//							System.out.printf("YEP: r %d c %d val %d count %d\n", r, c, i + hourglass[r][c], dp[i + hourglass[r][c]][r][c]);
						}
					}
					
					// fill in with the up and left cell
					for (int i = 0; i < 500 - hourglass[r][c]; i++) {
						if (dp[i][r-1][c+upLeft] >= 0) {
							if (dp[i + hourglass[r][c]][r][c] < 0) {
								dp[i + hourglass[r][c]][r][c] = 0;
							}
							dp[i + hourglass[r][c]][r][c] += dp[i][r-1][c+upLeft];
//							System.out.printf("YEP: r %d c %d val %d count %d\n", r, c, i + hourglass[r][c], dp[i + hourglass[r][c]][r][c]);
						}
					}
				}
			}
			
			// print it out
			
			int total = 0;
			
			ArrayList<String> paths = new ArrayList<String>();
			
			for (int i = 1; i <= N; i++) {
				if (dp[S][2*N-1][i] >= 0) {
					total += dp[S][2*N-1][i];
					
					StringBuilder sb = new StringBuilder();
					
					int r = 2*N-1;
					int c = i;
					int s = S;
					
					while (r > 1) {
						int newS = s - hourglass[r][c];
						
						if (prevUpRight[s][r][c]) {
							sb.append('L');
							if (r <= N) {
								c++;
							}
						} else {
							sb.append('R');
							if (r > N) {
								c--;
							}
						}
						
						s = newS;
							
						r--;
					}
					
					sb.reverse();
					
					paths.add((c-1) + " " + sb.toString());
				}
			}
			
			Collections.sort(paths);
			
			System.out.println(total);
			
			if (total > 0) {
				System.out.println(paths.get(0));
			} else {
				System.out.println();
			}
			
//			System.out.println(Arrays.toString(dp[7][2]));
		}
	}

}