Monday, January 26, 2015

Topcoder SRM 647 div2 500problem

I solve this problem in two way

one way is two for 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static int getMaxProfit(int M, int[] profit, int[] city, int[] visit){
  
  int len = visit.length;
  
  int sum = 0;
  int maxPossible=0;
  int maxCitiIndex=0;
  
  for (int i = 0; i < len; i++) {
   // find visitable array.
   
   boolean find = false;
   
   for(int j=0; j<city.length; j++){
    if(visit[i] == city[j]){
     if(maxPossible < profit[j]){
      maxPossible = profit[j];
      maxCitiIndex =j;
      find = true;
     }
    }
   }
   
   if(find){
    profit[maxCitiIndex] = 0;
    sum+= maxPossible;
   }
   
   maxPossible=0;
   maxCitiIndex=0;
  }
  
  return sum;
 }



and  the other is
make List array and reversOrder


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int getMaxProfit(int M, int[] profit, int[] city, int[] visit){
  ArrayList<Integer>[] list = new ArrayList[M+1];
  
  int max = 0;
  for (int i = 0; i < list.length; i++) {
   list[i] = new ArrayList<Integer>();
  }
  
  for (int i = 0; i < city.length; i++) {
   list[city[i]].add(profit[i]);
  }
  for (int i = 0; i < list.length; i++) {
   Collections.sort(list[i], Collections.reverseOrder());
  }
  
  for (int i = 0; i < visit.length; i++) {
   if(list[visit[i]].size() > 0){
    Integer x = list[visit[i]].remove(0);
    max += x; 
   }
  }
  return max;
 }

Wednesday, January 21, 2015

Floyd-Warshall's algorithm

Before starting to explain Floyd algorithm,  I want to compare Dijkstra algorithm with Floyd.


1. it is used only when we already know start node to all nodes
    this means that source node should be single.
2. It will fail if graph has negative distance. distance or weight should be > 0
3. it is also called single-source shortest path or SSSP algorithm.
4.  O(N^2)


Floyd-Warshall's algorithm

1. it is used to find all nodes to all nodes 
2. This only fails when there are negative cycles.
3.  O(N^3)
4. We can have one or more links of negative cost, c(x, y)<0,

Later on, I will Study Bellman-Ford  and also post on blog.



1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

Code Explanation 

1. line 3, define graph and initialize value. in my case Integer.max
2. line 5, set real weight of edge between two nodes.
3. find dist[i][j] through k node. .. repeatedly k = 1 to last node
    find and set if dist[i][j] < dist[i][k] + dist[k][j], in other words, find minimum path and update minimum distance


Picture Explanation




                                continue and continue.....
                                       .............
                                          .......
                                            ...
                                             .


Finally we get shorted graph from all nodes to all node

Last time, I wrote about shortest path by using dijkstra, with above graph.
at that time,  test case was 1 to 5 , and result is 20.
and also this result by using floyd is  the same as using dijkstra.

below is my java code



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package mybook;

import java.util.Arrays;

public class FloydWarshall {
 public int[][] graph ;
 public final int INFINITY =Integer.MAX_VALUE;

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  FloydWarshall floyd = new FloydWarshall();
  floyd.init();
  floyd.printValue(floyd.graph);
  floyd.start();
  
