Saturday, June 8, 2013

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

250P

Problem Statement

     Manao has N cards arranged in a sequence. He numbered them from left to right with numbers from 0 to N-1. Each card is colored black on one side and white on the other. Initially, each of the cards may lie on a different side. That is, some of the cards (possibly none or all of them) will be black side up and others will be white side up. Manao wants to flip some cards over to obtain an alternating configuration: every pair of successive cards must be of different colors.

You are given a string cardFront consisting of N characters. For each i, character i of cardFront is 'B' if card i lies black side up, and 'W' otherwise. Count and return the minimum number of cards which must be flipped to obtain an alternating configuration.

Definition

    
Class: BlackAndWhiteSolitaire
Method: minimumTurns
Parameters: string
Returns: int
Method signature: int minimumTurns(string cardFront)
(be sure your method is public)
    

Constraints

- cardFront will be between 3 and 50 characters long, inclusive.
- Each character in cardFront will be either 'B' or 'W'.

Examples

0)
    
"BBBW"
Returns: 1
The first three cards lie with their black side up and the fourth card lies with its white side up. Flipping the second card will give us the alternating configuration "BWBW".
1)
    
"WBWBW"
Returns: 0
The cards already form an alternating configuration.
2)
    
"WWWWWWWWW"
Returns: 4
Manao only needs to flip 4 cards to make the alternating configuration "WBWBWBWBW".
3)
    
"BBWBWWBWBWWBBBWBWBWBBWBBW"
Returns: 10

       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.  

[Thought]
很简单,题目只有两种模式“BWBWBW..."或者“WBWBWB....”,对于两种模式各做一次统计,然后取最小值即可。


[Code]
1:  #include <string>  
2:  using namespace std;  
3:  class BlackAndWhiteSolitaire  
4:  {  
5:  public:  
6:  int minimumTurns(string cardFront);  
7:  };  
8:  int BlackAndWhiteSolitaire::minimumTurns(string cardFront)  
9:  {  
10:       int len = cardFront.size();  
11:       int turn1 =0, turn2 =0;  
12:       string sample1 = "BW";  
13:       string sample2 = "WB";  
14:       for(int i =0; i< len; i++)  
15:       {  
16:            if(sample1[i%2] != cardFront[i])  
17:                 turn1++;  
18:            if(sample2[i%2] != cardFront[i])  
19:                 turn2++;  
20:       }  
21:       return min(turn1, turn2);  
22:  }  


500P

Problem Statement

     There is a long narrow storehouse. The storehouse is divided into a sequence of N identical sectors, labeled 0 through N-1. Each sector is large enough to contain a single container. Currently, some sectors are empty and some sectors are filled by containers. The storehouse also contains a surveillance system that is described below.

We are going to break into the storehouse. As a part of preparation for the heist, we already found out some information about the warehouse. In particular, we know exactly how the containers are currently placed in the warehouse. You are given a String containers consisting of N characters. For each i, character i of containers is 'X' if sector i contains a container, and it is '-' if sector i is empty.

We also discovered some information about the surveillance system. The system consists of several hidden cameras. You are given a int L with the following meaning: Each of the cameras monitors exactly L consecutive sectors. The segments of sectors monitored by different cameras might overlap, but no two cameras watch exactly the same segment. (In other words, each sector may be monitored by multiple cameras, but each camera monitors a different set of consecutive sectors.)

Finally, we know something about what the cameras currently see. You are given a int[] reports. Each element of reports corresponds to one of the cameras (in no particular order). More precisely, reports[i] is the number of containers stored in the sectors monitored by the corresponding camera.

It is guaranteed that all our information is correct and consistent.

Your task is to use the provided information to deduce which sectors are monitored by at least one surveillance camera. Return a String containing N characters. For each i, character i of the return value should be one of '+', '?', and '-'. Character '+' represents that sector i is certainly monitored by at least one camera. Character '-' represents that sector i is certainly not monitored by any of the cameras. Character '?' represents the remaining case: given the information we have, it is possible that sector i is monitored, but it is also possible that it is not monitored.

Definition

    
Class: SurveillanceSystem
Method: getContainerInfo
Parameters: String, int[], int
Returns: String
Method signature: String getContainerInfo(String containers, int[] reports, int L)
(be sure your method is public)
    

