[Microsoft] string permutation with upcase and lowcase

Give a string, which only contains a-z. List all the permutation of upcase and lowcase.
For example, str = "ab",  the output should be
"ab", "aB", "Ab", "AB"
for str = "abc", the output should be
"abc", "abC", "aBc", "aBC", "Abc", "AbC", "ABc", "ABC"

[Thoughts]
首先,肯定可以用递归来做，每一个节点有大小两种可能。代码可以简单的写成：

  1: void ListPermutation(string sample, int depth, string& result)
  2: {
  3:     if(depth == sample.size())
  4:     {
  5:         prinf("%s\r\n", result.c_str());
  6:         return;
  7:     }
  8:     
  9:     // process low-case char
 10:     result.push_back(sample[depth]);
 11:     ListPermutation(sample, depth+1, result);
 12:     result.pop_back();
 13:     
 14:     //process up-case char
 15:     result.push_back(sample[depth]-32);
 16:     ListPermutation(sample, depth+1, result);
 17:     result.pop_back();
 18: }

但是，如果考虑空间复杂度的话，这是个指数级的实现。如果字符串有几千行或者几万行，内存就不得了了。

如果换个思路想想的话，其实这个题有简单的解法。因为，大写和小写只有两种变化，其实就是0和1的变化。简单的说，如果字符串长L，那么遍历区间[0,2^L-1]，对于任意i，将其转换为长度为L的二进制表示，然后根据每一位二进制是0还是1，来决定输出大写还是小写。实现如下：

  1: void ListPermutation(string sample)
  2: {
  3:     int L = sample.size();
  4:     long end = pow(2, L) -1;
  5:     for(int i =0; i< end; i++)
  6:     {
  7:         // Convert Dec to Binary, 
  8:         // return a string to represent binary data with size L
  9:         string binaryRep = ConvertDecToBinany(i, L);
 10:         
 11:         string output;
 12:         for(int j=0; j<L; j++)
 13:         {
 14:             if(binaryRep[j] == '0') //low case
 15:             {
 16:                 output.push_back(sample[j]);
 17:             }
 18:             else
 19:             {
 20:                 output.push_back(sample[j]-32);
 21:             }        
 22:         }
 23:         printf("%s\r\n", output.c_str());
 24:     }
 25: }

这样的话，整体思路就更清晰，而且内存使用是O(L)。

[TopCoder] SRM 586 DIV 2, 500p, 1000p, Solution

Problem Statement
	F is a function that is defined on all real numbers from the closed interval [1,N]. You are given a vector <int> Y with N elements. For each i (1 <= i <= N) we have F(i) = Y[i-1]. Additionally, you know that F is piecewise linear: for each i, on the interval [i,i+1] F is a linear function. The function F is uniquely determined by this information. For example, if F(4)=1 and F(5)=6 then we must have F(4.7)=4.5. As another example, this is the plot of the function F for Y = {1, 4, -1, 2}. You are also given a vector <int> query. For each i, compute the number of solutions to the equation F(x) = query[i]. Note that sometimes this number of solutions can be infinite. Return a vector <int> of the same length as query. For each i, element i of the return value should be -1 if the equation F(x) = query[i] has an infinite number of solutions. Otherwise, element i of the return value should be the actual number of solutions this equation has.
Definition
	Class: PiecewiseLinearFunctionDiv2 Method: countSolutions Parameters: vector <int>, vector <int> Returns: vector <int> Method signature: vector <int> countSolutions(vector <int> Y, vector <int> query) (be sure your method is public)
Constraints
-	Y will contain between 2 and 50 elements, inclusive.
-	Each element of Y will be between -1,000,000,000 and 1,000,000,000, inclusive.
-	query will contain between 1 and 50 elements, inclusive.
-	Each element of query will be between -1,000,000,000 and 1,000,000,000, inclusive.
Examples
0)
	{1, 4, -1, 2} {-2, -1, 0, 1} Returns: {0, 1, 2, 3 } This is the example from the problem statement. The detailed information about the queries is: There is no such x that F(x) = -2 is satisfied. F(x) = -1 is only true for x = 3. F(x) = 0 has two roots: 2.8 and 10/3. F(x) = 1 has three roots: 1, 2.6 and 11/3.