  System.out.println();
  floyd.printValue(floyd.graph);
 }
 
 
 private void start() {
  for(int k=1; k<7; k++){
   for(int i=1; i<7; i++){
    for(int j=1; j<7; j++){
     if(graph[i][k]!= INFINITY && graph[k][j] != INFINITY && i != j){
      
      System.out.println();
      System.out.println("from : " + i + ", center : " + k + ", to : " + j);
      if(graph[i][j] > graph[i][k] + graph[k][j]){
       graph[i][j] = graph[i][k] + graph[k][j];
      }
      
      //System.out.println("[" +i +  "]["+j +"] : "  + graph[i][j] );
      printValue(graph);
     }
     
    }
   }
  }
 }


 public void init(){
  int count = 7;
  
  graph = new int [count][count];
  printValue(graph);
  int len =graph.length;
  for(int i=0; i<len; i++){
   for(int j =0; j<len; j++){
    graph[i][j] = INFINITY;
   }
  }
  
  printValue(graph);
  
  
  setvalue(graph, 1, 3, 9);
  setvalue(graph, 1, 2, 7);
  setvalue(graph, 1, 6, 14);
  setvalue(graph, 2, 3, 10);
  setvalue(graph, 2, 4, 15);
  setvalue(graph, 3, 4, 11);
  setvalue(graph, 3, 6, 2);
  setvalue(graph, 4, 5, 6);
  setvalue(graph, 5, 6, 9);
 }
 
 public void setvalue(int [][] graph, int start, int end, int val){
  graph[start][end] = val;
  graph[end][start] = val;
 }
 
 public  void printValue(int graph[][]){
  for(int i=1; i<graph.length; i++){
   for(int j=1; j< graph.length; j++){
    
    String pr = "";
    int val = graph[i][j];
    if(0< val && val < 10){
     pr = "0"+ val; 
    }else{
     if(val == Integer.MAX_VALUE){
      System.out.print("xx");  
      System.out.print(pr + " ");
      continue;
     }
     
     pr = val +"";
    }
    System.out.print(pr + " ");
   }
   System.out.println();
  }
 }
}

if you have any question Comment Please~

Monday, January 19, 2015

Topcoder SRM 639 div 2 500 problem.

If I solve this problem I sholud know find N

ex) 1+2+3+5... +N = 5050
n*(n+1)/2 = 5050




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package srm639;

/**
 * n(n+1)/2 = x   1+2+3+4+5+N
 * @author ddavid
 *
 */
public class AliceGameEasy {
 public static void main(String args[]){
  AliceGameEasy age= new AliceGameEasy();
  System.out.println(age.findMinimumValue(10, 0));
  System.out.println(age.findMinimumValue(932599670050l, 67400241741l));
 }
 
 public long findMinimumValue(long x, long y){
  long sqrt = (long)Math.sqrt((x+y) *2);
  if(sqrt *(sqrt +1) != (x+y) *2){
   return -1l;
  }
  long sum =0l;
  int cnt =0;
  while(sum < x){
   sum += sqrt;
   sqrt--;
   cnt++;
  }
  return cnt;
 }
}

Topcoder SRM 636 250 problem.

One of my hobbies is solving algorithm problem in topcoder.
I'm very interested in learning.

Today I solve this problem.
http://community.topcoder.com/stat?c=problem_statement&pm=13543&rd=16082

My access was make two subsets and there are intersection between A and B




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package srm639;

import java.util.HashSet;

/**
 * 14분 걸림
 * @author ddavid
 *
 */
public class ElectronicPetEasy {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  ElectronicPetEasy ep= new ElectronicPetEasy();
  
//  System.out.println(ep.isDifficult(3, 3, 3, 5, 2, 3));

//  System.out.println(ep.isDifficult(1, 1000, 1000, 2, 1000, 1000));
  System.out.println(ep.isDifficult(1, 1, 1, 2, 2, 2));
  
 }
 
 public String isDifficult(int st1, int p1, int t1, int st2, int p2, int t2){
  
  HashSet<Integer> set = new HashSet<Integer>();
  HashSet<Integer> set2= new HashSet<Integer>();
  
  set.add(st1);
  for(int i=1; i<t1; i++){
   int val = st1+(p1*i);
   set.add(val);
  }
  
  
  set2.add(st2);
  for(int i=1; i<t2; i++){
   int val = st2+(p2*i);
   set2.add(val);
  }
  
  System.out.println(set);
  System.out.println(set2);
  
  int totalSize =set.size() + set2.size();
  
  //merge size
  set.addAll(set2);
  
  if(totalSize == set.size()){
   return "Easy";
  }else{
   return "Difficult";
  }
  
  
 }

}

Topcoder SRM 640 div2 500problem

It took about 1hour to solve this problem

In contest I failed to solve this one.

After days later I retried to solve this one
Finally I was able to solve this one.

My code is below

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package srm640;

import java.util.Arrays;

