greeness notes

another dp

2009-12-07T16:57:00.000-08:00

TheSwap

framework for a dp solution


// memoization unit
int memo[][];

int main() {

  // reset memo
  memset(memo, 0, sizeof(memo));

  // calling subroutine to iteratively solve the problem
  return doit();
}


int doit(int n, int k ) {
  //if already visited state, return memo[][];
  if (memo[][] != 0) return memo[][];

  // if it is the stopping condition, return memo[] = ? //
  // e.g., k = 0 return n????

  // initialize return value
  int ret = 0; // -1 sometimes

  for(all the possible variables) {
    for(for the possible variables) {

      // pre-processing to get n_1

      // enter subproblem
      // comparison_funct, e.g., max, min, ++
      // note k-1 below, this identifies the subproblem
      ret = comparison_function(ret, doit(n_1, k-1) ) ; 

      // post-processing to get back n
      // we might need some processing to retrieve n in the original problem 
      n = f(n_1);
    }
  }

  // this state is visited, set it in the memo
  return ret = memo[][];

}


int doit(vector &v, int k) {
  int rv = get_v(v);

  // visited
  if(memo[rv][k] != 0) return memo[rv][k];

  if(k == 0) return memo[rv][k] = rv;

  int a = -1;
  for(int i = 0; i < v.size(); ++i) {
    for(int j = i+1; j < v.size(); ++j) {

      // excluded cases: highest digit does not swap with '0'
      if (j == v.size()-1 && v[i] == 0) continue;

      // pre-processing
      int tmp = v[i];
      v[i] = v[j], v[j] = tmp;
      // enter subproblem
      a = max(a, doit(v, k-1));

      // post-processing
      v[j] = v[i], v[i] = tmp;
    }
  }
      
  return memo[rv][k] = a;
}

For another problem in NumbersAndMaches.

const int dis[10][7] =
{
  {1, 1, 1, 0, 1, 1, 1},
  {0, 0, 1, 0, 0, 1, 1},
  {1, 0, 1, 1, 1, 0, 1},
  {1, 0, 1, 1, 0, 1, 1},
  {0, 1, 1, 1, 0, 1, 0},
  {1, 1, 0, 1, 0, 1, 1},
  {1, 1, 0, 1, 1, 1, 1},
  {1, 0, 1, 0, 0, 1, 0},
  {1, 1, 1, 1, 1, 1, 1},
  {1, 1, 1, 1, 0, 1, 1},
};


long long dp[20][127][127];

int _inc[10][10], _dec[10][10];

int k;
long long solve(long long N, int idx, int added, int removed) {
 
  if (dp[idx][added][removed] != -1) 
    return dp[idx][added][removed];

  if(N == 0) {
    if (added == removed && added <= k) {
      return 1LL;
    }
    return 0LL;
  }

  int i = N % 10;
  long long ret = 0;
  for(int j = 0; j <= 9; ++j) {
    ret += solve(N/10, idx+1, added + _inc[i][j], removed + _dec[i][j]);
  }
  return dp[idx][added][removed] = ret;
}
  
long long NumbersAndMatches::differentNumbers(long long N, int K)
{
    for (int i = 0; i < 10; i ++)
      for (int j = 0; j < 10; j ++)
      {
        _inc[i][j] = _dec[i][j] = 0;
        for (int k = 0; k < 7; k ++)
        {
          if (dis[i][k] < dis[j][k])
            _inc[i][j] ++;
          if (dis[i][k] > dis[j][k])
            _dec[i][j] ++;
        }
      }
    k = K;
    memset(dp, -1, sizeof(dp));
    return solve(N, 0, 0, 0);    
}

bitset and memoization

2009-11-28T20:35:00.000-08:00

SRM 448 DIVII LEVEL 3

http://forums.topcoder.com/?module=Thread&threadID=651040&start=0

Let D(n,m) = number of ways to arrange the cards given that we have used "m" cards (m = bitmask representation) and the last card that was chosen was card n.

sscanf

2009-11-21T14:54:00.000-08:00

to read in the numbers in the following string

string s = "1000 ml of water, weighing 1000 g"


int v;
sscanf(s, "%d ml of", &v);

size_t p = s.find(',');

int m;
sscanf(s.substr(p+2, s.length()-p).c_str(), "weighing %d", &m);

Note: the use of c_str() and sscanf()

STL comparison FUNCTOR

2009-11-21T13:23:00.000-08:00

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm374


#include < iostream >
#include < vector >
#include < string >
#include < algorithm >
using namespace std;

bool isvowl(char c) {
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
    return true;
  return false;
  
}

struct word {
  string w;
  vector s1; //sorted
  vector s2; //unsorted
};

// comparison function
bool operator < (const word &a, const word &b) {
  if (a.s1 != b.s1) return a.s1 < b.s1;
  return a.s2 < b.s2;
}  

  
class SyllableSorting {
public:
  
  vector  sortWords(vector  words) {
    
    vector vw;

    
    for(int i = 0; i < words.size(); ++i) {
    
      vector syl;
      word W;
          
      string s("");
      s += words[i][0];
          
      for (int j = 1; j < words[i].length(); ++j) {
        char c = words[i][j];
        bool pv = isvowl(words[i][j-1]);
        bool v  = isvowl(c);
        if (pv) { //previous char is a vowl
          if (v)
            s += c;
          else {
            syl.push_back(s);
            s = c;
          }
        } else {  // previous char is a consonant
          s += c;
        } 
      }
      syl.push_back(s);
      
      for(int k = 0; k < syl.size(); ++k)
        cout << syl[k] << "  ";
      cout << endl;
      
      W.w = words[i];
      
      W.s2 = (syl);
      
      sort(syl.begin(), syl.end());
      
      W.s1 = (syl);
           
      vw.push_back(W);
    
    }
    
    sort(vw.begin(), vw.end());
    vector ret;
    for(int i = 0; i < vw.size(); ++i)
      ret.push_back(vw[i].w);
    return ret;
  }
};

Coin toss and Absorbing Markov Chain

2009-11-18T18:57:00.000-08:00

http://www.mitbbs.com/mitbbs_bbsdoc_div_article.php?board=Quant&gid=31212871

A fair coin is flipped until the first time one of the following two
patterns appeared: TTH or HTH
ask: which one you should choose for a better chance to win

+ TT = .5 TTH + .5 TT
| HT = .5 HTH + .5 TT
| T = .5 TT + .5 H
| H = .5 HT + .5 H
+ S = .5 T + .5 H

If we let TTH = 1 and HTH = 0, we finally get S = 5/8 (the probability of reaching TTH first)
or otherwise
we let HTH = 1 and TTH = 0, we finally get S = 3/8 (the probability of reaching HTH first)

We start from the definition of Absorbing Markov Chain.
REF: Chap 11, Markov Chains, from www.dartmouth.edu/~chance/teaching

A state s_i of a Markov chain is called absorbing if it is impossible to leave it (i.e., p_ii = 1). A Markov chain is absorbing if it has at lease one absorbing state, and if from every state it is possible to go to an absorbing state (not necessarily in one step). The state that is not absorbing is called transient.

The interesting questions about an absorbing Markov chain are:

- What is the probability that the process will eventually reach a given absorbing state?
- On the average, how long will it take for the process to be absorbed?
- On the average, how many times will the process be in each transient state?

In general, the answers to all questions depends on
- the state from which the process starts
- the transition probabilities.
The answers to the above questions are the theorems listed below.

We first write the transition matrix in canonical Form by explicitly write Q and R.



      TT           T         S         H         HT
Q =

TT    0.5000         0         0         0         0
 T    0.5000         0         0    0.5000         0
 S         0    0.5000         0    0.5000         0
 H         0         0         0    0.5000    0.5000
HT    0.5000         0         0         0         0


       TTH       HTH
R =   

TT    0.5000         0
 T         0         0
 S         0         0
 H         0         0
HT         0    0.5000

Theorem: For an absorbing Markov chain the matrix I-Q has an inverse N = I + Q + Q^2 + .... The ij-entry of the matrix N is the expected number of times the chain is in state s_j, given that it starts in state s_i.


>> N = inv(eye(5)-Q)

N =

    2.0000         0         0         0         0
    1.5000    1.0000         0    1.0000    0.5000
    1.2500    0.5000    1.0000    1.5000    0.7500
    1.0000         0         0    2.0000    1.0000
    1.0000         0         0         0    1.0000

By reading the first line of N, we know that starting from TT, the expected number of times we still in TT is 2.

Theorem: The sum of row i of N is the expected number of steps before the chain is absorbed given that the chain starts in state s_i.



>> t = N*ones(5,1)

t =

     2
     4
     5
     4
     2

So starting from S, the expected number of steps before absorbing in either TTH or HTH is 5.

Theorem: Let b_ij be the probability that an absorbing chain will be absorbed in the absorbing state s_j if it starts in the transient state s_i. Let B be the matrix with entries b_ij. Then B is an txr matrix, and

B = NR,

where N is the fundamental matrix and R is as in the canonical form.


>> B = N*R

B =

    1.0000         0
    0.7500    0.2500
    0.6250    0.3750
    0.5000    0.5000
    0.5000    0.5000

Thus starting from S, we have probability of 0.625 = 5/8 to be absorbed into state TTH and probability of 0.375 = 3/8 to be absorbed into state HTH.

Now let us consider adding another absorbing state THT. The transition graph is as below:


Q =      S         T         H        TH        HT        TT

         0    0.5000    0.5000         0         0         0     S
         0         0         0    0.5000         0    0.5000     T
         0         0    0.5000         0    0.5000         0     H
         0         0    0.5000         0         0         0     TH
         0         0         0         0         0    0.5000     HT
         0         0         0         0         0    0.5000     TT

R =    THT       HTH       TTH

         0         0         0  S
         0         0         0  T
         0         0         0  H
    0.5000         0         0  TH
         0    0.5000         0  HT
         0         0    0.5000  TT

>> N = inv(eye(6)-Q)

N =

    1.0000    0.5000    1.2500    0.2500    0.6250    1.1250
         0    1.0000    0.5000    0.5000    0.2500    1.2500
         0         0    2.0000         0    1.0000    1.0000
         0         0    1.0000    1.0000    0.5000    0.5000
         0         0         0         0    1.0000    1.0000
         0         0         0         0         0    2.0000

>> N*ones(6,1)

ans =

    4.7500 S
    3.5000 T
    4.0000 H
    3.0000 TH
    2.0000 HT
    2.0000 TT

>> B = N*R

B =    THT       HTH       TTH

    0.1250    0.3125    0.5625  S
    0.2500    0.1250    0.6250  T
         0    0.5000    0.5000  H
    0.5000    0.2500    0.2500  TH
         0    0.5000    0.5000  HT
         0         0    1.0000  TT

protected data or private data

2009-02-24T19:23:00.000-08:00

http://www.parashift.com/c++-faq-lite/basics-of-inheritance.html

Here's the way I say it: if I expect derived classes, I should ask this question: who will create them? If the people who will create them will be outside your team, or if there are a huge number of derived classes, then and only then is it worth creating a protected interface and using private data. If I expect the derived classes to be created by my own team and to be reasonable in number, it's just not worth the trouble: use protected data. And hold your head up, don't be ashamed: it's the right thing to do!

The benefit of protected access functions is that you won't break your derived classes as often as you would if your data was protected. Put it this way: if you believe your users will be outside your team, you should do a lot more than just provide get/set methods for your private data. You should actually create another interface. You have a public interface for one set of users, and a protected interface for another set of users. But they both need an interface that is carefully designed — designed for stability, usability, performance, etc. And at the end of the day, the real benefit of privatizing your data (including providing an interface that is coherent and, as much as possible, opaque) is to avoid breaking your derived classes when you change that data structure.

But if your own team is creating the derived classes, and there are a reasonably small number of them, it's simply not worth the effort: use protected data. Some purists (translation: people who've never stepped foot in the real world, people who've spent their entire lives in an ivory tower, people who don't understand words like "customer" or "schedule" or "deadline" or "ROI") think that everything ought to be reusable and everything ought to have a clean, easy to use interface. Those kinds of people are dangerous: they often make your project late, since they make everything equally important. They're basically saying, "We have 100 tasks, and I have carefully prioritized them: they are all priority 1." They make the notion of priority meaningless.

Repeated Squaring

2008-11-15T19:23:00.001-08:00

http://www.algorithmist.com/index.php/Repeated_Squaring

Repeated squaring, or repeated doubling is an algorithm that computes integer powers of a number quickly. The general problem is to compute xy for an arbitrary integer y.

// Calculates n to the p power, where p is a positive number.
func power( var n as integer, var p as integer )
   if p = 0 return 1
   if p = 1 return n
   if p is odd
      return n * power( n * n, (p-1) / 2 )
   else
      return power( n * n, p / 2 )
end func

quadtree

2008-11-11T21:00:00.000-08:00

http://en.wikipedia.org/wiki/Quadtree

UVa problem: 297: Quadtrees

refer to forum: http://acm.uva.es/board/viewtopic.php?f=2&t=700&p=2691&hilit=297&sid=156699fafa75aaeacf281e1af3a8006c#p2691

#include <iostream>

#define M 32
int p[M];
int idx;

int mask[] = {
  0, 0x1, 0x3, 0, // 0-3
  0xf, 0, 0, 0, 0xff, //4-8
  0,0,0,0,0,0,0,0xffff, // 16
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0xffffffff // 32
};

#ifndef ONLINE_JUDGE
// couting 1's
int count_bit(int n) {
    int bits = 0;
    while(n) {
        n &= n-1;
        ++bits;
    }
    return bits;
}
#endif

void color (char *str, int size, int x, int y) {
  if (str[idx] == 'p') {
    idx ++;
    int sz = size>>1;
    color(str, sz, x+sz, y);
    color(str, sz, x, y);
    color(str, sz, x, y+sz);
    color(str, sz, x+sz, y+sz);
  }
  else if (str[idx] == 'f') {
    idx ++;
    for (int i = y; i < y + size; i ++)
      p[i] |= mask[size] << x;
  }
  else idx++;
}
int main () {
  int num;
  char tree1[1500], tree2[1500];

  scanf("%d\n", &num);
  while(num--) {
    scanf("%s\n%s\n", tree1, tree2);

    memset(p, 0, sizeof(p));

    idx=0;
    color(tree1, M, 0, 0);

    idx=0;
    color(tree2, M, 0, 0);

    int total = 0;
    for (int i = 0; i < M; i ++)
#ifndef ONLINE_JUDGE
      total += count_bit(p[i]);
#else
      total += __builtin_popcount(p[i]);
#endif

    printf("There are %d black pixels.\n", total);
  }
  return 0;
}

UVa problem: 752 - Unscrambling Images

#include <iostream>
#include <deque>
using namespace std;
int q[16][16];
int e[16][16]; // encrypted

int d[16][16]; // decoded
inline int getxy(int size, int k, int &x, int &y) {

  deque<int> Q;
  while(k > 0) {
    int r = k % 4;
    if (r == 0) {
      r = 4;
      k = (k-4) >> 2;
    } else
      k = k >>2;

    Q.push_front(r);
  }

  x = 0, y = 0;
  for(int i = 0; i < Q.size(); ++i) {
    size = size >> 1;
    int idx = Q[i];

    if (idx == 2)
      y += size;
    if (idx == 3)
      x += size;
    if (idx == 4) {
      x += size;
      y += size;
    }
  }
  return size;
}

int main() {
  int ndata;
  scanf("%d ", &ndata);
  int nd = 1;
  while(nd <= ndata) {
    if(nd > 1) printf("\n");
    printf("Case %d\n\n", nd++);
    int n;
    scanf("%d ", &n);

    // quadtree reset to all 0
    memset(q, 0, sizeof(q));

    int m; // number of leaf nodes

    scanf("%d ", &m); 
    int k;
    int intensity;
    for(int i = 0; i < m; ++ i) {
      scanf("%d %d ", &k, &intensity);
      int x, y;
      int size = getxy(n, k, x, y);

      for(int i = x; i < x+size; ++i)
        for(int j = y;j < y+size; ++j)
          q[i][j] = intensity;      
    }
/*
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j)
        printf("%4d", q[i][j]);
      printf("\n");
    }
    printf("\n");
*/
    scanf("%d ", &m);

    // encrypted quadtree reset to all 0
    memset(e, 0, sizeof(e));
    for(int i = 0; i < m; ++ i) {
      scanf("%d %d ", &k, &intensity);
      int x, y;
      int size = getxy(n, k, x, y);

      for(int i = x; i < x+size; ++i)
        for(int j = y;j < y+size; ++j)
          e[i][j] = intensity;
    }

    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j) {
        int x = q[i][j] / n;
        int y = q[i][j] % n;
        d[x][y] = e[i][j];
      }
    }
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j)
        printf("%4d", d[i][j]);
      printf("\n");
    }
  }
}

Add without +

2008-11-05T12:10:00.001-08:00

Write a program to add two numbers a and b.
1. Without Using + operator
2. Without using any loops

Sum = A XOR B
Carry = A AND B

#include <iostream>

int add(int p, int q)
{
  if(q == 0)
    return p;
  int k, r;
  k = p ^ q;
  r = p & q;
  return add(k, r<<1); // carry left shift 1 bit
}

int main() {
  printf("%d\n", add(4,7));
  printf("%d\n", add(401,7));
  printf("%d\n", add(14,7));
  printf("%d\n", add(4,47));
  printf("%d\n", add(4,-97));
  printf("%d\n", add(-4,-97));
}

output:

11
408
21
51
-93
-101

C++ notes II

2008-11-05T12:08:00.001-08:00

Segmentation fault: A segmentation fault occurs when a program attempts to access a memory location that it is not allowed to access, or attempts to access a memory location in a way that is not allowed. Segmentation is one approach to memory management and protection in the operating system.

Stack Overflow: Stack buffer overflow bugs are caused when a program writes more data to a buffer located on the stack than there was actually allocated for that buffer. This almost always results in corruption of adjacent data on the stack, and in cases where the overflow was triggered by mistake, will often cause the program to crash or operate incorrectly.

A core dump is the recorded state of the working memory of a computer program at a specific time, generally when the program has terminated abnormally (crashed).In practice, other key pieces of program state are usually dumped at the same time, including the processor registers, which may include the program counter and stack pointer, memory management information, and other processor and operating system flags and information.

Static function:

The differences between a static member function and non-static member functions are as follows.

A static member function can access only static member data, static member functions and data and functions outside the class. A non-static member function can access all of the above including the static data member.
A static member function can be called, even when a class is not instantiated, a non-static member function can be called only after instantiating the class as an object.
A static member function cannot be declared virtual, whereas a non-static member functions can be declared as virtual
A static member function cannot have access to the 'this' pointer of the class.

The static member functions are not used very frequently in programs. But nevertheless, they become useful whenever we need to have functions which are accessible even when the class is not instantiated.

A memory leak is a particular type of unintentional memory consumption by a computer program where the program fails to release memory when no longer needed. This condition is normally the result of a bug in a program that prevents it from freeing up memory that it no longer needs.

http://linux.die.net/man/2/fork

fork() creates a child process that differs from the parent process only in its PID and PPID, and in the fact that resource utilizations are set to 0. File locks and pending signals are not inherited.

Under Linux, fork() is implemented using copy-on-write pages, so the only penalty that it incurs is the time and memory required to duplicate the parent's page tables, and to create a unique task structure for the child.

Return Value

On success, the PID of the child process is returned in the parent's thread of execution, and a 0 is returned in the child's thread of execution. On failure, a -1 will be returned in the parent's context, no child process will be created, and errno will be set appropriately.

Shallow copies and deep copies

A shallow copy of an object copies all of the member field values. This works well if the fields are values, but may not be what you want for fields that point to dynamically allocated memory. The pointer will be copied. but the memory it points to will not be copied -- the field in both the original object and the copy will then point to the same dynamically allocated memory, which is not usually what you want. The default copy constructor and assignment operator make shallow copies.

A deep copy copies all fields, and makes copies of dynamically allocated memory pointed to by the fields. To make a deep copy, you must write a copy constructor and overload the assignment operator, otherwise the copy will point to the original, with disasterous consequences.

Deep copies need ...

If an object has pointers to dynamically allocated memory, and the dynamically allocated memory needs to be copied when the original object is copied, then a deep copy is required.

A class that requires deep copies generally needs:

A constructor to either make an initial allocation or set the pointer to NULL.
A destructor to delete the dynamically allocated memory.
A copy constructor to make a copy of the dynamically allocated memory.
An overloaded assignment operator to make a copy of the dynamically allocated memory.

Defunct Process: Defunct processes are corrupted processes that can no longer communicate between the parent and child one. Sometimes, they become “zombies” and remain in your system until you reboot your machine. You can try to apply “kill -9″ command, but most of the time you’ll be out of luck.

Stack unwinding:

When an exception is thrown and control passes from a try block to a handler, the C++ run time calls destructors for all automatic objects constructed since the beginning of the try block. This process is called stack unwinding. The automatic objects are destroyed in reverse order of their construction. (Automatic objects are local objects that have been declared auto or register, or not declared static or extern. An automatic object x is deleted whenever the program exits the block in which x is declared.)

If an exception is thrown during construction of an object consisting of subobjects or array elements, destructors are only called for those subobjects or array elements successfully constructed before the exception was thrown. A destructor for a local static object will only be called if the object was successfully constructed.

http://en.wikipedia.org/wiki/Data_segment

In the PC architecture there are four basic read-write memory regions in a program: Stack, Data, BSS, and Heap.

