Monday, September 22, 2008

David Heinemeier Hansson at Startup School 08

<div><a href='http://www.omnisio.com'>Share and annotate your videos</a> with Omnisio!</div>

Wednesday, August 6, 2008

TopCoder SRM 413 Round1 Div 2 Problem 250

Problem Statement
Subway trains can move people quickly from one station to the next. It is known that the distance between two consecutive stations is length meters. For safety, the train can't move faster than maxVelocity meters/sec. For comfort, the absolute acceleration can't be larger than maxAcceleration meters/sec^2. The train starts with velocity 0 meters/sec, and it must stop at the next station (i.e., arrive there with a velocity of 0 meters/sec). Return the minimal possible time to get to the next station.
Definition
Class:
Subway2
Method:
minTime
Parameters:
int, int, int
Returns:
double
Method signature:
double minTime(int length, int maxAcceleration, int maxVelocity)
(be sure your method is public)

Notes
-
Your return value must be accurate to within an absolute or relative tolerance of 1E-9.
-
If the train's speed at time 0 is v0 and the acceleration is always a, then at time t the speed will be (v0 + t * a) and the train will be (v0 * t + 0.5 * a * t^2) away.
Constraints
-
length, maxAcceleration and maxVelocity will each be between 1 and 1000, inclusive.
Examples
0)

1
2
10
Returns: 1.4142135623730951
maxVelocity is very large. So the train can keep speeding up until it reaches position 0.5.
1)

1
1
1
Returns: 2.0

2)

10
1
1
Returns: 11.0
The train reaches its maximum velocity after 1 second, while traveling 0.5 meters. It then travels the next 9 meters in 9 seconds, and takes 1 second to decelerate to 0 m/s while covering the final 0.5 meters.
3)

1
10
1
Returns: 1.1

4)

778
887
384
Returns: 2.458961621570838

5)

336
794
916
Returns: 1.301036207838119

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 Subway2{
    public double minTime(int l,int a,int vMax){
        double t,t1,t2,v,s;
        v=Math.sqrt(2*a*l);
        v=Math.min(v,vMax);
        t1=v/a;
        s=a*t1*t1/2;
        t2=(l-2*s)/v;
        if(l>=2*s) return 2*t1+t2;
        return 2*Math.sqrt((double)l/a);
    }
}

Thursday, July 31, 2008

The Big Idea

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.

Wednesday, July 16, 2008

Google Code Jam Beta 1 triangle Java

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

Labels