TopCoder SRM 609 Div2 - Level2

Problem Links:

http://community.topcoder.com/stat?c=problem_statement&pm=12995

Problem:

Solution:

---

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

/**
 * This is a Dynamic Programming problem with memoization. The state mark[r][g][b] represents the package needed for packing r red balls, g green balls and b blue balls.
 */

public class PackingBallsDiv2
{
 private int[][][] mark;
 public int minPacks(int R, int G, int B)
 {
  mark = new int[R+1][G+1][B+1];
  for(int i=0; i<=R; i++) for(int j=0; j<=G; j++) for(int k=0; k<=B; k++)mark[i][j][k] = -1;
  return solve(R,G,B);
 }
 
 private int solve(int r, int g, int b){
  if(mark[r][g][b] != -1) return mark[r][g][b];
  if(r==0 && g==0 && b==0) return mark[r][g][b] = 0;
  if(r==1 && g==1 && b==1) return mark[r][g][b] = 1;
  mark[r][g][b] = Integer.MAX_VALUE;
  if(r >= 3) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r-3, g, b));
  if(r >= 2) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r-2, g, b));
  if(r >= 1) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r-1, g, b));
  if(g >= 3) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r, g-3, b));
  if(g >= 2) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r, g-2, b));
  if(g >= 1) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r, g-1, b));
  if(b >= 3) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r, g, b-3));
  if(b >= 2) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r, g, b-2));
  if(b >= 1) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r, g, b-1));
  if(r>=1 && g>=1) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r-1, g-1, b));
  if(r>=1 && b>=1) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r-1, g, b-1));
  if(b>=1 && g>=1) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r, g-1, b-1));
  if(r>=1&&g>=1&&b>=1) mark[r][g][b] = Math.min(mark[r][g][b], 1 + solve(r-1, g-1, b-1));
  return mark[r][g][b];
 }
}

TopCoder SRM 233 Div1 - Level2

Problem Links:

http://community.topcoder.com/stat?c=problem_statement&pm=3935&rd=6532

Problem:

SmartWordBoy.

Solution:

See it in the comment.

---

Source Code:

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

/**
 * For this problem, it's easy to find out each 4-digit string is a state. And
 * it's easy to move to next state from current state by going to next
 * alpha-letter or previous alpha-letter. So here, using BFS to track the state
 * to state process, and find out the shortest distance from start to finish
 * state.
 * 
 * PS: initially, I used Map interface to keep the record of state's distance
 * from start, it will Exceed Time Limit. Then, I used a 4-dim array to keep
 * track of the state's distance. It works like a charm now. I think it's the
 * getter of Map interface costs too much time since I instantized with a
 * linkedlist, each time the iterator will go through every element in the map
 * to check the value of the key.
 * 
 * */
public class SmartWordToy {
 // Map<String, Integer> map;
 int[][][][] count;

 public int minPresses(String start, String finish, String[] forbid) {
  // map = new HashMap<String, Integer>();
  count = new int[26][26][26][26];
  // map.put(start, 0);
  for (int i = 0; i < 26; i++)
   for (int j = 0; j < 26; j++)
    for (int m = 0; m < 26; m++)
     for (int n = 0; n < 26; n++)
      count[i][j][m][n] = -1;
  preprocess(forbid);
  setCounter(start, 0);
  Queue<String> q = new LinkedList<String>();
  q.add(start);
  while (!q.isEmpty()) {
   start = q.poll();
   if (start.compareTo(finish) == 0)
    return getCounter(start);
   int value = getCounter(start);
   for (int i = 0; i < 4; i++) {
    String next = nextString(start, i);
    if (getCounter(next) == -1) {
     setCounter(next, value + 1);
     // map.put(next, map.get(start) + 1);
     q.add(next);
    }
    String prev = prevString(start, i);
    if (getCounter(prev) == -1) {
     setCounter(prev, value + 1);
     q.add(prev);
    }
   }
  }
  return -1;
 }

 private void setCounter(String s, int value) {
  count[s.charAt(0) - 'a'][s.charAt(1) - 'a'][s.charAt(2) - 'a'][s
    .charAt(3) - 'a'] = value;
 }

 private int getCounter(String s) {
  return count[s.charAt(0) - 'a'][s.charAt(1) - 'a'][s.charAt(2) - 'a'][s
    .charAt(3) - 'a'];
 }

 private void preprocess(String[] forbid) {
  for (String s : forbid) {
   String[] str = s.split("\\s");
   for (int i = 0; i < str[0].length(); i++) {
    for (int j = 0; j < str[1].length(); j++) {
     for (int m = 0; m < str[2].length(); m++) {
      for (int n = 0; n < str[3].length(); n++) {
       // String tmp = "" + str[0].charAt(i)
       // + str[1].charAt(j) + str[2].charAt(m)
       // + str[3].charAt(n);
       // map.put(tmp, -1);
       count[str[0].charAt(i) - 'a'][str[1].charAt(j) - 'a'][str[2]
         .charAt(m) - 'a'][str[3].charAt(n) - 'a'] = -10;
      }
     }
    }
   }
  }
 }

 private String nextString(String s, int index) {
  return s.substring(0, index)
    + (char) ('a' + (s.charAt(index) - 'a' + 1) % 26)
    + s.substring(index + 1);
 }

 private String prevString(String s, int index) {
  return s.substring(0, index)
    + (char) ('a' + (s.charAt(index) - 'a' + 25) % 26)
    + s.substring(index + 1);
 }
}

TopCoder SRM 170 Div1 - Level2

Problem Links:

http://community.topcoder.com/stat?c=problem_statement&pm=1864&rd=4655

Problem:

TopCoder SRM170 Div1 - Level II

Solution:

This problem demonstrates how we implement the solution with real understanding of the algorithm.

After reading the the problem, the time it asking is the distance between two cities, and we need to know the maximum distance between any two cities with the minimum cost. It's like Max(min1, min2, min3, ...)

When asking about distance between any two nodes, the first choice is always Floyd algorithm, which is a O(n^3) algorithm. But here, the way we calculate the distance needs our tention. When we were asking about the distance between two cities, it's not going be the sum of two distance, instead, it will be maximum of two costs.

---

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class CityLink
{
 
 public int timeTaken(int[] x, int[] y)
 {
  int N = x.length;
  int[][] dist = new int[N][N];
  for(int i=0; i<N; i++) 
   for(int j=0; j<N; j++) 
    dist[i][j] = Integer.MAX_VALUE;
  for(int i=0; i<N; i++) 
   for(int j=0; j<N; j++) 
    dist[i][j] = distance(x[i], y[i], x[j], y[j]);
  
  
        // Floyd Graph Algorithms, calculate the minimum time(distance) between any two cities.
  for(int k=0; k<N; k++){
   for(int i=0; i<N; i++){
    //if(i==k)continue;
    for(int j=0; j<N; j++){
     //if(j==k || j==i) continue;
                    //Here is the key. To connect the two cities through one, this is how we calculate the cost(distance).
     dist[i][j] = Math.min(dist[i][j], Math.max(dist[i][k], dist[k][j]));
    }
   }
  }
  int max = 0;
  for(int i=0; i<N; i++) 
   for(int j=0; j<N; j++)
    max = Math.max(max, dist[i][j]);
  
  return max;
 }
 
 private int distance(int x1, int y1, int x2, int y2){
  if(x1 == x2) return (Math.abs(y1-y2)+1)/2;
  if(y1 == y2) return (Math.abs(x1-x2)+1)/2;
  return Math.max(Math.abs(x1-x2), Math.abs(y1-y2));
 }
}
//Powered by [KawigiEdit] 2.0!