Code Jam 2020 Qualification Round solutions (75 points)

Q_1Vestigium.java

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

/**
 * 2020-Q. Vestigium
 * @author Albert Choi
 */
public class Q_1Vestigium {
	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 Q_1Vestigium().doProblem()
			));
		}
	}

	Object doProblem() {
		int N = nint(); nline();
		int r = 0;
		int c = 0;
		int[][] grid = new int[N][N];
		int diag = 0;
		for (int i=0; i<N; i++) {
			boolean[] row = new boolean[N];
			int add = 0;
			for (int j=0; j<N; j++) {
				int v = grid[i][j] = nint();
				if (i==j) diag += v;
				if (row[v-1]) add = 1;
				else row[v-1] = true;
			}
			r += add;
			nline();
		}
		for (int i=0; i<N; i++) {
			boolean[] col = new boolean[N];
			int add = 0;
			for (int j=0; j<N; j++) {
				int v = grid[j][i];
				if (col[v-1]) add = 1;
				else col[v-1] = true;
			}
			c += add;
		}
		return diag + " " + r + " " + c;
	}
}

Q_2NestingDepth.java

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

/**
 * 2020-Q. Nesting Depth
 * @author Albert Choi
 */
public class Q_2NestingDepth {
	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 Q_2NestingDepth().doProblem()
			));
		}
	}

	Object doProblem() {
		char[] s = nline().toCharArray();
		int lv = 0;
		StringBuilder sb = new StringBuilder();
		for (int i=0; i < s.length; i++) {
			char c = s[i];
			int d = c - '0';
			while (lv < d) {
				sb.append('(');
				lv++;
			}
			while (lv > d) {
				sb.append(')');
				lv--;
			}
			sb.append(d);
		}
		while (lv > 0) {
			sb.append(')');
			lv--;
		}
		return sb;
	}
}

Q_3ParentalPartneringReturns.java

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

/**
 * 2020-Q. PPR
 * @author Albert Choi
 */
public class Q_3ParentalPartneringReturns {
	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 Q_3ParentalPartneringReturns().doProblem()
			));
		}
	}

	static class Pair implements Comparable<Pair> {
		int start;
		int end;
		char ans;
		Pair(int s, int e) {
			start = s;
			end = e;
		}
		public int compareTo(Pair o) {
			return start - o.start;
		}
	}


	Object doProblem() {
		int N = nint(); nline();
		Pair[] times = new Pair[N];

		for (int i=0; i<N; i++){
			times[i] = new Pair(nint(), nint());
			nline();
		}
		Pair[] sorted = times.clone();
		Arrays.sort(sorted);

		Pair lastc = null, lastj = null;

		for (int i=0; i<N; i++) {
			Pair time = sorted[i];
			if (lastc == null || lastc.end <= time.start) {
				// no conflict
				lastc = time;
				time.ans = 'C';
			}
			else if (lastj == null || lastj.end <= time.start) {
				lastj = time;
				time.ans = 'J';
			}
			else return "IMPOSSIBLE";
		}
		
		char[] ans = new char[N];
		for (int i=0; i<N; i++) {
			ans[i] = times[i].ans;
		}

		return String.valueOf(ans);
	}
}

Q_4ESAbATAd.java

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

/**
 * 2020-Q. ESAb ATAd
 * @author Albert Choi
 */
public class Q_4ESAbATAd {
	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 int B;
	public static void main(String[] args) {
		int T = nint(); B = nint(); nline();
		for (int t=1; t<=T; t++) {
			new Q_4ESAbATAd().doProblem();
		}
	}

	// get response to answer as a char
	char getrc() {
		char c = nline().charAt(0);
		if (c == 'N') System.exit(0);
		return c;
	}

	static class Pair {
		int pos;
		char val;
		Pair(int p, char v) {
			pos = p;
			val = v;
		}
		int index() {
			return pos-1;
		}
		int rindex() {
			return B-pos;
		}
	}

	int pos = 1;
	int round = 0;
	
	List<Pair> sames = new ArrayList<>();
	List<Pair> diffs = new ArrayList<>();
	
	void doProblem() {

		while (true) {
			// find pairs of bits (x,y) at position P and B-P, i.e. mirrored positions
			findPairs();

			// we must have reached round 10 OR we went through half the array
			if (pos > B/2) {
				// went through half the array
				// we're done!
				// Convert pairs into an array
				char[] ans = new char[B];
				for (Pair p : sames) {
					ans[p.index()] = p.val;
					ans[p.rindex()] = p.val;
				}
				for (Pair p : diffs) {
					ans[p.index()] = p.val;
					ans[p.rindex()] = flip(p.val);
				}
				sout.println(ans);
				getrc();
				return;
			}
			if (round % 10 == 0) {
				if (!sames.isEmpty()) {
					// re-query same pair
					Pair same = sames.get(0);
					char newVal = query(same.pos);
					boolean flip = newVal != same.val;

					if (flip) {
						for (Pair p : sames) {
							p.val = flip(p.val);
						}
					}
				}
				if (!diffs.isEmpty()) {
					// re-query diff pair
					Pair diff = diffs.get(0);
					char newVal = query(diff.pos);
					boolean flip = newVal != diff.val;
					
					if (flip) {
						for (Pair p : diffs) {
							p.val = flip(p.val);
						}
					}
				}
				if (round % 2 == 1) {
					// odd number, waste one
					query(1);
				}
			}
			else {
				// something horrible as happened
			}
				
		}
	}

	void findPairs() {
		while ((round == 0 || round % 10 != 0) && pos <= B/2) {
			char x = query(pos);
			char y = query(B-pos + 1);

			Pair p = new Pair(pos, x);
			if (x == y) {
				sames.add(p); 
			} else {
				diffs.add(p);
			}
			pos++;
		}
	}

	char flip(char c) {
		return (c == '0' ? '1': '0');
	}


	char query(int pos) {
		serr.println(">> "+round);
		sout.println(pos);
		round++;
		return nline().charAt(0);
	}

}

Q_5Indicium.java

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

/**
 * 2020-Q. (actual brute force)
 * @author Albert Choi
 */
public class Q_5Indicium {
	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 Q_5Indicium().doProblem()
			));
		}
	}

	Object doProblem() {
		N = nint();
		K = nint(); nline();
		grid = new int[N][N];
		ru = new boolean[N][N];
		cu = new boolean[N][N];

		boolean found = solve(0, 0);

		String s = (found ? "":"IM") + "POSSIBLE";
		
		if (found) {
			for (int i=0;i<N;i++) {
				s += "\n";
				for (int j=0;j<N;j++){
					s += (j==0 ? "":" ") + grid[i][j];
				}
			}
		}
		return s;
	}
	
	int[][] grid;
	int N;
	int K;
	boolean[][] ru, cu;
	
	boolean solve(int r, int c) {
		if (r == N && c == 0) {
			int sum = 0;
			for (int i=0;i<N;i++){
				sum += grid[i][i];
			}
			//serr.println(sum);
			return sum == K;
		}
		
		for (int j=0; j<N; j++) {
			if (!ru[r][j] && !cu[c][j]) {
				ru[r][j] = cu[c][j] = true;
				grid[r][c] = j+1;

				if (c == N-1) {
					if (solve(r+1, 0)) return true;
				}
				else {
					if (solve(r, c+1)) return true;
				}
				ru[r][j] = cu[c][j] = false;
			}
		}
		return false;
	}
}