johnluetke.net

On Saturday, I participated in the ACM Collegiate Programming Contest: Midwest Division.

Never have I undergone such mental pressure in my life.

My team only got one problem solved (#8), which was submitted at the 209th minute of a 300 minute competition. I regret not seeing that problem earlier, and submitting a correct solution before 2/3 of the contest was over. I would gladly bet that that could have motivated us to get another one finished. We were EXTREMELY close to solving #3 and #6, but a single itty-bitty mistake in both cases kept us from getting the correct answer. Our solution for #1 was correct, however it could not execute within the 10 second limit, due to my use of brute-force conversions of numbers to their binary representations (num % 2 for life!)

Here’s our solution to #8 for those interested. It really wasn’t that difficult, but still, it’s “Accepted Solution” receipt is our trophy:

import java.util.Scanner;

public class Problem8 {

	public static void main (String[] args) {
		String input = "";
		Scanner r = new Scanner(System.in);
		int index = 1;

			while (true) {
				input = r.nextLine();

				if (input.length() == 0)
					break;

				input = Problem8.flipAndPrepend(input);
				int[] sub_sum = new int[20];

				for (int i = 0; i < input.length(); i++) {
					int j = (i+1 >= input.length()-1) ? input.length()-1 : i+1;
					if (i == j)
						break;

					char c = input.charAt(i);
					char c2 = input.charAt(j);
					int val1 = Problem8.getRomanValue(c);
					int val2 = Problem8.getRomanValue(c2);

					if (val1 < val2)
						sub_sum[i] = val2-val1;
					else if (val1 >= val2)
						sub_sum[i] = val2+val1;
				}

				int total = 0;
				for (int i = 0; i < sub_sum.length; i++) {
					total += sub_sum[i];
				}

				System.out.println("Case "+(index++)+": total = "+total+"\n");
			}

	}

	public static String flipAndPrepend(String s) {
		String flipped = "";
		boolean even = (s.length() % 2 == 0);

		String t = (!even) ? s.substring(1, s.length()) : s;

		for (int i = t.length() -1 ; i >= 0; i--) {
			flipped += t.charAt(i)+"";
		}
		return flipped+s;
	}

	public static int getRomanValue (char c) {
		int value = 0;
		switch (c) {
			case 'I':
				value = 1; break;
			case 'V':
				value = 5; break;
			case 'X':
				value = 10; break;
			case 'L':
				value = 50; break;
			case 'C':
				value = 100; break;
			case 'D':
				value = 500; break;
			case 'M':
				value = 1000; break;
			default:
				value = 0;
		}
		return value;
	}
}

The hardest part was only having one computer to use between 3 people. The people on my team (myself included) are used to dynamic programming (testing our solution as we go along), and that ended up hurting us in the long run.

I would say there’s always next year, but for me, that isn’t the case. May is only 7 months away….

This entry was posted on Tuesday, November 3rd, 2009 at 7:05 pm and is filed under Blog. You can follow any responses to this entry through the RSS 2.0 feed. Responses are currently closed, but you can trackback from your own site.