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.
