466. Swaps to Sort Both Rows

Two arrays a and b have the same length. One operation picks an index i and exchanges a[i] with b[i]. Print the fewest operations that leave BOTH arrays strictly increasing, or -1 if no set of operations does.

a = 1 3 5 4, b = 1 2 3 7 -> 1 swap index 3 a = 1 2, b = 2 1 -> -1

Each index is decided independently, swapped or not, so a brute force over 2^n assignments is the obvious first idea and is far too slow. But the decision at index i only has to be consistent with the decision at i-1, because strict increase is a condition on NEIGHBOURS. That makes it a scan over two states.

keep fewest swaps so far, with index i NOT swapped swap fewest swaps so far, with index i swapped

Four transitions, each guarded by the pair of comparisons it needs. Writing x for the value ending up in a and y for the value ending up in b:

keep -> keep needs a[i] > a[i-1] and b[i] > b[i-1] swap -> keep needs a[i] > b[i-1] and b[i] > a[i-1] keep -> swap needs b[i] > a[i-1] and a[i] > b[i-1] swap -> swap needs b[i] > b[i-1] and a[i] > a[i-1]

Look at the middle two: the conditions are IDENTICAL. Exactly one swap among the two neighbours is legal under one test, and which of the two it is does not change feasibility, only the cost. Noticing that halves the comparisons and is a good sign the transitions have been derived rather than guessed.

Both comparisons are strict, and both must hold, so an index where every arrangement fails makes the whole instance impossible. Guard against overflow when adding to an infinity sentinel, or a blocked state becomes cheap and the answer comes out wrong rather than as -1. The test a = 1 2 3, b = 1 2 2 is there because its first two indices need no swap at all and only the last one is impossible.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ value ≤ 1000000000`