## Saturday, May 25, 2013

250 points

### Problem Statement

A group of freshman rabbits has recently joined the Eel club. No two of the rabbits knew each other. Today, each of the rabbits went to the club for the first time. You are given vector <int>s s and t with the following meaning: For each i, rabbit number i entered the club at the time s[i] and left the club at the time t[i].
Each pair of rabbits that was in the club at the same time got to know each other, and they became friends on the social network service Shoutter. This is also the case for rabbits who just met for a single moment (i.e., one of them entered the club exactly at the time when the other one was leaving).
Compute and return the number of pairs of rabbits that became friends today.

### Definition

 Class: ShoutterDiv2 Method: count Parameters: vector , vector Returns: int Method signature: int count(vector s, vector t) (be sure your method is public)

### Constraints

- s and t will contain between 1 and 50 integers, inclusive.
- s and t will contain the same number of elements.
- Each integer in s and t will be between 0 and 100, inclusive.
- For each i, t[i] will be greater than or equal to s[i].

### Examples

0)

 `{1, 2, 4}` `{3, 4, 6}`
`Returns: 2`
 Rabbit 0 and Rabbit 1 will be friends because both of them are in the club between time 2 and 3. Rabbit 0 and Rabbit 2 won't be friends because Rabbit 0 will leave the club before Rabbit 2 enters the club. Rabbit 1 and Rabbit 2 will be friends because both of them are in the club at time 4.
1)

 `{0}` `{100}`
`Returns: 0`
2)

 `{0,0,0}` `{1,1,1}`
`Returns: 3`
3)

 `{9,26,8,35,3,58,91,24,10,26,22,18,15,12,15,27,15,60,76,19,12,16,37,35,25,4,22,47,65,3,2,23,26,33,7,11,34,74,67,32,15,45,20,53,60,25,74,13,44,51}` `{26,62,80,80,52,83,100,71,20,73,23,32,80,37,34,55,51,86,97,89,17,81,74,94,79,85,77,97,87,8,70,46,58,70,97,35,80,76,82,80,19,56,65,62,80,49,79,28,75,78}`
`Returns: 830`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

[Thoughts]

1. A与B左部重合
2. A与B右部重合
3. A包括B
4. B包括A

if((s[j] >= s[i] && S[j]<=t[i]) || (t[j]>=s[i] && t[j]<=t[i]) || (s[i] < s[j] && t[i] > t[j]) || (s[i]>s[j] && t[i] < t[j]))
{
count++;
}

if( min(t[i],t[j]) - max(s[i], s[j]) ) >==0

[Code]

``````1:  #include <vector>
2:  using namespace std;
3:  class ShoutterDiv2
4:  {
5:       public:
6:       int count(vector <int> s, vector <int> t);
7:  };
8:  int ShoutterDiv2::count(vector <int> s, vector <int> t)
9:  {
10:       int count=0;
11:       for(int i =0; i< s.size()-1; i++)
12:       {
13:            for(int j =i+1; j< s.size(); j++)
14:            {
15:                 if(min(t[i],t[j]) - max(s[i], s[j])>=0)
16:                 {
17:                      count++;
18:                 }
19:            }
20:       }
21:       return count;
22:  }
``````

500 points

### Problem Statement

Rabbit went to a river to catch eels. All eels are currently swimming down the stream at the same speed. Rabbit is standing by the river, downstream from all the eels.

Each point on the river has a coordinate. The coordinates increase as we go down the stream. Initially, Rabbit is standing at the origin, and all eels have non-positive coordinates.

You are given two vector <int>s: l and t. These describe the current configuration of eels. The speed of each eel is 1 (one). For each i, the length of eel number i is l[i]. The head of eel number i will arrive at the coordinate 0 precisely at the time t[i]. Therefore, at any time T the eel number i has its head at the coordinate T-t[i], and its tail at the coordinate T-t[i]-l[i].

Rabbit may only catch an eel when some part of the eel (between head and tail, inclusive) is at the same coordinate as the rabbit. Rabbit can catch eels at most twice. Each time he decides to catch eels, he may catch as many of the currently available eels as he wants. (That is, he can only catch eels that are in front of him at that instant, and he is allowed and able to catch multiple eels at once.)

Return the maximal total number of eels Rabbit can catch.

### Definition

 Class: EelAndRabbit Method: getmax Parameters: vector , vector Returns: int Method signature: int getmax(vector l, vector t) (be sure your method is public)

