Programming is my life~! : January 2015

Monday, January 26, 2015

Topcoder SRM 647 div2 500problem

I solve this problem in two way

one way is two for

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

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

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

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

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

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

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

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 v ≠ source            // 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

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

secondcase is from geeksforgeeks

http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

if you like....

if you have question...

if you found something is strange...

Comment plz~

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 ");
  }
 }
}

Programming is my life~!