1)
	{0, 0} {-1, 0, 1} Returns: {0, -1, 0 } This function's plot is a horizontal segment between points (1, 0) and (2, 0). F(x) = 0 is satisfied for any x between 1 and 2 and thus the number of solutions is infinite. For any other value on the right-hand side, it has no solutions.
2)
	{2, 4, 8, 0, 3, -6, 10} {0, 1, 2, 3, 4, 0, 65536} Returns: {3, 4, 5, 4, 3, 3, 0 }
3)
	{-178080289, -771314989, -237251715, -949949900, -437883156, -835236871, -316363230, -929746634, -671700962} {-673197622, -437883156, -251072978, 221380900, -771314989, -949949900, -910604034, -671700962, -929746634, -316363230} Returns: {8, 6, 3, 0, 7, 1, 4, 8, 3, 4 }

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]  
把Y中连续的两个数字作为一个区间，然后对于每一个Q[i]，遍历所有Y区间，统计覆盖次数即可。

[Code]  

1:  #include<vector>  
2:  using namespace std;  
3:  class PiecewiseLinearFunctionDiv2  
4:  {  
5:  public:  
6:       vector <int> countSolutions(vector <int> Y, vector <int> query)  
7:       {  
8:            vector<int> result;  
9:            for(int i =0; i< query.size(); i++)  
10:            {  
11:                 int searchNum = query[i];  
12:                 int start = 0;  
13:                 int solution=0;  
14:                 if(searchNum == Y[start]) solution++;  
15:                 for(int j =1; j< Y.size(); j++)  
16:                 {  
17:                      if(max(Y[start], Y[j]) > searchNum && min( Y[start], Y[j]) < searchNum)  
18:                      {  
19:                           solution++;                           
20:                      }  
21:                      if(searchNum == Y[j])  
22:                      {  
23:                           if(searchNum == Y[start])  
24:                           {  
25:                                solution =-1;  
26:                                break;  
27:                           }  
28:                           solution++;  
29:                           //j++;                                                
30:                      }  
31:                      start = j;       
32:                 }  
33:                 result.push_back(solution);  
34:            }  
35:            return result;  
36:       }  
37:  };  

Problem Statement  1000P
	In this problem, all strings consist of uppercase English letters only. That is, there are 26 distinct letters. The weight of a string S can be computed as follows: for each letter that occurs at least once in S, its leftmost and rightmost occurrences L and R are found and the weight is increased by R-L. For example, if S="ABCACAZ", the weight of S is (5-0) + (1-1) + (4-2) + (6-6) = 7. (The leftmost occurrence of 'A' is at the index L=0, the rightmost one is at R=5, so 'A' contributes 5-0 = 5 to the weight of S. The only 'B' contributes 0, the pair of 'C's adds 2, and the only 'Z' adds 0.) You are given a int L. Consider all strings of length L. Compute the weight of each of these strings. The strings with the minimum weight among all of them are called light. Your task is to count the number of light strings of length L. Since this count may be very large, return it modulo 1,000,000,009.
Definition
	Class: StringWeightDiv2 Method: countMinimums Parameters: int Returns: int Method signature: int countMinimums(int L) (be sure your method is public)
Constraints
-	L will be between 1 and 1000, inclusive.
Examples
0)
	1 Returns: 26 Any string of length 1 has weight equal to 0.
1)
	2 Returns: 650 We can divide strings of length 2 into two classes: the strings with distinct first and second letter, and the strings with two equal letters. The strings composed of two equal letters have weight 1. All the other strings have weight 0. Thus, the number of strings of minimum weight is 26*26-26=650.
2)
	50 Returns: 488801539

       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]  

这题就是一个排列组合题。

首先当L<=26的时候，毫无疑问，最小的字符串就是由不同的字符构成的，权重为0，那么等价于在26个字符中，挑L个进行组合，结果就是P(26,L) = (26!)/(L!).  （P是指排列数）