### Constraints

- l will contain between 1 and 50 elements, inclusive.
- Each element of l will be between 1 and 1,000,000,000, inclusive.
- l and t will contain the same number of elements.
- Each element of t will be between 0 and 1,000,000,000, inclusive.

### Examples

0)

 `{2, 4, 3, 2, 2, 1, 10}` `{2, 6, 3, 7, 0, 2, 0}`
`Returns: 6`
 Rabbit can catch 6 eels in the following way: At time 2, catch Eel 0, Eel 4, Eel 5, and Eel 6. At time 8, catch Eel 1 and Eel 3.
1)

 `{1, 1, 1}` `{2, 0, 4}`
`Returns: 2`
 No two eels are in front of Rabbit at the same time, so Rabbit can catch at most two eels.
2)

 `{1}` `{1}`
`Returns: 1`
3)

 `{8, 2, 1, 10, 8, 6, 3, 1, 2, 5}` `{17, 27, 26, 11, 1, 27, 23, 12, 11, 13}`
`Returns: 7`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

[Thoughts]

[Code]

``````1:  #include <vector>
2:  #include <string>
3:  using namespace std;
4:  class EelAndRabbit
5:  {
6:  public:
7:       int getmax(vector <int> l, vector <int> t);
8:       int GetFish(vector <int>& l, vector <int>& t, int time, vector<int>& visited, bool isSecond);
9:  };
10:  int EelAndRabbit::getmax(vector <int> l, vector <int> t)
11:  {
12:       vector<int> visited(t.size());
13:       int maxCatch=0;
14:       for(int i =0;i<t.size(); i++) // t is the left boundary of interval, and l will be right boundary
15:       {
16:            l[i] = l[i] +t[i];
17:       }
18:       for(int i =0; i< t.size(); i++)
19:       {
20:            std::fill(visited.begin(), visited.end(),0);
21:            int firstCatch = GetFish(l,t, t[i], visited,false); //first catch
22:            int secondCatch=0;
23:            for(int j=0;j<t.size(); j++)
24:            {
25:                 if(j== i || t[i]>t[j]) continue;
26:                 int temp = GetFish(l,t, t[j], visited,true); //second catch
27:                 if(temp>secondCatch) secondCatch = temp;
28:            }
29:            if((firstCatch+secondCatch) >maxCatch)
30:            {
31:                 maxCatch=firstCatch+secondCatch;
32:            }
33:       }
34:       return maxCatch;
35:  }
36:  int EelAndRabbit::GetFish(vector <int>& l, vector <int>& t, int time, vector<int>& visited, bool isSecond)
37:  {
38:       int temp=0;
39:       for(int i =0; i< t.size(); i++)
40:       {
41:            if(visited[i]) continue; //fish had been caught in first round.
42:            if((time >= t[i] && time<=l[i]))  // find the overlap interval
43:            {
44:                 if(!isSecond) visited[i] =1;
45:                 temp++;
46:            }
47:       }
48:       return temp;
49:  }
``````

1000 points

### Problem Statement

Rabbit and Eel are playing a board game. The game is played with a single token on a rectangular board that is divided into a grid of unit cells. Some cells contain a digit that represents the cost of placing the token onto that cell. Other cells contain the letter 'x' that represents a blocked cell. It is not allowed to place the token onto a blocked cell.
Initially, the token is placed on the leftmost cell of the topmost row. (The constraints guarantee that this cell will never be blocked and its cost will always be 0.) Eel starts the game by putting up some walls. Eel may place as many walls as he wants, including none. Each wall must be placed between two adjacent cells in the same column.
Once Eel has placed the walls, Rabbit gets to move the token. In each step, Rabbit may move the token one cell left, one cell right, or one cell down. (Note that Rabbit is not allowed to move the token upwards.) Rabbit may only move the token into cells that are not blocked. Each time Rabbit moves the token into a cell, he has to pay the cost associated with that cell.
The game ends when Rabbit first moves the token into the bottommost row. The constraints guarantee that this can be achieved if Eel does not place any walls. The game must always be allowed to end. That is, Eel must not place a set of walls that blocks all possible paths to the bottommost row.
Rabbit's goal is to minimize and Eel's goal is to maximize the total cost paid by Rabbit during the game. You are given the String[] costs representing the costs of cells: character j of element i of cost is either a digit that represents the cost written in the cell in row i, column j; or it is the letter 'x' that represents a blocked cell. Return the total cost of the game assuming that both Rabbit and Eel play optimally.