Constraints

- containers will contain N elements, where N is between 1 and 50, inclusive.
- Each character in containers will be either 'X' or '-'.
- L will be between 1 and N, inclusive.
- reports will contain between 1 and N-L+1 elements, inclusive.
- Each element of reports will be between 0 and L, inclusive.
- The given information will be consistent.

Examples

0)
    
"-X--XX"
{1, 2}
3
Returns: "??++++"
This storehouse has 6 sectors. There are containers in sectors 1, 4, and 5. There are two cameras: camera #0 monitors 1 container, and camera #1 monitors 2 containers. Clearly, camera #1 must be watching sectors 3, 4, and 5. Camera #0 may be watching sectors (0, 1, 2), (1, 2, 3), or (2, 3, 4). Thus, camera #0 is surely monitoring sector 2. Sectors 0 and 1 may or may not be monitored.
1)
    
"-XXXXX-"
{2}
3
Returns: "???-???"
The camera is monitoring either the leftmost or the rightmost segment, thus the middle sector is surely not under surveillance.
2)
    
"------X-XX-"
{3, 0, 2, 0}
5
Returns: "++++++++++?"
We can deduce that cameras #1 and #3 are watching segments (0, 1, 2, 3, 4) and (1, 2, 3, 4, 5). Camera #2 is monitoring the segment (4, 5, 6, 7, 8), since this is the only segment with two occupied sectors. Camera #0 is either watching (5, 6, 7, 8, 9) or (6, 7, 8, 9, 10), thus the rightmost sector might have slipped from the surveillance.
3)
    
"-XXXXX---X--"
{2, 1, 0, 1}
3
Returns: "???-??++++??"
4)
    
"-XX--X-XX-X-X--X---XX-X---XXXX-----X"
{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}
7
Returns: "???++++?++++++++++++++++++++??????--"

       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]
这道500分的题挺直观。其实就是一个概率覆盖的问题。

首先对于输入字符串,进行一次预处理。统计下来,对于任意[i, i+L)区间内,有多少container。

然后处理camera信息,统计对于每一个监控数量i的出现次数。以测试用例3 为例,监控数量为1的camera共有两个,这就意味这,有两个不相同的区间只包含一个container, 那么在输入字符串中,我们可以发现有如下四个区间只包含一个container,我们将每个区间值都标识为1,表示出现一次。

- X X X X X - - - X - -
                  1 1 1
                        1 1 1
                           1 1 1
                              1 1 1
-------------------------------
                  1 1 2 2 3 2 1
在此,将出现概率加和,可以发现,如果四个区间里面选两个出来的话,只有出现概率>(4-2) (抽屉原理)的container才会必然被监控到。

假设D[K]表示,输入字符串中包含K个container的区间数量,那么处理camera的条件只有两个, 对于任意监控数量K
1. 如果K>= D[K], 那么将所有包含K个container的区间置为‘+’
2. 如果K<D[K],即如上例,那么将所有出现概率>(D[K]-K)的位置置为‘+’,其余位置置为'?'

