Posts

Showing posts from January, 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 34publicstaticintgetMaxProfit(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 23publicstaticintgetMaxProfit(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…

Floyd-Warshall's algorithm

Image
Before starting to explain Floyd algorithm,  I want to compare Dijkstra algorithm with Floyd.
Dijkstra's algorithm 
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 forkfrom 1 to |V| 7 forifrom 1 to |V| 8 forjfrom 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j]…

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 29package srm639;/** * n(n+1)/2 = x 1+2+3+4+5+N * @author ddavid * */publicclassAliceGameEasy{publicstaticvoidmain(String args[]){ AliceGameEasy age=new AliceGameEasy(); System.out.println(age.findMinimumValue(10,0)); System.out.println(age.findMinimumValue(932599670050l,67400241741l));}publiclongfindMinimumValue(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 58package srm639;importjava.util.HashSet;/** * 14분 걸림 * @author ddavid * */publicclassElectronicPetEasy{publicstaticvoidmain(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<…

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 67package srm640;importjava.util.Arrays;publicclassNumberGameAgain{publicstaticvoidmain(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);}publiclongsolve(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…

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 92package srm646;importjava.util.LinkedList;importjava.util.Queue;publicclassTheGridDivTwo{publicstaticvoidmain(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,

Dijkstra's algorithm in java

Image
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 ifvsource// Where v has not yet been removed from Q (unvisite…