## Saturday, June 8, 2013

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

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

- 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

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

### 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:  }
``````