Google code Jam 2013 – Qualification round finished

As many of you know, it’s been 10 hours since qualification round finished at Google code jam contest: http://code.google.com/codejam/

Appx. 21000 participants took part around the world with 25h time available for the round.

codejam_pic

Here are my solutions to 3 problems given out of 4:

https://github.com/vibneiro/googleJam2013

So, here’s the analysis:

1. Problem A: Tic-Tac-Toe-Tomek

Works on small and large sets. Just a simple algorithm to implement. The point is to comply with all the conditions. The goal is to find a winner. If there’s no winner, it should be draw, otherwise if we have empty cells the game is not completed.

import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

/**
  @Author: Ivan Voroshilin
  @Date: April 13 2013
  Problem A
  Small and large inputs
 */
public class TicTacToeTomek {

    private final static char XPLAYER = 'X';
    private final static char OPLAYER = 'O';
    private final static char T = 'T';
    private final static char EMPTY = '.';

    private final static String X_WON = "X won";
    private final static String O_WON = "O won";
    private final static String DRAW = "Draw";
    private final static String NOT_COMPLETED = "Game has not completed";

    private void solve(Scanner sc, PrintWriter pw) {

        char[][] array = { sc.next().toCharArray(), sc.next().toCharArray(), sc.next().toCharArray(), sc.next().toCharArray() };

        int xXCount = 0;
        int yXCount = 0;
        int xOCount = 0;
        int yOCount = 0;

        int dForwardXCount = 0;
        int dBackwardXCount = 0;
        int dForwardOCount = 0;
        int dBackwardOCount = 0;
        boolean hasEmptyCells = false;
        boolean hasWinner = false;

        for(int x = 0; x < array.length; x++) { // 4

            for(int y = 0; y < array.length; y++) { // 4

                //x-X
                if(array[x][y] == XPLAYER || array[x][y] == T) {
                    xXCount++;
                }

                //y-X
                if(array[y][x] == XPLAYER || array[x][y] == T) {
                    yXCount++;
                }

                //x-O
                if(array[x][y] == OPLAYER || array[x][y] == T) {
                    xOCount++;
                }

                //y-O
                if(array[y][x] == OPLAYER || array[x][y] == T) {
                    yOCount++;
                }

                if(array[x][y] == EMPTY) {
                    hasEmptyCells = true;
                }
            }

            if(!hasWinner && (xXCount == array.length || yXCount == array.length)) {
                System.out.println(X_WON);
                pw.println(X_WON);
                hasWinner = true;
            }

            if(!hasWinner && (xOCount == array.length || yOCount == array.length)) {
                System.out.println(O_WON);
                pw.println(O_WON);
                hasWinner = true;
            }

            xXCount = yXCount = xOCount = yOCount = 0;

            if(array[x][x] == XPLAYER || array[x][x] == T) {
                dForwardXCount++;
            }

            if(array[(array.length - 1 - x)][x] == XPLAYER || array[(array.length - 1 - x)][x] == T) {
                dBackwardXCount++;
            }

            if(array[x][x] == OPLAYER || array[x][x] == T) {
                dForwardOCount++;
            }

            if(array[(array.length - 1 - x)][x] == OPLAYER || array[(array.length - 1 - x)][x] == T) {
                dBackwardOCount++;
            }

        }

        if(!hasWinner && (dForwardXCount == array.length || dBackwardXCount == array.length)) {
            System.out.println(X_WON);
            pw.println(X_WON);
            hasWinner = true;
        } else
        if(!hasWinner && (dForwardOCount == array.length || dBackwardOCount == array.length)) {
            System.out.println(O_WON);
            pw.println(O_WON);
            hasWinner = true;
        }

        if(!hasWinner) {
            if(hasEmptyCells) {
                System.out.println(NOT_COMPLETED);
                pw.println(NOT_COMPLETED);
            } else {
                System.out.println(DRAW);
                pw.println(DRAW);
            }
        }

    }

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(new FileReader("A-large.in.txt"));
        PrintWriter pw = new PrintWriter(new FileWriter("output.txt"));

        int caseCnt = sc.nextInt();
        sc.nextLine();
        for (int caseNum = 0; caseNum < caseCnt; caseNum++) {
            System.out.println("Processing test case " + (caseNum + 1));
            pw.print("Case #" + (caseNum + 1) + ": ");
            new TicTacToeTomek().solve(sc, pw);

        }

        pw.flush();
        pw.close();
        sc.close();
    }

}

3. Problem C: Fair and Square

