Friday, July 18, 2008

Google Code Jam

I took a couple of hours last night the to solve the problems of Google Code Jam preliminary(qualifying) round. Both are correct. And are "beautiful", or so I think.

The detailed problem statements are here: http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtcg8LEghjb250ZXN0cxjqOQw

All the solutions are also downloadable. But many are solutions in C++ with Vectors and some nifty solutions in python. At least the top solutions are so. Any way, here I have what I think are good solutions in Java. Let me know if U think otherwise and why so. If you are looking for alternative Java solution, head over to this page: http://code.google.com/codejam/contest/scoreboard?c=agdjb2RlamFtcg8LEghjb250ZXN0cxjqOQw&show_type=all&start_pos=161&views_time=1&views_number=1&views_file=0&csrfmiddlewaretoken= to check out the solution of Tsubosaka, rank 168.

For executing, place the files a1.txt (b3.txt for the second program) in the same folder as the Java files are placed.

Problem 1: Search Engines

import java.io.*;
import java.util.*;
public class A2 {
    int seMax,inMax;
    String[] se,in;
    int i,count;
    boolean b[];
    
    A2(int seMax,String[] se,int inMax,String[] in){
        this.seMax=seMax;
        this.inMax=inMax;
        this.se=se;
        this.in=in;
    
        boolean bol[]= new boolean [seMax];
        Arrays.fill(bol,true);
        b=bol;
        //System.out.println("seMax="+seMax+" inMax= "+inMax);
    }
    
    int findStrPosi(String[] sa, String str, int sMax){
        int posi;
        for(posi=0;posi<sMax && !str.equals(sa[posi]);posi++);
        return posi;
    }
    
    int findCount(){
        //System.out.println(in[]);
        for(i=0;i<inMax;i++){
            //System.out.println(findStrPosi(se,in[i],seMax));
            int curSea=findStrPosi(se,in[i],seMax);
            b[curSea]=false;
            
            boolean isChange=false;
            for(int j=0;j<seMax;isChange=isChange||b[j],j++);
            isChange=!isChange;
            
            if(isChange){
                count++;
                Arrays.fill(b, true);
                b[curSea]=false;
            }
        }
        return count;
        }
 
    public static void main(String[] x)throws IOException{
        File file=new File("./a1.txt");
        String[] se=new String[100];
        String[] in=new String[1000];
        BufferedReader fileIn = new BufferedReader(new FileReader(file));
        
        String fileLine=fileIn.readLine();
        int pMax=Integer.parseInt(fileLine);
        for(int p=0;p<pMax;p++){
            int seMax=Integer.parseInt(fileIn.readLine());
            for(int q=0;q<seMax;q++){
                se[q]=fileIn.readLine().toString();
            }
            int inMax=Integer.parseInt(fileIn.readLine());
            int delcount=0;
            for(int q=0;q<inMax;q++){
                String inpStr=fileIn.readLine().toString();
                int r=0;
                for(r=0;r<seMax && !inpStr.equals(se[r]);r++);
                if(r<seMax){
                    in[q-delcount]=inpStr;
                }else delcount++;
                //System.out.println("in["+(q-delcount)+"]="+in[q-delcount]);
            }
            System.out.println("Case #"+(p+1)+": "+new A2(seMax,se,inMax-delcount,in).findCount());
        }
    }
}

Problem 2: Train Schedules

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
public class B {
    int[] aWant,aAvail,bWant,bAvail;
    int aTrains,bTrains;
    
    B(int wt, int[] aLeave, int[] bArrive, int[] bLeave, int[] aArrive){
        Arrays.sort(aLeave);
        Arrays.sort(bArrive);
        Arrays.sort(bLeave);
        Arrays.sort(aArrive);
        aWant=aLeave;
        bWant=bLeave;
        for(int i=0;i<bArrive.length;bArrive[i]+=wt,i++);
        for(int i=0;i<aArrive.length;aArrive[i]+=wt,i++);
        bAvail=bArrive;
        aAvail=aArrive;
    }
    
    String findTrains(){
        int aExists=0;
        for(int i=aExists;i<aWant.length && aAvail.length>0;i++){
            if(aAvail[0]<=aWant[i]){
                aAvail[0]=2000;
                Arrays.sort(aAvail);
                aExists++;
            }
        }
        int bExists=0;
        for(int i=bExists;i<bWant.length && bAvail.length>0;i++){
            if (bAvail[0]<=bWant[i]){
                bAvail[0]=2000;
                Arrays.sort(bAvail);
                bExists++;
            
            }
        }
        
        return (aWant.length-aExists)+" "+(bWant.length-bExists);
    }
    
    public static void main(String[] in)throws IOException{
        File file=new File("./b3.txt");
        BufferedReader fileIn = new BufferedReader(new FileReader(file));
        String fileLine=fileIn.readLine(),inputs[];
        int pMax=Integer.parseInt(fileLine);
        for(int p=0;p<pMax;p++){
            int wt=Integer.parseInt(fileIn.readLine());
            fileLine=fileIn.readLine();
            inputs=fileLine.split(" ",2);
            int a2b=Integer.parseInt(inputs[0]);
            int b2a=Integer.parseInt(inputs[1]);
            int[] aLeave=new int[a2b];
            int[] bArrive=new int[a2b];
            int[] bLeave=new int[b2a];
            int[] aArrive=new int[b2a];
            for(int i=0;i<a2b;i++){
                fileLine=fileIn.readLine();
                aLeave[i]=Integer.parseInt(fileLine.split(" ",2)[0].split(":",2)[0])*60+Integer.parseInt(fileLine.split(" ",2)[0].split(":",2)[1]);
                //System.out.println(aLeave[i]);
                bArrive[i]=Integer.parseInt(fileLine.split(" ",2)[1].split(":",2)[0])*60+Integer.parseInt(fileLine.split(" ",2)[1].split(":",2)[1]);
                //System.out.println(bArrive[i]);
            }
            for(int i=0;i<b2a;i++){
                fileLine=fileIn.readLine();
                bLeave[i]=Integer.parseInt(fileLine.split(" ",2)[0].split(":",2)[0])*60+Integer.parseInt(fileLine.split(" ",2)[0].split(":",2)[1]);
                aArrive[i]=Integer.parseInt(fileLine.split(" ",2)[1].split(":",2)[0])*60+Integer.parseInt(fileLine.split(" ",2)[1].split(":",2)[1]);
            }
            System.out.println("Case #"+(p+1)+": "+new B(wt,aLeave,bArrive,bLeave,aArrive).findTrains());
        }
    }
}

 

Yes, these solutions are also available from GCJ site in this page: http://code.google.com/codejam/contest/scoreboard?c=agdjb2RlamFtcg8LEghjb250ZXN0cxjqOQw&show_type=all&start_pos=3741&views_time=1&views_number=1&views_file=0&csrfmiddlewaretoken=, My name in rank 3755- I submitted it late in the night and rank depends on at what time one submitted it.

Now I am keen on the next rounds, the earliest one on next Sunday.

blog comments powered by Disqus

Labels