Saturday 23 January 2016

Google Apac Test Round Dynamic Grid[Java Solution] using DFS

Google Apac Test Round Dynamic Grid[Java Solution] using DFS


Problem Statement:-https://code.google.com/codejam/contest/11214486/dashboard

Hint:- Apply DFS.

Java Program:-

/**
 * @(#)DynamicGrid.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/1/23
 */
import java.io.*;
import java.util.*;

class DynamicGrid {

    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new FileReader("A-large-practice.in"));
    PrintWriter out=new PrintWriter(new FileWriter("output-large.out"));
   
    int T=Integer.parseInt(br.readLine());
    int nt=1;
    while(T--!=0){
    out.println("Case #"+(nt++)+":");
    String inp[]=br.readLine().split(" ");
    int R=Integer.parseInt(inp[0]);
    int C=Integer.parseInt(inp[1]); 
   
    int grid[][]=new int[R][C];
   
    String str;
    for(int i=0;i<R;i++){
    str=br.readLine();
    for(int j=0;j<C;j++){
    grid[i][j]=Integer.parseInt(str.charAt(j)+"");
    }
    }
   
    int nQ=Integer.parseInt(br.readLine());
   
    while(nQ--!=0){
   
    inp=br.readLine().split(" ");
   
    if(inp[0].charAt(0)=='Q'){
    out.println(solve(grid));
    }else{
    int x=Integer.parseInt(inp[1]);
    int y=Integer.parseInt(inp[2]);
    int z=Integer.parseInt(inp[3]);
   
    grid[x][y]=z;
    }
   
    }
    }
    out.close();
    }
    
    public static int solve(int grid[][]){
    int ans=0;
    int newGrid[][]=new int[grid.length][grid[0].length];
   
    for(int i=0;i<grid.length;i++){
    for(int j=0;j<grid[0].length;j++){
    newGrid[i][j]=grid[i][j];
    }
    }
   
    for(int i=0;i<grid.length;i++){
    for(int j=0;j<grid[0].length;j++){
    if(newGrid[i][j]==1){
    dfs(newGrid,i,j);
    ans++;
    //printGrid(newGrid);
    }
    }
    }
    return ans;
    }
    
    public static void dfs(int grid[][],int i,int j){
   
    grid[i][j]=5;
   
   
   
    if(i-1>=0&&grid[i-1][j]==1){
    grid[i-1][j]=5;
    dfs(grid,i-1,j);
    }
    if(j-1>=0&&grid[i][j-1]==1){
    grid[i][j-1]=5;
    dfs(grid,i,j-1);
    }
    if(i+1<grid.length&&grid[i+1][j]==1){
    grid[i+1][j]=5;
    dfs(grid,i+1,j);
    }
    if(j+1<grid[0].length&&grid[i][j+1]==1){
    grid[i][j+1]=5;
    dfs(grid,i,j+1);
    }
   
    }
    
}


Input:-

1
4 4
0101
0010
0100
1111
7
Q
M 0 2 1
Q
M 2 2 0
Q
M 2 1 0
Q

Output:-

Case #1:
4
2
2
2

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Labels: ,

posted by Suyash @ January 23, 2016   0 Comments

Spoj Problem BITMAP- Bitmap[Java Solution]  using BFS


Problem Statement:-http://www.spoj.com/problems/BITMAP/

Hint:- Apply BFS.

Perform the BFS on the nodes where 1 is present and to elaborate(open) those nodes which are not 1 in BITMAP and calculate the distance and sotred in 2d array(i.e here sol[][]).If the solution array previously had any value(other than -1 i.e initially all -1) then minimum should be stored.

Java Program:-

/**
 * @(#)BITMAP.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2015/12/14
 */

import java.io.*;
import java.util.*;


class Node{
     int x;
     int y;
     int value;
    
     @Override
     public boolean equals(Object obj){
     Node n=(Node)obj;
     return this.x==n.x&&this.y==n.y;
     }
}

class BITMAP {

    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
    int T=Integer.parseInt(br.readLine());
   