那么当L>26的时候呢？我们可以把问题缩小规模，来看看规律。

假设当前问题是，给定{a,b,c}三种字符，问当L=4的时候，权重最小的字符串有哪些？

我们已经知道L=3的时候，最小的字符有6个：

ABC

ACB

BAC

BCA

CAB

CBA

现在要再加一个字符，怎么加？以ABC为例，无论再加一个什么字符，这个字符都得和同样的字符在一起才能获得最小权重，这个很容易理解，因为同类的放在一起，right-left是最小的。那么ABC的衍生就有

AABC 权重1

ABBC 权重1

ABCC 权重1

同理推导其他最小权重字符的时候，都适用同样的规则，即同样的字符放在一起，最终的权重是最小的。

这样，问题就简单了，对于任意L的长度，我们把它切成26段，每一段赋给一个独立的字符就好了，那么这种排列组合共有多少个呢？

如上图，把L长度的字符串切成26段，这就意味着在(L-1)个空挡中挑出25个来插入分界符， 有C(L-1, 25)种可能（C是指组合数），对于26段，每段给一个字符的话，有P(26,26)种排列方式，所以这样的排列组合数共有

C(L-1, 25) * P(26, 26) = (L-1)!/(  (L-26)! *  (25!) )  * 26! = P(L-1, 25) *26

这里之所以要做这一步转换的原因，是为了避免处理基于余数的除法。组合数是带除法的，而排列数仅是乘法，实现简单。

[Code]

1:  int mod = 1000000009;  
2:  class StringWeightDiv2  
3:  {  
4:  public:  
5:       long Permutation(int n, int m)  
6:       {  
7:            long result=1;  
8:            for(int i =0; i< m; i++)  
9:            {  
10:                 result*=n;  
11:                 result%=mod;  
12:                 n--;  
13:            }  
14:            return result;  
15:       }  
16:       int countMinimums(int L)  
17:       {  
18:            if(L<=26) return Permutation(26, L);  
19:            else  
20:                 return Permutation(L-1, 25)*26%mod;  
21:       }  
22:  };  

[TopCoder] SRM 587 DIV 2, 250p, 500p, 1000p, Solution

Problem Statement  250P
	You are given two strings: init and goal. Both init and goal contain lowercase letters only. Additionally, init does not contain the character 'z'. Your goal is to transform init into goal. The only operation you are allowed to do is to insert the character 'z' anywhere into init. You can repeat the operation as many times as you want, and each time you can choose any position where to insert the 'z'. For example, if init="fox", you can transform it to "fzox" in one operation. Alternately, you can transform "fox" into "zzzfoxzzz" in six operations. It is not possible to transform "fox" into any of the strings "fx", "foz", "fxo", "foxy". Return "Yes" (quotes for clarity) if it is possible to transform init into goal. Otherwise, return "No".
Definition
	Class: InsertZ Method: canTransform Parameters: string, string Returns: string Method signature: string canTransform(string init, string goal) (be sure your method is public)
Notes
-	Note that the return value is case sensitive.
Constraints
-	init and goal will each contain between 1 and 50 characters, inclusive.
-	Each character of init and goal will be a lowercase letter ('a'-'z').
-	init will not contain the letter 'z'.
Examples
0)
	"fox" "fozx" Returns: "Yes" By inserting 'z' to the position bettween 'o' and 'x' in "fox", we obtain "fozx".
1)
	"fox" "zfzoxzz" Returns: "Yes" You may perform the operation multiple times.
2)
	"foon" "foon" Returns: "Yes" In this case init and goal are equal. You do not have to perform the operation.
3)
	"topcoder" "zopzoder" Returns: "No"
4)
	"aaaaaaaaaa" "a" Returns: "No"
5)
	"mvixrdnrpxowkasufnvxaq" "mvizzxzzzrdzznzrpxozzwzzkazzzszzuzzfnvxzzzazzq" Returns: "Yes"
6)
	"opdlfmvuicjsierjowdvnx" "zzopzdlfmvzuicjzzsizzeijzowvznxzz" Returns: "No"

       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]

这题即比较两个字符串，期间，如果字符为z的话，就视而不见好了。