The Data segment contains constants used by the program that are not initialized to zero. For instance the string defined by char s[] = "hello world"; in C would exist in the data part.
The BSS segment starts at the end of the data segment and contains all global variables that are initialized to zero. For instance a variable declared static int i; would be contained in the BSS segment.
The heap area begins at the end of the data segment and grows to larger addresses from there. The Heap area is managed by malloc, realloc, and free, which use the brk and sbrk system calls to adjust its size. The Heap area is shared by all shared libraries and dynamic load modules in a process.
The stack is a LIFO structure, typically located in the higher parts of memory. It usually "grows down" with every register, immediate value or stack frame being added to it. A stack frame consists at minimum of a return address.

Virtual Table The virtual table is a lookup table of functions used to resolve function calls in a dynamic/late binding manner.

A Simple Garbage Collector for C++ http://www.devarticles.com/c/a/Cplusplus/A-Simple-Garbage-Collector-for-C-plus-plus/

A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.

In scheduling, priority inversion is the scenario where a low priority task holds a shared resource that is required by a high priority task. This causes the execution of the high priority task to be blocked until the low priority task has released the resource, effectively "inverting" the relative priorities of the two tasks. If some other medium priority task, one that does not depend on the shared resource, attempts to run in the interim, it will take precedence over both the low priority task and the high priority task.

3Sum problem

2008-11-05T10:56:00.001-08:00

http://discuss.techinterview.org/default.asp?interview.11.613896.3

http://en.wikipedia.org/wiki/3SUM

Given an unsorted array of integers. Find any three numbers satisfying following condition:
c = a+b

First, sort the array in O(nlogn).
For each element c of the array try to find two numbers a and b such that a+b = c.
Time complexity:
O(n) to find a+b = c in sorted array. (We can use two pointers and move them towards the middle)

Since we do this for each element. O(n^2).

Maximun Flow

2008-11-03T22:18:00.001-08:00

Residual network: (credit: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow)

if the flow along the edge x-y is less than the capacity there is a forward edge x-y with a capacity equal to the difference between the capacity and the flow (this is called the residual capacity),
if the flow is positive there is a backward edge y-x with a capacity equal to the flow on x-y.

Augmenting path: a path from the source to the sink in the residual network, whose purpose is to increase the flow in the original one.

Ford-Fulkerson method: start with no flow everywhere and increase the total flow in the network while there is an augmenting path from the source to the sink with no full forward edges or empty backward edges - a path in the residual network.

A cut in a flow network is simply a partition of the vertices in two sets, let's call them A and B, in such a way that the source vertex is in A and the sink is in B.

The capacity of a cut is the sum of the capacities of the edges that go from a vertex in A to a vertex in B.

The flow of the cut is the difference of the flows that go from A to B (the sum of the flows along the edges that have the starting point in A and the ending point in B), respectively from B to A, which is exactly the value of the flow in the network, due to the entering flow equals leaving flow - property, which is true for every vertex other than the source and the sink.

The flow of the cut is less or equal to the capacity of the cut due to the constraint of the flow being less or equal to the capacity of every edge.

This implies that the maximum flow is less or equal to every cut of the network. This is where the max-flow min-cut theorem comes in and states that the value of the maximum flow through the network is exactly the value of the minimum cut of the network.

Maximum Bipartite Matching

http://shygypsy.com/tools/bpm.cpp (a bpm code)

UVa Problems:

10080: Gopher (II) (跟670几乎一样，先确定graph[][]即可,用scanf("%lf", ..) 和eps比较double型)
10092: The Problem with the Problem Setter (L: the number of problems that should be included; R: the total number of problems in the pool)
259: Software Allocation (每台机子只能run一个application, 又是典型的0-1 assignment)
670: The dog task

其实就是先填一个graph[][]即可，在每两个master点之间，确定dog能到达哪些interesting places. 然后就是一个0-1 assignment问题而已。另注意double型比较用了eps = 1e-18(开始用1e-15 WA: )

special case:

2 1
0 0 2 2
3 3

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX 101
#define eps 1e-18
typedef pair<int,int> ii;

bool graph[MAX][MAX];
bool seen[MAX];
int matchL[MAX], matchR[MAX];
// n: dim of L; m: dim of R
int n, m;

bool bpm( int u ) {
    for( int v = 0; v < m; v++ ) if( graph[u][v] )
    {
        if( seen[v] ) continue;
        seen[v] = true;

        if( matchR[v] < 0 || bpm( matchR[v] ) )
        {
            matchL[u] = v;
            matchR[v] = u;
            return true;
        }
    }
    return false;
}

double dist(ii a, ii b) {
  return sqrt((a.first - b.first) * (a.first - b.first) + 
              (a.second - b.second) * (a.second - b.second) + 0.0);
}

int main() {
  int ndata;
  scanf("%d ", &ndata);
  while(ndata--) {
    scanf("%d %d ", &n, &m);

    vector<ii> master(n);
    vector<ii> place(m);
    for(int i = 0; i < n; ++i)
      scanf("%d %d ", &master[i].first, &master[i].second);

    for(int i = 0; i < m; ++i)
      scanf("%d %d ", &place[i].first, &place[i].second);

    memset(graph, false, sizeof(graph));
    memset( matchL, -1, sizeof( matchL ) );
    memset( matchR, -1, sizeof( matchR ) );

    for(int i = 0; i < n-1; ++i) {

      // master's walking distance doubled
      double d2 = dist(master[i], master[i+1]) * 2;
      for(int j = 0; j < m; ++j) {
        // dog's walking distance
        double dogdist = dist(master[i], place[j]) + dist(place[j], master[i+1]);
        // as long as dog's walking distance is no more than 2xmaster's, the dog can visit this place
        if(d2 - dogdist>= eps) 
          graph[i][j] = true;
      }
    }

    int cnt = 0;
    for( int i = 0; i < n; ++ i){
      memset(seen, 0, sizeof( seen ) );
      if(bpm(i)) cnt++;
    }

    printf("%d\n", n+cnt);
    printf("%d %d", master[0].first, master[0].second);
    for(int i = 0; i < n; ++i) {
      if(i) printf(" %d %d", master[i].first, master[i].second);
      if(matchL[i] != -1) {
        int p = matchL[i];
        printf(" %d %d", place[p].first, place[p].second);
      }
    }
    printf("\n");
    if(ndata) printf("\n");
  }
}

663: Sorting Slides (use point in rectangle to get graph[][])

这题难点在于要输出unique的matching, 我是run max bipartite matching 算法 |E|次(the number of edges), 每次检查uniqueness

#include <iostream>
#include <vector>
using namespace std;

struct Rect {
  int xmin;
  int xmax;
  int ymin;
  int ymax;
};

#define MAX 27 // the number of alphabet
bool graph[MAX][MAX];
bool seen[MAX];
int matchL[MAX], matchR[MAX];
int n;
Rect slides[MAX];

bool exist;      // if solution already exists
int savedR[MAX]; // save previous solution

// if a points is inside a rectangle
inline bool ptInRect(int x, int y, Rect r) {
  //No number will lie on a slide boundary.
  if (x > r.xmin && x < r.xmax && y > r.ymin && y < r.ymax) return true;
  return false; 
}

bool bpm( int u ) {
  for( int v = 0; v < n; v++ ) if( graph[u][v] )
  {
    if( seen[v] ) continue;
    seen[v] = true;

    if( matchR[v] < 0 || bpm( matchR[v] ) )
    {
      matchL[u] = v;
      matchR[v] = u;
      return true;
    }
  }
  return false;
}

int main() {
  int ndata = 0;
  while(scanf("%d ", &n) && n) {
    printf("Heap %d\n", ++ndata);

    for(int i = 0; i < n; ++i) {
      scanf("%d %d %d %d ", &slides[i].xmin, 
                            &slides[i].xmax,
                            &slides[i].ymin,
                            &slides[i].ymax);
    }

    memset(graph, false, sizeof(graph));
    memset(savedR, -1, sizeof(savedR));
    exist = false;

    int x, y;
    for(int i = 0; i < n; ++i) {
      scanf("%d %d ", &x, &y);
      for(int j = 0; j < n; ++j)
        if(ptInRect(x, y, slides[j]))
          graph[i][j] = true;
    }
    
    int cnt = 0;
    for(int u = 0; u < n; ++u) {
      for(int v = 0; v < n; ++v) {
        // each time, put one edge into the match
        // and try to construct the max bipartite match based on that
        if(!graph[u][v]) 
          continue;

        memset( matchL, -1, sizeof( matchL ) );
        memset( matchR, -1, sizeof( matchR ) );
        
        matchL[u] = v;
        matchR[v] = u;

        int cnt = 1;
        for( int i = 0; i < n; ++ i){
          if (i == u) continue;
          memset(seen, 0, sizeof( seen ));
          if(bpm(i)) cnt++;
        }

        if(exist) {
          for(int k = 0; k < n; ++k)
            //check uniqueness
            if (matchR[k] != savedR[k])
              savedR[k] = -1;  // not unique, reset to -1 
        } else {
          memcpy(savedR, matchR, sizeof(int)*n); // save the first solution
          exist = true;
        }
      }
    }

    int cardinal = 0;
    int i;
    for(i = 0; i < n; ++i) {
      if(savedR[i] != -1) {
        ++cardinal;
        printf("(%c,%d)", i + 'A', savedR[i] + 1);
        break;
      }
    }

    for(++i; i < n; ++i) {
      if(savedR[i] != -1) {
        ++cardinal;
        printf(" (%c,%d)", i + 'A', savedR[i] + 1);
      }
    }

    if(cardinal == 0) 
      printf("none");

    printf("\n\n");
  }
}

Hungarian Method

2008-11-03T21:04:00.001-08:00

Easy to understand examples:

http://www.ee.oulu.fi/~mpa/matreng/eem1_2-1.htm

http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf

http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html

animation: http://www.ifors.ms.unimelb.edu.au/tutorial/hungarian/index.html

topcoder tutorial: Assignment Problem and Hungarian Algorithm (very good regarding theory and c++ code)

http://www.math.uwo.ca/~mdawes/courses/344/kuhn-munkres.pdf

String Searching

2008-11-02T15:31:00.001-08:00

http://allisons.org/ll/AlgDS/Strings/

http://en.wikipedia.org/wiki/String_searching_algorithm

http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm

Suffix Tree

2008-11-02T13:32:00.001-08:00

Tries and suffix tree

wiki - Suffix Trees

http://allisons.org/ll/AlgDS/Tree/Suffix/

The suffix tree can be built in O(n) time (linear time regarding the length of strings) due to Ukkonen (1995).

Applications: [1,2,3] from http://allisons.org/ll/AlgDS/Tree/Suffix/

String Search: Searching for a substring, pat[1..m], in txt[1..n], can be solved in O(m) time (after the suffix tree for txt has been built in O(n) time).
Palindromes: The longest palindrome of txt[1..n] can be found in O(n) time, e.g. by building the suffix tree for txt$reverse(txt)# or by building the generalized suffix tree for txt and reverse(txt).
Longest Common String: The longest common substring of two strings, txt₁ and txt₂, can be found by building a generalized suffix tree for txt₁ and txt₂: Each node is marked to indicate if it represents a suffix of txt₁ or txt₂ or both. The deepest node marked for both txt₁ and txt₂ represents the longest common substring. Equivalently, one can build a (basic) suffix tree for the string txt₁$txt₂#, where `$' is a special terminator for txt₁ and `#' is a special terminator for txt₂. The longest common substring is indicated by the deepest fork node that has both `...$...' and `...#...' (no $) beneath it.

google c++ coding style

2008-10-24T12:27:00.001-07:00

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Header_File_Dependencies#Header_File_Dependencies

Header File Dependencies

How can we use a class Foo in a header file without access to its definition?

We can declare data members of type Foo* or Foo&.
We can declare (but not define) functions with arguments, and/or return values, of type Foo.
We can declare static data members of type Foo. This is because static data members are defined outside the class definition.

On the other hand, you must include the header file for Foo if your class subclasses Foo or has a data member of type Foo.

Inline Functions

A decent rule of thumb is to not inline a function if it is more than 10 lines long. Beware of destructors, which are often longer than they appear because of implicit member- and base-destructor calls!

Another useful rule of thumb: it's typically not cost effective to inline functions with loops or switch statements (unless, in the common case, the loop or switch statement is never executed).

Function Parameter Ordering

When defining a function, parameter order is: inputs, then output

Parameters to C/C++ functions are either input to the function, output from the function, or both. Input parameters are usually values or const references, while output and input/output parameters will be non-const pointers. When ordering function parameters, put all input-only parameters before any output parameters. In particular, do not add new parameters to the end of the function just because they are new; place new input-only parameters before the output parameters.

Local Variables

There is one caveat: if the variable is an object, its constructor is invoked every time it enters scope and is created, and its destructor is invoked every time it goes out of scope.

// Inefficient implementation:
for (int i = 0; i < 1000000; ++i) {
  Foo f;  // My ctor and dtor get called 1000000 times each.
  f.DoSomething(i);
}

It may be more efficient to declare such a variable used in a loop outside that loop:

Foo f;  // My ctor and dtor get called once each.
for (int i = 0; i < 1000000; ++i) {
  f.DoSomething(i);
}

Doing Work in Constructors

Do only trivial initialization in a constructor. If at all possible, use an Init() method for non-trivial initialization.

Decision: If your object requires non-trivial initialization, consider having an explicit Init() method and/or adding a member flag that indicates whether the object was successfully initialized.

Explicit Constructors

Use the C++ keyword explicit for constructors with one argument.

Definition: Normally, if a constructor takes one argument, it can be used as a conversion. For instance, if you define Foo::Foo(string name) and then pass a string to a function that expects a Foo, the constructor will be called to convert the string into a Foo and will pass the Foo to your function for you. This can be convenient but is also a source of trouble when things get converted and new objects created without you meaning them to. Declaring a constructor explicit prevents it from being invoked implicitly as a conversion.

Pros: Avoids undesirable conversions.

Cons: None.

Decision:

We require all single argument constructors to be explicit. Always put explicit in front of one-argument constructors in the class definition: explicit Foo(string name);

The exception is copy constructors, which, in the rare cases when we allow them, should probably not be explicit. Classes that are intended to be transparent wrappers around other classes are also exceptions. Such exceptions should be clearly marked with comments.

Copy Constructors

Consider adding dummy declarations for the copy constructor and assignment operator in the class' private: section, without providing definitions. With these dummy routines marked private, a compilation error will be raised if other code attempts to use them. For convenience, a DISALLOW_COPY_AND_ASSIGN macro can be used:

// A macro to disallow the copy constructor and operator= functions
// This should be used in the private: declarations for a class
#define DISALLOW_COPY_AND_ASSIGN(TypeName) \
  TypeName(const TypeName&);               \
  void operator=(const TypeName&)Then, in class Foo: 

class Foo {
 public:
  Foo(int f);
  ~Foo();

 private:
  DISALLOW_COPY_AND_ASSIGN(Foo);
};

Structs vs. Classes

Use a struct only for passive objects that carry data; everything else is a class.

Declaration Order

Your class definition should start with its public: section, followed by its protected: section and then its private: section. If any of these sections are empty, omit them.

Within each section, the declarations generally should be in the following order:

Typedefs and Enums
Constants
Constructors
Destructor
Methods, including static methods
Data Members, including static data members

The DISALLOW_COPY_AND_ASSIGN macro invocation should be at the end of the private: section. It should be the last thing in the class.

Reference Arguments

All parameters passed by reference must be labeled const.

Within function parameter lists all references must be const:

void Foo(const string &in, string *out);

In fact it is a very strong convention that input arguments are values or const references while output arguments are pointers. Input parameters may be const pointers, but we never allow non-const reference parameters.

Casting

Use C++ casts like static_cast<>(). Do not use other cast formats like int y = (int)x; or int y = int(x);.

Do not use C-style casts. Instead, use these C++-style casts.

Use static_cast as the equivalent of a C-style cast that does value conversion, or when you need to explicitly up-cast a pointer from a class to its superclass.
Use const_cast to remove the const qualifier (see const).
Use reinterpret_cast to do unsafe conversions of pointer types to and from integer and other pointer types. Use this only if you know what you are doing and you understand the aliasing issues.
Do not use dynamic_cast except in test code. If you need to know type information at runtime in this way outside of a unittest, you probably have a design flaw.

sizeof

Use sizeof(varname) instead of sizeof(type) whenever possible.

Use sizeof(varname) because it will update appropriately if the type of the variable changes. sizeof(type) may make sense in some cases, but should generally be avoided because it can fall out of sync if the variable's type changes.

Struct data;
memset(&data, 0, sizeof(data));

memset(&data, 0, sizeof(Struct));

File Comments

Every file should contain the following items, in order:

a copyright statement (for example, Copyright 2008 Google Inc.)
a license boilerplate. Choose the appropriate boilerplate for the license used by the project (for example, Apache 2.0, BSD, LGPL, GPL)
an author line to identify the original author of the file

File Contents

Every file should have a comment at the top, below the and author line, that describes the contents of the file.

Generally a .h file will describe the classes that are declared in the file with an overview of what they are for and how they are used. A .cc file should contain more information about implementation details or discussions of tricky algorithms. If you feel the implementation details or a discussion of the algorithms would be useful for someone reading the .h, feel free to put it there instead, but mention in the .cc that the documentation is in the .h file.

Do not duplicate comments in both the .h and the .cc. Duplicated comments diverge.

Every class definition should have an accompanying comment that describes what it is for and how it should be used.

// Iterates over the contents of a GargantuanTable.  Sample usage:
//    GargantuanTable_Iterator* iter = table->NewIterator();
//    for (iter->Seek("foo"); !iter->done(); iter->Next()) {
//      process(iter->key(), iter->value());
//    }
//    delete iter;
class GargantuanTable_Iterator {
  ...
};

Function Comments

Declaration comments describe use of the function; comments at the definition of a function describe operation.

Function Declarations

Every function declaration should have comments immediately preceding it that describe what the function does and how to use it. These comments should be descriptive ("Opens the file") rather than imperative ("Open the file"); the comment describes the function, it does not tell the function what to do. In general, these comments do not describe how the function performs its task. Instead, that should be left to comments in the function definition.

Types of things to mention in comments at the function declaration:

What the inputs and outputs are.
For class member functions: whether the object remembers reference arguments beyond the duration of the method call, and whether it will free them or not.
If the function allocates memory that the caller must free.
Whether any of the arguments can be NULL.
If there are any performance implications of how a function is used.
If the function is re-entrant. What are its synchronization assumptions?

Here is an example:

// Returns an iterator for this table.  It is the client's
// responsibility to delete the iterator when it is done with it,
// and it must not use the iterator once the GargantuanTable object
// on which the iterator was created has been deleted.
//
// The iterator is initially positioned at the beginning of the table.
//
// This method is equivalent to:
//    Iterator* iter = table->NewIterator();
//    iter->Seek("");
//    return iter;
// If you are going to immediately seek to another place in the
// returned iterator, it will be faster to use NewIterator()
// and avoid the extra seek.
Iterator* GetIterator() const;

random programs

2008-10-23T18:35:00.001-07:00

摘几个programming pearls 上提到的random function.

1. knuth version. 从1-n之间生成有序的m个不同的随机数( the output is a sorted list of m random integers in the range 0...n-1 in which no integer occurs more than once).

void genknuth(int m, int n) {
  for (int i = 0; i < n; ++i) {
    /* select m of remaining n-i */
    if ((bigrand() % (n-i)) < m) {
      cout << i << "\n";
      --m;
    }
  }
}

2. shuffle the first m elements of the array. output the sorted list of the m random numbers.

void genshuf(int m, int n) {
  int i, j;
  int *x = new int[n];
  for(i = 0; i < n; ++i)
    x[i] = i;
  for(i = 0; i < m; ++i) {
    j = randint(i, n-1);
    int t = x[i]; x[i] = x[j]; x[j] = t;
  }
  sort(x, x+m);
  for(i = 0; i < m; ++i)
    cout << x[i] << "\n";
}

3. floyd. This algorithm uses only m random numbers, even in the worst case.

void genfloyd(int m, int n) {
  set<int> S;
  set<int>::iterator i;
  for(int j = n-m; j < n; ++j) {
    int t = bigrand() % (j+1);
    if(S.find(t) == S.end())
      S.insert(t); // t not in S
    else
      S.insert(j); // t in S
  }
  for(i = S.begin(); i != S.end(); ++i)
    cout << *i << "\n";
}

4. reservoir sampling. when we do not know the length of the data ( we see the data sequentially. )

We always select the first line, we select the second line with probability one half, the third line with probability one third, and so on. At the end of the process, each line has the same probability of being chosen (1/n, where n is the total number of lines in the article).

counting sort + bit operation

2008-10-19T20:30:00.001-07:00

UVa problem: Bridge Hands

每一花色牌不超过13张，4种花色，用一个long long表示，每16位一组表示一个花色

#include <stdio.h>
#include <string.h>

long long player[4];
int p[90];
char ip[4] = {'C', 'D', 'S', 'H'};
int seat[90];
char iseat[4] = {'S','W','N','E'};
int idx[90];
char inverse_idx[15] = {'0','1','2','3','4','5','6','7','8','9','T','J','Q','K','A'};
//int __builtin_ctz(long long);
int main() {
    char buff[60];
    seat['S'] = p['C'] = 0; 
    seat['W'] = p['D'] = 1;
    seat['N'] = p['S'] = 2;
    seat['E'] = p['H'] = 3;
    int i, j;
    for(i = 2; i <= 9; ++i)
        idx[i+48] = i;
    idx['T'] = 10;
    idx['J'] = 11;
    idx['Q'] = 12;
    idx['K'] = 13;
    idx['A'] = 14;       
    char t;
    while((t = getchar()) != '#') {
        while(gets(buff) && strlen(buff)==0){};
        int side = seat[t];
        memset(player, 0, sizeof(player));
        for(i = 0; i < 52; i += 2) {
            if(++side == 4) side = 0;
            /* get card, set its bit */
            player[side] |= 1LL<< (p[buff[i]]<<4LL) + idx[buff[i+1]]; 
        }
        gets(buff);
        for(i = 0; i < 52; i += 2) {
            if(++side == 4) side = 0;
            player[side] |= 1LL<< (p[buff[i]]<<4LL) + idx[buff[i+1]];
        }
        
        for(i = 0; i < 4; ++i) {
            int printed = 0;
            printf("%c: ", iseat[i]); 
            for(j = 0; j < 4; ++j) {                
                /* get current color */
                int c = player[i] & 0xffff;
                player[i] >>= 16; /* next color */
                while(c) {
                    int pos = __builtin_ctz(c);
                    c ^= 1LL << pos;  /* clear printed bit */
                    printf("%c%c", ip[j], inverse_idx[pos]); 
                    if(++printed < 13) printf(" ");
                }
            }
            printf("\n");
        }
    }
}

/* gcc has built in __builtin_ctz, vc not*/

/*
int __builtin_ctz(long long c) {

    for(int i = 0; i < 64; ++i)
        if(c & (1LL<<i)) return i;
}*/

Maximum interval sum

2008-10-19T15:41:00.001-07:00

Or maximum contiguous subvector of the input.

Do a linear sweep from left to right, accumulate the sum. Start new interval whenever you encounter partial sum < 0.

/* 1-d linear alg O(n) */
inline int mis1d(int line[], int size) {
    int maxv = -INF;
    int p = 0;
    for(int i = 0; i < size; ++i) {
        p += line[i];
        if(p < 0) p = 0;
        if(p > maxv) maxv = p;
    }
    return maxv;
}

In a 2D problem, we are expected to find a maximum sum subrectangle in a mxn matrix.

We first calculate the accumulative sum in the dimension of length m (smaller dim).

We then use the above technique in the dimension of length n.

The total running time is O(m^2 n). (for nxn matrix, that is O(n^3) )

UVa problem: 108, 836

#include <iostream>
using namespace std;

#define INF 999999999
int M[101][101];
int partialSum[101][101];
int line[101];

/* 1-d linear alg O(n) */
inline int mis1d(int line[], int size) {
    int maxv = -INF;
    int p = 0;
    for(int i = 0; i < size; ++i) {
        p += line[i];
        if(p < 0) p = 0;
        if(p > maxv) maxv = p;
    }
    return maxv;
}

/* 2-D O(n^3) */
int mis2d(int size) {
    int maxv = -INF;
    for(int j = 0; j < size; ++j) {
        partialSum[0][j] = M[0][j];
        for (int i = 1; i < size; i++)
            partialSum[i][j] = partialSum[i-1][j] + M[i][j];
    }
    for(int i = 0; i < size; ++i) {   // use from the i-th row
        for(int j = i; j < size; ++j) {  // to the j-th row
            if(i == j) 
                memcpy(line, M[i], size*sizeof(int));
            else {
                // generate the data i to j-th row
                for(int k = 0; k < size; ++k)
                    line[k] = partialSum[j][k] - partialSum[i][k];
            }
            int v = mis1d(line, size);
            if(v > maxv) maxv = v;
        }
    }
    return maxv;
}

int main() {
    int n;
    while(scanf("%d ", &n) == 1) {
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                scanf("%d", &M[i][j]);
        printf("%d\n", mis2d(n));
    }
}

Related problems:

find the subvector with the sum closest to zeros

calc the accumulative sum so that cum[i] = x[0] + ... + x[i]

The subvector x[l ... u] sums to zeros if cum[l-1] = cum[u]

the subvector with the sum closest to zeros is found by locating the two closest elements in cum

which can be done in O(nlogn) by sorting

find the subvector with the sum closest to a given real number t.

a simple extension from the above case

The subvector x[l ... u] sums to t if cum[l-1] + t = cum[u] and l-1<u

first nlogn sorting

then for each element, do a (log n) binary search for closest to (cum[i]+t)

initialize upon the first use

2008-10-19T11:58:00.001-07:00

This is a technique coverd in Programming Pearls. (Chap 1, Problems 9)

This method use constant time for initialization and for each vector access, and use extra space proportional to the size of the vector. Because this method reduces initialization time by using even more space, it should be considered only when space is cheap, time is deer and the vector is sparse.

My test code here ( #define COL to enable 2-D matrix test case)

#include <iostream>
#include <ctime>
using namespace std;

// max row and col size
#define ROW 8000
// if 1-d, just comment the next line
#define COL 8000
int top = 0;

#ifndef COL
int data[ROW];
#define MAXE ROW
#else
int data[ROW][COL];
#define MAXE ROW*COL
#endif

// two additional array to implement a simple signature
int from[MAXE];
int to[MAXE];

// if element i in the array is initialised 
inline bool exist(int i, int j=0) {
#ifdef COL
    int idx = COL*i+j;
#else
    int idx = i;
#endif
    if(from[idx] < top && to[from[idx]] == idx)
        return true;
    return false;
}

// assign data value to the i-th element
#ifndef COL
inline void setdata(int i, int v) {
    if(!exist(i)) {        
        from[i] = top;
        to[top] = i;
        ++ top;
    }
    data[i] = v;
}

#else
inline void setdata(int i, int j, int v) {
    if(!exist(i, j)) {
        int idx = COL*i+j;
        from[idx] = top;
        to[top] = idx;
        ++ top;
    }
    data[i][j] = v;
}
#endif

int main(int argc, char* argv[]) {
    int startt = clock();
    printf("initialize at start time--\n");
    memset(data, 0, sizeof(data));

    int n;
    if(argc < 2 || atoi(argv[1]) > ROW) n = 100;
    else n = atoi(argv[1]);

#ifndef COL
    for(int i = 0; i < n; ++i)
        data[i] = (i*i-i)/(i+1);
    int starts = clock();
    printf("use %d\n", starts-startt);

    printf("no initialization--\n");
    for(int i = 0; i < n; i++)
        setdata(i, (i*i-i)/(i+1));
    printf("use %d\n", clock()-starts); 

#else
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; ++j)
            data[i][j] = (i*j-i)/(i+1);

    int starts = clock();
    printf("use %d\n", starts-startt);

    printf("no initialization--\n");
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; ++j)
            setdata(i, j, (i*j-i)/(i+1));

    printf("use %d\n", clock()-starts);
#endif
}

From the test result:

When the operations overhead is much less than the initialization cost, use init upon the first use.

When the vector/matrix is not sparse (e.g., > 10% full), memset is fast enough.

It seems the access speed of alg2 is 10 times slower than direct access speed

+------------+----------+-----------+----------+
|matrix dim  |#  op     |alg 1 (ms) |alg 2 (ms)| 
|8000 x 8000 |10 x 10   |312        |0         |
|8000 x 8000 |100x100   |312        |0         |
|8000 x 8000 |1000x1000 |328        |187       |
|8000 x 8000 |4000x4000 |531        |2922      |
+------------+----------+-----------+----------+

bit operation again SRM 422

2008-10-18T16:11:00.001-07:00

topcder: BirthdayCake

用gcc的__builtin_popcount()速度快了两倍多。

由于cake 那个是50位的，用了long long，然后调用__builtin_popcount两次分别处理高低32位然后求和。注意给常数1加上LL后缀。

// couting 1's
inline int count_bit(long long n) {
    return __builtin_popcount(n>>32) + __builtin_popcount(n &((1LL<<32)-1LL));
}

void checkmax(int &a, int b) {
    if(a < b) a = b;
}

int BirthdayCake::howManyFriends(vector <string> availableFruits, vector <string> f, int K) {

    int N = availableFruits.size(); // total number of available fruit
    int m = f.size(); // friend number
    map<string,int> fruit;
    for(int i = 0; i < N; ++i)
        fruit.insert(make_pair(availableFruits[i], fruit.size()));

    long long mask = (1LL<<N)-1LL;
    vector<long long> like(m, mask);
    for(int i = 0; i < m; ++i) {
        stringstream ss;
        ss << f[i];
        string tmp;
        while(ss >> tmp) { 
            if(!fruit.count(tmp)) continue;
            like[i] &= ~(1LL<< fruit[tmp]); // clear uliked bits
        }
    }
    int max = (1<<(m))-1; // all friends included
    
    int maxnf = 0; // max number of friends included
    // brute force traversal of all subsets
    for(int i = max; i >=0 ; --i) {
        long long cake = mask;
        for(int j = 0; j < m; ++j) if( i & (1<<j) ) {
            cake &= like[j];
            if( count_bit(cake) < K )
                goto next;
        }
        checkmax(maxnf, count_bit(i));
next:   continue;
    }
    return maxnf;
}

closest pair problem

2008-10-17T17:57:00.001-07:00

Closest pair of points problem on wiki

nearest neighbor problem

k-d tree on wiki

Sweeping: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPair1D.html

every time the sweep line encounters a point p, we will perform the following actions:

Remove the points further than d to the left of p from the ordered set D that is storing the points in the strip.
Determine the point on the left of p that is closest to it
If the distance between this point and p is less than d (the current minimum distance), then update the closest current pair and d.

The summary and analysis of the plane sweep algorithm goes something like this:

sort the set according to x-coordinates (this is necessary for a plane sweep approach to determine the coordinates of the next point), which takes O(nlogn) time
inserting and removing each point once from the ordered set D (each insertion takes O(logn) time as shown in the section on (2,4)-trees), which takes a total of O(nlogn) time
comparing each point to a constant number of its neighbors (which takes O(n) time in total )

K-D Tree

Animation: http://donar.umiacs.umd.edu/quadtree/points/kdtree.html

Complexity

Building a static kd-tree from n points takes O(n log ² n) time if an O(n log n) sort is used to compute the median at each level. The complexity is O(n log n) if a linear median-finding algorithm such as the one described in Cormen et al^[3] is used.

Inserting a new point into a balanced kd-tree takes O(log n) time.
Removing a point from a balanced kd-tree takes O(log n) time.
Querying an axis-parallel range in a balanced kd-tree takes O(n^1-1/d +k) time, where k is the number of the reported points, and d the dimension of the kd-tree.
Finding the nearest point is an O(log N) operation.

Bit operations hacks

2008-10-17T15:13:00.001-07:00

I find a few more interesting sites:

Bit Twiddling Hacks

The Aggregate Magic Algorithms

Design Patterns (4) - Factory method and Abstract Factory

2008-10-16T19:18:00.001-07:00

Factory method
Define an interface for creating an object, but let subclasses decide which class to instantiate. Factory Method lets a class defer instantiation to subclasses.

Why would anybody use such a design pattern?

Imagine you are writing the code for the “Client” object. The “client” object needs to use the “Product” object. You hard code the object creation process in the “Client” Now any changes in the object creation procedure would mean that you need to change the “client” too. The sole purpose of the “Factory” object is to create “Product” This gives us a certain amount of flexibility. The “client” delegates that task to “Factory”. Any changes in the object creation process do not affect the “client” and changes to “Factory” should be fairly simple as that is the only thing it does.

ref: http://vorleakchy.wordpress.com/2008/08/15/factory-method-design-pattern/

Principles:

No variable should hold a reference to a concrete class. If you use new, you' ll be holding a reference to a concrete class. Use a factory to get around that!

No class should derive from a concrete class. If you derive from a concret class, you're depending on a concrete class. Derive from an abstraction, like an interface or an abstract class.

No method should override an implemented method of any its base class. If you override an implemented method, then your base class wasn't really an abstraction to start with. Those methods implemented in the base class are meant to be shared by all your subclasses.

My simple factory method example:

//Pizza example:

#include <string>
#include <iostream>
class Pizza {
public:
    virtual void get_price() = 0;
};
 
class HamAndMushroomPizza: public Pizza {
public:
    virtual void get_price(){
        std::cout << "Ham and Mushroom: $8.5" << std::endl;
    }
};
 
class DeluxePizza : public Pizza {
public:
    virtual void get_price() {
        std::cout << "Deluxe: $10.5" << std::endl;
    }
};
 
class SeafoodPizza : public Pizza {
public:
    virtual void get_price(){
        std::cout << "Seafood: $11.5" << std::endl;
    }
};
 
class PizzaFactory {
public:
    static Pizza* create_pizza(const std::string type) {
        if (type == "Ham and Mushroom")
            return new HamAndMushroomPizza();
        else if (type == "Seafood Pizza")
            return new SeafoodPizza();
        else
            return new DeluxePizza();
    }
};
//usage
int main() {
    PizzaFactory factory;
    Pizza *pz = factory.create_pizza("Default");
    pz->get_price();
 
    Pizza *ph = factory.create_pizza("Ham and Mushroom");
    ph->get_price();
 
    delete pz;
    pz = factory.create_pizza("Seafood Pizza");
 
    pz->get_price();
    delete pz;
    delete ph;
}

Design Patterns (3) - Decorator

2008-10-16T18:00:00.001-07:00

Decorator: Attach additional responsibilities to an object dynamically keeping the same interface. Decorators provide a flexible alternative to subclassing for extending functionality.

The idea:

Start with a basic component and "decorate" it with condiments at runtime.
Decorators have the same supertype as the objects they decorate.
Given that the decorator has the same supertype as the object it decorates, we can pass around a decorated object in place of the original object.
The decorator adds its own behavior either before and/or after delegating to the object it decorates to do the rest of the job.
Objects can be decorated at any time, so we can decorate objects dynamically at runtime with as many decorators as we like.

Design Patterns (2) - Observer

2008-10-16T16:24:00.000-07:00

Observer :

Define a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.

Design principles of Observer ( from head first Design Pattern Chap 2)

The thing that varies in the Observer Pattern is the state of the Subject and the number and types of Observers. With this pattern, you can vary the objects that are dependent on the state of the Subject, without having to change that Subject. That's called planning ahead!
Both the Subject and Observer use interfaces. the subject keeps track of objects implementing the Observer interface, while the observers register with, and get notified by the Subject interface. As we've seen, this keeps things nice and loosely coupled.
The Observer Pattern uses composition to compose any number of Observers with their Subjects. These relationships aren't set up by some kind of inheritance hierarchy. No, they are set up at runtime by composition!

wiki's c++ example shows an implementation of head first's chap 2 problem. It is a nice example.

Just refer to it for deep understanding of the pattern.

Design Patterns (1) - Strategy

2008-10-16T14:49:00.001-07:00

book reference:

Gang-of-four: Design Patterns
Head first design patterns

resource reference:

Strategy Pattern:

Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it.

The Context has-a behavior of Strategy, which can be implemented with different algorithms.
We define a private member in Context: a pointer to the general superclass Strategy.
We have a set_strategy method in Context class to change behavior at runtime.
We also have a superclass: Strategy and a bunch of subclass : ConcreteStrategy to implement the behavior.
In client code, we have one or multiple instances of Context.
At any given time, only one ConcreteStrategy is availabe to be executed a single Context object.

Strategy Pattern example:

#include <iostream>
 
using namespace std;
 
class StrategyInterface
{
    public:
        virtual void execute() = 0;
};
 
class ConcreteStrategyA: public StrategyInterface
{
    public:
        virtual void execute()
        {
            cout << "Called ConcreteStrategyA execute method" << endl;
        }
};
 
class ConcreteStrategyB: public StrategyInterface
{
    public:
        virtual void execute()
        {
            cout << "Called ConcreteStrategyB execute method" << endl;
        }
};
 
class ConcreteStrategyC: public StrategyInterface
{
    public:
        virtual void execute()
        {
            cout << "Called ConcreteStrategyC execute method" << endl;
        }
};
 
class Context
{
    private:
        StrategyInterface *_strategy;
 
    public:
        Context(StrategyInterface *strategy):_strategy(strategy)
        {
        }
        void set_strategy(StrategyInterface *strategy) 
        {
            _strategy = strategy;
        }
        void execute() 
        {
            _strategy->execute();
        }
};
 
int main(int argc, char *argv[])
{
    ConcreteStrategyA concreteStrategyA;
    ConcreteStrategyB concreteStrategyB;
    ConcreteStrategyC concreteStrategyC;

    Context contextA(&concreteStrategyA);
    Context contextB(&concreteStrategyB);
    Context contextC(&concreteStrategyC);
 
    contextA.execute();
    contextB.execute();
    contextC.execute();

    contextA.set_strategy(&concreteStrategyB);
    contextA.execute();
 
    return 0;
}

interprocess communication IPC (2) - shared memory

2008-10-14T22:40:00.000-07:00

I use the IPC-shared memory to help solve UVa problem 495: fib freeze.

The same algorithm is ranked 3rd !

The idea is as follows:

the main process fork a child to precompute the Fib numbers up to 5000.

the main process at the same time read in all input n!

as soon as the child finish, main process begin table-lookup and output

the shared memory is a char [][], each char[] contains a factorial for the corresponding n

i use semaphore (here actually act as a mutex) to synchronize the shared memory access

the child process get resource and release until it finishes computing 5000!

the main process then access the resource to lookup the result

The program flow:

shmget: to request a shared memory block from the system

shmat: to link the pointer to the shared memory

semget: to create a semaphore (IPC_CREAT)

semctl: to initialize the semaphore (SET_VAL)

fork: to generate a child process

semop: to use semaphore to maintain the resource access

semctl: to remove semaphore ( IPC_RMID)

shmdt: to detatch the pointer from the shared memory

shmctl: to delete the shared memory ( IPC_RMID)

shmget很容易出错,如果是异常退出，可能需要更换key，重新run, （考虑用ipcrm -m #shmid kill)

最大可分配的memory及相关的参数可在man shmget中找到

e.g., /proc/sys/kernal/shmmax maximum memory

#include <stdio.h>
#include <unistd.h>
#include <vector>
#include <sys/shm.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

#include "BigInt.h"

#define MAXSZ  5000

struct databuf {
  char memo [MAXSZ+1][1050];
};

int main(int argc, char *argv[])
{
    key_t key = 0x18845;
    int shmid;
    int semid;
    int mode;

    /* make the key: */
    /*
    if ((key = ftok("plotter.c", 'R')) == -1) {
        perror("ftok");
        exit(1);
	}*/

    /* connect to (and possibly create) the segment: */
    if ((shmid = shmget(key, sizeof(databuf), 0600 |IPC_CREAT)) == -1) {
      printf("shmid %d %d\n", shmid,errno);
      perror("shmget");
      switch(errno) {
      case EACCES:
	    printf("access permit\n");break;
      case EEXIST:
	    printf("segment exist\n"); break;
      case EINVAL:
	    printf("einval\n");break;
      case ENFILE:
	    printf("enfile\n");break;
      case ENOENT:
	    printf("enoent\n");break;
      case ENOMEM:
	    printf("no memory\n");break;
      case ENOSPC:
	    printf("enospc\n");break;
      case EPERM:
	    printf("eperm\n");break;
      default:
	    printf("other\n");break;
      }      
	
      exit(1);
    }
    /* attach to the segment to get a pointer to it: */
    databuf* data = (databuf*)shmat(shmid, (void *)0, 0);
      
    if (data == (databuf *)(-1)) {
        perror("shmat");
        exit(1);
    }
    //memset(data, 0, sizeof(data));

    struct sembuf P = {0, -1, 0};  /* set to allocate resource */
    struct sembuf V = {0, 1, 0}; /* free resource */

    /*
    if ((key = ftok("fibfreeze.c", 'J')) == -1) {
        perror("ftok");
        exit(1);
	}*/

    /* create a semaphore set with 1 semaphore: */
    if ((semid = semget(0x99543, 1, 0666 | IPC_CREAT)) == -1) {
        perror("semget");
        exit(1);
    }
    //printf("sem id %d\n", semid);

    /* initialize semaphore #0 to 1: */
    if (semctl(semid, 0, SETVAL, 1) == -1) {
        perror("semctl");
        exit(1);
    }

    pid_t kid = fork();
    if(kid  == 0) {
      //printf("kid process \n");
      //kid process, computer fib number up to 5000
      BigInt a1(0), a2(1), a;
      semop(semid, &P, 1);
      strcpy(data->memo[0], "0");
      strcpy(data->memo[1], "1");
      
      for(int i = 2; i <= MAXSZ; ++i){
	    a = a1 + a2;
	    strcpy(data->memo[i], a.toString().c_str());
	    //printf("calc m[%d]=%s\n", i, data->memo[i] );
	    //printf("calc %d, len %d\n", i, strlen(data->memo[i]));
	    a1 = a2;
	    a2 = a;
      }
      semop(semid, &V, 1);
      exit(0);
    } else {
      //printf("parent process\n");
      std::vector<int> n;
      int tmp;

      while(scanf("%d ", &tmp) != EOF)
	    n.push_back(tmp);
          
      //wait();
      semop(semid, &P, 1);
      int N = n.size();
      for(int i = 0; i < N; ++i)
	    printf("The Fibonacci number for %d is %s\n", n[i], data->memo[n[i]]);
      semop(semid, &V, 1);
    }
    
    /* remove semaphore */
    if (semctl(semid, 0, IPC_RMID, 0) == -1) {
      perror("semctl");
      exit(1);
    }
    //printf("free semaphores done\n");

    /* detach from the segment: */
    if (shmdt(data) == -1) {
        perror("shmdt");
        exit(1);
    }
    /* remove shared memory */
    if (shmctl(shmid, IPC_RMID, 0) == -1) {
       perror("shmctl shmid");
       exit(1);
    }    
    //printf("free memory segment done\n");
    return 0;
}

interprocess communication IPC (1) - message queue

2008-10-14T12:57:00.000-07:00

Beej's Guide
Advanced Linux Programming

IPC methods:

Signal
Pipe
Named Pipe
Message Queue
Shared Memory

