QABC - EDITORIAL

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Misha Chorniy
Tester: Hasan Jaddouh
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Observations and simple Invariant would do the trick. Just a creative or experienced mind is sufficient. :smiley:

PROBLEM:

Given two sequence A and B of length N each, we need to apply operation on array A to make it same as array B. The operation is decsribed as

  • Choose any position i in range [1, N-2].
  • Do A[i] += 1, A[i+1]+=2 and A[i+2]+=3. (Called as applying operation on position i.)

SUPER QUICK EXPLANATION

  • Perform operations from left to right. If A[i] > B[i] at any point, answer is -1. Also, If after applying operations till position position N-2, If last two elements differ in both arrays, answer is again impossible.
  • If A[i] == B[i], we can directly move to next position without applying operation. If A[i] < B[i], we apply operation B[i]-A[i] times at position i and move to next position.

EXPLANATION

This problem require certain observations, which are stated below.

If A[i]>B[i] after any number of operations (including zero), answer is impossible since we can never reduce A[i] or increase B[i], hence achieving A[i]==B[i] is impossible now.

Second crucial thing is, that the order of applying operations is irrelevant. That is, Suppose we apply operation at position 2 first, followed by operation at position 1. It will give same results as applying operation at position 1 followed by operation at position 2.

Second observation allow us to apply operations from left to right, because, if a valid sequence of operations exist, there will also exist a perumtation of those operations which are arranged from left to right.

But you might be wondering why should we apply operations from left to right. So, here we go.

Since we know, that A[i] can only be altered by operations applied at position i, i-1 and i-2. But, A[1] can only be altered by operation at position 1. So, we have to apply operation at position 1 B[i]-A[i] times. Now, We face same problem again. A[2] can be altered by operation at position 1 and 2. But we cannot apply operation at position 1 anymore, since it will also increase A[1] leading to impossible case.

Here, we have the invariant, that once we reach position i, we have made A[j] == B[j] \forall j < i, thus, we have to apply operation B[i]-A[i] times, so that We achieve A[i]==B[i]. After applying operations, we can no longer apply operation at any position j, j \leq i. This continues till we reach N-2 position.

At the end, If after appling operation for all positions in range [1, N-2], if elements at last two positions in both arrays do not match, we can never make array A same as array B, thus, answer becomes impossible in this case too.

PS: A new term for today is Invariant, useful in proving correctness of an algorithm or process, which can be read about here.

Time Complexity

Since we iterate from left to right across whole range, Time complexity is O(N).

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile: