class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {


        int sz = A.size();
        int swap = 1, dont_swap = 0;
        for (int i = 1 ; i < sz ; i++)
        {
            int al = A[i - 1], ar = A[i], bl = B[i - 1], br = B[i];
            bool both_increasing = al < ar && bl < br;
            bool if_swapped_increasing = al < br && bl < ar;

            if (both_increasing && if_swapped_increasing)
            {
                int m = min (swap, dont_swap);
                swap = m + 1;
                dont_swap = m;
            }
            else if (both_increasing && !if_swapped_increasing  )
            {
                swap += 1;


            }
            else
            {
                int temp = dont_swap;
                dont_swap = swap;
                swap = temp + 1;

            }

        }

        return min (swap, dont_swap);
    }
};


/*
1 3 5 4 9
1 2 3 7 10

state
whether we swap the element at index i to make A[0..i] and B[0..i] both increasing can uniquely identify a state, i.e. a node in the state graph.

state function
state(i, 0) is the minimum swaps to make A[0..i] and B[0..i] both increasing if we donot swap A[i] with B[i]

state(i, 1) is the minimum swaps to make A[0..i] and B[0..i] both increasing if we do swap A[i] with B[i]

goal state
min{state(n - 1, 0), state(n - 1, 1)} where n = A.length

state transition
We define areBothSelfIncreasing: A[i - 1] < A[i] && B[i - 1] < B[i], areInterchangeIncreasing: A[i - 1] < B[i] && B[i - 1] < A[i].
Since 'the given input always makes it possible', at least one of the two conditions above should be satisfied.




*/