[Code]  
1:  #include <vector>  
2:  #include <string>  
3:  #include <map>  
4:  #include <bitset>  
5:  using namespace std;  
6:  class SurveillanceSystem  
7:  {  
8:      public:  
9:      string getContainerInfo(string containers, vector <int> reports, int L)  
10:      {  
11:        sort(reports.begin(), reports.end());                 
12:                 string target(containers.size(), '-');  
13:                 map<int, vector<int> > lengthDir;  
14:                 int pre=0, cur = 0, count=0; //two-pointer scan  
15:                 for(int i =0; i<L; i++)  
16:                 {  
17:                      if(containers[i] =='X')  
18:                           count++;  
19:                      pre++;  
20:                 }  
21:                 vector<int>* dir = &lengthDir[count];  
22:                 dir->push_back(cur);                 
23:                 while(pre< containers.size())  
24:                 {                      
25:                      if(containers[pre] == 'X')  
26:                           count++;  
27:                      if(containers[cur] == 'X')  
28:                           count--;  
29:                      pre++;  
30:                      cur++;  
31:                      vector<int>* dir = &lengthDir[count];  
32:                      dir->push_back(cur);  
33:                 }  
34:                 bitset<51> doubtless, doubt;                 
35:                 int expectCount;  
36:                 int report;  
37:                 for(int length =0; length<reports.size(); length++)  
38:                 {  
39:                      expectCount=1;  
40:                      report = reports[length];  
41:                      while(length<reports.size()-1 && reports[length] == reports[length+1])  
42:                      {  
43:                           expectCount++;  
44:                           length++;  
45:                      }  
46:                      if(expectCount < lengthDir[report].size())// for exmple, expect 1 camera watching 3 storages, but there are muiltiple choice  
47:                      {  
48:                           int counter[51];  
49:                           memset(counter, 0, sizeof(counter));                           
50:                           for(int k =0; k< lengthDir[report].size(); k++ )  
51:                           {  
52:                                for(int j =0; j<L; j++)  
53:                                {  
54:                                     counter[lengthDir[report][k] +j] ++;  
55:                                }                                
56:                           }  
57:                           for(int k =0; k< target.size(); k++)  
58:                           {  
59:                                if(counter[k] ==0) continue;  
60:                                if(expectCount > lengthDir[report].size() - counter[k])  
61:                                     doubtless.set(k,1);  
62:                                else  
63:                                     doubt.set(k,1);  
64:                           }                 
65:                      }  
66:                      else  
67:                      {                           
68:                           for(int k =0; k< lengthDir[report].size(); k++ )  
69:                           {  
70:                                for(int j =0; j<L; j++)  
71:                                {  
72:                                     doubtless.set(lengthDir[report][k]+j,1);  
73:                                }                                
74:                           }                      
75:                      }                      
76:                 }  
77:                 for(int i =0; i< target.size();i++)  
78:                 {  
79:                      if(doubtless[i] ==1)  
80:                           target[i] ='+';  
81:                      else if(doubt[i] ==1)  
82:                           target[i] ='?';  
83:                 }  
84:                 return target;  
85:      }                
86:  };  



1000P

Problem Statement

     This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

Manao is studying graph theory and simple cycles in particular. A simple cycle of length L ≥ 3 in graph G is a sequence of vertices (v0, v1, ..., vL-1) such that all v0, v1, ..., vL-1 are pairwise distinct and for each i=0..L-1, an edge between vi and v(i+1) mod L exists in G.

Manao is interested in graphs formed by connecting two trees. The connection process is as follows. Manao takes two trees composed of N vertices each. The vertices in each tree are labeled from 0 to N - 1. Then, he generates some permutation P of numbers from 0 to N - 1. Finally, the graph is formed by connecting vertex i of the first tree to vertex P[i] of the second tree, for each i from 0 to N - 1. To remove ambiguity, the vertices of the first tree within the graph are referred to as A0, A1, ..., AN-1 and the vertices of the second graph are referred to as B0, B1, ..., BN-1. Manao wants to know the maximum number of simple cycles of length K which the resulting graph could contain if he chooses P optimally.

You are given two String[]s, tree1 and tree2. Both contain N elements, each of them N characters long. The j-th character in the i-th element of tree1 is 'X' if vertices i and j in the first tree are connected and '-' otherwise. tree2 describes the second tree in the same fashion.

Compute and return the maximum possible number of simple cycles of length K in the graph formed by connecting the two given trees as described above. Two simple cycles are equal if one of them can be cyclically shifted, or reversed and cyclically shifted, to coincide with the second. According to this definition, (1, 2, 3, 4), (2, 3, 4, 1) and (3, 2, 1, 4) are all equal.

Definition

    
Class: TreeUnionDiv2
Method: maximumCycles
Parameters: String[], String[], int
Returns: int
Method signature: int maximumCycles(String[] tree1, String[] tree2, int K)
(be sure your method is public)
    

Constraints

- tree1 and tree2 will each contain N elements, where N is between 1 and 9, inclusive.
- Each element of tree1 and tree2 will be N characters long.
- Each element of tree1 and tree2 will consist of 'X' and '-' characters only.
- tree1[i][i] and tree2[i][i] will be '-' for each i between 0 and N-1.
- tree1[i][j] will be equal to tree1[j][i] for each i, j between 0 and N-1.
- tree2[i][j] will be equal to tree2[j][i] for each i, j between 0 and N-1.
- Both tree1 and tree2 will describe a graph which is a tree.
- K will be between 3 and 7, inclusive.

