Code Jam 2020 - Round 1A solutions (33 points)

R1A_1PatternMatching.java

import java.io.PrintStream;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

/**
 * 2020-R1A. Pattern Matching - solves Test Sets 1 and 2 (one asterisk only)
 * @author Albert Choi
 */
public class R1A_1PatternMatching {
	static Scanner in = new Scanner(System.in);
	static PrintStream sout = System.out, serr = System.err;
	static int nint() {return in.nextInt();}
	static long nlong() {return in.nextLong();}
	static BigInteger nbig() {return in.nextBigInteger();}
	static String nline() {return in.nextLine();}

	public static void main(String[] args) {
		int T = nint(); nline();
		for (int t=1; t<=T; t++) {
			sout.println("Case #" + t + ": " + String.valueOf(
					new R1A_1PatternMatching().doProblem()
			));
		}
	}

	int N;
	char[][] words;
	String[] swords;
	int[] curs;
	String ans = "";

	Object doProblem() {
		N = nint(); nline();
		words = new char[N][];
		swords = new String[N];
		curs = new int[N];
		//List<String> words = new ArrayList<>();
		for (int i=0;i<N;i++){
			//words.add(nline().trim());
			swords[i] = nline().trim();
			words[i] = swords[i].toCharArray();
		}
		String pre = findToStar();
		for (int i=0;i<N;i++){
			String s = swords[i];
			words[i] = rev(s);
			curs[i] = 0;
		}
		String post = findToStar();
		if (pre == null || post == null) {
			return "*";
		}
		return pre + String.valueOf(rev(post));
	}

	char[] rev(String s){
		char[] w = new char[s.length()];
		for (int j=0;j<s.length();j++){
			w[j] = s.charAt(s.length()-j-1);
		}
		return w;
	}
	String findToStar() {
		String ans = "";
		while (true) {
			char chosen = 0;
			int wilds = 0;

			for (int i=0;i<N;i++){
				if (words[i].length <= curs[i]) continue;  // done

				char[] word = words[i];
				char c= word[curs[i]];
				if (c == '*') {
					wilds++;
					continue; // match any
				}
				
				if (chosen == 0) {
					chosen = c;
					ans += c;
				}
				else {
					if (chosen != c) {
						return null;
					}
				}
				curs[i]++;
			}
			
			if (chosen == 0) {
				break;
			}
		}
		return ans;
	}
	
}

R1A_2PascalWalk.java

import java.io.PrintStream;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

/**
 * 2020-R1A. Pascal Walk - solves Test Sets 1 and 2 (up to N = 1000) only
 * @author Albert Choi
 */
public class R1A_2PascalWalk {
	static Scanner in = new Scanner(System.in);
	static PrintStream sout = System.out, serr = System.err;
	static int nint() {return in.nextInt();}
	static long nlong() {return in.nextLong();}
	static BigInteger nbig() {return in.nextBigInteger();}
	static String nline() {return in.nextLine();}

	static long[][] pascal = new long[50][];

	static long pascal(int i, int j){
		if (j == 1 || j == i) return 1;
		else return pascal[i][j];
	}

	// generate a row and save it
	static void gen(int i) {
		pascal[i] = new long[i+1];
		for (int j=1;j<i+1;j++){
			if (j==1 || j==i) {
				pascal[i][j] = 1;
			}
			else pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
			//serr.print(pascal[i][j] + " ");
		}
	}

	public static void main(String[] args) {
		for (int i=1;i<50;i++){
			//gen(i);
			//serr.println();
		}		

		// generate test cases
		for (int i=1; i<1001; i++) {
			//serr.println(i);
		}
		int T = nint(); nline();
		for (int t=1; t<=T; t++) {
			sout.println("Case #" + t + ": " + String.valueOf(
					new R1A_2PascalWalk().doProblem()
					));
		}
	}

	int N;

	Object doProblem() {
		N = nint();
		path.add(new Pair(1,1));
		findPath(N-1);
		StringBuilder sb = new StringBuilder();

		long sum = 0;
		for (Pair p: path){
			sb.append("\n");
			sb.append(p.a);
			sb.append(" ");
			sb.append(p.b);
			//sb.append(" " + pascal(p.a, p.b));
			sum += pascal(p.a, p.b);
		}
		// verify answer
		if (sum != N) {
			throw new RuntimeException("FAIL");
			//serr.println("FAIL " + N + " " + sum);
			//return sb;
		}
		return sb;
	}

