Tuesday, September 30, 2008

MST (minimum spanning tree)

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


EditorialThis 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

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

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.

Monday, September 29, 2008

bit operation

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

Wiki

Applications of BFS

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

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 


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? :roll:


    • S-S-S-S
      |.|.|.|
      S-S-S-S
      |.|.|.|
      S-S-S-S
      |.|.|.|
      S-S-S-.
    There are less than 24 positions that logs can be put down. Also the current position can be represented with 4 bits (we can only stand on a stump), so the state space can be represented as 4bit + 24bit = 28 bits.  如果有只有7个available slots for logs那么我们的bitvector只用11位就可以了。比如,0110|0110110, 表示现在我们的位置是第6号stump,图中有4个logs,共有7处slots(当然不同长度的log必须放在其相应的slots中,对每个log而言,可能没有7处可用的slots.)


    #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;
    }
     

    Thursday, September 25, 2008

    DFS

    Applications

    Here are some algorithms where DFS is used:

    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: imageDFS 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

    Wednesday, September 24, 2008

    Dijkstra: single source shortest path

    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

    Tuesday, September 23, 2008

    Flood Fill

    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 3srm411_holecakecuts_approach_3.jpg

    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:



    1. 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.

    2. 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.

    Monday, September 22, 2008

    C++ Effective notes

    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.


     image image


    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=.


    image image

    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.


    image


    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++.

    Sunday, September 21, 2008

    Number Split

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