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.