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: Bash, 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, Swift-4.1, TypeScript, 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