## 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

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[] list = new ArrayList[M+1]; int max = 0; for (int i = 0; i < list.length; i++) { list[i] = new ArrayList(); } 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

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 set = new HashSet(); HashSet set2= new HashSet(); set.add(st1); for(int i=1; i

### 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[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 queue= new LinkedList(); int[][] visited = new int[2001][2001]; for(int i=0;i

## 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 #

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 used = new HashSet(); // not visited node HashSet notUsed = new HashSet(); 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 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 uI = used.iterator(); while(uI.hasNext()){ int used = uI.next(); Iterator 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(); notUsed= new HashSet(); 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(); notUsed= new HashSet(); 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