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, 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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?