[Code]

1:  #include <string>  
2:  #include <cstring>  
3:  using namespace std;  
4:  class InsertZ  
5:  {  
6:  public:  
7:       string canTransform(string init, string goal)  
8:       {  
9:            int i =0, j=0;  
10:            while(i<init.size() && j<goal.size())  
11:            {  
12:                 if(goal[j] == 'z')  
13:                 {  
14:                      j++;  
15:                      continue;  
16:                 }  
17:                 if(init[i]!=goal[j])  
18:                 {  
19:                      return "No";  
20:                 }  
21:                 i++;  
22:                 j++;  
23:            }  
24:            if(i<init.size())  
25:                 return "No";  
26:            while(j<goal.size())  
27:            {       
28:                 if(goal[j] != 'z')  
29:                      return "No";  
30:                 j++;  
31:            }  
32:            return "Yes";       
33:       }  
34:  };  

Problem Statement  500P
	Little Fox Jiro is standing at the bottom of a long flight of stairs. The bottom of the stairs has number 0, the bottommost step has number 1, the next step has number 2, and so on. The staircase is so long that Jiro is guaranteed not to reach its top. Jiro will now perform N consecutive actions. The actions are numbered 1 through N, in order. When performing action X, Jiro chooses between two options: either he does nothing, or he jumps exactly X steps up the stairs. In other words, if Jiro starts performing action X standing on step Y, he will end it either on step Y, or on step Y+X. For example, if N=3, Jiro will make three consecutive choices: whether or not to jump 1 step upwards, 2 steps upwards, and then 3 steps upwards. One of the steps is broken. The number of this step is badStep. Jiro cannot jump onto this step. You are given the ints N and badStep. Compute and return the number of the topmost step that can be reached by Jiro.
Definition
	Class: JumpFurther Method: furthest Parameters: int, int Returns: int Method signature: int furthest(int N, int badStep) (be sure your method is public)
Constraints
-	N will be between 1 and 2,000, inclusive.
-	badStep will be between 1 and 4,000,000, inclusive.
Examples
0)
	2 2 Returns: 3 The optimal strategy is to jump upwards twice: from step 0 to step 1, and then from step 1 to step 3. This trajectory avoids the broken step.
1)
	2 1 Returns: 2 In this case step 1 is broken, so Jiro cannot jump upwards as his first action. The optimal strategy is to first stay on step 0, and then to jump from step 0 to step 2.
2)
	3 3 Returns: 5
3)
	1313 5858 Returns: 862641
4)
	1 757065 Returns: 1

       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]
这题其实是个数学题。对于Jiro来说，最好的就是从1开始把N个step都走一遍，这样可以走的最远。但是有可能会踩到BadStep，所以如果踩到的话，那就没办法了，从2开始走，再不行，从3开始，最后总会有条路。

所以，只要找出第一个不会踩到badstep的起始路径就可以了。假设，Jiro走的路是这样，
k, k+1, k+2, .....,   k+m       1<=k<=N, 0<=m<N-1

那么走的总长度就是
(k+k+m)*(m+1)/2