Examples

0)
    
{"-X",
 "X-"}
{"-X",
 "X-"}
4
Returns: 1
Manao has two trees with two vertices each. He can connect them in two ways:



Either way, the resulting graph is a single cycle of length 4.
1)
    
{"-X-",
 "X-X",
 "-X-"}
{"-X-",
 "X-X",
 "-X-"}
5
Returns: 2
These are the possible six graphs which can be obtained by connecting the two given trees:



Except for the two topmost graphs, all the graphs contain two cycles of length 5.
2)
    
{"-X-",
 "X-X",
 "-X-"}
{"-X-",
 "X-X",
 "-X-"}
3
Returns: 0
These are the same trees as in the previous example. You can see at the pictures that none of the obtained graphs contains a cycle of length 3.
3)
    
{"-X---",
 "X-XXX",
 "-X---",
 "-X---",
 "-X---"}
{"-X-X-",
 "X-X-X",
 "-X---",
 "X----",
 "-X---"}
6
Returns: 5
When the permutation P is {0, 3, 2, 1, 4}, the resulting graph contains the following five simple cycles of length 6:
  • A0, A1, A4, B4, B1, B0
  • A0, A1, A2, B2, B1, B0
  • A1, A2, B2, B1, B0, B3
  • A1, A2, B2, B1, B4, A4
  • A1, A4, B4, B1, B0, B3
The corresponding graph is the following:

4)
    
{"-XX------",
 "X------X-",
 "X--XX-X--",
 "--X--X---",
 "--X------",
 "---X----X",
 "--X------",
 "-X-------",
 "-----X---"}

{"-X-------",
 "X-X------",
 "-X-XX----",
 "--X---X--",
 "--X--X---",
 "----X--XX",
 "---X-----",
 "-----X---",
 "-----X---"}
7
Returns: 17

       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]
还没做


















Saturday, June 1, 2013

[TopCoder] SRM580, DIV1, 600p, Solution


Problem Statement

     A group of freshman rabbits has recently joined the Eel club. No two of the rabbits knew each other. Yesterday, each of the rabbits went to the club for the first time. 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).
In Shoutter, each user can post a short message at any time. The message can be read by the user's friends. The friends can also repost the message, making it visible to their friends that are not friends with the original poster. In turn, those friends can then repost the message again, and so on. Each message can be reposted in this way arbitrarily many times. If a rabbit wants to repost multiple messages, he must repost each of them separately.
Today, each of the rabbits posted a self-introduction to Shoutter. Each rabbit would now like to read the self-introductions of all other rabbits (including those that are currently not his friends). Compute and return the minimal number of reposts necessary to reach this goal. If it is impossible to reach the goal, return -1 instead.
As the number of rabbits can be greater than what the TopCoder arena supports, you are given the times s[i] and t[i] encoded in the following form: You are given vector <string>s s1000, s100, s10, and s1. Concatenate all elements of s1000 to obtain a string S1000. In the same way obtain the strings S100, S10, and S1. Character i of each of these strings corresponds to the rabbit number i. More precisely, these characters are the digits of s[i]: we obtain s[i] by converting the string S1000[i]+S100[i]+S10[i]+S1[i] to an integer. For example, if S1000[4]='0', S100[4]='1', S10[4]='4', and S1[4]='7', then s[4]=to_integer("0147")=147. You are also given vector <string>s t1000, t100, t10, and t1. These encode the times t[i] in the same way.

Definition

    
Class: ShoutterDiv1
Method: count
Parameters: vector <string>, vector <string>, vector <string>, vector <string>, vector <string>, vector <string>, vector <string>, vector <string>
Returns: int
Method signature: int count(vector <string> s1000, vector <string> s100, vector <string> s10, vector <string> s1, vector <string> t1000, vector <string> t100, vector <string> t10, vector <string> t1)
(be sure your method is public)
    

Constraints

- s1000, s100, s10, s1, t1000, t100, t10 and t1 will each contain between 1 and 50 elements, inclusive.
- s1000, s100, s10, s1, t1000, t100, t10 and t1 will contain the same number of elements.
- Each element of s1000, s100, s10, s1, t1000, t100, t10 and t1 will contain between 1 and 50 characters, inclusive.
- For each i, the i-th elements of all input variables will all contain the same number of characters.
- Each character in the input variables will be a digit ('0'-'9').
- For each i, t[i] will be greater than or equal to s[i].

Examples

0)
    
{"22", "2"}
{"00", "0"}
{"11", "1"}
{"21", "4"}
{"22", "2"}
{"00", "0"}
{"11", "1"}
{"43", "6"}
Returns: 2
After parsing the input, you will get the following information: Rabbit 0 will enter the room at 2012 and leave the room at 2014. Rabbit 1 will enter the room at 2011 and leave the room at 2013. Rabbit 2 will enter the room at 2014 and leave the room at 2016. Therefore, Rabbit 0 and Rabbit 1 will be friends, and Rabbit 0 and Rabbit 2 will be friends too, but Rabbit 1 and Rabbit 2 won't be friends.

Rabbit 0 can already see the self-introductions of all rabbits, but rabbits 1 and 2 cannot see each other's self-introduction. Two actions are needed: First, Rabbit 0 reposts the self-introduction of Rabbit 1, and then Rabbit 0 reposts the self-introduction of Rabbit 2. Now everybody can read everything.
1)
    
{"00"}
{"00"}
{"00"}
{"13"}
{"00"}
{"00"}
{"00"}
{"24"}
Returns: -1
If it is impossible to achieve the goal, return -1.
2)
    
{"0000"}
{"0000"}
{"0000"}
{"1234"}
{"0000"}
{"0000"}
{"0000"}
{"2345"}
Returns: 6
The following pairs will be friends: Rabbit 0 and 1, 1 and 2, and 2 and 3. One of the optimal strategies is as follows:
  • Rabbit 1 shares introductions of Rabbit 0 and 2.
  • Rabbit 2 shares introductions of Rabbit 1 and 3.
  • Rabbit 1 shares introduction of Rabbit 3 (this is possible because now Rabbit 3's introduction is shared by Rabbit 2, who is a Rabbit 1's friend).
  • Rabbit 2 shares introduction of Rabbit 0 (this is possible because now Rabbit 0's introduction is shared by Rabbit 1, who is a Rabbit 2's friend).
3)
    
{"0000000000"}
{"0000000000"}
{"0000000000"}
{"7626463146"}
{"0000000000"}
{"0000000000"}
{"0000000000"}
{"9927686479"}
Returns: 18
4)
    
{"00000000000000000000000000000000000000000000000000"}
{"00000000000000000000000000000000000000000000000000"}
{"50353624751857130208544645495168271486083954769538"}
{"85748487990028258641117783760944852941545064635928"}
{"00000000000000000000000000000000000000000000000000"}
{"00000000000000000000000000000000000000000000000000"}
{"61465744851859252308555855596388482696094965779649"}
{"37620749792666153778227385275518278477865684777411"}
Returns: 333

       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]
第三组测试数据比较有代表性,以此作为分析样例,如下图















Robbit                         好友列表
0                                 1,2,3,4
1                                 0
2                                 0,3,4,5,6,7,8
3                                 0,2,4,5,6,7,8,9
4                                 0,2,3,5,6,7,8
5                                 2,3,4,6,7,8,9
6                                 2,3,4,5,7,8,9
7                                 2,3,4,5,6,8,9
8                                 2,3,4,5,6,7,9
9                                 3,5,6,7,8

对于Robbit 0,当它发出个人介绍以后,Set = {1,2,3,4}都会收到,那么下一步只需要通过3 RePost,那么Set = {1,2,3,4} U {0,2,4,5,6,7,8,9} = {0,1,2,3,4,5,6,7,8,9},所有人至此都收到了Robbit 0的介绍。所以,Robbit 0 只需要repost 1次。

对于Robbit 1,比较复杂,因为它只有一个好友,当它发出个人介绍以后,接收者Set = {0}, 然后Robbit 0 repost Robbit 1的个人介绍一次, Set = {0} U {1,2,3,4} = {0,1,2,3,4}, 然后需要Robbit 3再repost一次到所有的Robbit,Set = {0,1,2,3,4} U {0,2,4,5,6,7,8,9}。所以,Robbit 1需要2 次。

