## Saturday, June 1, 2013

### 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='0', S100='1', S10='4', and S1='7', then s=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 , vector , vector , vector , vector , vector , vector , vector Returns: int Method signature: int count(vector s1000, vector s100, vector s10, vector s1, vector t1000, vector t100, vector t10, vector 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                                   Repost Num
0                                           1
1                                           2
2                                           2
3                                           1
4                                           2
5                                           2
6                                           2
7                                           2
8                                           2
9                                           2

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, t;
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 +=s1000[i];
17:            s100 +=s100[i];
18:            s10 +=s10[i];
19:            s1 +=s1[i];
20:            t1000 +=t1000[i];
21:            t100 +=t100[i];
22:            t10 +=t10[i];
23:            t1 +=t1[i];
24:       }
25:       len = s1000.size();
26:       for(int i =0; i< len; i++)
27:       {
28:            s[i] = (s1000[i]-'0')*1000 + (s100[i]-'0')*100 +(s10[i]-'0')*10 +(s1[i]-'0');
29:            t[i] = (t1000[i]-'0')*1000 + (t100[i]-'0')*100 +(t10[i]-'0')*10 +(t1[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:  }
``````