Logo

Who is talking?

Archive

Google Code Jam

over 9 years ago | Lakshman Prasad: becomingGuru.com

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.

Google Code Jam Beta 1 triangle Java

over 9 years ago | Lakshman Prasad: becomingGuru.com

Code: import java.io.*; public class Triangle { double s1,s2,s3,area; Triangle(int x1,int y1,int x2,int y2,int x3,int y3){ area=x1*(y3-y2)+x2*(y1-y3)+x3*(y2-y1); s1=distBetween(x1,y1,x2,y2); s2=distBetween(x1,y1,x3,y3); s3=distBetween(x2,y2,x3,y3); } double distBetween(int x1,int y1, int x2, int y2){ double dist=Math.sqrt(Math.pow((x2-x1),2)+Math.pow((y2-y1),2)); return dist; } void triType(){ if(area==0) { System.out.println("not a triangle"); return; } if(s1==s2 || s2==s3 || s1==s3){ System.out.print("isosceles "); }else System.out.print("scalene "); if(Math.pow(s1, 2)== (Math.pow(s2, 2)+Math.pow(s3, 2)) || Math.pow(s2, 2)==Math.pow(s1, 2)+Math.pow(s3, 2) || Math.pow(s3, 2)==Math.pow(s1, 2)+Math.pow(s2, 2)) System.out.println("right triangle"); else if(Math.pow(s1, 2)>Math.pow(s2, 2)+Math.pow(s3, 2) || Math.pow(s2, 2)>Math.pow(s1, 2)+Math.pow(s3, 2) || Math.pow(s3, 2)>Math.pow(s1, 2)+Math.pow(s2, 2)) System.out.println("obtuse triangle"); else System.out.println("acute triangle");; } public static void main(String[] in)throws IOException{ File file=new File("./a2.txt"); BufferedReader fileIn = new BufferedReader(new FileReader(file)); String fileLine=fileIn.readLine(),inputs[]; int iMax=Integer.parseInt(fileLine); for(int i=1;i<iMax+1;i++){ fileLine=fileIn.readLine(); inputs=fileLine.split(" ",6); int x1=Integer.parseInt(inputs[0]); int y1=Integer.parseInt(inputs[1]); int x2=Integer.parseInt(inputs[2]); int y2=Integer.parseInt(inputs[3]); int x3=Integer.parseInt(inputs[4]); int y3=Integer.parseInt(inputs[5]); System.out.print("Case #"+i+": "); new Triangle(x1,y1,x2,y2,x3,y3).triType(); } } } Input: 100 0 0 0 4 1 2 1 1 1 4 3 2 2 2 2 4 4 3 3 3 3 4 5 3 4 4 4 5 5 6 5 5 5 6 6 5 6 6 6 7 6 8 7 7 7 7 7 7 0 1 0 1 2 4 0 1 2 4 0 1 2 4 0 1 0 1 0 0 1 1 2 0 0 0 2 2 3 1 0 0 1 2 3 1 0 0 1 2 5 0 1 0 2 3 4 9 0 0 4 1 6 7 2 0 5 7 4 8 7 4 1 8 3 1 5 6 8 7 3 7 8 1 4 6 5 2 4 3 7 3 0 5 2 5 8 7 6 7 7 6 0 1 2 9 9 3 5 6 2 6 8 2 2 0 0 9 8 0 3 5 2 7 5 0 5 1 2 0 1 5 2 7 1 9 9 0 4 3 2 1 2 9 9 8 1 1 7 6 7 0 0 2 3 8 5 4 1 3 3 2 7 4 7 1 1 3 4 1 5 5 3 1 9 7 0 1 3 3 7 2 4 5 5 3 8 1 4 2 3 7 9 8 4 0 2 7 0 7 8 6 2 1 0 8 1 2 1 6 5 9 3 6 3 0 6 8 3 0 1 4 8 6 1 2 2 4 4 8 0 1 8 9 5 4 1 5 4 9 9 6 2 4 9 3 5 7 3 5 2 3 3 9 7 6 2 1 2 2 0 8 2 0 2 2 9 7 2 7 3 3 1 6 1 2 4 1 6 2 8 0 6 3 4 5 8 7 2 5 2 2 7 2 4 7 7 3 6 9 1 5 0 5 8 9 1 4 9 4 0 6 9 1 4 0 7 9 3 3 0 4 6 1 0 0 6 3 6 8 4 6 3 4 3 9 5 7 9 2 1 0 5 9 7 0 8 8 7 8 1 4 4 9 2 9 1 3 2 0 0 0 9 0 0 4 3 5 4 4 6 8 6 7 4 4 4 4 4 5 1 8 6 1 9 1 6 4 0 4 3 0 5 2 5 9 8 5 9 2 4 6 6 8 9 6 9 5 9 1 7 6 0 7 3 8 3 5 6 4 4 4 4 3 2 8 8 7 5 8 4 0 5 1 5 1 9 2 1 2 2 5 0 3 2 2 4 5 1 4 8 9 8 0 0 8 9 6 5 3 3 3 7 0 6 4 3 5 6 2 9 8 9 0 1 9 4 8 9 9 1 5 7 7 4 9 0 7 1 1 3 6 7 2 2 0 7 7 6 0 1 7 5 7 5 3 1 2 3 8 1 3 0 0 6 3 1 1 3 5 9 0 9 7 3 6 9 9 4 2 7 4 0 4 7 0 7 8 9 6 9 5 6 9 4 7 8 1 3 3 0 3 0 4 7 0 5 8 8 3 8 5   Output: Case #1: isosceles obtuse triangle Case #2: scalene acute triangle Case #3: isosceles acute triangle Case #4: scalene obtuse triangle Case #5: scalene obtuse triangle Case #6: isosceles obtuse triangle Case #7: not a triangle Case #8: not a triangle Case #9: not a triangle Case #10: not a triangle Case #11: not a triangle Case #12: isosceles acute triangle Case #13: scalene right triangle Case #14: isosceles right triangle Case #15: scalene acute triangle Case #16: not a triangle Case #17: scalene obtuse triangle Case #18: scalene obtuse triangle Case #19: scalene acute triangle Case #20: scalene obtuse triangle Case #21: scalene obtuse triangle Case #22: scalene obtuse triangle Case #23: scalene obtuse triangle Case #24: scalene acute triangle Case #25: scalene obtuse triangle Case #26: scalene acute triangle Case #27: scalene obtuse triangle Case #28: scalene obtuse triangle Case #29: isosceles obtuse triangle Case #30: scalene obtuse triangle Case #31: scalene acute triangle Case #32: scalene acute triangle Case #33: scalene acute triangle Case #34: scalene acute triangle Case #35: scalene acute triangle Case #36: scalene obtuse triangle Case #37: scalene acute triangle Case #38: scalene obtuse triangle Case #39: scalene obtuse triangle Case #40: scalene obtuse triangle Case #41: scalene obtuse triangle Case #42: scalene obtuse triangle Case #43: not a triangle Case #44: scalene obtuse triangle Case #45: scalene obtuse triangle Case #46: scalene obtuse triangle Case #47: scalene acute triangle Case #48: scalene right triangle Case #49: scalene acute triangle Case #50: scalene obtuse triangle Case #51: scalene obtuse triangle Case #52: scalene obtuse triangle Case #53: scalene obtuse triangle Case #54: scalene obtuse triangle Case #55: scalene obtuse triangle Case #56: scalene obtuse triangle Case #57: scalene obtuse triangle Case #58: scalene acute triangle Case #59: scalene obtuse triangle Case #60: scalene obtuse triangle Case #61: scalene obtuse triangle Case #62: scalene obtuse triangle Case #63: scalene obtuse triangle Case #64: scalene acute triangle Case #65: scalene obtuse triangle Case #66: scalene obtuse triangle Case #67: not a triangle Case #68: scalene obtuse triangle Case #69: scalene obtuse triangle Case #70: scalene obtuse triangle Case #71: isosceles acute triangle Case #72: scalene acute triangle Case #73: scalene obtuse triangle Case #74: scalene obtuse triangle Case #75: scalene obtuse triangle Case #76: scalene acute triangle Case #77: scalene obtuse triangle Case #78: scalene obtuse triangle Case #79: not a triangle Case #80: scalene acute triangle Case #81: scalene obtuse triangle Case #82: scalene acute triangle Case #83: scalene obtuse triangle Case #84: scalene acute triangle Case #85: isosceles acute triangle Case #86: scalene obtuse triangle Case #87: scalene obtuse triangle Case #88: scalene obtuse triangle Case #89: scalene acute triangle Case #90: scalene acute triangle Case #91: scalene obtuse triangle Case #92: scalene obtuse triangle Case #93: scalene acute triangle Case #94: scalene acute triangle Case #95: scalene obtuse triangle Case #96: isosceles acute triangle Case #97: scalene obtuse triangle Case #98: scalene obtuse triangle Case #99: scalene obtuse triangle Case #100: scalene obtuse triangle

