ReversalChain

SRM 400 · 2008-05-01 · by ymatsu

SRM 400 · 2008-05-01 · by ymatsu · Dynamic Programming

Show categories

Class Name: ReversalChain

Return Type: int

Method Name: minReversal

Arg Types: (string, string)

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(i₁, j₁), r(i₂, j₂), ..., r(i_m, j_m) is a reversal chain if i₁ <= i₂ <= ... <= i_m, and j₁ >= j₂ >= ... >= j_m.

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.

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

"1100"
"0110"
Returns: 1

r(0, 2) transforms "1100" into "0110".

"111000"
"101010"
Returns: 2

r(1, 4) and r(2, 3) transforms "111000" into "101010".

"0"
"1"
Returns: -1

It is impposible to transform "0" into "1" by a reversal chain.

"10101"
"10101"
Returns: 0

You do not have to do anything.

"111000111000"
"001100110011"
Returns: 4

10)

"001000011000000111000000001111"
"001001001001001001001001001001"
Returns: 8

rev: 6 29 rev: 6 26 rev: 9 26 rev: 10 24 rev: 12 23 rev: 15 23 rev: 16 21 rev: 18 20

Submissions are judged against all 171 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ReversalChain with a public method int minReversal(string init, string goal) · 171 test cases · 2 s / 256 MB per case