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