    while(T--!=0){
   
    String str[]=br.readLine().split(" ");
   
    int n=Integer.parseInt(str[0]);
    int m=Integer.parseInt(str[1]);
   
    Node bitmap[][]=new Node[n][m];
   
    int sol[][]=new int[n][m];
    String temp;
    Node temp2;
    int c=1;
    for(int i=0;i<n;i++){
    temp=br.readLine();
    for(int j=0;j<m;j++){
    temp2=new Node();
    temp2.x=i;
    temp2.y=j;
    temp2.value=Integer.parseInt(temp.charAt(j)+"");
    bitmap[i][j]=temp2;
    sol[i][j]=-1;
    }
    }
    for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
    if(bitmap[i][j].value==1){
    sol[i][j]=0;
    bfs(bitmap,bitmap[i][j],sol);
    }
    }
    }
    StringBuilder sb=new StringBuilder();
    for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
    //System.out.print(sol[i][j]+" ");
    sb.append(sol[i][j]+" ");;
    }
    //System.out.println();
    sb.append("\n");
    }
    System.out.print(sb);
    br.readLine();
   
    }
   
    }
    
    
    public static void bfs(Node bitmap[][],Node root,int sol[][]){
   
    int visited[][]=new int[bitmap.length][bitmap[0].length];
    Queue<Node> Q=new LinkedList<Node>();
    Q.offer(root);
   
    visited[root.x][root.y]=1;
    Node temp;
    int x1,y1,d;
    while(!Q.isEmpty()){
    temp=Q.poll();
    x1=temp.x;y1=temp.y;
   
    if(x1-1>=0&&visited[x1-1][y1]==0&&bitmap[x1-1][y1].value!=1){
    Q.offer(bitmap[x1-1][y1]);
    visited[x1-1][y1]=1;
    d=(int)Math.abs((x1-1)-root.x)+(int)Math.abs(y1-root.y);
    if(sol[x1-1][y1]==-1){
    sol[x1-1][y1]=d;
    }else{
    sol[x1-1][y1]=Math.min(sol[x1-1][y1],d);
    if(sol[x1-1][y1]<d){
    Q.remove(bitmap[x1-1][y1]);
    }
    }
    }
    if(y1-1>=0&&visited[x1][y1-1]==0&&bitmap[x1][y1-1].value!=1){
    Q.offer(bitmap[x1][y1-1]);
    visited[x1][y1-1]=1;
    d=(int)Math.abs(x1-root.x)+(int)Math.abs((y1-1)-root.y);
    if(sol[x1][y1-1]==-1){
    sol[x1][y1-1]=d;
    }else{
    sol[x1][y1-1]=Math.min(sol[x1][y1-1],d);
    if(sol[x1][y1-1]<d){
    Q.remove(bitmap[x1][y1-1]);
    }
    }
    }
    if(y1+1<bitmap[0].length&&visited[x1][y1+1]==0&&bitmap[x1][y1+1].value!=1){
    Q.offer(bitmap[x1][y1+1]);
    visited[x1][y1+1]=1;
    d=(int)Math.abs(x1-root.x)+(int)Math.abs((y1+1)-root.y);
    if(sol[x1][y1+1]==-1){
    sol[x1][y1+1]=d;
    }else{
    sol[x1][y1+1]=Math.min(sol[x1][y1+1],d);
    if(sol[x1][y1+1]<d){
    Q.remove(bitmap[x1][y1+1]);
    }
    }
    }
    if(x1+1<bitmap.length&&visited[x1+1][y1]==0&&bitmap[x1+1][y1].value!=1){
    Q.offer(bitmap[x1+1][y1]);
    visited[x1+1][y1]=1;
    d=(int)Math.abs((x1+1)-root.x)+(int)Math.abs(y1-root.y);
    if(sol[x1+1][y1]==-1){
    sol[x1+1][y1]=d;
    }else{
    sol[x1+1][y1]=Math.min(sol[x1+1][y1],d);
    if(sol[x1+1][y1]<d){
    Q.remove(bitmap[x1+1][y1]);
    }
    }
    }
    }
   
   
   
    }
    
    
    
}



Input:-

1
3 4
0001
0011
0110

Output:-

3 2 1 0
2 1 0 0
1 0 0 1

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Labels: , ,

posted by Suyash @ January 23, 2016   0 Comments

Spoj-PARTY - Party Schedule Java Solution


Explanation:
This problem can be easily sovled by Dynamic Programming Approach.This problem can be solved  by two methods i.e. recursive approach and iterative approach.Here, an iterative approach is given.The key point to solve problem is that which party is to be selected or not and to maximize the fun and cost should be in budget.

The first example case data maintained is given i.e.

5 3
1 60
2 100
3 120


Data maintained for this case:

     0     1     2      3      4       5
0   0     0     0      0      0       0
1   0    60    60    60    60     60
2   0    60    100  160  160   160
3   0    60    100  120  180   220



Program:


/**
 * @(#)PARTY.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2015/12/20
 */
import java.io.*;

class PARTY {

    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
    while(true){
   
    String temp[]=br.readLine().split(" ");
   
    int budget=Integer.parseInt(temp[0]);
    int n=Integer.parseInt(temp[1]);
   
    if(budget==0&&n==0){
    break;
    }
   
    int ar[][]=new int[n+1][budget+1];
   
    int cost[]=new int[n];
    int val[]=new int[n];
   
    for(int i=0;i<n;i++){
    temp=br.readLine().split(" ");
    cost[i]=Integer.parseInt(temp[0]);
    val[i]=Integer.parseInt(temp[1]);
    }
   
    for(int i=0;i<n+1;i++){
    for(int b=0;b<budget+1;b++){
   
    if(i==0||b==0){
    ar[i][b]=0;
    }else if(cost[i-1]<=b){
    ar[i][b]=Math.max(val[i-1]+ar[i-1][b-cost[i-1]],ar[i-1][b]);
    }else{
    ar[i][b]=ar[i-1][b];
    }
   
    }
    }
    int i=n,b=budget;
    while(ar[i][b]==ar[i][b-1]){
    b--;
    }
   
   
    System.out.println(b+" "+ar[n][budget]);//find(budget,cost,val,n-1));
   
   
    br.readLine();
    }
   
    }
    
}



Sample Input:

5 3
1 60
2 100
3 120

50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9 

50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2

0 0

Sample Output:

5 220
49 26
48 32



-----------X-----------X-----------X-----------X-----------X-----------X-----------X-----------X----------

Labels: , , ,

posted by Suyash @ January 23, 2016   0 Comments