Google+ Followers

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


















Post a Comment