### Definition

 Class: WallGameDiv2 Method: play Parameters: String[] Returns: int Method signature: int play(String[] costs) (be sure your method is public)

### Constraints

- costs will contain between 2 and 50 elements, inclusive.
- Each element of costs will contain between 1 and 50 characters, inclusive.
- Each element of costs will contain the same number of characters.
- Each character of each element of costs will be a letter 'x' or a decimal digit ('0'-'9').
- There will be at least one valid path from the leftmost cell of topmost row to a cell in the bottommost row.
- costs will always be '0'.

### Examples

0)

 ```{"042" ,"391"}```
`Returns: 13`
 Eel's optimal stategy is to put two walls: between '0'-'3' and between '2'-'1'. Then Rabbit's optimal strategy is to move the token along the path '0'->'4'->'9'. The total cost will be 13.
1)

 ```{"0xxxx" ,"1x111" ,"1x1x1" ,"11191" ,"xxxx1"}```
`Returns: 16`
 There's only one path from the starting cell to the bottom row and Eel isn't allowed to block it. Rabbit will move the token along this path and will get to pay a cost of 16. Note that it is not allowed to move the token upwards.
2)

 ```{"0" ,"5"}```
`Returns: 5`
3)

 ```{"0698023477896606x2235481563x59345762591987823x663" ,"1x88x8338355814562x2096x7x68546x18x54xx1077xx5131" ,"64343565721335639575x18059738478x156x781476124780" ,"2139850139989209547489708x3466104x5x3979260330074" ,"15316x57171x182167994729710304x24339370252x2x8846" ,"459x479948xx26916349194540891252317x99x4329x34x91" ,"96x3631804253899x69460666282614302698504342364742" ,"4x41693527443x7987953128673046855x793298x8747219x" ,"7735427289436x56129435153x83x37703808694432026643" ,"340x973216747311x970578x9324423865921864682853036" ,"x1442314831447x860181542569525471281x762734425650" ,"x756258910x0529918564126476x481206117984425792x97" ,"467692076x43x91258xx3xx079x34x29xx916574022682343" ,"9307x08x451x2882604411x67995x333x045x0x5xx4644590" ,"4x9x088309856x342242x12x79x2935566358156323631235" ,"04596921625156134477422x2691011895x8564609x837773" ,"223x353086929x27222x48467846970564701987061975216" ,"x4x5887805x89746997xx1419x758406034689902x6152567" ,"20573059x699979871151x444449x5170122650576586x898" ,"683344308229681464514453186x51040742xx138x5170x93" ,"1219892x9407xx63107x24x4914598xx4x478x31485x69139" ,"856756530006196x8722179365838x9037411399x41126560" ,"73012x9290145x1764125785844477355xx827269976x4x56" ,"37x95684445661771730x80xx2x459547x780556228951360" ,"54532923632041379753304212490929413x377x204659874" ,"30801x8716360708478705081091961915925276739027360" ,"5x74x4x39091353819x10x433010250089676063173896656" ,"03x07174x648272618831383631629x020633861270224x38" ,"855475149124358107x635160129488205151x45274x18854" ,"091902044504xx868401923845074542x50x143161647934x" ,"71215871802698346x390x2570413992678429588x5866973" ,"87x4538137828472265480468315701832x24590429832627" ,"9479550007750x658x618193862x80317248236583631x846" ,"49802902x511965239855908151316389x972x253946284x6" ,"053078091010241324x8166428x1x93x83809001454563464" ,"2176345x693826342x093950x12x7290x1186505760xx978x" ,"x9244898104910492948x2500050208763770568x92514431" ,"6855xx7x145213846746325656963x0419064369747824511" ,"88x15690xxx31x20312255171137133511507008114887695" ,"x391503034x01776xx30264908792724712819642x291x750" ,"17x1921464904885298x58x58xx174x7x673958x9615x9230" ,"x9217049564455797269x484428813681307xx85205112873" ,"19360179004x70496337008802296x7758386170452xx359x" ,"5057547822326798x0x0569420173277288269x486x582463" ,"2287970x0x474635353111x85933x33443884726179587xx9" ,"0x697597684843071327073893661811597376x4767247755" ,"668920978869307x17435748153x4233659379063530x646x" ,"0019868300350499779516950730410231x9x18749463x537" ,"00508xx083203827x42144x147181308668x3192478607467"}```
