Click here to see the full article post
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?
Could you please explain a bit on the second if condition (second possiblity) ? I didn't quite understand the thought process behind it.
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!
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.
@awice Does the order of the if statements matter?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.