	static class Pair {
		int a, b;
		Pair(int aa, int bb) {a=aa;b=bb;}
	}

	List<Pair> path = new ArrayList<>();

	void findPath(long goal) {
		while (goal > 0) {
			Pair last = path.get(path.size()-1);
			if (goal <= 500 - path.size()) {
				// go left, then straight down
				while (last.b > 1) {
					last = new Pair(last.a, last.b - 1);
					path.add(last);
					goal -= pascal[last.a][last.b];
				}
				while (goal > 0) {
					last = new Pair(last.a+1, 1);
					path.add(last);
					goal--;
				}
			}
			else {
				long nextRow = 0;
				// generate row if not memoized yet
				if (pascal[last.a+1] == null) {
					gen(last.a+1);
				}
				for (int k=1; k<=last.b; k++) {
					nextRow += pascal[last.a+1][k];
				}
				// down right
				if (nextRow + pascal[last.a+1][last.b+1] <= goal) {
					path.add(new Pair(last.a+1, last.b+1));
					goal -= pascal[last.a+1][last.b+1];
				}
				// down
				else if (nextRow <= goal) {
					path.add(new Pair(last.a+1, last.b));
					goal -= pascal[last.a+1][last.b];
				}
				// left
				else {
					path.add(new Pair(last.a, last.b-1));
					goal -= pascal[last.a][last.b-1];
				}
			}
		}
	}
}

R1A_3SquareDance.java

import java.io.PrintStream;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

/**
 * 2020-R1A. Square Dance - solves Test Set 1 only
 * @author Albert Choi
 */
public class R1A_3SquareDance {
	static Scanner in = new Scanner(System.in);
	static PrintStream sout = System.out, serr = System.err;
	static int nint() {return in.nextInt();}
	static long nlong() {return in.nextLong();}
	static BigInteger nbig() {return in.nextBigInteger();}
	static String nline() {return in.nextLine();}

	public static void main(String[] args) {
		int T = nint(); nline();
		for (int t=1; t<=T; t++) {
			sout.println("Case #" + t + ": " + String.valueOf(
					new R1A_3SquareDance().doProblem()
			));
		}
	}

	int R, C;
	int skill[][];

	Object doProblem() {
		R=nint(); C=nint(); nline();
		skill = new int[R][C];
		for (int i=0;i<R;i++){
			for (int j=0;j<C;j++){
				skill[i][j] = nint();
			}
			nline();
		}

		long total = 0;

		while(true) {
			int elims = 0;
			int[][] count = new int[R][C];
			int[][] csum = new int[R][C];

			// by row
			for (int i=0;i<R;i++){
				int last = 0; // value
				int lastj = -1;
				
				for (int j=0;j<C;j++){
					int cur = skill[i][j]; 

					if (cur > 0) {
						if (lastj >= 0) {
							csum[i][j] += last;
							count[i][j] ++;
							csum[i][lastj] += cur;
							count[i][lastj] ++;
						}
						last = cur;
						lastj = j;
					}
				}
			}
			// by col
			for (int j=0;j<C;j++){
				int last = 0;
				int lasti = -1;
	
				for (int i=0;i<R;i++){
					int cur = skill[i][j]; 

					if (cur > 0) {
						if ( lasti >= 0) {
							csum[i][j] += last;
							count[i][j] ++;
							csum[lasti][j] += cur;
							count[lasti][j] ++;
						}
						last = cur;
						lasti = i;
					}
				}
			}

			for (int i=0;i<R;i++){
				for (int j=0;j<C;j++){
					int cur = skill[i][j]; 
					total += cur; // INTEREST

					if (cur > 0) {
						int thresh = cur * count[i][j];
						if (csum[i][j] > thresh) {
							elims++;
							skill[i][j] = 0;
						}
					}
				}
			}

			if (elims == 0) break;
		}
		return total;
	}
}