TopCoder problem "PaperUnfolding" used in TCHS SRM 45 (Division I Level Three)



Problem Statement

    

You have a sheet of paper and you are looking at it sideways. You can fold the paper exactly in half using one of the following operations:

  1. Fold the right half of the paper counterclockwise over the left half.
  2. Fold the right half of the paper clockwise under the left half.
The following picture illustrates the two possible folds:

Figure 1 shows the original sheet of paper. Figure 2 shows the result of performing fold operation 1, and figure 3 shows the result of performing fold operation 2 (each on the original sheet of paper).

After one initial fold, the paper is two layers thick. You can continue folding the paper any number of times, and each time it will become twice as thick and half as long. The following picture shows one possible sequence of folds:

Figure 1 shows the original sheet of paper. Figure 2 shows the result of performing fold operation 1 on the original sheet. Figure 3 shows the result of performing fold operation 2 on the resulting two-layer sheet.

After some number of folds (possibly zero), you decide to unfold the paper. To do this, you simply work backwards and reverse each fold until you end up with the original sheet. Unfortunately, the paper will now show marks where each of the folds occurred. We go from left to right and label each mark where the paper bends slightly clockwise as an OUT, and each mark where the paper bends slightly counterclockwise as an IN. The following picture shows the unfolded version of the paper from the previous picture.

You are given a String[] code. Concatenate the elements of code to obtain one string. This string contains the marks on an unfolded sheet of paper from left to right, where '1' (one) represents an OUT and '0' (zero) represents an IN. So, for example, the paper in the picture above would be represented as "100". Return "YES" if code represents a piece of paper that could have been produced using the process described above, or "NO" otherwise (all quotes for clarity).

 

Definition

    
Class:PaperUnfolding
Method:isValidUnfolding
Parameters:String[]
Returns:String
Method signature:String isValidUnfolding(String[] code)
(be sure your method is public)
    
 

Constraints

-code will contain between 0 and 50 elements, inclusive.
-Each element of code will contain between 1 and 50 characters, inclusive.
-code will contain only the characters '1' (one) and '0' (zero).
-The total number of characters in code will be 2^n-1, where n is an integer greater than or equal to zero.
 

Examples

0)
    
{}
Returns: "YES"
This sheet of paper has no marks, which means that no folding operations were applied.
1)
    
{"0"}
Returns: "YES"
This paper was only folded once.
2)
    
{"000"}
Returns: "NO"
No sequence of valid folds can produce an unfolded sheet containing three consecutive INs.
3)
    
{"1000110"}
Returns: "YES"
Do two folding operations of type 1, and one folding operation of type 2.
4)
    
{"10001101100111001000110010011101100011011001110110",
 "00110010011101100011011001110010001100100111001000",
 "11011001110110001100100111001000110110011100100011",
 "00100111011000110110011101100011001001110010001101",
 "10011100100011001001110010001101100111011000110010",
 "01110"}
Returns: "YES"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8088

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10799&pm=8088

Writer:

Relja

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Recursion