All Tracks Algorithms Dynamic Programming Problem

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, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications