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 2: #include 3: #include 4: using namespace std; 5: class ShoutterDiv1 6: { 7: public: 8: int count(vector s1000,vector s100,vector s10,vector s1,vector t1000,vector t100,vector t10,vector t1); 9: }; 10: int s[3000], t[3000]; 11: int ShoutterDiv1::count(vector s1000,vector s100,vector s10,vector s1,vector t1000,vector t100,vector t10,vector 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 <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: }