Message Queue:


/* use ftok(...) to generate a key */
/* key_t ftok(const char* path, int id) */

key_t key = ftok("/home/someone/somefile", 'b');

/* create or connect to an existing queue */
/* int msgget(key_t key, int msgflg) */
/* 666 -> rw-rw-rw- */
int msqid = msgget(key, 0666|IPC_CREAT);

/* each message is made up of two parts */
/* mtype is set to any positive number as a message type */
/* mdata is any data struct that will be added to the queue */
   struct pirate_msgbuf {
       long mtype;  /* must be positive */
       char name[30];
       char ship_type;
       int notoriety;
       int cruelty;
       int booty_value;
   };

/* pass the message to the queue */
/* int msgsnd(int msqid, const void *msgp, size_t msgsz, int msgflg);
struct pirate_msgbuf pmb = {2, "L'Olonais", 'S', 80, 10, 12035};
msgsnd(msqid, &pmb, sizeof(pmb), 0);

/* retrieve message from the queue */
struct pirate_msgbuf pmrecv;
/*  int msgrcv(int msqid, void *msgp, size_t msgsz, long msgtyp, int msgflg); */
msgrcv(msqid, &pmrecv, sizeof(pmb), 2, 0);

/* destroy a message queue */
msgctl(msqid, IPC_RMID, NULL);

beej's guide provides a pair of nice example source
kirk.c spock.c
start kirk and spock, you can send text through kirk and receive them through spock.
Also you can try to add mtype to enable multiple kirks and spocks.

Here is a little piece of code of my test:
I am using fork() to create a kid process to read characters from stdin,
then using the parent process to simulate running a simple algorithm based on the message read by kid.

/* interprocess communication: Message Queue */

#include < stdio.h >
#include < stdlib.h >
#include < ctype.h >
#include < sys/ipc.h >
#include < sys/msg.h >
#include < unistd.h >
#include < time.h >

const int ARR_SIZE = 8;


struct mymsgbuf{
  long mtype; // a positive integer: 
  int a[ARR_SIZE];
};

int main(int argc, char* argv[]) {

  int N = 0;
  if(argc < 2)
    N = 100;
  else 
    N = atoi(argv[1]);

  printf("number of computations = %d\n", N*N);

  key_t key = ftok("ab.", 'm');
  int msgq_id; // message queue id

  //initializes a new message queue
  if((msgq_id = msgget(key, IPC_CREAT|0660)) == -1) {
    printf("msgget error\n");
    exit(1);
  } else {
    printf("msg queue id %d created\n", msgq_id);
  }
  
  if(fork() == 0) {
    printf("this is child process\n");
    mymsgbuf qbuf;
    qbuf.mtype = 1;
    
    int j = 0;
    while(!feof(stdin)) {
      for(int i = 0; i < ARR_SIZE; ++i) {
 scanf("%d ", &qbuf.a[i]);
      }
      if((msgsnd(msgq_id, &qbuf, sizeof(mymsgbuf)-sizeof(long), 0)) == -1) {
 printf("error in msgsnd\n");
 exit(1);
      }
      ++j;
    }
    // the last message 
    // use mtype = 2 to notify the parent process
    qbuf.mtype = 2;
    msgsnd(msgq_id, &qbuf, sizeof(mymsgbuf)-sizeof(long),0);
    printf("send %d\n", j);
    return 0;
  } else { // in parent process
    printf("this is parent process\n");
    mymsgbuf qbuf;
    int j = 0;
    while(msgrcv(msgq_id, &qbuf, 200, 0, 0)) {
      if(qbuf.mtype == 2) break;

      int total = 0;
      int t = N;

      /* just doing some work */
      while(t--) {
 for(int i = 0; i < ARR_SIZE; ++i)
   for(int k = 0; k < ARR_SIZE; ++k)
     total += qbuf.a[i] * qbuf.a[k];
      }
      ++j;
    }
    wait(); // wait until the child process finish
    printf("recv %d\n", j);
    msgctl(msgq_id, IPC_RMID, 0); // delete the message queue
    printf("msg q removed\n");
  }

  // printf("time taken %d\n", clock()-startt);
  return 0;
}

running output:time ./msgq 100 < tmp
number of computations = 10000
msg queue id 557057 created
this is child process
this is parent process
send 39036
recv 39036
msg q removed

real    0m1.452s
user    0m1.384s
sys     0m0.064s

C++ notes

2008-10-13T20:16:00.001-07:00

From Wikipedia, the free encyclopedia

auto_ptr
- auto_ptr is a template class available in the C++ Standard Library (declared in <memory>) that provides some basic RAII features for C++ raw pointers.
  The auto_ptr template class describes an object that stores a pointer to an allocated object of type Type* that ensures that the object to which it points gets destroyed automatically when control leaves a scope.
Resource Acquisition Is Initialization (RAII)
- The acquisition is typically bound to the construction (initialization) and the automatic, deterministic destruction (uninitialization) is used to guarantee the resource is released. Since scoped objects are cleaned up regardless of whether the scope exits through normal use or through an exception, RAII is a key concept for writing exception-safe code.
virtual inheritance
- In the C++ programming language, virtual inheritance is a kind of inheritance that solves some of the problems caused by multiple inheritance (particularly the "diamond problem") by clarifying ambiguity over which ancestor class members to use.
- c++-faq-lite
placement new
- The simplest use is to place an object at a particular location in memory. This is done by supplying the place as a pointer parameter to the new part of a new expression.
volatile keyword

Data structure alignment

numeric_limits

2008-10-12T15:08:00.001-07:00

#include <iostream>
#include <limits> 

using namespace std;
int main() { 

    cout << "max(short): " << numeric_limits<short>::max() << endl;
    cout << "max(int):   " << numeric_limits<int>::max() << endl;
    cout << "max(long long):  " << numeric_limits<long long>::max() << endl;
    cout << "max(unsigned long long):  " << numeric_limits<unsigned long long>::max() << endl; 

    cout << "max(double):  " << numeric_limits<double>::max() << endl; 

    return 0;
}

output:

max(short): 32767
max(int): 2147483647
max(long long): 9223372036854775807
max(unsigned long long): 18446744073709551615
max(double): 1.79769e+308

C++ FAQ Lite

2008-10-12T15:07:00.001-07:00

http://www.parashift.com/c++-faq-lite/

[18] Const correctness

Constness means using the keyword const to prevent const objects from getting mutated. Declaring the const-ness of a parameter is just another form of type safety.

For example, if you wanted to create a function f() that accepted a std::string, plus you want to promise callers not to change the caller's std::string that gets passed to f(), you can have f() receive its std::string parameter...

void f1(const std::string& s); // Pass by reference-to-const
void f2(const std::string* sptr); // Pass by pointer-to-const
void f3(std::string s); // Pass by value

You have to read pointer declarations right-to-left.

const Fred* p means "p points to a Fred that is const" — that is, the Fred object can't be changed via p.
Fred* const p means "p is a const pointer to a Fred" — that is, you can change the Fred object via p, but you can't change the pointer p itself.
const Fred* const p means "p is a const pointer to a const Fred" — that is, you can't change the pointer p itself, nor can you change the Fred object via p.

"`const` member function" inspects (rather than mutates) its object.

"`const`-overloading"

class Fred { ... }; class MyFredList { public: const Fred& operator[] (unsigned index) const; ← subscript operators often come in pairs Fred& operator[] (unsigned index); ← subscript operators often come in pairs ...};

POSIX Thread

2008-10-10T23:29:00.001-07:00

A nice posix thread tutorial.
Also google a pdf pthread tutorial by Peter Chapin.

Here I am trying to do a very trivial UVa problem: 11172 Relational Operators using multi-threading.
But UVa compiler does not do g++ -pthread. We just play here instead of submission. :)
Two threads:

the first thread read fron stdin
the second thread compare the two numbers and output
both thread access the two buffers using semaphore to synchronize

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/types.h>
#include <errno.h>

struct MYDATA{
  int a;
  int b;
};

MYDATA data[2];

struct sembuf p1 = {0, -1, 0}; // request buf 0
struct sembuf p2 = {1, -1, 0}; // request buf 1
struct sembuf v1 = {0, 1, 0};  // release buf 0
struct sembuf v2 = {1, 1, 0};  // release buf 1

int ndata;
int semid;


void* read(void*) {
  int c = ndata;
  while(1) {
    scanf("%d %d ", &data[0].a, &data[0].b);
    //printf("read %d %d, c %d \n", data[0].a, data[0].b, c);
    if(c-- == 0) break;
    semop(semid, &v1, 1);
    
    semop(semid, &p2, 1);
    scanf("%d %d ", &data[1].a, &data[1].b);
    //printf("read %d %d, c %d \n", data[1].a, data[1].b, c);
    if(c--==0) break;
    semop(semid, &v2, 1);  
    semop(semid, &p1, 1);
  }
  //printf("read thread end\n");
  pthread_exit((void*)0);
}

inline void cmp(int a, int b) {
  if(a > b) printf(">\n");
  else if(a < b) printf("<\n");
  else printf("=\n");
}

void* compare(void*) {
  int c = ndata;
  while(1) {
    //semop(semid, &p2, 1);
    //printf("compare %d %d \n", data[1].a, data[1].b);
    cmp(data[1].a, data[1].b);
    if(c-- == 0) break;
    semop(semid, &v2, 1);
    
    semop(semid, &p1, 1);
    //printf("compare %d %d \n", data[0].a, data[0].b);    
    cmp(data[0].a, data[0].b);
    if(c--==0) break;
    semop(semid, &v1, 1);
    semop(semid, &p2, 1);
  }
  pthread_exit((void*)0);
}

int main() {
  pthread_attr_t attr;
   
  /* create threads */
  pthread_attr_init(&attr);
  pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
  
  scanf("%d ", &ndata);
  scanf("%d %d ", &data[1].a, &data[1].b);
  ndata --;

  if((semid = semget(0x3332, 2, 0600 |IPC_CREAT)) == -1) {
    perror("semget");
    exit(1);
  }

  if(semctl(semid, 0, SETVAL, 0) == -1) {
    perror("semctl");
    exit(1);
  }

  if(semctl(semid, 1, SETVAL, 0) == -1) {
    perror("semctl");
    exit(1);
  }

  pthread_t readThd, compareThd;
  pthread_create(&readThd, &attr, read, (void*)0);
  pthread_create(&compareThd, &attr, compare, (void*)0);


  void * status;
  pthread_join(readThd, &status);
  pthread_join(compareThd, &status);
  
  pthread_exit(NULL);  
}

The IPC shared memory version is as follows:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/shm.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>


struct databuf {
  int a1;
  int b1;
  int a2;
  int b2;
};

inline void cmp(int a, int b) {
  if(a > b) printf(">\n");
  else if(a < b) printf("<\n");
  else printf("=\n");
}

int main(int argc, char *argv[])
{
    key_t key = 0x18875;
    int shmid;
    int semid;
    int mode;

    /* make the key: */
    /*
    if ((key = ftok("plotter.c", 'R')) == -1) {
        perror("ftok");
        exit(1);
    }*/

    /* connect to (and possibly create) the segment: */
    if ((shmid = shmget(key, sizeof(databuf), 0600 |IPC_CREAT)) == -1) {
      perror("shmget");
      exit(1);
    }
    /* attach to the segment to get a pointer to it: */
    databuf* data = (databuf*)shmat(shmid, (void *)0, 0);
      
    if (data == (databuf *)(-1)) {
        perror("shmat");
        exit(1);
    }
    //memset(data, 0, sizeof(data));

    struct sembuf p1 = {0, -1, 0};  /* set to allocate resource */
    struct sembuf p2 = {1, -1, 0};
    struct sembuf v1 = {0, 1, 0}; /* free resource */
    struct sembuf v2 = {1, 1, 0};

    /*
    if ((key = ftok("fibfreeze.c", 'J')) == -1) {
        perror("ftok");
        exit(1);
    }*/

    /* create a semaphore set with 1 semaphore: */
    if ((semid = semget(0x1543, 2, 0666 | IPC_CREAT)) == -1) {
        perror("semget");
        exit(1);
    }
    //printf("sem id %d\n", semid);

    /* initialize semaphore #0 to 1: */
    if (semctl(semid, 0, SETVAL, 0) == -1) {
        perror("semctl");
        exit(1);
    }
    if (semctl(semid, 1, SETVAL, 0) == -1) {
        perror("semctl");
        exit(1);
    }

    int ndata;
    scanf("%d ", &ndata);
    scanf("%d %d ", &(data->a2), &(data->b2));
    
    pid_t kid = fork();
    if(kid  == 0) {
      while(1) {
    if(feof(stdin)) {
      semop(semid, &v1, 1);
      break;
    }
    scanf("%d %d ", &data->a1, &data->b1);
    //printf("read %d %d \n", data->a1, data->b1);
    
    semop(semid, &v1, 1);
    semop(semid, &p2, 1);
    if(feof(stdin)) {
      semop(semid, &v2, 1);
      break;
    }
    scanf("%d %d ", &data->a2, &data->b2);
    //printf("read %d %d \n", data->a2, data->b2);
    
    semop(semid, &v2, 1);  
    semop(semid, &p1, 1);
      }
      //printf("kid exit\n");
      exit(0);
    } else {
      int c = ndata;
      while(1) {
    //printf("cmp %d %d, c %d\n", data->a2, data->b2, c);
    cmp(data->a2, data->b2);
    if(--c ==0) break;
    semop(semid, &v2, 1);
    semop(semid, &p1, 1);

    //printf("cmp %d %d, c %d\n", data->a1, data->b1, c);
    cmp(data->a1, data->b1);
    if(--c ==0) break;
    semop(semid, &v1, 1);
    semop(semid, &p2, 1);
      }
    }
    
    /* remove semaphore */
    if (semctl(semid, 0, IPC_RMID, 0) == -1) {
      perror("semctl");
      exit(1);
    }
    //printf("free semaphores done\n");

    /* detach from the segment: */
    if (shmdt(data) == -1) {
        perror("shmdt");
        exit(1);
    }
    /* remove shared memory */
    if (shmctl(shmid, IPC_RMID, 0) == -1) {
       perror("shmctl shmid");
       exit(1);
    }    
    //printf("free memory segment done\n");
    return 0;
}

RPN and evaluation tree

2008-10-10T20:33:00.000-07:00

First, here is a very good article on "An expression evaluator" with source code. It also gives detailed introduction on RPN (Reverse Polish Notation).
Here is the algorithm to parse in RPN's manner:


for each char of the expression
  decide if the char is part of an operand or of an operator
  if the char is part of an operand,
    append it to the list of operands
  else if the char is part of an operator,
    look up the operator
  match it with supported operators
  compare operator with the preceding operators
  if this operator is prevalent,
    store the operator in a stack
    otherwise, unstack the preceding operator,
               append the preceding operator to the list of operands
               stack the new operator
  end if
  end if
end for

Wiki's article on RPN.

For example: an math expression: 9+8x5-20^3


list 1 (operand)      | list 2 (operator)
9                     |
9                     | +                      
9 8                   | +
9 8                   | + x ( x has precedence over +, so just append x)
9 8 5                 | + x
9 8 5 x               | + - ( x has precedence over -, so remove x, append x to operand list, then  append - to operator list)
9 8 5 x 20            | + -
9 8 5 x 20            | + - ^ (of course, ^ has precedence over -, just append ^ on operator list)
9 8 5 x 20 3          | + - ^
9 8 5 x 20 3 ^        | + - (now start from the tail, remove all elements from operator list and append then to the operand list one by one)
9 8 5 x 20 3 ^ -      | +
9 8 5 x 20 3 ^ - +    |

RPN parsing done!

Calculation starts from the left, push elements onto calc stack.
Whenever you get one operator, do the calculation immediately. push the result onto the stack.

Calculation stack     | comment
9                     |
9 8 5 x               | 8 x 5 = 40
9 40                  |
9 40 20               |
9 40 20 3             |
9 40 20 3 ^           | 20 ^ 3 = 8000
9 40 8000             |
9 40 8000 -           | 40 - 8000 = -7960
9 -7960               |
9 -7960 +             | 9 + (-7960) = -7951
-7951

done! so 9+8x5-20^3 = -7951

Problem UVa 288: Arithmetic Operations With Large Integers

I used BigInt library from shygypsy.com
Just modified the operator ^ to support "repeated squaring".
i.e.,


BigInt BigInt::operator^  (BigInt n){
  
  BigInt result = 1;
  BigInt base = *this;
  while(n > 0) {
    if(n % 2 == 1) {
      result *= base;
    }
    base *= base;
    n /= 2;
  }
    
  return result;
}

// operator precedence
// + - 2+3-4-5+4, use left -> right
// 2*3*4*5, use left->right
// 6^7^8^9, use right->left
bool precedence(int z1, int z2) {
  if(z1 == -10) return true;
  if(z2 == -10) return false;

  if(z1 == z2) return false;
  if(z1 == -5) return true;
  if(z2 == -5) return false;
  return false;
}

char buff[35000];
int main() {
  while(gets(buff) && !feof(stdin)) {
    string b(buff);
    // since op is positive, we use 
    // - negative integer to represent operator, 
    // - positive integer to represent operand
   
    // so we define
    //   **  = ^ = -10
    //   *   = -5
    //   + = -1
    //   - = -2
 
    deque number;
    deque op;
    int pos = 0;
    for(int i = 0; i < b.size(); ++i) {
      if(b[i]>='0' && b[i]<='9') continue;

      // append previous numbers
      number.push_back(BigInt(b.substr(pos, i-pos).c_str()));
      
      int v;
      // power has highest priority
      if(b[i]=='*' && b[i+1] == '*') {
 v = -10;
 ++i;
      } else {
 if(b[i] == '*') v = -5;
 else if(b[i] == '+') v = -1;

 else if(b[i] == '-') v = -2;

 if(!op.empty() && !precedence(v, op.back())) {
   number.push_back(BigInt(op.back()));
   op.pop_back();
 }
      }
 
      op.push_back(v);
      pos = i + 1;
    }
    // append the last number
    number.push_back(BigInt(b.substr(pos).c_str()));
    
    while(!op.empty()) {
      number.push_back(BigInt(op.back()));
      op.pop_back();
    }
    
    /*
    deque tmp(number);
    while(!tmp.empty()){
      cout << tmp.front()<< " ";
      tmp.pop_front();
    }
    printf("\n");*/

    // parse into reverse polish format   
    stack calc;
    while(!number.empty()) {
      BigInt t = number.front();
      number.pop_front();

      // t is an operator
      if( t < 0) {
 BigInt right = calc.top(); calc.pop();
 BigInt left = calc.top();  calc.pop();
 BigInt res;
 if(t == -1) res = left+right;
 else if(t == -2) res = left-right;
 else if(t == -5) res = left*right;
 else res = left^right;

 calc.push(res);
      } else {
 calc.push(t);
      }
    }  
    cout << calc.top()<< endl;
  } 
  return 0;  
}

Tree Recovery

2008-10-09T17:41:00.001-07:00

Problem UVa: 536 - Tree Recovery

给了pre-order 和 in-order traversal 序列，要求输出post-order

The idea behind the code below is this:
1) The root is first element of the pre-order traversal
2) Everything left of the root in the in-order traversal belongs to the left subtree. Similarly everything to the right belongs to the right subtree.
3) The children of the current root are the first elements of the sub-pre-order-traversals.
4) recurse and put the numbers of the children in an array
5) recurse in post-order traversal through the new tree

/* 536 - Tree Recovery */
/* recursion */

#include <iostream>
char preorder[30];
char inorder[30];

void recover(int x1, int y1, int x2, int y2) {

    char t = preorder[x1];
    if(x1 == y1) {
        printf("%c", t);
        return;
    }  

    // locate the root position in in-order 
    // which split the travel seq into two halves
    int pos;
    for(int i = x2; i <= y2; ++i)
        if(inorder[i] == t) {
            pos = i;
            break;
        }

    int p = x1+pos-x2;

    // visit left sub-tree
    if(pos-1 >= x2)
        recover(x1+1, p , x2, pos-1);
    // visit right sub-tree
    if(y2 >= pos+1)
        recover(p+1, y1, pos+1, y2);

    // postorder -> print root at last
    printf("%c", t);
}
int main() {

    while(scanf("%s %s ",preorder, inorder) != EOF) {
        int L = strlen(preorder) - 1;
        recover(0, L, 0, L); // first <0,L> is preorder index, second <0,L> is in-order index
        printf("\n");
    }
}

Problem UVa: 10410 Tree Reconstruction

给了BFS和DFS traversal序列，要输出每个节点和它相应的叶子结点

Skill keywords in IT job-seeking website

2008-10-09T07:20:00.001-07:00

.Net
Algorithm
AJAX
ASP
ASP.net
Analyst
C
C#
Data Structure
Design Pattern
CSS
Database Design
DB2/UDB
DHTML
HTML
J2EE
JAVA
JDBC
JSP
NetBeans
OOP
Oracle
Performance Tuning
Perl
PHP
PVCS Team Tracker
Python
Ruby
Scripting
UML
Unix/Linux
VB
Web App
XML
XSL

gcd, binomial number

2008-10-07T17:07:00.001-07:00

Problem: UVa 530 Binomial Showdown

这道题我用了cache + online computation, 一小部分数据先算好，不在表里的现算，在表内的直接查表

typedef unsigned long long uLL;
uLL gcd(uLL a, uLL b) {
    if(a % b == 0) 
        return b;
    else
        return gcd(b, a%b);
}

void divbygcd(uLL &a, uLL &b) {
    uLL g = gcd(a,b);
    a /= g;
    b /= g;
}