public class NumberGameAgain {

 public static void main(String[] args) {
  NumberGameAgain num = new NumberGameAgain();
  
 // int k=40;
//  long table[] = {2l,4l,8l,16l,32141531l,2324577l,1099511627775l,2222222222l,33333333333l,4444444444l,2135l}; 

  int k=3;
  long table[] = {2,4,6}; 
//  int k=5;
//  long table[] = {2,3}; 
  
  num.solve(k, table);
  
 }
 
 public long solve(int k, long[]table){
  
  // 1차 필터링
  Arrays.sort(table);
  for(int i=table.length -1; i>0; i--){
   long val = table[i];
   hello:
   while((val = val /2) > 1){
    for(int p = i-1; p>= 0; p--){
     if(table[p] == val){
      
      table[i] = -1;
      break hello;
     }
    }
   }
  }
  
  
  long total = (long) Math.pow(2, k) -2;
  
  for(int i=0; i<table.length; i++){
    long val = table[i];
    for(int j=1; j<k+1; j++){
     
     if(table[i] == -1) continue;
     //System.out.println("j : " + j + "   Math.pow(2, j) : " + Math.pow(2, j));
     
     if(Math.pow(2, j) > table[i]){
      
      //System.out.println("minus : " +(Math.pow(2, k-(j-1)) -1));
      total -= Math.pow(2, k-(j-1)) -1;
      break;
     }
    }
  }
  
  
  //System.out.println(total);
  

//  System.out.println(Arrays.toString(table));
  return total;
 }

}

Sunday, January 18, 2015

Topcoder SRM 646 Div2 500 problem

I was not ablet to solve this promblem when participated in the contest.

and I see other people's source and finally i rewrite and sovle this problem using Queue

my code is



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package srm646;

import java.util.LinkedList;
import java.util.Queue;


public class TheGridDivTwo {

 public static void main(String[] args) {
  
  int [] x = {5, 1, -1, 4, 1, 3, 5, 2, 1, -1, 4, 2, -1, -1, 0, -2, 3, 3, 1, 2, 4, 4, 1, 2, 3, 2, 3, 5, -1, 0, 1, 5, 4, -2, 5, 0, 0, 4, -2, 0, 3};
  int [] y = {3, 4, 2, 1, -2, 4, -2, 0, 1, -1, 0, 2, 5, 1, 3, 4, -2, 1, 2, 5, 2, -2, 5, -2, 3, 3, 5, 5, 0, 4, 0, 1, 4, 0, 4, -2, 2, -1, -2, 1, 0};
  int k = 11;
  
  TheGridDivTwo two = new TheGridDivTwo();
  System.out.println(two.find(x, y, k));
 }
 
 public int find(int[] x, int[] y, int k){
  Queue<Point> queue= new LinkedList<Point>();
  int[][] visited = new int[2001][2001];
  for(int i=0;i<x.length; i++){
   visited[x[i]+1000][y[i]+1000] = 1;
  }
  if(x.length == 0){
   return k;
  }
  
  Point start = new Point(0, 0, k);
  visited[1000][1000] = 1;
  queue.add(start);
  int maxX = 0;
  while(!queue.isEmpty()){
   
   Point point  = queue.poll();
   if(point.sec <= 0){
    continue;
   }
   
   Point right = new Point(point.x + 1, point.y, point.sec-1);
   Point top = new Point(point.x , point.y + 1,  point.sec-1);
   Point bottm = new Point(point.x , point.y - 1, point.sec-1);
   Point left = new Point(point.x - 1, point.y, point.sec-1);
   
   // right
   if(!isVisited(right,  visited) ){
    queue.add(right);
    maxX = Math.max(maxX, point.x +1);
   }
   // top
   if(!isVisited(top, visited) ) queue.add(top);   
   
   // bottom
   if(!isVisited(bottm,  visited)) queue.add(bottm);
   
   // left
   if(!isVisited(left ,visited)) queue.add(left);
  }
  
  return maxX;
  
 }
 