`Returns: 3512`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

[Thoughts]
DP

[Code]

``````1:  #include <vector>
2:  #include <string>
3:  using namespace std;
4:  class WallGameDiv2
5:  {
6:  public:
7:       int play(vector <string> costs);
8:  };
9:  int cost;
10:  int dp;
11:  int row, col;
12:  int WallGameDiv2::play(vector <string> costs)
13:  {
14:       //initialize the cost and dp array
15:       ````memset(cost, -1, sizeof(cost));````
16:       ````memset(dp, -1, sizeof(dp));````
17:       row = costs.size();
18:       col = costs.size();
19:       for(int i =0; i< row; i++)
20:       {
21:            for(int j=0; j< col; j++)
22:            {
23:                 if(costs[i][j] != 'x')
24:                 {
25:                      cost[i][j] = costs[i][j]-'0';
26:                 }
27:            }
28:       }
29:       dp =0;
30:       //first row
31:       for(int i =1; i< col && cost[i]!=-1; i++)
32:       {
33:            dp[i] = (dp[i-1] + cost[i]);
34:       }
35:       for(int i =1; i< row-1; i++)
36:       {
37:            for(int j=0; j<col; j++)
38:            {
39:                 if(dp[i-1][j] == -1) continue;
40:                 //for each cost i,j, update the value with worst cost
41:                 int estiCost = dp[i-1][j];
42:                 //right
43:                 for(int k = j; k<col && cost[i][k]!=-1; k++)
44:                 {
45:                      estiCost+=cost[i][k];
46:                      dp[i][k] = max(dp[i][k], estiCost);
47:                 }
48:                 //left
49:                 estiCost = dp[i-1][j];
50:                 for(int k=j; k >=0&& cost[i][k]!=-1; k--)
51:                 {
52:                      estiCost+=cost[i][k];
53:                      dp[i][k] = max(dp[i][k], estiCost);
54:                 }
55:            }
56:       }
57:       // last row is special
58:       int steps = 0;
59:       for(int i =0; i< col; i++)
60:       {
61:            if(cost[row-1][i] ==-1) continue;
62:            steps = max(steps, dp[row-2][i]+cost[row-1][i]);
63:       }
64:       return steps;
65:  }
``````

[Note]
Line 15 & 16

memset(cost, -1, sizeof(cost)/sizeof(int));
memset(dp, -1, sizeof(dp)/sizeof(int));

## Tuesday, May 21, 2013

### Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Everybody loves geometry, so here is a geometry problem. You have a few marbles of possibly different sizes. You are given a vector <int> radius that describes the marbles: each element of radius is the radius of one of your marbles.

You want to place all marbles onto a straight line that is drawn on the table. Clearly, this makes the problem two-dimensional: we can just view the marbles as circles that will all be touching the line from above. Of course, the marbles cannot overlap, so in our problem no two circles are allowed to overlap. Note that you may place the marbles onto the line in any order, you do not have to preserve the order in which they are given in radius.

Additionally, you want to pack the bottoms of the marbles as close together as possible. More precisely: For each marble consider the point where it touches the line. Compute and return the smallest possible distance between the farthest two of those points. (That is, if you imagine the line as going from the left to the right, your task is to minimize the distance between the leftmost and the rightmost of the points where the circles touch the line.)

### Definition

 Class: MarblePositioning Method: totalWidth Parameters: vector Returns: double Method signature: double totalWidth(vector radius) (be sure your method is public)

### Notes

- The returned values must have an absolute or relative error less than 1e-9.

### Constraints

- radius will contain between 2 and 8 elements, inclusive.
- Each element of radius will be between 1 and 1000000000 (10^9), inclusive.

### Examples

0)

 `{1, 2}`
`Returns: 2.8284271247461903`
 One of the best ways to place the marbles is the following one: 1)

 `{7,7,7}`
`Returns: 28.0`
2)

 `{10, 20, 30}`
`Returns: 62.92528739883945` 3)

 `{100, 100,11,11,25}`
`Returns: 200.0` 4)

 `{1,999950884,1}`
`Returns: 63246.0`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

[Thoughts]

