Find us on Google+ Kill the code: March 2013

Sunday, 31 March 2013

Rope Intranet : Google Code Jam

 Problem Statement 
A company is located in two very tall buildings. The company intranet connecting the buildings consists of many wires, each connecting a window on the first building to a window on the second building.
You are looking at those buildings from the side, so that one of the buildings is to the left and one is to the right. The windows on the left building are seen as points on its right wall, and the windows on the right building are seen as points on its left wall. Wires are straight segments connecting a window on the left building to a window on the right building.
You've noticed that no two wires share an endpoint (in other words, there's at most one wire going out of each window). However, from your viewpoint, some of the wires intersect midway. You've also noticed that exactly two wires meet at each intersection point.
On the above picture, the intersection points are the black circles, while the windows are the white circles.
How many intersection points do you see?
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing an integer N, denoting the number of wires you see.
The next N lines each describe one wire with two integers Ai and Bi. These describe the windows that this wire connects: Ai is the height of the window on the left building, and Bi is the height of the window on the right building.

Rope Intranet : Google Code Jam

public class rope_intranet {
    static int input[][] = {{5,6},{7,7},{4,3},{2,1},{1,5}};
    public static void main(String args[]) {
        int row = input.length;
        int count = 0;
        for(int t=0;t input[i][1]) {
        System.out.println("count = " + count);

Friday, 29 March 2013

Water Shield : Google Code Jam


Geologists sometimes divide an area of land into different regions based on where rainfall flows down to. These regions are called drainage basins.
Given an elevation map (a 2-dimensional array of altitudes), label the map such that locations in the same drainage basin have the same label, subject to the following rules.
  • From each cell, water flows down to at most one of its 4 neighboring cells.
  • For each cell, if none of its 4 neighboring cells has a lower altitude than the current cell's, then the water does not flow, and the current cell is called a sink.
  • Otherwise, water flows from the current cell to the neighbor with the lowest altitude.
  • In case of a tie, water will choose the first direction with the lowest altitude from this list: North, West, East, South.
Every cell that drains directly or indirectly to the same sink is part of the same drainage basin. Each basin is labeled by a unique lower-case letter, in such a way that, when the rows of the map are concatenated from top to bottom, the resulting string is lexicographically smallest. (In particular, the basin of the most North-Western cell is always labeled 'a'.)


public class water_shield1 {
    static int val1 = 0,row = 3,col = 3;
    /*static int input[][] = {{1,2,3,4,5},{2,9,3,9,6},{3,3,0,8,7},{4,9,8,9,8},{5,6,7,8,9}};
    /*static int input1[][] = {{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};
    static int input2[][] = {{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};*/
    static int input[][] = {{9,6,3},{5,9,6},{3,5,9}};
    /*static int input[][] = {{1,2,3},{4,5,6},{7,8,9}};*/
    static int input1[][] = {{0,0,0},{0,0,0},{0,0,0}};
    static int input2[][] = {{0,0,0},{0,0,0},{0,0,0}};
    /*static int input[][] = {{8,8,8,8,8,8,8,8,8,8,8,8,8},{8,8,8,8,8,8,8,8,8,8,8,8,8}};
    static int input1[][] = {{0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0}};
    static int input2[][] = {{0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0}};*/
    public static void main(String args[]) {
        //water_shield1 w = new water_shield1();
        int max = input[0][0],min = input[0][0];
        int i1 = 0,j1 = 0,count = 0;
        for(int i=0;i input[i][j]) {
                    min= input[i][j];
        for(int t=0;t=0) {
            min_ard = input[i][j-1];
            a = i;
            b = j-1;
        if((i-1)>=0 && min_ard > input[i-1][j]) {
            min_ard = input[i-1][j];
            a = i-1;
            b = j;
        if((i+1) input[i+1][j]) {
            min_ard = input[i+1][j];
            a = i+1;
            b = j;
        if((j+1) input[i][j+1]) {
            min_ard = input[i][j+1];
            a = i;
            b = j+1;
        //System.out.println("a = " + a + " b = " + b);
        //System.out.println("input1[a][b]" + input1[a][b] + " input1[i][j] = " + input1[i][j]);
        if(input1[a][b] == 0) {
            if(input1[i][j] != 0) {
                input1[a][b] = input1[i][j];
                //replace(input1[a][b], input1[i][j]);
            else {
            input1[a][b] = input1[i][j] = ++val1;
            //System.out.println("val1" + val1 + " i=" + i + " j = " + j + " a = " + a + " b = " + b);
        else if(input[a][b] != input[i][j]) {
            //System.out.println("input[i][j] = " + input1[i][j] + "input[a][b] = " + input1[a][b]);
            int temp = input1[i][j];
            input1[i][j] = input1[a][b];
            if(input1[a][b] < temp) replace(temp, input1[a][b]);
            else replace(input1[a][b],temp);
        else {
            input1[i][j] = ++val1;
    static void replace(int a,int b) { //a is original value, to be replaced with b.
        for(int i=0;i