TopCoder problem "ReversalChain" used in SRM 400 (Division I Level Two)



Problem Statement

    

Given a string, the reversal operation r(i, j) reverses the substring of the string from the i-th character to the j-th character (0-indexed, inclusive). A reversal chain is a sequence of reversals where the range of each reversal is included in the range of the previous reversal. Formally, the sequence r(i1, j1), r(i2, j2), ..., r(im, jm) is a reversal chain if i1 <= i2 <= ... <= im, and j1 >= j2 >= ... >= jm.

You are given a string init which contains only '0' (zero) and '1' (one) characters. You want to transform this string into the string goal using a reversal chain. Return the minimum possible length of a reversal chain that transforms init into goal. Return -1 if it is impossible.

 

Definition

    
Class:ReversalChain
Method:minReversal
Parameters:String, String
Returns:int
Method signature:int minReversal(String init, String goal)
(be sure your method is public)
    
 

Constraints

-init will contain between 1 and 50 characters, inclusive.
-init and goal will contain the same number of characters.
-Each character of init and goal will be '0' (zero) or '1' (one).
 

Examples

0)
    
"1100"
"0110"
Returns: 1
r(0, 2) transforms "1100" into "0110".
1)
    
"111000"
"101010"
Returns: 2
r(1, 4) and r(2, 3) transforms "111000" into "101010".
2)
    
"0"
"1"
Returns: -1
It is impposible to transform "0" into "1" by a reversal chain.
3)
    
"10101"
"10101"
Returns: 0
You do not have to do anything.
4)
    
"111000111000"
"001100110011"
Returns: 4

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12172&pm=8765

Writer:

ymatsu

Testers:

PabloGilberto , Andrew_Lazarev , ivan_metelsky

Problem categories:

Dynamic Programming