 public boolean isVisited(Point point,  int[][] visited){
  
  int x = point.x;
  int y = point.y;
  int sec = point.sec;
  
  if((sec + x < 0) || visited[x+ 1000][y+1000] == 1){
   return true;
  }
  
  visited[x+ 1000][y+1000] = 1;
  
  return false;
 }  
 
 class Point{
  private int x;
  private int sec;
  private int y;

  public Point(int x, int y, int sec) {

   this.x = x;
   this.y = y;
   this.sec = sec;
  }
 }

}

Thursday, January 15, 2015

Dijkstra's algorithm in java

Today I want to post Dijkstra Algorithm.

Dijkstra Algorithm is used to find shortest path.
this algorithm is well-known because many applications which programmed by this algorithm we are using in practice.

Usage,
Subway Map, GeoGraphic Infomation System and so on.

Before posting this algorithm, I had to study many things to understand for this one.

# List #

1. BFS(Breadth-First-Search),
2. DFS(Depth-First-Search),
3. Prim algorithm,
4. Union Find algorithm,
5. Kruskal algorithm,
6. Topology algorithm,

After writing those code in Java, I was able to totally understand Dijkstra Algorithm, usages where to use and how to customizing,

Pseudocode

 1  function Dijkstra(Graph, source):
 2
 3      dist[source] ← 0                       // Distance from source to source
 4      prev[source] ← undefined               // Previous node in optimal path initialization
 5
 6      for each vertex v in Graph:  // Initialization
 7          if vsource            // Where v has not yet been removed from Q (unvisited nodes)
 8              dist[v] ← infinity             // Unknown distance function from source to v
 9              prev[v] ← undefined            // Previous node in optimal path from source
10          end if 
11          add v to Q                     // All nodes initially in Q (unvisited nodes)
12      end for
13      
14      while Q is not empty:
15          u ← vertex in Q with min dist[u]  // Source node in first case
16          remove u from Q 
17          
18          for each neighbor v of u:           // where v has not yet been removed from Q.
19              alt ← dist[u] + length(u, v)
20              if alt < dist[v]:               // A shorter path to v has been found
21                  dist[v] ← alt 
22                  prev[v] ← u 
23              end if
24          end for
25      end while
26
27      return dist[], prev[]
28
29  end function


this is graph start from node 1


check length (weight) 

 visit node 2 (minimu length from visited to none visited)  
and check neighbors length

visit 3

visit 6



this is what shortest path


and I will show you my java code and this has two testcase 

firstcase is from wekipedia

secondcase is from geeksforgeeks

if you like....
if you have question...
if you found something is strange...

Comment plz~


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
package mybook;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

public class DijkstraTest {
 
 int[][] graph ;
 int[][] dijsktraGraph ;
 int[] dist;
 int[] previous;
 int startPosition ;
 
 // visited node
 HashSet<Integer> used = new HashSet<Integer>();

 // not visited node
 HashSet<Integer> notUsed = new HashSet<Integer>();
 
 public static void main(String[] args){
  DijkstraTest prim = new DijkstraTest();
  prim.secondCaseInit();
  prim.start();
  prim.printValue(prim.dijsktraGraph);
  
  // first test
  // find shortest path from start node
  prim.printPath(1);
  prim.printPath(2);
  prim.printPath(3);
  prim.printPath(4);
  prim.printPath(5);
  prim.printPath(6);
  
  
  // second  test
  prim.firstCaseInit(); 
  prim.start();
  prim.printValue(prim.dijsktraGraph);
  prim.printPath(1);
  prim.printPath(2);
  prim.printPath(3);
  prim.printPath(4);
  prim.printPath(5);
  prim.printPath(6);
  prim.printPath(8);
 }
 
