Cycle string
Tag(s):

## Algorithms, Dynamic Programming, Easy-Medium

Problem
Editorial
Analytics

Given two cyclic sequences $A$ and $B$ each of length $n$, consisting of 0 and 1. In cyclic sequence $a_{i+1}$ comes after $a_i$ and $a_0$ comes after $a_{n-1}$. In a single turn you can flip three consecutive elements: $a_i$, $a_{(i+1)\bmod n}$ and $a_{(i+2) \bmod n}$. Flipping element is altering its value: if it is 0, it becomes 1, and vice versa. What is the minimum number of turns you need to make to obtain sequence $B$ from $A$?

Input format

First line of input contains single integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of $A$ and $B$.

The second line of input contains $n$ integers $a_i$ ($0 \leq a_i \leq 1$) — sequence $A$.

The third line of input contains $n$ integers $b_i$ ($0 \leq b_i \leq 1$) — sequence $B$.

Output format

Print single integer — number of operations if it is possible to obtain $B$ from $A$. Otherwise print "Impossible" (without quotes).

SAMPLE INPUT
4
0 0 1 1
1 0 1 1
SAMPLE OUTPUT
3
Explanation

Sequence of turns in the example is

• $(0, 0, 1, 1)$ - sequence $A$
• $(1, 1, 1, 0)$ - $1$, $2$ and $4$ are flipped
• $(0, 0, 0, 0)$ - $1$, $2$ and $3$ are flipped
• $(1, 0, 1, 1)$ - $1$, $3$ and $4$ are flipped, sequence $B$
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Math > Number Theory
• Algorithms > Graphs
• Algorithms > Graphs
• Data Structures > Advanced Data Structures