``````1:  #include <string>
2:  #include <vector>
3:  #include <cmath>
4:  using namespace std;
5:  class MarblePositioning
6:  {
7:       struct Circle
8:       {
9:            double x;
10:            int r;
11:       };
12:  public:
13:       double GetXOfCenter(vector<Circle>& arrange, Circle& added);
14:       double GetCurrentLength(vector<Circle>& c);
15:       void GetMinArrangement(vector<Circle>& circles, vector<Circle>& arrange, vector<bool>& visited, double& minLen);
17:  };
18:  // Get the X coordinate of center of the circle.
19:  // Here, need go through all the circles instead of comparing with previous circle only, in case of circle overlap.
``````20:  double MarblePositioning::GetXOfCenter(vector<Circle>& arrange, Circle& added)
21:  {
22:       double x=0;
23:       for(int i =0; i<arrange.size(); i++)
24:       {
25:            // sqrt( (ra+rb)^2 - (ra-rb)^2)
26:            double temp = arrange[i].x + 2* sqrt(arrange[i].r*added.r);
27:            if(temp>x) x= temp;
28:       }
29:       return x;
30:  }  ``````
31:  // Get t``````he length of current circle queue
32:  double MarblePositioning::GetCurrentLength(vector<Circle>& c)
33:  {
34:       if(c.size() ==0) return 0;
35:       return c[c.size()-1].x - c.x;
36:  }
37:  void MarblePositioning::GetMinArrangement(vector<Circle>& circles, vector<Circle>& arrange, vector<bool>& visited, double& minLen)
38:  {
39:       if(GetCurrentLength(arrange) > minLen) return; // pruning all non-optimization branch
40:       if(circles.size() == arrange.size())
41:       {
42:            double newLen = GetCurrentLength(arrange);
43:            if(newLen < minLen) minLen = newLen;
44:            return;
45:       }
46:       for(int i =0; i < circles.size(); i++)
47:       {
48:            if(visited[i]) continue;
49:            circles[i].x = GetXOfCenter(arrange, circles[i]);
50:            arrange.push_back(circles[i]);
51:            visited[i] = true;
52:            GetMinArrangement(circles, arrange, visited, minLen);
53:            arrange.pop_back();
54:            visited[i] = false;
55:            circles[i].x =0;
56:       }
57:  }
59:  {
61:       for(int i =0; i< radius.size(); i++)
62:       {
64:            sample[i].x = 0;
65:       }
66:       vector<Circle> arrange;
68:       double minLen = INT_MAX;
69:       GetMinArrangement(sample, arrange, visited, minLen);
70:       return minLen;
71:  }
``````

[Some Notes]
1. Function  GetMinArrangement  的 visited数组是不必要的，可以通过判断circle.x ==0来代替，这里完全是为了可读性。

## Sunday, May 12, 2013

### Problem Statement

Crow Keith is looking at the goose cage in the zoo. The bottom of the cage is divided into a grid of square cells. There are some birds sitting on those cells (with at most one bird per cell). Some of them are geese and all the others are ducks. Keith wants to know which birds are geese. He knows the following facts about them:
• There is at least one goose in the cage.
• Each bird within Manhattan distance dist of any goose is also a goose.
You are given a vector <string> field and the int dist. The array field describes the bottom of the cage. Each character of each element of field describes one of the cells. The meaning of individual characters follows.
• The character 'v' represents a cell that contains a bird.
• The character '.' represents an empty cell.
Return the number of possible sets of geese in the cage, modulo 1,000,000,007. Note that for some of the test cases there can be no possible sets of geese.

### Definition

 Class: GooseInZooDivTwo Method: count Parameters: vector , int Returns: int Method signature: int count(vector field, int dist) (be sure your method is public)

### Notes

- The Manhattan distance between cells (a,b) and (c,d) is |a-c| + |b-d|, where || denotes absolute value. In words, the Manhattan distance is the smallest number of steps needed to get from one cell to the other, given that in each step you can move to a cell that shares a side with your current cell.

### Constraints

- field will contain between 1 and 50 elements, inclusive.
- Each element of field will contain between 1 and 50 characters, inclusive.
- Each element of field will contain the same number of characters.
- Each character of each element of field will be 'v' or '.'.
- dist will be between 0 and 100, inclusive.

### Examples

0)

 `{"vvv"}` `0`
`Returns: 7`
 There are seven possible sets of positions of geese: "ddg", "dgd", "dgg", "gdd", "gdg", "ggd", "ggg" ('g' are geese and 'd' are ducks).