 public void start(){
  // start vertex(node) should be set in advance.
  notUsed.remove(startPosition);
  used.add(startPosition);
  checkWeight(startPosition);
  
  while (! notUsed.isEmpty()) {
   // find shortest distance from used usedNode to targetNode
   int [] node = minimumNode();
   int targetNode = node[1];
   
   // remove target from Queue
   notUsed.remove(targetNode);
   used.add(targetNode);
   
   // draw graph
   dijsktraGraph[node[0]][node[1]]=1;
   
   // check new weight to neighbors of target
   checkWeight(targetNode);
  }
 }
 
 
 /**
  * check the new distances of neighbors of the targetNode if graph[u][v] + dist[u] < dist[v]
  * 
  *  u = from 
  *  v = t
  *  
  * @param u
  */
 public void checkWeight(int u){
  for(int v=startPosition+1; v<graph.length; v++){
   if(graph[u][v] > 0){
    if((dist[v] ==0) || notUsed.contains(v) && graph[u][v] + dist[u] < dist[v] ){
     dist[v] = graph[u][v] + dist[u];
     // chase for the shortest way
     previous[v] = u;
    }
   }
  }
  System.out.println(Arrays.toString(dist));
 }

 /**
  * find targetnode which has min weight in from used node to notUsed node
  * 
  * @return node[from][to]
  */
 private int[] minimumNode() {
  int minValue = Integer.MAX_VALUE;
  int[] node = new int[2];
  
  Iterator<Integer> uI = used.iterator();
  while(uI.hasNext()){
   int used = uI.next();
   
   Iterator<Integer> nI = notUsed.iterator();
   while(nI.hasNext()){
    int notUsed = nI.next();
    if(graph[used][notUsed] > 0){
     int distance = dist[used] + graph[used][notUsed]; 
     if( distance < minValue){
      minValue = distance;
      node[0]= used;
      node[1] = notUsed;
     }
    }
   }
  }
  return node;
 } 
 
 public void setvalue(int [][] graph, int start, int end, int val){
  graph[start][end] = val;
  graph[end][start] = val;
 }
 
 public  void printValue(int graph[][]){
  for(int i=0; i<graph.length; i++){
   for(int j=0; j< graph.length; j++){
    
    String pr = "";
    int val = graph[i][j];
    if(val < 10){
     pr = "0"+ val; 
    }else{
     pr = val +"";
    }
    System.out.print(pr + " ");
   }
   System.out.println();
  }
 }
 
 public void firstCaseInit(){
  int count = 9;
  
  graph = new int [count][count];
  dijsktraGraph = new int [count][count];
  dist = new int[count];
  previous = new int[count];
  startPosition = 0;
   
   used= new HashSet<Integer>();
   notUsed= new HashSet<Integer>();
  
  setvalue(graph, 0, 1, 4);
  setvalue(graph, 0, 7, 8);
  setvalue(graph, 1, 7, 11);
  setvalue(graph, 1, 2, 8);
  setvalue(graph, 2, 8, 2);
  setvalue(graph, 8, 6, 6);
  setvalue(graph, 6, 7, 1);
  setvalue(graph, 7, 8, 7);
  setvalue(graph, 2, 3, 7);
  setvalue(graph, 2, 5, 4);
  setvalue(graph, 5, 6, 2);
  setvalue(graph, 3, 5, 14);
  setvalue(graph, 3, 4, 9);
  setvalue(graph, 4, 5, 10);
  
  for(int i=startPosition; i<count; i++){
   notUsed.add(i); 
  }
 }
 
 public void secondCaseInit(){
  int count = 7;
  
  graph = new int [count][count];
  dijsktraGraph = new int [count][count];
  dist = new int[count];
  previous = new int[count];
  
  startPosition = 1;
  
  used= new HashSet<Integer>();
  notUsed= new HashSet<Integer>();
  
  setvalue(graph, 1, 3, 9);
  setvalue(graph, 1, 2, 7);
  setvalue(graph, 1, 6, 14);
  setvalue(graph, 2, 3, 10);
  setvalue(graph, 2, 4, 15);
  setvalue(graph, 3, 4, 11);
  setvalue(graph, 3, 6, 2);
  setvalue(graph, 4, 5, 6);
  setvalue(graph, 5, 6, 9);
  
  for(int i=startPosition; i<count; i++){
   notUsed.add(i); 
  }
 }
 
 private void printPath(int i) {
  if(i != startPosition){
   System.out.print(i + "to " + previous[i] + ", ");
   printPath(previous[i]);
  }else{
   System.out.println(i + " is last ");
  }
 }
}