Best Cow Line (POJ 3617)

You actually can solve the problem No. 3617 in POJ, Peking University Judge Online, with the greedy algorithm.

The author of "Programming contest challenge book" says that the greedy algorithm is effective for a problem that deal with dictionally order.

Here is more simple description of POJ 3617.

- - - - -


Description:
You have a string S that length is N and make a string T that length is N. At the beginning, length of S is zero. You can do either operation from below:

 - delete the first character of S and add it into the end of T
 - delete the last character of S and add it into the end of T

Make T as small as in dictionary order.

Constraint:
1 <= N <= 2000
string s can contain small alphabet.

Sample Input:
N = 6
S = "ABCDBCB"

Sample Output:
ABCBCD

My Solution:
https://github.com/yohei1126/pccb/blob/master/beginner/search/GreedyAlgorithm/BestCowLine/BestCowLine.cpp

Interval Scheduling Problem or a.k.a Earliest Deadline First Scheduling

Here is another example of the greedy algorithm, "Interval Scheduling Problem". You can find detailed explanation on Wikipedia. 

If I explain how this algorithm can work in an instinctive way, I can say like this:

• The earlier a job ends, the more jobs you can choose.

This is not a proof. If you want to know how to proof, please see  "Earliest deadline first scheduling" on Wikipedia. Earliest deadline first scheduling is is a dynamic scheduling algorithm used in real-time operating systems.

-----

Problem:
You have 'N' jobs. Each job starts at time 'si' and ends at time 'ti'. You have to choose join or not for each job. If you join, you must jon from the beginning to the end of the job. You cannot join more than two jobs at one time. An overlapping of start time and end time is not permitted. You want to join as much as possible. Hou many jobs can you join?

Constraint:
1 <= N <= 100000
1 <= si < ti <= 10^9

Sample input:
N = 5
s = {1, 2, 4, 6, 8}
t = {3, 5, 7, 9, 10}

Sample output:
3

My Solution:

https://github.com/yohei1126/pccb/blob/master/beginner/search/GreedyAlgorithm/IntervalScheduling/IntervalScheduling.cpp

Coins Problem : An example of greedy algorithm

The greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum.

Please see details of the greedy algorithm on wikipedia.

Coins problem in "Problem contest challenge book" is an example of a greedy algorithm. The point is that you use the largest amount of coin preferentially.

---

Problem:

You have coins as bellow.

• A number of 1     yen coin is C1
• A number of 5     yen coin is C5
• A number of 10   yen coin is C10
• A number of 50   yen coin is C50
• A number of 100 yen coin is C100
• A number of 500 yen coins is C500

You want to pay A yen with the minimum number of coins. How many coins do you have to pay? There is at least one solution for this. 

Constraint

0 <= C1, C5, C10, C50, C100, C500 <= 10^9

0 <= A <= 10^9 

Sample input:

A = 620
c500 = 2, c100 = 0, c50 = 3, c10 = 1, c5 = 2, c1 = 3 

Sample output:

6

My solution:

You can find my solution for this problem on my github.

https://github.com/yohei1126/pccb/blob/master/beginner/search/GreedyAlgorithm/Coins/Coins.cpp

An example of the breadth-first search

You can use the breadth-first search to process every state like the depth-first search.

When you want to search the shortest path for search space like a maze, the breadth-first search is a good solution for you because you have to search the same state so many times with the depth first-search.

The breadth-first search has a weak point. It needs memory that is proportional to a number of state.


This is an example of the breadth-first search:

- Description
You have a maze which size is M * N. The maze consists of path and wall.
You can move 4 direction (up, down, right and left) in one turn.
Solve the shortest path from the start to the goal.

- Constraint
N, M >= 100

- Sample Input
10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

- Sample Output
22

My solution is like this. You can find it on my github repository.

#include 
#include 
#include 
using namespace std;

const int INF = 1000000;
const int MAX_N = 100;
const int MAX_M = 100;

typedef pair P;
char maze[MAX_N][MAX_M+1];  // maze
int n, m;   // size of maze
int sx, sy; // start position
int gx, gy; // goal position

//shortest path for each point
int d[MAX_N][MAX_M];

//vector for for moving direction
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

//solve the shortest path from (sx, sy) to (gx, gy)
int bfs() {
  queue
 q;
  //initialize every point with INF before search 
  for(int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      d[i][j] = INF;
    }
  }
  q.push(P(sx,sy));
  d[sx][sy] = 0;

  while(q.size()) {
    P tmp = q.front();
    q.pop();
    //if you find goal then you finish search 
    if ((tmp.first == gx)&&(tmp.second == gy)){
      break;
    }
    for(int i = 0; i < 4; i++) {
      int nx = tmp.first + dx[i];
      int ny = tmp.second + dy[i];

      if ((0 <= nx) && (nx < n) &&
   (0 <= ny) && (ny < m) &&
   (maze[nx][ny] != '#') &&
   (d[nx][ny] == INF)) {
 // if d[nx][ny] == INF then it is a position that
 // you have already visited. 
 q.push(P(nx,ny));
 d[nx][ny] = d[tmp.first][tmp.second] + 1; 
      } 
    }
  }
  return d[gx][gy];
}

void solve() {
  int res = bfs();
  cout << res << endl; 
}

int main(int argc, char* argv[]) {
  if (argc != 2) {
    cout << "./a.out ";
    return 1;
  }
  ifstream ifs(argv[1]);
  if (!ifs) {
    cout << "can't open file:" << argv[1] << endl; 
    return 1;
  }
  string buf;
  getline(ifs, buf);
  sscanf(buf.c_str(), "%d %d", &n, &m);
  
  for(int i = 0; i < n; i++) {
    getline(ifs, buf);
    for (int j = 0; j < m; j++) {
      maze[i][j] = buf[j];
      if (maze[i][j] == 'S') {
 sx = i;
 sy = j; 
      }
      if (maze[i][j] == 'G') {
 gx = i;
 gy = j;
      } 
    }
  }

  solve();

  return 0;
}

Lake Counting(POJ No.2386)

http://poj.org/problem?id=2386

This is a good example of Depth-First Search.

Description

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

Output

* Line 1: The number of ponds in Farmer John's field.

Sample Input

10 12

W........WW.

.WWW.....WWW

....WW...WW.

.........WW.

.........W..

..W......W..

.W.W.....WW.

W.W.W.....W.

.W.W......W.

..W.......W.

Sample Output

3

You can find my solution on github:

https://github.com/yohei1126/pccb/blob/master/beginner/search/LakeCounting/LakeCounting.cpp