对于Robbit2,第一次post,Set = {0,3,4,5,6,7,8}, 需要在Robbit 0 Repost一次到Robbit1,需要在Robbit 5处Repost一次到Robbit 9. 共计 2次

再比如Robbit 5, 第一次Post, Set = {2,3,4,6,7,8,9}, 需要在Robbit 2处Repost一次到Robbit 0, 然后需要在Robbit 0处Repost一次到Robbit 1, 共计2次

同理可以推导出,
Robbit                                   Repost Num
0                                           1
1                                           2
2                                           2
3                                           1
4                                           2
5                                           2
6                                           2
7                                           2
8                                           2
9                                           2

总计18次。

所以,这个就是图的最小覆盖问题。从一个节点出发,覆盖整个图最少需要走多少步。然后遍历每一个节点,将步数求和即可。

有个简单的实现,基于bitset来做。


Main Logic
1:  #include <string>  
2:  #include <vector>  
3:  #include <bitset>  
4:  using namespace std;  
5:  class ShoutterDiv1  
6:  {  
7:  public:  
8:       int count(vector<string> s1000,vector<string> s100,vector<string> s10,vector<string> s1,vector<string> t1000,vector<string> t100,vector<string> t10,vector<string> t1);  
9:  };  
10:  int s[3000], t[3000];  
11:  int ShoutterDiv1::count(vector<string> s1000,vector<string> s100,vector<string> s10,vector<string> s1,vector<string> t1000,vector<string> t100,vector<string> t10,vector<string> t1)  
12:  {  
13:       int len = s1000.size();  
14:       for(int i=1; i< len; i++)  
15:       {  
16:            s1000[0] +=s1000[i];  
17:            s100[0] +=s100[i];  
18:            s10[0] +=s10[i];  
19:            s1[0] +=s1[i];  
20:            t1000[0] +=t1000[i];  
21:            t100[0] +=t100[i];  
22:            t10[0] +=t10[i];  
23:            t1[0] +=t1[i];            
24:       }  
25:       len = s1000[0].size();       
26:       for(int i =0; i< len; i++)  
27:       {  
28:            s[i] = (s1000[0][i]-'0')*1000 + (s100[0][i]-'0')*100 +(s10[0][i]-'0')*10 +(s1[0][i]-'0');  
29:            t[i] = (t1000[0][i]-'0')*1000 + (t100[0][i]-'0')*100 +(t10[0][i]-'0')*10 +(t1[0][i]-'0');  
30:       }  
31:       vector<bitset<3000> > firstConnection;  
32:       for(int i =0; i< len; i++)  
33:       {  
34:            bitset<3000> friends(0);  
35:            for(int j=0; j< len; j++)  
36:            {  
37:                 if(min(t[i],t[j]) - max(s[i], s[j])>=0)  
38:                 {  
39:                      friends.set(j,1);  
40:                 }  
41:            }  
42:            firstConnection.push_back(friends);  
43:       }  
44:       int count=0;  
45:       for(int i =0; i< len; i++)  
46:       {  
47:            bitset<3000> connections(0);            
48:            connections = connections | firstConnection[i];  
49:            if(connections.count() == len) // already arrive all Robbits  
50:            {  
51:                 continue;  
52:            }            
53:            while(true)  
54:            {  
55:                 bitset<3000> left = connections;  
56:                 left.flip();  
57:                 int bestChoice=-1, coveredNum=0;  
58:                 for(int j =0; j< len; j++)  //greedy. Find the largest override
59:                 {  
60:                      if(!connections[j]) continue;  
61:                      bitset<3000> result = left & firstConnection[j];  
62:                      if(result.count() > coveredNum)  
63:                      {  
64:                           coveredNum = result.count();  
65:                           bestChoice = j;  
66:                      }                      
67:                 }  
68:                 if(bestChoice == -1) //No new Friends found  
69:                 {  
70:                      return -1;  
71:                 }                 
72:                 connections = connections | firstConnection[bestChoice];                 
73:                 count++;  
74:                 if(connections.count() == len) // already arrive all Robbits  
75:                 {  
76:                      break;  
77:                 }  
78:            }  
79:       }  
80:       return count;       
81:  }