## Friday, August 2, 2013

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

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

k, k+1, k+2, .....,   k+m       1<=k<=N, 0<=m<N-1

(k+k+m)*(m+1)/2

[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);
16:                      {
17:                           index = mid;
18:                           break;
19:                      }
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]

1. 全部一样的对角线
2. 两两相同的对角线
3. 三个格子对角线相同

[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.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:  };
``````