1)

 `{"."}` `100`
`Returns: 0`
 The number of geese must be positive, but there are no birds in the cage.
2)

 `{"vvv"}` `1`
`Returns: 1`

[Thoughts]

(a*b)%m=(a%m*b%m )%m;

[Code]

``````1:  #define pb push_back
2:  #define INF 100000000000
3:  #define L(s) (int)((s).size())
4:  #define FOR(i,a,b) for (int _n(b), i(a); i<=_n; i++)
5:  #define rep(i,n) FOR(i,1,(n))
6:  #define rept(i,n) FOR(i,0,(n)-1)
7:  #define C(a) memset((a), 0, sizeof(a))
8:  #define ll long long
9:  #define VI vector<int>
10:  #define ppb pop_back
11:  #define mp make_pair
12:  #define MOD 1000000007
13:       struct Node {
14:            int x;
15:            int y;
16:            Node(int a, int b) : x(a), y(b) { }
17:       };
18:       int toInt(string s){ istringstream sin(s); int t; sin>>t;return t;}
19:       vector<Node> GooseInZooDivTwo::flood(vector<string> &field, vector<vector<bool> > &visit, int x, int y, int dist, int m, int n)
20:       {
21:            vector<Node> ret;
22:            queue<Node> S;
23:            visit[x][y] = true;
24:            S.push(Node(x, y));
25:            while (!S.empty())
26:            {
27:                 Node cur = S.front();
28:                 ret.pb(S.front());
29:                 S.pop();
30:                 for (int i = max(0, cur.x-dist); i <= min(m-1, cur.x+dist); i++)
31:                 {
32:                      for (int j = max(0, cur.y-dist); j <= min(n-1, cur.y+dist); j++)
33:                      {
34:                           if (field[i][j] == 'v' && !visit[i][j] && (abs(i-cur.x)+abs(j-cur.y) <=dist))
35:                           {
36:                                S.push(Node(i, j));
37:                                visit[i][j] = true;
38:                           }
39:                      }
40:                 }
41:            }
42:            return ret;
43:       }
44:       int GooseInZooDivTwo::count(vector <string> field, int dist) {
45:            int m = L(field);
46:            if (!m) return 0;
47:            int n = L(field);
48:            vector<vector<bool> > visit(m, vector<bool>(n, false));
49:            vector<vector<Node> > ret;
50:            rept(i, m)
51:            {
52:                 rept(j, n)
53:                 {
54:                      if (field[i][j] == 'v' && !visit[i][j])
55:                      {
56:                           ret.pb(flood(field, visit, i, j, dist, m, n));
57:                      }
58:                 }
59:            }
60:            if (!L(ret)) return 0;
61:            long num=1;
62:            for(int i =0; i< L(ret); i++) //要考虑排列溢出的情况
63:            {
64:                 num*=2;
65:                 if(num> MOD)
66:                 {
67:                      num = num % MOD;
68:                 }
69:            }
70:            return num-1;
71:       }
``````

## Tuesday, May 7, 2013

### Algorithm and Data Structure Review

1、常见数据结构

链表：
队列，
堆栈，
块状数组（数组+链表）
hash表，
双端队列
位图（bitmap）

二叉树：
堆（大顶堆、小顶堆）
trie树（字母树or字典树）
后缀树，
后缀树组
二叉排序/查找树，
B+/B-，
AVL树
Treap
红黑树
splay树
线段树
树状数组

2、常见算法

（1）       基本思想：枚举，
递归：

分治，
模拟&贪心： Gray CodeInsert IntervalJump Game II，

二分查找：

（2）       图算法：深度优先遍历与广度优先遍历， 最短路径，最小生成树，拓扑排序

（3）       字符串算法：

hash算法，KMP算法

（4）       排序算法：冒泡，插入，选择，快排，归并排序，堆排序，
桶排序： First Missing Positive

（5）       动态规划：Distinct SubsequencesLargest Rectangle in Histogram
背包问题，最长公共子序列，最优二分检索树

（6）       数论问题：素数问题，整数问题，进制转换，同余模运算，
进制转换：Integer To Roman
乘除法：Divide Two Integers

（7）       排列组合：排列和组合算法

（8）       其它：LCA与RMQ问题

（9） 水箱问题：Trapping Rain WaterContainer With Most Water

3. 常见设计题
（1）海量数据处理