Small Data Sets

On small data sets it is a piece of cake – a classical algorithmic task which took me about 10 mins to write the code:

import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 @Author: Ivan Voroshilin
 @Date: April 13 2013
 Problem C
 Small inputs
 */
public class FairNSquare {

    private boolean isPalindrome(long num) {
        long reversed = 0;
        long n = num;

        while (n > 0) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }

        return num == reversed;
    }

    private void solve(Scanner sc, PrintWriter pw) {

        sc.nextLong();

        long a = sc.nextLong();
        long b = sc.nextLong();

        System.out.println(a);
        System.out.println(b);

        long number = a;
        long count = 0;

        while(number <= b) {
            if(isPalindrome(number)) {
                double d = Math.sqrt(number);
                if((d % 1) == 0 && isPalindrome((long)d)) {
                    count++;
                }
            }
            number++;
        }

        pw.println(count);
    }

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(new FileReader("C-small-attempt0.in.txt"));
        PrintWriter pw = new PrintWriter(new FileWriter("output.txt"));

        int caseCnt = sc.nextInt();
        sc.nextLine();
        for (int caseNum = 0; caseNum < caseCnt; caseNum++) {
            System.out.println("Processing test case " + (caseNum + 1));
            pw.print("Case #" + (caseNum + 1) + ": ");
            new FairNSquare().solve(sc, pw);
        }

        pw.flush();
        pw.close();
        sc.close();
    }

}

Large Data Sets

I tried to come up with a solution on large data sets, wrote the code which works using standard Bisection method based on a binary search but struggled to optimize time complexity of square root on BigInteger and palindrome checking on large ranges, I vaguely remember from Euler’s project there were some mathematical proofs regarding number 11 and palindromic numbers. There might be some very important facts which would allow to optimize for better performance however I decided not to waste time on it and moved to another problem.

Ok, here’s my solution which as been said didn’t pass time requirement.

import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Scanner;

/**
 @Author: Ivan Voroshilin
 @Date: April 13 2013
 Problem C
 Large inputs
 Comment: Poor time complexity
 */
public class FairNSquareLarge {

    private static boolean isPalindrome(BigInteger num) {
        BigInteger reversed = BigInteger.ZERO;
        BigInteger n = num;

        while (n.compareTo(BigInteger.ZERO) > 0) {
            reversed = reversed.multiply(BigInteger.valueOf(10)).add(n.mod(BigInteger.valueOf(10)));
            n = n.divide(BigInteger.valueOf(10));
        }

        return num.compareTo(reversed) == 0;
    }

    private static BigInteger sqrt(BigInteger n) {
        BigInteger a = BigInteger.ONE;
        BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
        while(b.compareTo(a) >= 0) {
            BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
            if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE);
            else a = mid.add(BigInteger.ONE);
        }
        return a.subtract(BigInteger.ONE);
    }

    private void solve(Scanner sc, PrintWriter pw) {

        BigInteger a = sc.nextBigInteger();
        BigInteger b = sc.nextBigInteger();

        BigInteger number = a;
        long count = 0;

        while(number.compareTo(b) <= 0) {
            if(isPalindrome(number)) {

                BigInteger d = sqrt(number);

                if(d.multiply(d).compareTo(number) == 0 && isPalindrome(d)) {
                    count++;
                }
            }
            number = number.add(BigInteger.ONE);
            System.out.println(number.toString());
        }

        pw.println(count);
    }

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(new FileReader("C-large-1.in.txt"));
        PrintWriter pw = new PrintWriter(new FileWriter("output.txt"));

        int caseCnt = sc.nextInt();
        sc.nextLine();
        for (int caseNum = 0; caseNum < caseCnt; caseNum++) {
            System.out.println("Processing test case " + (caseNum + 1));
            pw.print("Case #" + (caseNum + 1) + ": ");
            new FairNSquareLarge().solve(sc, pw);
        }

        pw.flush();
        pw.close();
        sc.close();
    }

}

4. Problem D: Treasure

Small Data Sets

I first did a straightforward BFS with checking for deadlocks and then realized from conditions that there might be several paths to open all chests and the goal is to select minimal path from all sorted lexicographically. Sure, we could make a simple systematic backtracking using all permutations of paths which has a terrible complexity O(n!) and doesn’t meet time requirements even on small sets, e.g. N=20 chests where we have 20! distinct permutations (ouch!).

I had time pressure (1h until the end of round) and nixed that idea to proceed but this problem is really challenging. Sorry!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s