uLL combination(int n, int k) {
    uLL num = 1, den = 1, tomul, todiv, i;
    if(k > n/2) k = n-k; //use smaller k
    for(i = k; i; --i) {
        tomul = n-k+i;
        todiv = i;
        divbygcd(tomul, todiv);
        divbygcd(num, todiv);
        divbygcd(tomul, den);
        num *= tomul;
        den *= todiv;
    }
    return num / den;
}

Prime Numbers

2008-10-07T12:36:00.000-07:00

Sieve of Eratosthenes:

#include <cmath>
const int MAX = 1000000;
const int SQRT_MAX = (int)sqrt(MAX);

short primes[MAX];
void gen_primes() 
{ 
  for(int i=0;i<MAX;i++) 
    primes[i] = 1; 
  for(int i=2; i<= SQRT_MAX;i++) 
    if (primes[i]) 
      for(int j=i;j*i<MAX;j++) 
        primes[i*j] = 0; 
}

or use our bitvector to store primes[]:

Problem: UVa 543: Goldbach's Conjecture

#include <iostream>
const int MAX = 1000001;
const int SQRT_MAX = 1000;

const int SHIFT = 5;
const int MASK = (1<<SHIFT)-1;

inline void SET(unsigned int a[], int i) {
	a[i>>SHIFT] |= (1 << (i & MASK));
}
inline void CLEAR(unsigned int a[], int i) {
	a[i>>SHIFT] &= ~(1 << (i & MASK));
}
inline bool TEST(unsigned int a[], int i) {
	return a[i>> SHIFT] & (1 << (i & MASK));
}

const unsigned int N = MAX/(sizeof(int)<<3);
unsigned int primes[N+1];

void gen_primes() 
{ 
    memset(primes, 0xAAAAAAAA, sizeof(primes));
    SET(primes, 2);
    for(int i = 3; i <= SQRT_MAX; ++ i) {
        if (TEST(primes, i))  {
            for(int j = i; j * i < MAX; ++ j)  {
                CLEAR(primes, i * j);
            }
        }
    }
} 

int main() {
    gen_primes();
    int n;
    while(scanf("%d ", &n) && n) {
        unsigned int i = 2, pos = 0;
        while(true) {
            unsigned int p = n-i;
            if(TEST(primes,i) && TEST(primes, p)) {             
                printf("%d = %d + %d\n", n, i, p);
                break;
            }
            while(!TEST(primes,++i)) {};
        }
    }
}

Flickr Photostream

2008-10-04T14:15:00.001-07:00

BTW, get your flickr user id here. Also check this.
Created with Admarket's flickrSLiDR.

Trie

2008-10-02T08:16:00.001-07:00

topCoder article: Using Tries

This data structure is used to index and search strings inside a text. Trie allows us to find words that have a single character different, a prefix in common, a character missing, etc. Running time: O(L), where L is the length of a single word.

The left figure is an example from topcoder article. It shows a trie with the words "tree", "trie", "algo", "assoc", "all", and "also".

The trie is a tree where each vertex represents a single word or a prefix.
The root represents an empty string (""), the vertexes that are direct sons of the root represent prefixes of length 1, the vertexes that are 2 edges of distance from the root represent prefixes of length 2, the vertexes that are 3 edges of distance from the root represent prefixes of length 3 and so on. In other words, a vertex that are k edges of distance of the root have an associated prefix of length k.
Let v and w be two vertexes of the trie, and assume that v is a direct father of w, then v must have an associated prefix of w.

My C++ Code:

#include <string>
#include <iostream>

// Interval node data structure
class Node {
    static const int m_n = 26;  // maximum number of kids
private:   
    char m_data;         // data stored at current node
    int m_prefixes;   // how many words have the prefix of the vertex
    int m_words;      // the number of words that match with a given string
    Node* m_kids[m_n];  // pointers to all its kids

public:
    // create an empty node
    Node(): m_data(' '), m_prefixes(0), m_words(0) {
        for(int i = 0; i < m_n; ++i)
            m_kids[i] = NULL;
    };

    // create a node to store data v
    Node(char v): m_data(v), m_prefixes(0), m_words(0) {
        for(int i = 0; i < m_n; ++i)
            m_kids[i] = NULL;
    };

    // copy constructor, recursively copy nodes from p
    Node(const Node& p) {
        this->m_data = p.m_data;
        this->m_prefixes = p.m_prefixes;
        this->m_words = p.m_words;
        for(int i = 0; i < m_n; ++i) {
            if(p.m_kids[i] == NULL) {
                this->m_kids[i] = NULL;
                continue;
            }
            this->m_kids[i] = new Node(*p.m_kids[i]);
        }
    };

    // print substree rooted at p
    void Print(Node* p, const std::string prefix) const {
        int nkids = 0;
        for(int i = 0; i < m_n; ++i) {
            if(p->m_kids[i] == NULL) continue;
            Print(p->m_kids[i], prefix + p->m_data);
            nkids++;
        }
        if(nkids == 0) {
            std::cout << prefix+p->m_data << std::endl;
        }
    };

    // add words rooted at p
    void AddWord(Node* p, const std::string word) {
        if(word.empty())
            p->m_words ++;
        else {
            p->m_prefixes ++;
            int k = word[0]-'a';
            if(p->m_kids[k] == NULL) 
                p->m_kids[k] = new Node(word[0]);
            AddWord(p->m_kids[k], word.substr(1));
        }
    };

    int CountWords(Node *p, const std::string word) const{
        int k = word[0]-'a';
        if(word.empty())
            return p->m_words;
        
        else if(p->m_kids[k] == NULL)
            return 0;
        else 
            return CountWords(p->m_kids[k], word.substr(1));
    };

    int CountPrefixes(Node *p, const std::string prefix) const{
        int k = prefix[0]-'a';
        if(prefix.empty())
            return p->m_prefixes;
        
        else if(p->m_kids[k] == NULL)
            return 0;
        else 
            return CountWords(p->m_kids[k], prefix.substr(1));
    };

    // recursively delete node tree
    ~Node() {
        for(int i = 0; i < m_n; ++i) {
            if(this->m_kids[i] == NULL) continue;
            delete this->m_kids[i];
        }
    };
};
// Trie data structure
class Trie {
public:
    Trie() {m_root = new Node(' ');};
    Trie(const Trie &t) { m_root = new Node(*t.m_root);}
    ~Trie() {delete m_root;};
    void AddWord(const std::string word) { m_root->AddWord(m_root, word); }
    int CountWords(const std::string word) { return m_root->CountWords(m_root, word);}
    int CountPrefixes(const std::string prefix) {return m_root->CountPrefixes(m_root, prefix);}
    void Print() {m_root->Print(m_root, std::string(""));}
private: 
    // root node
    Node* m_root;
};

int main() {
    Trie* t = new Trie();
    t->AddWord(std::string("tree")); 
    t->AddWord(std::string("trie")); 
    t->AddWord(std::string("trie")); 
    t->AddWord(std::string("trie")); 
    t->AddWord(std::string("trie"));
    t->AddWord(std::string("trieg"));
    t->AddWord(std::string("algo"));
    t->AddWord(std::string("algo"));
    t->AddWord(std::string("assoc"));
    t->AddWord(std::string("all"));
    t->AddWord(std::string("allall"));
    t->AddWord(std::string("allus"));
    t->AddWord(std::string("also"));

    t->Print();
    printf("%d\n", t->CountPrefixes(std::string("trie")));  
    printf("%d\n", t->CountPrefixes(std::string("trieg")));
    printf("%d\n", t->CountWords(std::string("trie")));
    
    Trie r(*t);
    delete t;
    r.Print();

    return 0;
}

output:

algo
allall
allus
also
assoc
tree
trieg
4
1
4
algo
allall
allus
also
assoc
tree
trieg

MST (minimum spanning tree)

2008-09-30T19:40:00.001-07:00

Kruskal's algorithm

// G: graph
// w: weight
MST-Kruskal(G, w)
  A = empty set
  for each vertex v in V[G]
      do Make-Set(v)
  sort the edges of E into nondecreasing order by weight w
  for each edge (u,v) in E, taken in nondecreasing order by weight w
      do if Find-Set(u) != Find-Set(v)
          then A = A union {(u,v)}
               Union(u,v)
  return A // MST

Animation: Kruskal Algorithm

Problem: topcoder RoadReconstruction

Editorial: This problem can be solved by modification of standard Kruskal algorithm of finding MST (minimal spanning tree) in undirected graph. Cities will be the vertice of that graph, and roads will be its edges. Each damaged road will provide the corresponding edge the weight that equals the cost of the reconstruction. Other (non-damaged) roads will have weight 0.
Now, let's sort all the edges in ascending order of their weights, and in the case of a tie - in the lexicographical order of their identifiers.
The Kruskal algorithm gives us the minimal spanning tree. Finally, to obtain the answer to the problem let's remove all edges that don't need to be reconstructed from MST. Don't forget to sort the remaining identifiers in the lexicographical order!

下面是Zhomart's solution, 注意他对i/o的处理 (sscanf)，customized sort,

#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<string>
#include<vector>
using namespace std;

struct ROAD {
   int id1,id2,cost;
   char ID[51];
}tr;
map<string,int> names;
vector<ROAD> ed;

char ID[51],STR1[51],STR2[51];
int N,col[51];

bool compare(const ROAD &r1,const ROAD &r2) {
   if( r1.cost!=r2.cost ) return r1.cost<r2.cost;
   return string(r1.ID)<string(r2.ID);
   return false;
}

class RoadReconstruction {
public:
  string selectReconstruction(vector<string> ss) {
     N = 0;
     for(int i=0; i<ss.size(); ++i) {
        ss[i]+=' ';
        tr.cost=0;
        if( sscanf(ss[i].c_str(),"%s %s %s %d",tr.ID,STR1,STR2,&tr.cost)==3 ) tr.cost=0;
        if( names[STR1]==0 ) names[STR1] = ++N;
        if( names[STR2]==0 ) names[STR2] = ++N;
        tr.id1 = names[STR1];
        tr.id2 = names[STR2];
        ed.push_back(tr);
     }

     for(int i=1; i<=N; ++i)
        col[i] = i;

     int M = N;
     sort(ed.begin(),ed.end(),compare);

     string res="";
     vector<string> rr;
     for(int i=0; i<ed.size(); ++i)
        if( col[ ed[i].id1 ] != col[ ed[i].id2 ] ) {
           int ccol = col[ed[i].id1],new_col = col[ed[i].id2];

           //after union, update union id           
           for(int j=1; j<=N; ++j)
              if( col[j]==ccol ) col[j] = new_col;
           // if it is a damaged road
           if( ed[i].cost>0 )
              rr.push_back(ed[i].ID);
           M--; // total set number --, it is supposed to be 1 set left after MST is done
        }
     sort(rr.begin(),rr.end());
     for(int i=0; i<rr.size(); ++i) {
        if( i>0 ) res+=" ";
        res+=rr[i];
     }
     if( M!=1 ) res = "IMPOSSIBLE";

     return res;
  }
};

Prim's algorithm

Union Find

2008-09-30T14:37:00.001-07:00

By wiki: A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which set a particular element is in. Also useful for determining if two elements are in the same set.
Union: Combine or merge two sets into a single set.

topCoder article on Union Find

Applications

Disjoint-set data structures model the partitioning of a set, for example to keep track of the components of a graph of an undirected graph. This model can then be used to determine whether two vertices belong to the same component, or whether adding an edge between them would result in a cycle.
This data structure is used by the Boost Graph Library to implement its Incremental Connected Components functionality.
It is also used for implementing Kruskal's algorithm to find the minimum spanning tree of a graph.

Visualization

a very clear C++ implementation by Emil Stefanov

// Disjoint Set Data Structure
// Author: Emil Stefanov
// Date: 03/28/06
// Implementaton is as described in http://en.wikipedia.org/wiki/Disjoint-set_data_structure

#include <cassert>
#include <vector>

class DisjointSets
{
public:

    // Create an empty DisjointSets data structure
    DisjointSets(){
	    m_numElements = 0;
	    m_numSets = 0;
    };
    // Create a DisjointSets data structure with a specified number of elements (with element id's from 0 to count-1)
    DisjointSets(int count){
	    m_numElements = 0;
	    m_numSets = 0;
	    AddElements(count);
    };
    // Copy constructor
    DisjointSets(const DisjointSets & s){
	    this->m_numElements = s.m_numElements;
	    this->m_numSets = s.m_numSets;

	    // Copy nodes
	    m_nodes.resize(m_numElements);
	    for(int i = 0; i < m_numElements; ++i)
		    m_nodes[i] = new Node(*s.m_nodes[i]);

	    // Update parent pointers to point to newly created nodes rather than the old ones
	    for(int i = 0; i < m_numElements; ++i)
		    if(m_nodes[i]->parent != NULL)
			    m_nodes[i]->parent = m_nodes[s.m_nodes[i]->parent->index];
    };
    // Destructor
    ~DisjointSets(){
	    for(int i = 0; i < m_numElements; ++i)
		    delete m_nodes[i];
	    m_nodes.clear();
	    m_numElements = 0;
	    m_numSets = 0;
    };

    // Find the set identifier that an element currently belongs to.
    // Note: some internal data is modified for optimization even though this method is consant.
    int FindSet(int element) const;
    // Combine two sets into one. All elements in those two sets will share the same set id that can be gotten using FindSet.
    void Union(int setId1, int setId2);
    // Add a specified number of elements to the DisjointSets data structure. The element id's of the new elements are numbered
    // consequitively starting with the first never-before-used elementId.
    void AddElements(int numToAdd){
	    assert(numToAdd >= 0);
	    // insert and initialize the specified number of element nodes to the end of the `m_nodes` array
	    m_nodes.insert(m_nodes.end(), numToAdd, (Node*)NULL);
	    for(int i = m_numElements; i < m_numElements + numToAdd; ++i)
	    {
		    m_nodes[i] = new Node();
		    m_nodes[i]->parent = NULL;
		    m_nodes[i]->index = i;
		    m_nodes[i]->rank = 0;
	    }

	    // update element and set counts
	    m_numElements += numToAdd;
	    m_numSets += numToAdd;
    };
    // Returns the number of elements currently in the DisjointSets data structure.
    int NumElements() const {return m_numElements;};
    // Returns the number of sets currently in the DisjointSets data structure.
    int NumSets() const {return m_numSets;};

private:
    // Internal Node data structure used for representing an element
    struct Node
    {
	int rank; // This roughly represent the max height of the node in its subtree
	int index; // The index of the element the node represents
	Node* parent; // The parent node of the node
    };

    int m_numElements; // the number of elements currently in the DisjointSets data structure.
    int m_numSets; // the number of sets currently in the DisjointSets data structure.
    std::vector<Node*> m_nodes; // the list of nodes representing the elements
};


// Note: some internal data is modified for optimization even though this method is consant.
// path compression
int DisjointSets::FindSet(int elementId) const
{
	assert(elementId < m_numElements);
	Node* curNode;

	// Find the root element that represents the set which `elementId` belongs to
	curNode = m_nodes[elementId];
	while(curNode->parent != NULL)
		curNode = curNode->parent;
	Node* root = curNode;

	// Walk to the root, updating the parents of `elementId`. Make those elements the direct
	// children of `root`. This optimizes the tree for future FindSet invokations.
	curNode = m_nodes[elementId];
	while(curNode != root)
	{
		Node* next = curNode->parent;
		curNode->parent = root;
		curNode = next;
	}
	return root->index;
}

// union by rank
void DisjointSets::Union(int setId1, int setId2)
{
	assert(setId1 < m_numElements);
	assert(setId2 < m_numElements);
	assert(setId1 != setId2);

	Node* set1 = m_nodes[setId1];
	Node* set2 = m_nodes[setId2];

	// Determine which node representing a set has a higher rank. The node with the higher rank is
	// likely to have a bigger subtree so in order to better balance the tree representing the
	// union, the node with the higher rank is made the parent of the one with the lower rank and
	// not the other way around.
	if(set1->rank > set2->rank)
		set2->parent = set1;
	else if(set1->rank < set2->rank)
		set1->parent = set2;
	else // set1->rank == set2->rank
	{
		set2->parent = set1;
		++set1->rank; // update rank
	}
	// Since two sets have fused into one, there is now one less set so update the set count.
	--m_numSets;
}


#include <iostream>
using namespace std;
void printElementSets(const DisjointSets & s)
{
	for (int i = 0; i < s.NumElements(); ++i)
		cout << s.FindSet(i) << "  ";
	cout << endl;
}
int main()
{
	DisjointSets s(10);
	printElementSets(s);
	s.Union(s.FindSet(5),s.FindSet(3));
	printElementSets(s);
	s.Union(s.FindSet(1),s.FindSet(3));
	printElementSets(s);
	s.Union(s.FindSet(6),s.FindSet(7));
	printElementSets(s);
	s.Union(s.FindSet(8),s.FindSet(9));
	printElementSets(s);
	s.Union(s.FindSet(6),s.FindSet(9));
	printElementSets(s);
	s.AddElements(3);
	printElementSets(s);
	s.Union(s.FindSet(11),s.FindSet(12));
	printElementSets(s);
	s.Union(s.FindSet(9),s.FindSet(10));
	printElementSets(s);
	s.Union(s.FindSet(7),s.FindSet(11));
	printElementSets(s);

	system("pause");
	return 0;
}

output:

0 1 2 3 4 5 6 7 8 9
0 1 2 5 4 5 6 7 8 9
0 5 2 5 4 5 6 7 8 9
0 5 2 5 4 5 6 6 8 9
0 5 2 5 4 5 6 6 8 8
0 5 2 5 4 5 6 6 6 6
0 5 2 5 4 5 6 6 6 6 10 11 12
0 5 2 5 4 5 6 6 6 6 10 11 11
0 5 2 5 4 5 6 6 6 6 6 11 11
0 5 2 5 4 5 6 6 6 6 6 6 6
Press any key to continue . . .

Problem: topCoder grafixMask

Editorial suggest using a floodFill with BFS (DFS might have stack overflow problem)

We can also use Union-Find to solve this problem.

bit operation

2008-09-29T18:21:00.001-07:00

http://www.andrewwinter.com/programming/bitwise/

topCoder: A bit of fun: fun with bits

Set union A | B Set intersection A & B Set subtraction A & ~B Set negation ALL_BITS ^ A Set bit A |= 1 << bit Clear bit A &= ~(1 << bit) Negate bit A ^= (1 << bit) Test bit (A & 1 << bit) != 0

Programming Pearls: bitvector functions

const int SHIFT = 5;
const int MASK = (1<<SHIFT)-1;

inline void SET(unsigned int a[], int i) {
 a[i>>SHIFT] |= (1 << (i & MASK));
}
inline void CLEAR(unsigned int a[], int i) {
 a[i>>SHIFT] &= ~(1 << (i & MASK));
}
inline bool TEST(unsigned int a[], int i) {
 return a[i>> SHIFT] & (1 << (i & MASK));
}

int a[1 + N/(sizeof(int)<<3)];

