Saturday, May 25, 2013

[TopCoder] SRM 580 DIV 2, 250p, 500p, 1000p, Solution

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 <int>, vector <int>
Returns: int
Method signature: int count(vector <int> s, vector <int> 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]
简单的计算区间重合。对于任意两个区间A和B,存在以下四种重合情况:
1. A与B左部重合
2. A与B右部重合
3. A包括B
4. B包括A

假设A的区间是(s[i], t[i]), 而B的区间为(s[j],t[j]),那么重合的判断式如下:
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 <int>, vector <int>
Returns: int
Method signature: int getmax(vector <int> l, vector <int> 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]
这一题和Leetcode里面买股票的题很类似。

将输入参数转化为Interval,对于任意鱼i,Interval[i].left = t[i], Interval[i].right = t[i]+l[i]。有了Interval数组之后,只要计算该数组在任意时间点上的重合数量,即可确定在该时间点上可以抓到多少鱼。题目已经说了,机器人最多可以抓两次鱼,所以模拟两次抓鱼即可。


[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[0][0] 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
首先如果这个题只有Robbit的话,很容易发现这是一个最小路径的DP。此题巧妙处在于做了一个转换,增加了Eel,转换为双人博弈。题目中说了,Eel总是会增加阻碍,让Robbit只能走代价最高的路径。简单的说,如果Eel非常尽职的话,Robbit在每一行只能选择代价最高的那个cell,因为凡是好的路径,必然已经被Eel设置了路障。所以这个题说到底,就是最大路径的DP。具体看code。


[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[51][51];  
10:  int dp[51][51];  
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[0].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][0] =0;  
30:       //first row  
31:       for(int i =1; i< col && cost[0][i]!=-1; i++)  
32:       {  
33:            dp[0][i] = (dp[0][i-1] + cost[0][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));
刚开始提交,过不了大数据,翻来覆去的看,也没发现有什么问题。最后拿到visual studio里面debug才发现问题,多了sizeof(int)。对于c++不是特别熟悉呀。



Tuesday, May 21, 2013

[TopCoder] SRM 579 DIV 2, Marble Positioning, Solution

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 <int>
Returns: double
Method signature: double totalWidth(vector <int> 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]
分支限界法(branch and bound method)的具体实现之一。以广度优先或者最小损耗的方式搜索解空间,在搜索过程中,不断舍弃非最优解。

一般来说,分支限界法的实现,需要一个有限队列,每次,弹出一个扩展节点,然后基于该扩展节点再搜索,不断加入可能的扩展节点入队,直至队列为空。

但是在此题中,关于圆的排列,缺乏明确的条件在广度优先搜索中淘汰非最优节点。所以,退化为递归+剪枝。

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);  
16:       double totalWidth(vector <int> radius);  
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 the 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[0].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:  }  
58:  double MarblePositioning::totalWidth(vector <int> radius)  
59:  {  
60:       vector<Circle> sample(radius.size());  
61:       for(int i =0; i< radius.size(); i++)  
62:       {  
63:            sample[i].r = radius[i];  
64:            sample[i].x = 0;  
65:       }  
66:       vector<Circle> arrange;  
67:       vector<bool> visited(radius.size());  
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

[TopCoder] SRM 578 DIV 2, Goose In Zoo, Solution

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 <string>, int
Returns: int
Method signature: int count(vector <string> 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]
这道题非常有意思。刚拿到题的时候,第一个想法就是,这不是八皇后的变形吗? DFS一通到底就好了。但是细细的品味之后,发现这个不是这么简单。这道题其实是图论中连通区域的变形。

在题目中已经说了,给定任意一个点,如果该节点是一只鹅,那么所有与该鹅在曼哈顿距离以内的节点都是鹅。换句话说,所有与该鹅在曼哈顿距离以内的,都是连通的,可以收缩成一个节点,因为他们的行为时一致的,要么都是鹅,要么都不是鹅。


到这里,题目就变形为,在一个二维数组里面,找出连通区域的个数。然后对连通区域数求排列(这里就是2的幂数)。

计算大数取余的时候,要考虑溢出,通过迭代法计算。
(a*b)%m=(a%m*b%m )%m;

[Code]
懒得自己写了,偷用Zhongwen的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[0]);  
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、常见数据结构

线性:
          数组:Merge Sorted Array
          链表:Merge k Sorted ListsPartition List
          队列,
          堆栈,
          块状数组(数组+链表)
          hash表,
          双端队列
        位图(bitmap)

树:
   二叉树: Minimum Depth of Binary Tree, Path Sum II, Inorder Travel
        堆(大顶堆、小顶堆)
          trie树(字母树or字典树)
          后缀树,
        后缀树组
          二叉排序/查找树,
          B+/B-,
        AVL树
        Treap
          红黑树
          splay树
        线段树
          树状数组

图:图

其它:并查集

2、常见算法

(1)       基本思想:枚举,
               递归: 
Flatten Binary Tree to Linked ListGenerate ParenthesesLetter Combinations of a Phone Number
               分治,
               模拟&贪心: Gray CodeInsert IntervalJump Game II, Multiply Strings, Next PermutationPalindrome NumberPascal's Triangle II
贪心,动态规划,剪枝,回溯
               二分查找:Median of Two Sorted ArraysSearch in Rotated Sorted Array

(2)       图算法:深度优先遍历与广度优先遍历, 最短路径,最小生成树,拓扑排序

(3)       字符串算法:
                   字符串查找: Implement strStrLength Of Last WordLongest Common Prefix, 
                                     Longest Palindromic SubstringLongest Non-Repeating SubString
                   双指针: Minimum Window Substring
                   hash算法,KMP算法

(4)       排序算法:冒泡,插入,选择,快排,归并排序,堆排序,
               桶排序: First Missing Positive

(5)       动态规划:Distinct SubsequencesEdit DistanceInterleaving StringJump GameLargest Rectangle in Histogram
  背包问题,最长公共子序列,最优二分检索树

(6)       数论问题:素数问题,整数问题,进制转换,同余模运算,
                     进制转换:Integer To Roman
                     乘除法:Divide Two Integers 

(7)       排列组合:排列和组合算法

(8)       其它:LCA与RMQ问题
               
 (9) 水箱问题:Trapping Rain WaterContainer With Most Water

3. 常见设计题
(1)海量数据处理