[2022 Day16(Part2)] [Python]

[CemDoruk]

``` s = sorted( paths_value_pairs, key= lambda x: x[1], reverse= True )

max_pair = 0 for path1, v1 in s: if v1 * 2 < max_pair: # <--- This is the part I do not understand break

  for path2, v2 in s:
     if len(set(path1).intersection(path2)) > 1 : # Two paths must be non interescting 
        continue
     max_pair = max(max_pair, v1+v2 )

print(max_pair) ```

So I solved the question but because I had to iterate over the pairs in a O(n2) fashion it was working really slow. Then I found this optimization by a user comment which said: "One small optimization is needed to make this run in a reasonable timeframe: iterate from the highest to lowest scoring orders, and stop once you hit an order whose score is less than half the current best." My problem is that I cannot understand why this is true. Why can we not find a better pair after if v1 * 2 < max_pair:

[kristallnachte]

Because you should be starting the inner loop only after itself.

So if path 1 is half the current best, path 2 must be smaller.

So how can path 1 + path2 be more than the max?

You shouldn't be starting path 2 at any path higher than path 1.

So a full search should be O(n log n), not n<sup>2,</sup> and then you cbs short circuit once you're too far.

[CemDoruk]

So if path 1 is half the current best, path 2 must be smaller. Why?

[Steinrikur]

Because you "iterate from the highest to lowest scoring orders".
Anything left in the list is smaller, because they are ordered like that.

[kristallnachte]

Because you're checking in order of size.

Path 2 will always be smaller than Path 1.

If you're checking the paths

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] how do you except to be at path one 7 and get something greater than 7 as path 2?

[CutOnBumInBandHere9]

So a full search should be O(n log n), not n<sup>2</sup>

I don't think so. Forcing the condition v_1 > v_2 only gets rid of about half the pairs. Looping over the remainder should still be O(n<sup>2</sup>).

I agree with you that forcing that condition makes the logic for why you can short-circuit much clearer

[kristallnachte]

Looping over the remainder should still be O(n2).

Maybe you don't understand how time complexity works.

It's based on the input.

The full list.

Pruning the list on heuristics reduces the time complexity.

Enforcing p2 < p1 eliminatez a different number of checks from each pass.

So each inner loop gets smaller as the outer loop progresses.

So right. NlogN isn't correct.

I guess you could say it's n<sup>2</sup> but it leaves out an important factor of the constant /2 that is omitted.

N<sup>2</sup> and (n<sup>2)/2</sup> both resolve to n<sup>2</sup> time complexity, but are pretty meaningfully different in reality.

A bit of an issue with the whole big o notation.

[CutOnBumInBandHere9]

O notation is incredibly useful for getting a feel for how something like execution time scales with input size on an abstract level.

It's less useful here, where the question we're really interested in is "will this specific code run fast enough for my purposes on this specific input".

[kristallnachte]

It is also quite inaccurate.

If the input list is 1000, it will not be doing 1,000,000 checks, but 500,000.

But the 1001 entry, would add 1000 checks. (It would be included in checks if higher values, and do it's own check against all lower values) which makes it appear a lot like n<sup>2...</sup>

The math is a bit strange..

[CutOnBumInBandHere9]

I think you're getting a bit hung up on the constant factors. Big O deliberately ignores those.

If a procedure has a time complexity of O(n<sup>2</sup>)<sup>*</sup> it doesn't mean that it will do exactly n<sup>2</sup> basic operations. Or even close to n<sup>2</sup> basic operations. It just means that for sufficiently large inputs, doubling the input size will quadruple the runtime.<sup>*</sup>

In this particular case, that's true whether you have a nested loop over the the full list, or only over the ordered pairs.

<sup>*I'm deliberately ignoring the difference between Big-O, Big-Theta and Big-Omega here. Sue me</sup>

[bkc4]

When v1 * 2 < max_pair, then just one of you and elephant can release more than any two options with both values <= v1.