Top Coder SRM 370 Div 2 250

over 9 years ago | Lakshman Prasad: becomingGuru.com

Problem Statement There are several empty containers lined up in a row, and you want to put packages into them. You start with the first container and the first package. Do the following until all the packages are inside containers: If the current package cannot fit into the current container, skip to step 3. Otherwise, go to the next step. Put the current package into the current container. Grab the next package, and go back to step 1. Put the current container aside (you will not put any more packages into that container). Move on to the next container in line, and go back to step 1. You are given a int[] containers, the i-th element of which is the capacity of the i-th container in line, and a int[] packages, the i-th element of which is the size of the i-th package. The constraints will guarantee that you will be able to put all the packages into containers using the above procedure. Return the sum of the wasted space in all the containers. The wasted space in a container is its capacity minus the total size of its contents. Definition Class: Containers Method: wastedSpace Parameters: int[], int[] Returns: int Method signature: int wastedSpace(int[] containers, int[] packages) (be sure your method is public) Notes - A set of packages fits into a container if the total size of all the packages in the set does not exceed the capacity of the container. - You must use the containers and the packages in the order that they are given. You may not reorder them. Constraints - containers will contain between 1 and 50 elements, inclusive. - Each element of containers will be between 1 and 1000, inclusive. - packages will contain between 1 and 50 elements, inclusive. - Each element of packages will be between 1 and 1000, inclusive. - It will be possible to put all the packages inside containers using the method described in the statement. Examples { 3, 4, 5, 6 } { 3, 3, 3, 3, 3 } Returns: 3 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. public class Containers { public int wastedSpace(int[] a, int[] b){ int w=0,i,j; for(i=0,j=0;j<b.length;){ if(a[i]>=b[j]){ a[i]-=b[j]; j++; }else { w+=(i==0?0:a[i]); i++; } } return w; } }