如果他踩到BadStep的话，那么有
（2*k+m)*(m+1）/2 = BadStep

所以，解法就出来了，固定一个k的取值，看是否存在整数m，使得Jiro踩到BadStep，有过有，则k=k+1，如果没有，k就是解， 计算从k到N的总长度即可。


[Code]
     

1:  class JumpFurther  
2:  {  
3:  public:  
4:       int furthest(int N, int badStep)  
5:       {  
6:            int k=1;  
7:            for(; k<=N; k++)  
8:            {            
9:                 int start=0, end = N-1;  
10:                 int index=-1;  
11:                 while(start<=end)  //这里二分查找m
12:                 {  
13:                      int mid = (start+end)/2;  
14:                      int result = (2*k + mid)*(mid+1);  
15:                      if( result == 2*badStep)  
16:                      {  
17:                           index = mid;  
18:                           break;                           
19:                      }  
20:                      else if(result < 2*badStep)  
21:                      {  
22:                           start = mid+1;  
23:                      }  
24:                      else  
25:                      {  
26:                           end = mid-1;  
27:                      }  
28:                 }  
29:                 if(index == -1)  
30:                 {  
31:                      break;  
32:                 }  
33:            }  
34:            return (k+N)*(N-k+1)/2;  
35:       }  
36:  };  

Problem Statement  1000P
	There is a H times W rectangle divided into unit cells. The rows of cells are numbered 0 to H-1 from top to bottom, and the columns are numbered 0 to W-1 from left to right. The corners of cells are called lattice points. By definition, there are (H+1)*(W+1) lattice points in our rectangle. Each of the four edges of each cell is painted white. Additionally, in each cell exactly one of the two diagonals is painted white. Two lattice points are called adjacent if they are connected by a white line segment. (In other words, consecutive corners of a cell are always adjacent, opposite corners of a cell are adjacent if and only if they are connected by a painted diagonal, and no other pairs of lattice points are adjacent.) We now want to color each of the lattice points using one of three available colors: red, green, or blue. There is only one constraint: adjacent lattice points are not allowed to share the same color. You are given a String[] cells with H elements, each consisting of W characters. If cells[i][j] is 'N', there is a diagonal line from the top left to the bottom right corner in the cell in row i, column j. If cells[i][j] is 'Z', there is a diagonal line from the top right to the bottom left corner in the cell in row i, column j. If there is at least one valid way to color all lattice points, return "Yes" (quotes for clarity). Otherwise, return "No".
Definition
	Class: ThreeColorabilityEasy Method: isColorable Parameters: String[] Returns: String Method signature: String isColorable(String[] cells) (be sure your method is public)
Constraints
-	cells will contain between 1 and 50 elements, inclusive.
-	Each element of cells will contain between 1 and 50 characters, inclusive.
-	All elements of cells will contain the same number of characters.
-	Each character of cells will be either 'N' or 'Z'.
Examples
0)
	{"Z"} Returns: "Yes" One of the possible colorings is as follows.
1)
	{"NZ" ,"NZ"} Returns: "Yes"
2)
	{"ZZZ" ,"ZNZ"} Returns: "No"
3)
	{"NZNZNNN" ,"NNZNNNZ" ,"NNNNZZZ" ,"ZZZNZZN" ,"ZZNZNNN" ,"NZZZZNN" ,"ZZZNZNN"} Returns: "No"
4)
	{"ZZZZ" ,"ZZZZ" ,"ZZZZ"} Returns: "Yes"

       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]
刚看到这个题的第一个想法就是，这不是图的m着色问题吗？回溯遍历解空间就好了。但是这个题有个简化在于，它是严格的矩形，而且每一个格子里面只能有一个对角线。

对于这种可能存在对称的图，挑个例子看一下就好了，比如四个格子，如上图，只有三种布局可能：
1. 全部一样的对角线
2. 两两相同的对角线
3. 三个格子对角线相同

如图示，对于#1及#2，都可以很容易找到解。但是对于第三种情况，总会有个点最后没法染色，因为它的周边已经被三种颜色渲染了。

所以落到这一题里面，只要在格子中找，是否存在第三种布局就好了。

[Code]

1:  #include <string>  
2:  #include <vector>  
3:  using namespace std;  
4:  class ThreeColorabilityEasy  
5:  {  
6:  public:  
7:       string isColorable(vector <string> cells)  
8:       {  
9:            int row = cells.size();  
10:            int col = cells[0].size();  
11:            if(row == 1 || col ==1) return "Yes";  
12:            for(int i =0; i<row-1; i++)  
13:            {                 
14:                 for(int j=0; j<col-1; j++)  
15:                 {  
16:                      int count=0;  
17:                      if(cells[i][j] == 'N') count++;  
18:                      if(cells[i][j+1] == 'N') count++;  
19:                      if(cells[i+1][j] == 'N') count++;  
20:                      if(cells[i+1][j+1] == 'N') count++;  
21:                      if(count ==1 || count ==3) return "No";  
22:                 }  
23:            }  
24:            return "Yes";  
25:       }  
26:  };