## 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[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

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