上一贴BFS中用的visited最多支持到 2^27, int visited[2^27], 要用512M内存 (再多vc compilier Error C2148: total size of array must not exceed 0x7fffffff bytes --- 2GB) 。用上面这个bitvector数组可以只用 2^22 int, 16M memory，好很多了。相应改动非常少：

  int BFS( ... ) {
    // ...
    int N = 1 << (totalslots-1); // totalslots+4-5
    unsigned int *v = new unsigned int[N+1];
    memset(v, 0, sizeof(unsigned int)*(N+1));
    queue<State> Q;
    Q.push(State(status, 0, 0)
    SET(v, status); //v[status] = 1;
    while(!Q.empty()) {

                // ...
                // move to the next stump
                int ns = (s.status ^ (uid << totalslots)) | (next << totalslots);
                if(TEST(v, ns) == 0) { //if(v[ns] == 0)
                    SET(v, ns); //v[ns] = 1;
                }
                // ...

提交完这份用了bitvector array的代码后，在UVa 上显示运行时间0.000s :-)

Problem: UVa 594: One Little, Two Little, Three Little Endians

要注意的是，signed int是带着符号位移位的，所以我先把signed int 转成了 unsigned int

/*bit operation*/
#include "stdio.h"

short shift[4] = {24, 16, 8, 0};
int main() {
    int n;
    while(scanf("%d ", &n) != EOF) {    
        unsigned int d = 0;
        unsigned int m = n;
        for(int i = 0; i < 4; ++i) {
            d |= (m & 0xff) << shift[i];
            m = m >> 8; 
        }
        printf("%ld converts to %ld\n", n, d);
    }
}

BFS

2008-09-29T16:13:00.000-07:00

Wiki

Applications of BFS

Breadth-first search can be used to solve many problems in graph theory, for example:

Finding all connected components in a graph.
Finding all nodes within one connected component
Copying Collection, Cheney's algorithm
Finding the shortest path between two nodes u and v (in an unweighted graph)
Finding the shortest path between two nodes u and v (in a weighted graph: see talk page)
Testing a graph for bipartiteness
(Reverse) Cuthill–McKee mesh numbering

topcoder example: use BFS to check graph connectivity

/*
Graph is considered to be stored as adjacent vertices list.
Also we considered graph undirected.
 
vvi is vector< vector<int> >
W[v] is the list of vertices adjacent to v

tr is the macro to get iterator and try each element
*/
 int N; // number of vertices
 vvi W; // lists of adjacent vertices   
 bool check_graph_connected_bfs() { 
      int start_vertex = 0; 
      vi V(N, false); 
      queue<int> Q; 
      Q.push(start_vertex); 
      V[start_vertex] = true; 
      while(!Q.empty()) { 
           int i = Q.front(); 
           // get the tail element from queue
           Q.pop(); 
           tr(W[i], it) { 
                if(!V[*it]) { 
                     V[*it] = true; 
                     Q.push(*it); 
                } 
           } 
      } 
      return (find(all(V), 0) == V.end()); 
 }

Problem

UVa 11501 - Laurel Creek

input :

7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E

7 11 : row and column size
B: starting position;
E: end position;
S: intermediate stump;
- or | : connecting logs
. empty (water)
constraints: row and column size <= 15, stumps # <= 15, all logs exist between stumps

一开始就用了BFS，做起来发现状态太多了。难点就在于怎样记录已经访问过的状态。开始试了一种状态表示，后来证明是错误的。当时用current pos + 该点四周logs的分布情况作为一个单独的状态，其实这是不行的。这种表示方法无法求解出下面这种情况，因为一个状态不仅跟自己所处位置的log相关，还跟其它位置的logs分布也相关。

....S...S..
........|..
B-----S.|.E
......|.|..
......|.S..
......|....
....S-S....

后来先后用了两种方法减少状态空间。利用了这个前提：stumps是固定的，变化的是自己的位置和logs的位置。

用一个2D-bitvector (nrow+1)x ncol 记录图中所有log的位置，每个位对应一个'-' 或者 '|', 多出来的一行用来表示当前位置(x* ncol + y)。整个2d-vector作为一个状态存入一个set visited,之后通过查询visited 中是否有该状态存在得知此状态是否访问过。这个版本由于用了stl set 速度比较慢（在测试数据上用的时间是第二种方法的15倍），但可以用于slots比较多的情况。

vector<int> bitlog;

for(int i = 0; i < nrow; ++i)
   for(int j = 0; j < ncol; ++j)
      if(m[i][j] == '-' || m[i][j] == '|')
          bitlog[i] = bitlog[i] | (1<<j);
bitlog[nrow] = start.first*ncol+start.second;

     set<vector<int> > visited;

在BFS里queue里的元素用了以下类型

struct State{
    ii pos;   // current position
    int log;  // log length
    vector<string> maze; // graph
    vector<int> bitlog;  // 2d bitvector
    int step; // current step
}

Considering the available slots where the log can be picked up or put down, the state space is not that big. Because there are at most 15 stumps with limited row and column size(<= 15) and logs only exist between stumps, the following case is the one that comes with the greatest number of logs. right?

S-S-S-S |.|.|.| S-S-S-S |.|.|.| S-S-S-S |.|.|.| S-S-S-.

#include <iostream>
#include <queue>
#include <ctime>
#include <map>
using namespace std;

typedef pair<int,int> ii;

struct State{
public:
    int status;// current position + log position
    int log;   // log length in hand
    int step;  // current step (for outputing shortest step to destination
    State(int st, int l, int s):status(st), log(l), step(s){}
};

// get log width, pos1/pos2 are stumps position
inline int length(ii pos1, ii pos2) {
    if(pos1.first == pos2.first) return abs(pos1.second-pos2.second)-1;
    return abs(pos1.first-pos2.first)-1;
}

int BFS(int start, int dest, map<int, ii> &stumppos,
        map<int, ii> &slotpos, map<ii,int> &slotlist, int status) {
    if(start == dest) return 0;

    // total available slots to put down or pickup logs
    int totalslots = slotlist.size();

    // make and clear all visited state
    // a bit vector: highest 4 bit --- current position (stump id#)
    // the rest bits: all correspond to an available slot

    // use int* instead of vector<int>, the former is a bit faster 
    int *v = new int[(1<< (totalslots + 4))-1];
    memset(v, 0, sizeof(int)*((1<< (totalslots + 4))-1));

    queue<State> Q;
    Q.push(State(status, 0, 0));
    v[status] = 1;

    while(!Q.empty()) {
        State s = Q.front();
        Q.pop();

        // current position in terms of stump id#
        int uid = s.status >> totalslots;
        // current position in terms of (row,col)
        ii u = stumppos[uid];

       // for each available log
        // i : slots id
        for(int i = 0; i < totalslots; ++i) if(s.status & (1<<i)) {
            ii logpair = slotpos[i];
            // find a connecting log
            if(uid == logpair.first || uid == logpair.second) {
                int next = uid == logpair.first? logpair.second: logpair.first;
                if(next == dest) {
                    delete [] v; // free visited state memory
                    return s.step+1;
                }
                // move to the next stump
                int ns = (s.status ^ (uid << totalslots)) | (next << totalslots);
                if(v[ns] == 0) {
                    v[ns] = 1;
                    Q.push(State(ns, s.log, s.step+1));
                }              

                if(s.log) continue;
                // pick up a log
                ns = s.status ^ (1<<i);
                if(v[ns] == 0) {
                    v[ns] = 1; 
                    // log width
                    int width = length(stumppos[logpair.first], stumppos[logpair.second]);
                    Q.push(State(ns, width, s.step+1));
                }
            }
        }

        map<ii,int>::iterator slot_it = slotlist.begin();
        map<ii,int>::iterator slot_end= slotlist.end();
        for(; slot_it!= slot_end; ++slot_it) {
            ii slot_pair = slot_it->first;
            int i = slot_pair.first;
            int j = slot_pair.second; 
            if(i != uid && j != uid) continue;
            
            if(length(stumppos[i],stumppos[j]) != s.log) continue;
            ii vv = i == uid ? stumppos[j] : stumppos[i];

            // first, check there is no log between them      
            if(s.status & (1<< slot_it->second)) continue;

            bool found = false;
            // second, check there are no other logs go through any points between them
            bool h1 = u.first == vv.first;
            for(int i = 0; i < totalslots; ++i) if(s.status & (1<<i)) {
                ii logpair = slotpos[i];
                ii pos1 = stumppos[logpair.first];
                ii pos2 = stumppos[logpair.second];

                bool  h2 = (pos1.first == pos2.first);
                if(h1 == h2) continue;
                if(h1 && pos1.first < u.first && pos2.first > u.first &&
                    u.second < pos1.second && vv.second > pos1.second) {
                    found = true;break;
                }
                if(h2 && pos1.second < u.second && pos2.second > u.second &&
                    u.first < pos1.first && vv.first > pos1.first) {
                        found = true; break;
                } 
            }
            if(found) continue;     
            int ns = s.status | (1<<slot_it->second);
            if(v[ns] == 0) {
                v[ns] = 1;
                Q.push(State(ns, 0, s.step+1));
            }           
        }        
    }
    delete []v;
    return 0;
}

// pre-calculate stump pairs, log positin, etc...
int get_adj(char m[15][15], map<int, ii> &stumppos, map<ii,int> &stumplist,
             map<int, ii> &slotpos, map<ii,int> &slotlist, int &slot_status,
             int& start, int& dest, int nrow, int ncol) {
    const short MAXDIR = 4;
    //   down, up, left, right
    const short dx[MAXDIR] = {1,-1,0, 0};
    const short dy[MAXDIR] = {0, 0,-1,1};
    const char  dl[MAXDIR] = {'|', '|', '-', '-'};

    for(int i = 0; i < nrow; ++i)
        for(int j = 0; j < ncol; ++j)
            if(m[i][j] == 'S' || m[i][j] == 'E' || m[i][j] == 'B') {
                if(m[i][j] == 'B') start = stumplist.size();
                if(m[i][j] == 'E') dest  = stumplist.size();
                stumplist.insert(make_pair(ii(i,j), stumplist.size()));
                stumppos.insert(make_pair(stumplist.size()-1, ii(i,j)));
            }
    // for each stump, scan for available slot to put down logs
    for(int j = 0; j < stumplist.size(); ++j){
        int x = stumppos[j].first;
        int y = stumppos[j].second;
        bool flag;
        for(int i = 0; i < MAXDIR; ++i) {
            int nx = x, ny = y;
            flag = false;
            do{
                nx = nx + dx[i];
                ny = ny + dy[i];
                if(nx<0 || nx >= nrow || ny < 0 || ny >= ncol) {
                    flag = true; break;
                }
                if(m[nx][ny] == 'S' || m[nx][ny] == 'E' || m[nx][ny] == 'B') break;
            } while(true);
            if(flag) continue;
            int logLen = max(abs(nx-x), abs(ny-y));
            if(logLen > 1 && (m[nx][ny] == 'S' || m[nx][ny] == 'E' || m[nx][ny] == 'B')) {
                int idnext = stumplist[ii(nx,ny)];
                ii logpos = j < idnext? ii(j, idnext) : ii(idnext, j);
                slotlist.insert(make_pair(logpos, slotlist.size()));
                slotpos.insert(make_pair(slotlist.size()-1, logpos));
            }
        }
    }
    int totalslots = slotlist.size();
    
    slot_status = 0;
    // scan for existing logs
    for(int j = 0; j < stumplist.size(); ++j){
        int x = stumppos[j].first;
        int y = stumppos[j].second;
        bool flag;
        for(int i = 0; i < MAXDIR; ++i) {
            int nx = x, ny = y;
            flag = false;
            do{
                nx = nx + dx[i];
                ny = ny + dy[i];
                if(nx<0 || nx >= nrow || ny < 0 || ny >= ncol) flag = true;
            } while(!flag && m[nx][ny] == dl[i]);

            if(flag) continue;
            int logLen = max(abs(nx-x), abs(ny-y));
            if(logLen > 1 && (m[nx][ny] == 'S' || m[nx][ny] == 'E' || m[nx][ny] == 'B')) {
                int idnext = stumplist[ii(nx,ny)];
                ii logpos = j < idnext? ii(j, idnext) : ii(idnext, j);
                slot_status |= (1<< slotlist[logpos]);
            }
        }
    }
    return totalslots;
}

int main() {
    int ndata;
    scanf("%d ", &ndata);
    char m[15][15]; // maze
    for(int data = 0; data < ndata; data++) {
        int nrow, ncol;
        scanf("%d %d ", &nrow, &ncol);
        for(int i = 0; i < nrow; ++i)
            scanf("%s ", &m[i]);
        map<ii, int> stumplist;
        map<int, ii> stumppos;
        map<ii,int> slotlist;
        map<int,ii> slotpos;
        
        int status, start, dest;
        int totalslots = get_adj(m, stumppos, stumplist, slotpos, slotlist, 
            status, start, dest, nrow, ncol);
        status |= (start<<totalslots);
        printf("%d\n", BFS(start, dest, stumppos, slotpos, slotlist, status));
    }
    return 0;
}

DFS

2008-09-25T21:41:00.001-07:00

Applications

Here are some algorithms where DFS is used:

Finding connected components.
Cycle detection.
Topological sorting.
Finding 2-(edge or vertex)-connected components.
Finding strongly connected components.
Solving puzzles with only one solution, such as mazes.

topcoder: DFS

Imagine we have an undirected graph. The simplest way to store a graph in STL is to use the lists of vertices adjacent to each vertex. This leads to the vector< vector<int> > W structure, where W[i] is a list of vertices adjacent to i. Let’s verify our graph is connected via DFS:

/*
Reminder from Part 1:
typedef vector<int> vi;
typedef vector<vi> vvi;

*/
 int N; // number of vertices 
 vvi W; // graph 
 vi V; // V is a visited flag 

 void dfs(int i) { 
       if(!V[i]) { 
            V[i] = true; 
            for_each(all(W[i]), dfs); 
       } 
 } 
 bool check_graph_connected_dfs() { 
       int start_vertex = 0; 
       V = vi(N, false); 
       dfs(start_vertex); 
       return (find(all(V), 0) == V.end()); 
 }

Problem: topcoder: CactusCount

用一个cycles[]存每个vertex所在的cycle的数目。用DFS进行cycle detection,每碰到一个cycle,将cycle 内所有元素 cycle[i]++。每一次DFS完毕，这一个connected component 内部如果至少有一个vertex的cycle[i] >= 2，则此component 不是cactus.

由于找到每个cycle后要回溯找cycle内所有元素，我们需要保存visit的路径。两种方法

每个元素保存一个parent, p[]可以查到每个元素的parent
用一个deque保存整条路径（编程略简单）

下面分别给出了两种实现：

typedef vector<int> vi;
vector<vi>  adj;   // adj list
int vv [201];      // visited vertex in DFS;
int p[201];        // parent of node i
int cycle[201];    // # of times in a cycle
int maxcycle;

void checkmax(int &a, int b) {
    if(b > a) a = b;
}
void DFS(int i, int n, int c = 0) {
    vv[i] = 0; // visiting
    //printf("visiting %d\n", i+1);

    // visit all neighbors of i
    for(int j = 0; j < adj[i].size(); ++j) {
        // get the j-th neighbor: k
        int k = adj[i][j];
        // new vertex, first visit
        if(vv[k] == -1) {
            // assign i as k's parent
            p[k] = i;
            // visit k
            DFS(k, n, c);
        }

        // detect a cycle : back edge vv[k] == 0 
        else if(vv[k] == 0 &&  k != p[i]) {
            // actually if maxcycle >=2 
            // we do not need to mark any more
            // just visit all and leave this component, right?

            //printf("cycle %d ", k+1);
            cycle[k] ++; checkmax(maxcycle, cycle[k]);

            //printf("%d ", i+1);
            cycle[i] ++; checkmax(maxcycle, cycle[i]);        
            int parent = p[i];
            do {
                //printf("%d ", parent+1);
                cycle[parent] ++; checkmax(maxcycle, cycle[parent]);
                parent = p[parent];                    
            } while(parent != k); 
            //printf("%d \n", k+1);
            continue;
        }
    }
    vv[i] = c;
    //printf("end visiting %d, max cycle %d\n", i+1, cycle[i]);
}

int CactusCount::countCacti(int n, vector <string> edges) {
    if(edges.empty()) return n;
    string edge;
    for(int i = 0; i < edges.size(); ++i)
        edge += edges[i];

    for(int i = 0; i < edge.size(); ++i)
        if(edge[i]==',') edge[i] = ' '; 
    
    adj.clear();
    adj.resize(n, vi());

    memset(vv,-1, sizeof(vv));
    memset(p, 0, sizeof(p));
    memset(cycle, 0, sizeof(cycle));

    stringstream ss(edge);
    int a, b;
    while(ss >> a >> b) {
        --a, --b;
        adj[b].push_back(a) ; adj[a].push_back(b);
    }
    int cnt = 0, c = 1;
    for(int i = 0; i < n; ++i) if(vv[i] == -1) {
        p[i] = -1;
        maxcycle = 0;
        DFS(i, n, c);
        //printf("component %d: %d, size %d\n", c, maxcycle, component[c].size());
        if(maxcycle <= 1) ++cnt;
        ++c;
    }
    return cnt;
}

// ----------------------------------------------------------
// use deque to save visiting path

vector<int> adj[200];  // adj list
int col[200];          // vertex color
int cycles[200];       // # of times in a cycle
bool iscacti;          // is the current component a cacti
deque<int> path;       // for backtrace
// visit vertex v whose parent is p
void dfs(int v, int p) {
    // visiting v
    col[v] = 1;
    path.push_front(v);
    for(int j = 0; j < adj[v].size(); ++j) {
        int k = adj[v][j];
        // unvisited
        if(col[k] == 0) dfs(k, v);
        // back edge detected
        else if(col[k] == 1 && k != p) {
            deque<int>::iterator root = ++find(ALL(path), k);
            for(deque<int>::iterator it = path.begin(); it!= root; ++it)
                if(++ cycles[*it] > 1) iscacti = false;
        }
    }
    path.pop_front();
    col[v] = 2;
}

int CactusCount::countCacti(int n, vector <string> edges) {
    REP(i, n) {
        adj[i].clear(); 
        col[i] = cycles[i] = 0;
    }
    stringstream ss;
    for(vector<string>::iterator it = edges.begin(); it != edges.end(); ++it)
        ss << *it;
    int a, b;
    while(ss >> a >> b) {
        ss.ignore(1); --a, --b;
        adj[b].push_back(a) ; adj[a].push_back(b);
    }
    int cnt = 0;
    memset(cycles, 0, sizeof(cycles));
    memset(col, 0, sizeof(col));
    REP(i,n) if(col[i] == 0) {
        iscacti = true;
        dfs(i, -1);
        if(iscacti) ++cnt;        
    }
    return cnt;
}

Example: DFS visiting log

-----------------------------------

visiting 1
visiting 2
visiting 3
visiting 4
visiting 5
cycle 3 5 4 3
end visiting 5, max cycle 1
end visiting 4, max cycle 1
cycle 1 3 2 1
end visiting 3, max cycle 2
end visiting 2, max cycle 1
end visiting 1, max cycle 1
------------------------------------
component 1: maxcycle 2
------------------------------------
visiting 6
visiting 7
visiting 8
cycle 6 8 7 6
visiting 9
visiting 10
visiting 11
cycle 9 11 10 9
end visiting 11, max cycle 1
end visiting 10, max cycle 1
end visiting 9, max cycle 1
end visiting 8, max cycle 1
end visiting 7, max cycle 1
end visiting 6, max cycle 1
------------------------------------
component 2: maxcycle 1
------------------------------------
visiting 12
visiting 13
end visiting 13, max cycle 0
end visiting 12, max cycle 0
------------------------------------
component 3: maxcycle 0
------------------------------------
visiting 14
visiting 15
visiting 16
visiting 17
cycle 14 17 16 15 14
end visiting 17, max cycle 1
cycle 14 16 15 14
end visiting 16, max cycle 2
end visiting 15, max cycle 2
end visiting 14, max cycle 2
------------------------------------
component 4: maxcycle 2
------------------------------------
Test Case #3...PASSED

Dijkstra: single source shortest path

2008-09-24T15:13:00.001-07:00

Wiki: Dijkstra algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge path costs, outputting a shortest path tree. This algorithm is often used in routing.

topCoder: Dijstra via priority_queue

Dijkstra
In the last part of this tutorial I’ll describe how to efficiently implement Dijktra’s algorithm in sparse graph using STL containers. Please look through this tutorial for information on Dijkstra’s algoritm. Consider we have a weighted directed graph that is stored as vector< vector< pair<int,int> > > G, where

G.size() is the number of vertices in our graph
G[i].size() is the number of vertices directly reachable from vertex with index i
G[i][j].first is the index of j-th vertex reachable from vertex i
G[i][j].second is the length of the edge heading from vertex i to vertex G[i][j].first

We assume this, as defined in the following two code snippets:

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)

      vi D(N, 987654321); 
      // distance from start vertex to each vertex

      priority_queue<ii,vector<ii>, greater<ii> > Q; 
      // priority_queue with reverse comparison operator, 
      // so top() will return the least distance
      // initialize the start vertex, suppose it¡¯s zero
      D[0] = 0;
      Q.push(ii(0,0));

      // iterate while queue is not empty
      while(!Q.empty()) {

            // fetch the nearest element
            ii top = Q.top();
            Q.pop();
                        
            // v is vertex index, d is the distance
            int v = top.second, d = top.first;

            // this check is very important
            // we analyze each vertex only once
            // the other occurrences of it on queue (added earlier) 
            // will have greater distance
            if(d <= D[v]) {
                  // iterate through all outcoming edges from v
                  tr(G[v], it) {
                        int v2 = it->first, cost = it->second;
                        if(D[v2] > D[v] + cost) {
                              // update distance if possible
                              D[v2] = D[v] + cost;
                              // add the vertex to queue
                              Q.push(ii(D[v2], v2));

                        }
                  }
            }
      }

Problems:

UVa 429 - Word Transformation

Flood Fill

2008-09-23T20:35:00.001-07:00

The idea is to find the node that has not been assigned to a component. Flood fill can be performed in two ways, both O(N+M):

depth-first: assign unvisited neighbors to the current component and recurses on them.
breadth-first: no recursion, all the unvisited neighbors are push onto a queue.

Problems:

UVa 352: The Seasonal War

int dx[] = {-1, 0, 0, 1, 1, -1, 1, -1};
int dy[] = {0 , -1,1, 0, 1, -1, -1, 1};

void visit(vector<vector<int> > &V, vector<string> &M, int i, int j) {
	int N = V.size();
	if(i < 0 || i >= N || j < 0 || j >= N) return ;

	// '0' pixel or  visited already
	if(M[i][j] == '0' || V[i][j] > 0) return ;
	
	V[i][j] = 1; 
	for(int k = 0; k < 8; ++k)
		visit(V, M, i+dx[k], j+dy[k]);
	return; 
}

int flood_fill(vector<string> &M) {
	int N = M.size();
	vector<vector<int> > V(N, vector<int>(N, -1));
	
	int ncomp = 0; // number of components
	for(int i = 0; i < N; ++i)
		for(int j = 0; j < N; ++j) {
			// the pixel contains "1" and it has not been visited
			if(M[i][j] == '1' && V[i][j] == -1) {
				ncomp ++;
				for(int k = 0; k < 8; ++k)
					visit(V, M, i+dx[k], j+dy[k]);
			}
		}
    return ncomp;
}

UVa 572: Oil Deposits

topCoder: HoleCakeCuts

Editorial:

Approach 1

Flood-filling by Depth-first search (DFS) or Breadth-first search (BFS) is used to count the number of pieces. The cake can be divided into many unit squares (each has a side length of 1), and a piece is a maximal connected group of unit squares which has the property that no common border (if existing) between any two squares in the group lies on a cut. So from a unit square of some piece we can visit all other unit squares belonging to that piece by limiting DFS or BFS not to cross any cut while travelling between squares. See Petr's solution for a clean implementation of this approach.
Approach 3

Another approach which has a smaller time complexity is to reduce the original problem to a problem with a cake and no hole. This can be done by finding two horizontal cuts:

the horizontal cut which is inside the hole and closest to the top side of the hole. It can be the cut going through the top side of the hole.

the horizontal cut which is inside the hole and closest to the bottom side of the hole. It can be the cut going through the bottom side of the hole.
These two cuts (which may be the same cut) together with the vertical sides of the hole divide the outer square of the cake into four rectangles each of which can be considered as a cake with no hole. The fifth rectangle in the center always contains no pieces. The four rectangles are colored differently in the following illustration:
If the two horizontal cuts of interest cannot be found, we can search for two vertical cuts with similar properties. And if, again, we cannot find the cuts, we can safely remove the hole from the original cake to obtain a reduced problem.
Solving a reduced problem is trivial. We just count the numbers of horizontal and vertical cuts which completely cut through the cake (not going through any border of the cake), add one to each number, and then multiply them together to get the number of pieces.

C++ Effective notes

2008-09-22T18:17:00.001-07:00

Intro

object的定义式是编译器为它配置内存的起点。

如果你想要产生一个对象数组，但该对象型别没有提供default constructor, 通常的做法是定义一个指针数组取而代之，然后利用new一一将每个指针初始化。

//class Automobile
class Autos { 
public: 
  int cost; 
  int features; 
  int fixTimes; 
  Autos(int c, int f, int fix): cost(c), features(f), fixTimes(fix){} 
  // ...
}; 

Autos *ptrArray[10]; 
ptrArray[0] = new Autos(10000,3,2); 
ptrArray[1] = new Autos(50000,2,10); 
//...

copy constructor: 以某对象作为另一个同型对象的初值

                                   string s1; // default constructor 
string s2(s1); // copy constructor 
string s2 = s1; // copy constructor

pass-by-value 是calling copy constructor的同义词
纯粹从操作的观点来看，initialization & assignment之间的差异在于前者由constructor执行，后者由operator=执行。两个动作对应不同的函数动作。C++严格区分两者，是因为上述两个函数考虑的事情不同。constructor通常必须检验其引数的validity, 大部分assignment运算符不必如此。assignment运算符认定其参数是合法的，它会检测诸如“自己赋值给自己”这样的病态情况，以及配置新内存之前先释放旧有内存。

Item 1: Prefer const and inline to #define.

Item 2: Prefer <iostream> to <stdio.h>

Item 3: Prefer new and delete to malloc and free.

Item 4: Prefer C++-style comments.

Item 5: Use the same form in corresponding uses of new and delete.

Item 6: Use delete on pointer members in destructors.

adding a pointer member almost always requires each of the following:

Initialization of the pointer in each of the constructors. If no memory is to be allocated to the pointer in a particular constructor, the pointer should be initialized to 0 (i.e., the null pointer).
Deletion of the existing memory and assignment of new memory in the assignment operator. (See also Item 17.)
Deletion of the pointer in the destructor.

Item 7: Be prepared for out-of-memory conditions.

The base class part of the design lets derived classes inherit the set_new_handler
and operator new functions they all need, while the template part of the design ensures that each inheriting class gets a different currentHandler data member.

template<class T>// "mixin-style" base class
class NewHandlerSupport {// for class-specific
public:// set_new_handler support 
  static new_handler set_new_handler(new_handler p); 
  static void * operator new(size_t size);
private: 
  static new_handler currentHandler;};
  
  template<class T>
  new_handler NewHandlerSupport<T>::set_new_handler(new_handler p)
  { 
    new_handler oldHandler = currentHandler; currentHandler = p; 
    return oldHandler;
  }

  template<class T>

void * NewHandlerSupport<T>::operator new(size_t size)
{ 
  new_handler globalHandler = 
    std::set_new_handler(currentHandler); 
  void *memory;  
  try {   
    memory = ::operator new(size); 
  } 
  catch (std::bad_alloc&) {   
    std::set_new_handler(globalHandler);   
    throw; 
  } 
  std::set_new_handler(globalHandler); 
  return memory;

}
  
// this sets each currentHandler to 0template<class T>
new_handler NewHandlerSupport<T>::currentHandler;

Item 8: Adhere to convention when writing operator new and operator delete.

pseudocode for a non-member operator new looks like this:
void * operator new(size_t size) // your operator new might
{ // take additional params 
  if (size == 0) { // handle 0-byte requests   
    size = 1; // by treating them as 
  } // 1-byte requests 
  while (1) {   
    attempt to allocate size   bytes;   
    if (the allocation was successful)     
      return (a pointer to the memory);   
    // allocation was unsuccessful; find out what the   
    // current error-handling function is (see Item 7)    
    new_handler globalHandler = set_new_handler(0);   
    set_new_handler(globalHandler);   
    if (globalHandler) (*globalHandler)();   
    else throw std::bad_alloc(); 
  }
}
Item 7 remarks that operator new contains an infinite loop, and the code above shows that loop explicitly. while (1) is about as infinite as it gets. The only way out of the loop is for memory to be successfully allocated or for the new-handling function to do one of the things described in Item 7:

make more memory available,
install a different new-handler,
deinstall the new-handler,
throw an exception of or derived from std::bad_alloc,
or fail to return.

It should now be clear why the new-handler must do one of those things. If it doesn't, the loop inside operator new will never terminate.
pseudocode for a non-member operator delete:
void operator delete(void *rawMemory)
{ 
  if (rawMemory == 0) return; // do nothing if the null 
  // pointer is being deleted 
  deallocate the memory pointed to by rawMemory; 
  return;
}

Item 9: Avoid hiding the "normal" form of new.

Item 10: Write operator delete if you write operator new.

Item 11: Declare a copy constructor and an assignment operator for classes with dynamically allocated memory.

if a class has dynamically allocated memory, but it has no copy consturctor and no assignment operator.

b = a;

after the assignment operation, the memory that contains "World\0" is lost!

the internal pointers in a and b both point to "Hello\0". If a's destructor is called, memory "Hello" is deleted, while b's pointer is still pointing to that memory!

Write your own versions of the copy constructor and the assignment operator if you have any pointers in your class. Inside those functions, you can either copy the
pointed-to data structures so that every object has its own copy, or you can implement some kind of reference-counting scheme (see Item M29) to keep track of how many objects are currently pointing to a particular data structure.

Item 12: Prefer initialization to assignment in constructors.

There are times when the initialization list must be used. In particular, const and reference members may only be initialized, never assigned.

template<class T>
class NamedPtr {
public:
  NamedPtr(const string& initName, T *initPtr);
  //...
private:
  const string name;
  T * const ptr;
};

This class definition requires that you use a member initialization list, because const members may only be initialized, never assigned. So,

template<class T>
NamedPtr<T>::NamedPtr(const string& initName, T *initPtr )
: name(initName), ptr(initPtr)
{}

instead of

template<class T>
NamedPtr<T>::NamedPtr(const string& initName, T *initPtr)
{
  name = initName;
  ptr = initPtr;
}

Note that static class members should never be initialized in a class's constructor. Static members are initialized
only once per program run, so it makes no sense to try to "initialize" them each time an object of the class's type
is created.

Item 13: List members in an initialization list in the order in which they are declared.

Item 14: Make sure base classes have virtual destructors.

When you try to delete a derived class object through a base class pointer and the base class has a nonvirtual destructor, the results are
undefined.

Item 15: Have operator= return a reference to *this.

Item 16: Assign to all data members in operator=.

Item 17: Check for assignment to self in operator=.

A more important reason for checking for assignment to self is to ensure correctness. Remember that an
assignment operator must typically free the resources allocated to an object (i.e., get rid of its old value) before it can allocate the new resources corresponding to its new value. When assigning to self, this freeing of resources can be disastrous, because the old resources might be needed during the process of allocating the new ones.

Item 18: Strive for class interfaces that are complete and minimal.

// return element for read/write
T& operator[](int index);
// return element for read-only
const T& operator[](int index) const;

By declaring the same function twice, once const and once non-const, you provide support for both const and non-const Array objects.

Item 19: Differentiate among member functions, non-member functions, and friend functions.

class Rational {
public:
  Rational(int numerator = 0, int denominator = 1);
  int numerator() const;
  int denominator() const;
  const Rational operator*(const Rational& rhs) const;
private:
  //...
};

Rational oneEighth(1, 8);
Rational oneHalf(1, 2);
Rational result = oneHalf * oneEighth; // fine
result = result * oneEighth; // fine
result = oneHalf * 2; // fine
result = 2 * oneHalf; // error!

隐式转换可以在 non-explicite constructor 的 parameter listed in the function declaration

// declare this globally or within a namespace; see
// Item M20 for why it's written as it is
const Rational operator*(const Rational& lhs,
const Rational& rhs)
{
return Rational(lhs.numerator() * rhs.numerator(),
lhs.denominator() * rhs.denominator());
}

Rational oneFourth(1, 4);
Rational result;
result = oneFourth * 2; // fine
result = 2 * oneFourth; // hooray, it works!

Lessons: (assume f is the function you're trying to declare properly and C is the class to which it is conceptually related )

Virtual functions must be members. If f needs to be virtual, make it a member function of C.

operator>> and operator<< are never members. If f is operator>> or operator<<, make f a non-member function. If, in addition, f needs access to non-public members of C, make f a friend of C.

Only non-member functions get type conversions on their left-most argument. If f needs type
conversions on its left-most argument, make f a non-member function. If, in addition, f needs access to
non-public members of C, make f a friend of C.

Everything else should be a member function. If none of the other cases apply, make f a member
function of C.

Item 20: Avoid data members in the public interface.

Item 21: Use const whenever possible.

char *p = "Hello"; // non-const pointer, non-const data
const char *p = "Hello"; // non-const pointer, const data
char * const p = "Hello"; // const pointer, non-const data
const char * const p = "Hello"; // const pointer, const data

Basically, you mentally draw a vertical line through the asterisk of a pointer declaration, and if the word const appears to the left of the line, what's pointed to is constant; if the word const appears to the right of the line, the pointer itself is constant; if const appears on both sides of the line, both are constant.

Some of the most powerful uses of const stem from its application to function declarations. Within a function declaration, const can refer to the function's return value, to individual parameters, and, for member functions, to the function as a whole.

Item 22: Prefer pass-by-reference to pass-by-value.

Item 23: Don't try to return a reference when you must return an object.

when deciding between returning a reference and returning an object, your job is to make the choice that does the right thing. Let your compiler vendors wrestle with figuring out how to make that
choice as inexpensive as possible.

Item 24: Choose carefully between function overloading and parameter defaulting.

The confusion over function overloading and parameter defaulting stems from the fact that they both allow a single function name to be called in more than one way.

void f(); // f is overloaded
void f(int x);
f(); // calls f()
f(10); // calls f(int)

void g(int x = 0); // g has a default parameter value
g(); // calls g(0)
g(10); // calls g(10)

The answer depends on two other questions. First, is there a value you can use for a default? Second, how many algorithms do you want to use? In general, if you can choose a reasonable default value and you want to employ only a single algorithm, you'll use default parameters (see also Item 38). Otherwise you'll use function overloading.

// A class for representing natural numbers
class Natural {
public:
  Natural(int initValue);
  Natural(const Natural& rhs);
private:
  unsigned int value;
  void init(int initValue);
  void error(const string& msg);
};
inline
void Natural::init(int initValue) { 
  value = initValue; 
}
Natural::Natural(int initValue) {
  if (initValue > 0) init(initValue);
  else error("Illegal initial value");
}
inline Natural::Natural(const Natural& x) { 
  init(x.value); 
}

The constructor taking an int has to perform error checking, but the copy constructor doesn't, so two different functions are needed. That means overloading. However, note that both functions must assign an initial value for the new object. This could lead to code duplication in the two constructors, so you maneuver around that problem by writing a private member function init that contains the code common to the two constructors. This tactic using overloaded functions that call a common underlying function for some of their work is worth remembering, because it's frequently useful (see e.g., Item 12).

Item 25: Avoid overloading on a pointer and a numerical type.

Item 26: Guard against potential ambiguity.

Item 27: Explicitly disallow use of implicitly generated member functions you don't want.

Item 28: Partition the global namespace.

Item 29: Avoid returning "handles" to internal data.

class String {
public:
  String(const char *value); // see Item 11 for pos-
  ~String(); // sible implementations;
  // see Item M5 for comments on the first constructor
  operator char *() const; // convert String -> char*;
  // see also Item M5
  //...
private:
  char *data;
};
const String B("Hello World"); // B is a const object
char * str = B;
strcpy(str, "Hi Mom");

The flaw in this function is that it's returning a "handle" ? in this case, a pointer ? to information that should be hidden inside the String object on which the function is invoked. That handle gives callers unrestricted access to what the private field data points to.

Item 30: Avoid member functions that return non-const pointers or references to members less accessible than themselves.

Item 31: Never return a reference to a local object or to a dereferenced pointer initialized by new within the function.

In spite of the foregoing discussion, you may someday be faced with a situation in which, pressed to achieve performance constraints, you honestly need to write a member function that returns a reference or a pointer to a less-accessible member. At the same time, however, you won't want to sacrifice the access restrictions that private and protected afford you. In those cases, you can almost always achieve both goals by returning a pointer or a reference to a const object.

Item 32: Postpone variable definitions as long as possible.

Not only should you postpone a variable's definition until right before you have to use the variable, you should try to postpone the definition until you have initialization arguments for it. By doing so, you avoid not only constructing and destructing unneeded objects, you also avoid pointless default constructions. Further, you help document the purpose of variables by initializing them in contexts in which their meaning is clear.

Item 33: Use inlining judiciously.

Item 34: Minimize compilation dependencies between files.

Item 35: Make sure public inheritance models "isa."

Item 36: Differentiate between inheritance of interface and inheritance of implementation.

Item 37: Never redefine an inherited nonvirtual function.

Item 38: Never redefine an inherited default parameter value.

Item 39: Avoid casts down the inheritance hierarchy.

Item 40: Model "has-a" or "is-implemented-in-terms-of" through layering.

Item 41: Differentiate between inheritance and templates.

Item 42: Use private inheritance judiciously.

Item 43: Use multiple inheritance judiciously.

Item 44: Say what you mean; understand what you're saying.

Item 45: Know what functions C++ silently writes and calls.

Item 46: Prefer compile-time and link-time errors to runtime errors.

Item 47: Ensure that non-local static objects are initialized before they're used.

Item 48: Pay attention to compiler warnings.

Item 49: Familiarize yourself with the standard library.

Item 50: Improve your understanding of C++.

Number Split

2008-09-21T22:24:00.001-07:00

topCoder: NumberSplit

By Editorial:

The first thing to notice here is that the numbers in every step become smaller. Let's take an example and say we have a five digit number of the form abcde (a, b, c, d and e represent the decimal digits of the number), which we split to produce the successor: ab * c * de. Here it is always c < 10 and de < 100, so for the successor we have: ab * c * de < ab * 10 * 100 = ab000 ≤ abcde. Similar with any other numbers and splittings.

Now we need a way to compute all possible successors, given a given number. For this we can use the following recursive pseudo-code:

generateSuccessors(int multiplier, int n) {
    add (multiplier * n) to the set of successors
    for (i = 10; i <= n; i *= 10) {
       generateSuccessors(multiplier * (n / i), n % i);
    }
}

We initialize the set of successors to an empty set, and call generateSuccessors(1, n) (where n is the number, for which we want to find the successors). Finally, we remove n from the generated set (since this is not a successor of n itself, we need to split the given number to at least two parts for a successor to be valid).

To compute the longest possible sequence, starting with the given start, generate all successors of start as described above, and for each n in the successor set compute recursively longestSequence(n). The return value is the maximum of all computed values + 1 (if start is a single digit number, the successors set will be empty, and we return 1). Note that this would not work if loops in the sequence were possible, but since each successor is smaller then the original number, this can not happen. In order to avoid a timeout, we need to memorize in a buffer all values already computed.

Alternatively, we can use dynamic programming, by initializing longest[i] = 1 for all single digit numbers i, and computing longest[i] from i = 10 up to i = start by adding 1 to the maximum of longest[j] for all j in the successor set of i. This works, since all successors of i are smaller than i. With this solution, we compute the longest sequence for more numbers than actually needed (many numbers between 1 and start can not be reached from start) but with the low constraints this solution was within the time limit.

my dp code with memoization (note: topCoder does not have itoa)

void itoa(int n, char* buff) {
    sprintf(buff, "%d", n);
}
// memoization array
int a[999999];
int solve(string s) {
    int ss = atoi(s.c_str());
    if(a[ss] != -1) return a[ss];
    char buff[10];
    if(s.length() == 1) return 1;
    int res = 0;
    for(int i = 1; i < s.length(); ++i) {
        // single split
        int left  = atoi(s.substr(0,i).c_str());
        int right = atoi(s.substr(i).c_str());
        itoa(left*right, buff);       
        checkmax(res, 1+solve(string(buff)));
        string rights = s.substr(i);
        if(rights.length() <= 1) continue;

        // this part does double split
        for(int j = 1; j < rights.length(); ++j) {
            int lleft  = atoi(rights.substr(0,j).c_str());
            int lright = atoi(rights.substr(j).c_str());
            itoa(left * lleft * lright, buff);
            checkmax(res, 1+solve(string(buff)));
        }           
    }
    return a[ss] = res;
}

int NumberSplit::longestSequence(int start) {
    char buff[10];
    itoa(start,buff);
    memset(a, -1, sizeof(a));
    string s(buff);
    return solve(buff);
}

Floyd-Warshall: All-Pairs Shortest Path

2008-09-21T20:44:00.001-07:00

By wiki, Floyd-Warshall is a graph analysis algorithm for finding shortest paths in a weighted, directed graph. A single execution of the algorithm will find the shortest paths between all pairs of vertices. The Floyd–Warshall algorithm is an example of dynamic programming.

 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
2    (infinity if there is none).
3    Also assume that n is the number of vertices and edgeCost(i,i)=0
4 */
5
6 int path[][];
7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
8    from i to j using intermediate values in (1..k-1).  Each path[i][j] is initialized to
9    edgeCost(i,j).
10 */
11
12 procedure FloydWarshall ()
13    for k: = 0 to n − 1
14       for each (i,j) in (0..n − 1)
15          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

For numerically meaningful output, Floyd-Warshall assumes that there are no negative cycles (in fact, between any pair of vertices which form part of a negative cycle, the shortest path is not well-defined because the path can be infinitely small). Nevertheless, if there are negative cycles, Floyd–Warshall can be used to detect them. A negative cycle can be detected if the path matrix contains a negative number along the diagonal. If path[i][i] is negative for some vertex i, then this vertex belongs to at least one negative cycle.

Applications:

Shortest paths in directed graphs (Floyd's algorithm).

Transitive closure of directed graphs (Warshall's algorithm). In Warshall's original formulation of the algorithm, the graph is unweighted and represented by a Boolean adjacency matrix. Then the addition operation is replaced by logical conjunction (AND) and the minimum operation by logical disjunction (OR).

Optimal routing. In this application one is interested in finding the path with the maximum flow between two vertices. This means that, rather than taking minima as in the pseudocode above, one instead takes maxima. The edge weights represent fixed constraints on flow. Path weights represent bottlenecks; so the addition operation above is replaced by the minimum operation.

Testing whether an undirected graph is bipartite

Minmax / Maxmin Distance

Shortest Path Problems:

int Floyd_Warshall (int n) {
for(int k = 0; k < n; ++k)
 for(int i = 0; i < n; ++i)
   for(int j = 0; j < n; ++ j)
     G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}

topCoder: MoneyExchange
UVa 104: Arbitrage
UVa 436: Arbitrage (II)
UVa 423: MPI Maelstrom
UVa 567: Risk

Transitive Closure/Hull

for(int k = 0; k < N; ++k)
for(int i = 0; i < N; ++i)
 for(int j = 0; j < N; ++j)
   G[i][j] = G[i][j] || (G[i][k] && G[k][j]);

UVa 334: Identifying concurrent events

Minmax/ Maxmin distance

void minmax(int n) {

for(int k = 0; k < n; ++k)
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
G[i][j] = min(G[i][j], max(G[i][k], G[k][j]));
}

void maxmin(int n) {
for(int k = 0; k < n; ++k)
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) 
G[i][j] = max(G[i][j], min(G[i][k], G[k][j]));
}

UVa 534: Frogger
UVa 10048: Audiophobia
UVa 544: Heavy Cargo
UVa 10099: The Tourist Guide

Subset Sum Problem

2008-09-21T13:10:00.001-07:00

The problem is this: given a set of integers, does the sum of some non-empty subset equal exactly zero?The problem is NP-Complete. wiki

An equivalent problem is this: given a set of integers and an integer s, does any non-empty subset sum to s? Subset sum can also be thought of as a special case of the knapsack problem. One interesting special case of subset sum is the partition problem, in which s is half of the sum of all elements in the set.

topCoder: PayBill Editorial

There are two basic approaches to this problem. The first, which inevitably fails due to timeout on larger test cases, is to try obtain the sum by either including or excluding the first element, and then calling itself recursively with the remainder of the set. Unfortunately, with the maximum 50 people, this is over 1 quadrillion operations to perform.

Instead, a more clever, dynamic programming approach needs to be used. Since each item can only be up to 10,000, we know that the sum cannot be more than 500,000. So, we simply need a boolean array of 500,000 elements, where the i-th element represents whether or not we can reach the total i with some subset of the original values. In code it looks something like this:
boolean[] canTotal = new boolean[500001];
canTotal[0] = true;
for (int i = 0; i < meals.length; i++)
  for (int j = totalMoney; j >= meals[i]; j--)
     if (canTotal[j - meals[i]]) canTotal[j] = true;

topCoder: LoadBalancing Editorial

int minTime(vector<int> chunkSizes)
{
   vector<int> dp(204801, 0);
   dp[0] = 1;
   int total = 0;
   for (int i=0; i<(int)chunkSizes.size(); i++)
   {
       total += chunkSizes[i]/1024;
       for (int j=204800; j>=0; j--)
           if (dp[j] == 1)
               dp[j+chunkSizes[i]/1024] = 1;
   }
   for (int i=(total+1)/2; true; i++)
       if (dp[i] == 1)
           return 1024 * i;
}

UVa 562: Dividing Coins

跟上面一题如出一辙，就是平分问题。这里用了bitvector

const int MAX = 50000;
const unsigned int N = 1563;
unsigned int a[N+1];

int coin[101];
int main() {
    int ndata;
    scanf("%d ", &ndata);
    while(ndata--) {
        int n; 
        scanf("%d ", &n);

        for(int i = 0; i < n; ++i) {
            scanf("%d ", &coin[i]);
        }

        int total = std::accumulate(coin, coin+n, 0);

        memset(a, 0, sizeof(int)*(total>>SHIFT));
        SET(a, 0);
        for(int i = 0; i < n; ++i) {
            for(int j = total; j >= 0; --j)
                if(TEST(a, j))
                    SET(a, j+coin[i]);
        }

        for(int i = (total+1)/2; true; ++i) {
            if(TEST(a, i)) {
                printf("%d\n", abs(2*i-total));
                break;
            }
        }
    }

UVa 11517 Exact Change

这道要多记一个coin的数目，不能用bitvector了

        a[0] = 1;
        for(int i = 0; i < n; ++i) {
            for(int j = max-1; j >= 0; --j)
                if(a[j]) {
                    int t = j+ bill[i];
                    if(t > max) continue;
                    if(a[t] != 0)
                        a[t] = a[t] < a[j]+1 ? a[t]: a[j]+1;
                    else 
                        a[t] = a[j]+1;
                }
        }
        for(int i = price; i <= MAX; ++i) {
            if(a[i]) {
                printf("%d %d\n", i, a[i]-1);
                break;
            }
        }

memo[i][j] = min ( memo[i][k] + memo[k+1][j] )

2008-09-20T21:35:00.000-07:00

用类似这一recurrence的题非常多，在这汇总一下

topCoder: QuickSums
topCoder: ShortPalindromes
topCoder: TreePlanting
topCoder: SentenceDecomposition

topCoder: QuickSums

INPUT: i, j, sum
for all  i <= k <= j   take out substring(i,k) from sum   try d[k+1][j] = solve(substring(k+1,j), sum - substring(i,k)); end for d[i][j] = min (1+d[k+1][j])         k=i...j

边缘情况注意一下，如果d[i][j]整体已经等于sum，直接返回，不用1+res

#define INF 999999999
int memo[12][12][102];
void checkmin(int &a, int b) {
  if(b < a) a = b;
}
int solve(string numbers, int i, int j, int s) {
  if(memo[i][j][s] >= 0) return memo[i][j][s];
  if(i == j) {
      if (numbers[i]-'0' == s) return memo[i][j][s] = 0;
      else return memo[i][j][s] = INF;
  }
  // the whole word match! 
  if(atoi(numbers.substr(i, j-i+1).c_str()) == s) return memo[i][j][s] = 0;
  int res = INF;
  for(int k = i; k < j; ++k) {
      int left  = atoi(numbers.substr(i,k-i+1).c_str());
      if(left <= s){
           //cout << numbers.substr(k+1, j-k+1) << "->" << s-left << endl;
           int sol = 1+solve(numbers, k+1, j, s-left);
           //cout << numbers.substr(k+1, j-k+1) << " (" << sol <<")" << endl;
           checkmin(res, sol);
      }
  }
  return memo[i][j][s] = res;
}

int QuickSums::minSums(string numbers, int sum) {
  memset(memo, -1, sizeof(memo));
  int res = solve(numbers, 0, numbers.length()-1, sum);
  if(res == INF) return -1;
  return res;
}

topCoder: ShortPalindromes

“ shortest(base)
   if base is already a palindrome then
       return base
   if base has the form A...A then
       return A + shortest(...) + A
   if base has the form A...B then
       return min(A + shortest(...B) + A,
                  B + shortest(A...) + B)

”

string memo[26][26];
string solve(string base, int i, int j) {
  //cout << base.substr(i,j-i+1) << endl;
  if(i>j) return string("");
  if(i == j) return memo[i][j]=base[i];
  if(memo[i][j] != "") return memo[i][j];

  string res;
  if(base[i] == base[j]) {
      res = base[i] + solve(base, i+1, j-1)+base[i];
      return memo[i][j]=res;
  }

  string pre = base[j] + solve(base, i, j-1) + base[j];
  string suf = base[i] + solve(base, i+1, j) + base[i];

  if(pre.length() != suf.length()) {
      if(pre.length() < suf.length()) res = pre;
      else res = suf;
  }
  else {
      if(pre < suf) res = pre;
      else res = suf;
  }
  return memo[i][j]=res;
}

string ShortPalindromes::shortest(string base) {

  int L = base.length();
  for(int i = 0; i < L; ++i)
      for(int j = 0; j < L; ++j)
          memo[i][j]="";
  return solve(base, 0, base.length()-1);
}

topCoder: TreePlanting

long long memo[62][62][62];
int N;
long long solve(long long status, int i, int j, int f) {

  if(memo[i][j][f] != -1LL) return memo[i][j][f];

  if(f == 0 || (i == j && f == 1)) return memo[i][j][f] = 1LL;
  if(i > j) return memo[i][j][f] = 0LL;
  if(i == j && f > 1) return memo[i][j][f] = 0LL;

  long long res = 0;
  for(int k = i; k <= j; ++k) if(status & 1LL<<k) {

      res += solve(status ^ (1LL<<k), k+2, j, f-1);
  }
  return memo[i][j][f] = res;
}

long long TreePlanting::countArrangements(int total, int fancy) {
  memset(memo, -1, sizeof(memo));
  N = total;
  long long status = (1LL<<total)-1;
  return solve(status, 0, total-1, fancy);
}

Editorial solution:

Here, we need to get a little creative to come up with a workable solution. Consider placing f fancy trees along a total of n locations, so that no two are adjacent. Call our function, C, the number of ways to do this. At our first location, we can either plant a fancy tree, or not plant a fancy tree. If we plant a fancy tree, then we can't plant a fancy tree in the second spot, and hence will have n-2 locations in which to plant the remaining f-1 fancy trees. If we don't plant a fancy tree in the first spot, then we have n-1 locations in which to place all f fancy trees. This gives us our recursive formula, C(n, f) = C(n - 2, f - 1) + C(n - 1, f). Our starting values are of course, C(1, 1) = 1, and C(0, 0) = 1.

However, with the problem constraints as they are, a simple recursive function by itself is not sufficient. We either need to implement memoization, whereby we store the values of previous recursive calls, to avoid recalculating them repeatedly, or we can use dynamic programming, as shown here:

public long countArrangements(int total, int fancy) {
  long[][] count = new long[total + 1][fancy + 1];
  count[0][0] = 1;
  count[1][1] = 1;
  for (int i = 0; i < = total; i++)
     for (int j = 0; j < = fancy; j++) {
        if (i > 0)
           count[i][j] += count[i - 1][j];
        if (i > 1 && j > 0)
           count[i][j] += count[i - 2][j - 1];
     };
  return count[total][fancy];
}

topCoder: SentenceDecomposition

int diff(string& a, string& b) {
    int cost = 0;
    for(int i = 0;i < a.length(); ++i)
        if(a[i]!=b[i]) cost ++;
    return cost;
}
bool match(string& aa, string &bb) {
    sort(ALL(aa));
    return aa==bb;
}
int memo[52];

//dict is a copy of validWords
//sort_dict is a copy of dict, but each row is sorted
vector<string> dict, sort_dict;
#define INF 999999999
int solve(int i, string &s) {
    //cout << s.substr(i) << endl;
    if(memo[i] != -1) return memo[i];

    if(i == s.length()) return memo[i] = 0;
    if(i > s.length()) return memo[i]=INF;
        
    bool found  = false;
    int mincost = INF;
    for(int k = 0; k < dict.size(); ++k) {
        int len = dict[k].length();
        if(!match(s.substr(i, len), sort_dict[k])) continue;
        int ret = 0;
        ret = solve(i+len, s); 
        if(ret == INF) continue;
        else {
            found = true;
            ret += diff(s.substr(i, len), dict[k]);
        }
        mincost = min(mincost, ret);
    }
    
    if(found) return memo[i] = mincost;
    return memo[i] = INF;
}

int SentenceDecomposition::decompose(string sentence, vector <string> validWords) {
    sort_dict = dict = validWords;
    for(int i = 0; i < sort_dict.size(); ++i)
        sort(ALL(sort_dict[i]));
    
    memset(memo, -1, sizeof(memo));
    
    int res = solve(0, sentence);    
    if(res == INF) return -1;
    return res;
}

Longest Increasing/Decreasing Subsequence

2008-09-19T17:54:00.000-07:00

A lot of related problems:

topCoder: thePriceIsRight
topCoder: autoMarket
topCoder: books
UVa 111: history grading
UVa 231: testing the catcher
UVa 497: strategic Defense Initiative
UVa 10051: Tower of Cubes
UVa 10131: Is Bigger Smarter
Hoj: online tutorial problem 117, Intercept Missiles

two basic dp algorithms

e.g.,

sequence: 1,6,2,3,5,4,7
algorithm 1: O(N^2)
a    1  2  3  4  5  6  7
---------------------------
 1  6  2  3  5  4  7
---------------------------
0|  1  1  1  1  1  1  1
1| (1) 2  2  2  2  2  2
2|  1 (2) 2  2  2  2  2
3|  1  2 (2) 3  3  3  3
4|  1  2  2 (3) 4  4  4 
5|  1  2  2  3 (4) 4  5
6|  1  2  2  3  4 (4) 5 <-            

algorithm 2: O(NlogN)
a    1  2  3  4  5  6  7
---------------------------
 1  6  2  3  5  4  7
---------------------------
0|  1
1|  1  6
2|  1  2
3|  1  2  3
4|  1  2  3  5
5|  1  2  3  4
6|  1  2  3  4  7 <-

topCoder: thePriceIsRight

// longest increasing sequence (O(N^2)) 
vector<int> lis (vector<int> prices) {
 vector<int> len(prices.size(), 1); //length of the longest inc sequence up to i 
 vector<int> ways(prices.size(), 1); //how many ways of the lcs up to i 

 for(int i = 0; i < prices.size()-1; ++i) {
     for(int j = i+1; j < prices.size(); ++j)
         if(prices[j] > prices[i]) {
             if(len[j] < len[i] + 1) {
                 len[j] = len[i] + 1;
                 ways[j] = ways[i];
             }
             else if(len[j] == len[i]+1)
                 ways[j]+= ways[i];
         }
 }
 int maxv = *max_element(len.begin(), len.end());
 int nways = 0;
 for(int i = 0; i < len.size(); ++i)
     if(len[i] == maxv) nways += ways[i];
 vector<int> res;
 res.push_back(maxv), res.push_back(nways);
 return res;
}

topCoder: Books

// binary search 
template<typename T1, typename T2> int bsearch(T1 &A, T2 target) {
    int u = 0; 
    int v = A.size()-1;
    while(u < v) {
        int c = (u + v) / 2;
        if (target > A[c]) u=c+1; 
        else v=c;
    }
    return u;
}

// longest non-decreasing sequence 
template<typename T> int lis (vector<T> &seq) {
    if(seq.empty()) return 0;
    vector<T> A;
    int n = seq.size();
    A.push_back(seq[0]);

    int u, v;
    for(int i = 1; i < n; ++i) {
        if(seq[i] >= A.back()) {
            A.push_back(seq[i]);
            continue;
        }
        int u = bsearch(A, seq[i]);
        //important !!! when compute non-increasing or non-decreasing seq
        if(A[u] == seq[i]) A[u+1] = seq[i];
        else A[u] = seq[i];
    }
    return A.size();
}

int Books::sortMoves(vector <string> titles) {
    return books.size()-lis(titles);
}

WordParts

2008-09-19T17:32:00.000-07:00

TopCoder: WordParts –> Editorial

prefix, suffix
memoization

d[i][j] = min(d[i][k] + d[k+1][j])
          k --- substring(i,k) exists in the prefix/suffix array

set<string> dict;
#define INF 999999999
int memo[51];

void checkmin(int &a, int b) {
   if (b < a) a = b;
}
int solve(string &compound, int cpos) {
   //cout << compound.substr(cpos) << " " << cpos << endl;
   if(memo[cpos] >= 0) return memo[cpos];
   if(cpos == compound.length()) return memo[cpos] = 0;

   int res = INF;
   int maxlen = compound.length() - cpos;

   for(int i = 1; i <= maxlen; ++i) {
       string s = compound.substr(cpos, i);      
       if(dict.count(s)) {
           checkmin(res, 1+solve(compound, cpos+i));
       }
   }
   return memo[cpos] = res;
}  

int WordParts::partCount(string original, string compound) {
   dict.clear(); // don’t forget to reset dict
   // add the whole word
   dict.insert(original);
   // add all prefix
   for(int i = 1; i <= original.length()-1; ++i)
       dict.insert(original.substr(0,i));
   // add all suffix
   for(int i = 1; i <= original.length()-1; ++i)
       dict.insert(original.substr(i));

   memset(memo, -1, sizeof(memo));
   int res = solve(compound, 0);
   if(res == INF) return -1;
   return res;
}

dancing couples

2008-09-19T08:06:00.000-07:00

topCoder: DancingCouples editorial
"Each subproblem is clearly defined by three variables: the set of unmatched boys, the set of unmatched girls, and the number of couples we need to make."

d[i][j][k]  ----- the total ways to make k couples 
  |  |  |
  |  |  i couples to make
  |  available girl status (bitmask)
  the i-th boy to match


d[i][j][k] = the ways to make k couples in which we do not use the i-th boy +
             the ways to make k couples in which we use the i-th boy
           = d[i-1][j][k] + sum (d[i-1][j^(1 << k)][k-1])
                         {k|A[k][j]='Y'}

对比上一贴：


cnt [v][s] = the ways in which z6 = 0 + the ways in which z6 > 0
           = cnt[v-1][s] + cnt[v][s-v]

The code:

int dp[12][1025][12];
int solve(int nboy, int available_girl, int K) {
    if(nboy < K || count_bit(available_girl) < K) return 0;
    if(K == 0) return 1;
    if(dp[nboy][available_girl][K] >= 0) return dp[nboy][available_girl][K];

    int res = solve(nboy-1, available_girl, K);

    for(int i = 0; i < cd[0].size(); ++i) {
        if(cd[nboy-1][i] == 'Y' && available_girl & (1<<i))
            res += solve(nboy-1, available_girl ^ (1<<i), K-1);
    }
    return dp[nboy][available_girl][K] = res;
}

knapsack problem

2008-09-19T04:26:00.000-07:00

0/1 Knapsack Problem

n items (U = {u1, u2, … , u_n} ) need to be packed in a knapsack of size C. Each item has value v_i and size s_i.We want to find a subset of U such that

sum_ vi is maximized subject to the constraint

sum_si <= C

let V[i][j] denote the value obtained by filling a knapsack of size j with items taken from the first i items in an optimal way.

V[i][j] = 0 (if i = 0 or j = 0)
V[i][j] = V[i-1][j] ( if j < si )
V[i][j] = max ( V[i-1][j], V[i-1][j-si] + vi ) ( if i > 0 and j >= si )

Matrix Chain Multiplication

2008-09-18T14:04:00.000-07:00

经典教科书题

zoj 1602: Multiplication Puzzle
UVa 442: Matrix Chain Multiplication (not really dp problem)
UVa 348: Optimal Array Multiplication Sequence

N个矩阵，N+1个维数


Matrix:     0 ...... N-1
-----------+---------------------------------------------------------
Matrix dim:| (M0 x M1) x (M1 x M2) x (M2 x M3) x ... x (M_N-1 x M_N)
-----------+---------------------------------------------------------
Matrix  |     0           1           2                   N-1 
---------------------------------------------------------------------

The i-th matrix's dimension: M_(i-1) x M_i
第i到j个矩阵相乘的代价


d[i][i] = 0
d[i][j] = min(d[i][j], d[i][k]+d[k+1][j]+ M_(i-1)*M_(k)*M_(j))

int C[N+1][N+1];
int K[N+1][N+1];
void mcm(vector<int> &M, int n) {
 for(int i = 1; i <= n; ++i)
     C[i][i] = 0;
 for(int d = 2; d <= n; ++d) {
     for(int i = 1; i <= n-d+1; ++i) {
         int j = i + d - 1;
         C[i][j] = INF;
         for(int k = i; k <= j-1; ++k) {
             int tmp = C[i][k] + C[k+1][j] + M[i-1] * M[k] * M[j];
             if( tmp < C[i][j]) {
                 K[i][j] = k;
                 C[i][j] = tmp;
             }
         }
     }
 }
}

C[1][N]中存着从1到N连乘最小的代价，从K[][]可以得到路径。

void print_opt(int i, int j) {
 if(i == j)
     cout << "A" << i;
 else {
     cout << "(";
     print_opt(i, K[i][j]);
     cout << " x ";
     print_opt(K[i][j]+1, j);
     cout << ")";
 }
}

调用时传入mcm()一个长度为N+1的数组，和N(不是N+1!）

vector<int> M(n+1);
mcm(M, n);

下面是memoization的版本，编程简单

int lookupMcm(vector<int> &M, int i, int j) {
    if(C[i][j] != INF) return C[i][j];
    if(i == j)
        return C[i][j] = 0;
    for(int k = i; k < j; ++k) {
        int q = lookupMcm(M, i, k) + lookupMcm(M, k+1, j) + M[i-1] * M[k] * M[j];
        if( C[i][j] > q)
            C[i][j] = q;
    }
    return C[i][j];
}

调用前将C[][]初始化为INF

for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                C[i][j] = INF;

printf("%d\n",  lookupMcm(M, 1, n));

Similarly, this technique can be used to solove the following problem: (in today's interview (oct 21) )

find the length of the longest regular brackets sequence that is a subsequence of s

主要思想就是从中间出发，往两边发展，

如果已和dp[i][j]则考虑 dp[i-1][j+1]

if s[i-1] match s[j+1], then dp[i-1][j+1] = dp[i][j]

else dp[i-1][j+1] = max (dp[i-1][k] + dp[k+1][j+1])

#include <cstdio>
#include <cstring>

const int MAX = 101;

// dynamic programming 2d array
int dp[MAX][MAX];

// return true if find matching brackets
inline bool match(char a, char b) {
    if(a == '(' && b == ')') return true;
    if(a == '[' && b == ']') return true;
    return false;
}

int main() {

  char buff[MAX];
   
  // terminate until "end"
  while (gets(buff) && buff[0] != 'e') {
    int n = strlen(buff);
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++ i)
     if (match(buff[i],buff[i+1]))
      dp[i][i+1] = 2;

    for (int k = 2; k < n; ++ k) {
       for (int i = 0; i < n; ++ i) {
          if (k + i < n) {
            if (match(buff[i], buff[i+k]))
                dp[i][i+k] = dp[i+1][i+k-1] + 2;
            for (int j = i; j < i + k; ++ j) {
         if (dp[i][j] + dp[j+1][i+k] > dp[i][i+k])
             dp[i][i+k] = dp[j+1][i+k] + dp[i][j];
            }
          }
       }     
    }
    printf("%d\n", dp[0][n-1]);
  }
  return 0;
}

greeness notes

another dp

bitset and memoization

sscanf

STL comparison FUNCTOR

Coin toss and Absorbing Markov Chain

protected data or private data

Repeated Squaring

quadtree

Add without +

C++ notes II

Return Value

Deep copies need ...

3Sum problem

Maximun Flow

Maximum Bipartite Matching

Hungarian Method

String Searching

Suffix Tree

google c++ coding style

random programs

counting sort + bit operation

Maximum interval sum

initialize upon the first use

bit operation again SRM 422

closest pair problem

Complexity

Bit operations hacks

Design Patterns (4) - Factory method and Abstract Factory

Design Patterns (3) - Decorator

Design Patterns (2) - Observer

Design Patterns (1) - Strategy

interprocess communication IPC (2) - shared memory

interprocess communication IPC (1) - message queue

C++ notes

From Wikipedia, the free encyclopedia

numeric_limits

C++ FAQ Lite

[18] Const correctness

"const member function" inspects (rather than mutates) its object.

"const-overloading"

POSIX Thread

RPN and evaluation tree

Tree Recovery

Skill keywords in IT job-seeking website

gcd, binomial number

Prime Numbers

Flickr Photostream

Trie

MST (minimum spanning tree)

Union Find

Applications

bit operation

BFS

Applications of BFS

DFS

Dijkstra: single source shortest path

Flood Fill

Approach 1

Approach 3

C++ Effective notes

Item 1: Prefer const and inline to #define.

Item 2: Prefer <iostream> to <stdio.h>

Item 7: Be prepared for out-of-memory conditions.

Item 11: Declare a copy constructor and an assignment operator for classes with dynamically allocated memory.

Item 12: Prefer initialization to assignment in constructors.

Item 14: Make sure base classes have virtual destructors.

Item 17: Check for assignment to self in operator=.

Item 18: Strive for class interfaces that are complete and minimal.

Item 21: Use const whenever possible.

Item 23: Don't try to return a reference when you must return an object.

Item 29: Avoid returning "handles" to internal data.

Item 32: Postpone variable definitions as long as possible.

Number Split

Floyd-Warshall: All-Pairs Shortest Path

Applications:

Subset Sum Problem

memo[i][j] = min ( memo[i][k] + memo[k+1][j] )

topCoder: QuickSums

topCoder: ShortPalindromes

"`const` member function" inspects (rather than mutates) its object.

"`const`-overloading"