Minimum Swaps To Make Sequences Increasing

  • 0

    Click here to see the full article post

  • 0

    would u please explain why one step local decision could lead to the global minimum for the second case where a1 < b2 and b1 < a2?
    like 1 3 8 5 ...
    2 7 4 9 ...

    for (3, 8) and (7, 4), A or B could get (3, 4) (7, 8) , how do you know one decision would cause the final optimal solution?

  • 0

    Could you please explain a bit on the second if condition (second possiblity) ? I didn't quite understand the thought process behind it.

  • 0

    I am confused about this solution, could you elaborate more?

  • 0

    I didn't thoroughly understand the second if condition as well, could you please explain more about that or give a more precise example, thank you a lot!

  • 2

    @beyourself @shriram2112 @proenca @Bug_Exceeded I will update the article shortly, but here is the idea:

    First, let's work through an example.

    Say we have
    A = [1, 3, 8]
    B = [2, 7, 4]

    At the beginning, just looking at one column, the cost to end in column (1, 2) is natural = 0, and the cost to end in (2, 1) is swapped = 1. (Cost can be infinity if it's not possible.)

    Now, when i = 1, if we ended in (1, 2), we could end in (3, 7) for no cost; we could end in (7, 3) for 1 cost [the cost of ending in (1,2), plus swapping the second column]; if we ended in (2, 1), we could end in (3, 7) for no additional cost [total cost 1], or end in (7, 3) for 1 additional cost [total cost 2]. In total, ending in (3, 7) has lowest total cost 0, and ending in (7, 3) has lowest total cost 1.

    Now, when i = 2, if we ended in (3, 7), we can't end in (8, 4) because the sequences won't be increasing [specifically, B won't be]. We could end in (4, 8) for an additional cost of 1 [total cost 1]. If we ended in (7, 3), we can end in (8, 4) for an additional cost of 0 [total cost 1], and we can't end in (4, 8) because A won't be increasing. In total, ending in (4, 8) has lowest total cost 1, and ending in (8, 4) also has lowest total cost 1.

    I know these above paragraphs are kind of confusing, but here is a recap:
    Cost to end the first i columns with the i-th column not flipped: 0, 0, 1
    Cost to end the first i columns with the i-th column flipped: 1, 1, 1

    Now to answer a question about what the second if condition means. It means "if you swap column i, and both A and B will become increasing from the (i-1)th column to the i-th column". In the worked example, when i = 2, we had n1 = 0 and s1 = 1 from before (from the end of the i=1 for-block). Then, the first if condition fails, but because of the second if condition, we were able to deduce that n2 = s1 : that the cost n2 of having a legal sequence up to column i that ends with column i not flipped, is going to be the cost s1 of having a legal sequence up to column i-1 that ends in column i-1 flipped, and a similar explanation for s2 = n2 + 1.

  • 0

    Very smart solution, thanks!

  • 0

    Thanks for your solution and explanation!Really cool!

  • 0

    @awice Does the order of the if statements matter?

  • 0

    why float "inf" ?

  • 0

    flot inf is the pythonic way of getting the largest maximum integer. That is useful where you are comparing numbers and want to initialize a variable in a way it is not going to affect the comparisons.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.