Turbo87/algorithm.md

## algorithm.md

      
    Raw
  

              algorithm.md
            
          
    Problem


We have an ordered list (P[]) of XYZ points (N = around 10 000 points)
We need to find the seven points (A-G, in order) of that list that have the largest total XY distance between them (AB + BC + ... + FG)
The Z distance between A and G must be below 1000 (A.Z < G.Z + 1000)

see https://www.onlinecontest.org/olc-3.0/segelflugszene/cms.html?url=rules_overview/b2_en (Section 4.3.1)
Naive Solution

Calculate the distance for all possible solutions and keep track of the best one.
This solution does not scale well, because we need to investigate roughly 10 000^7 (= 10 000 000 000 000 000 000 000 000 000) possible solutions, which would take forever, even on a reasonably fast computer
Complexity: O(n^7)
Slightly better solution

We can split up the work into multiple steps:


For each potential point B:

For each potential point A:

we calculate the distance AB


we save the maximum distance AB and what potential point A would fit best


For each potential point C:

For each each potential point B:

we calculate the distance BC
we lookup the distance AB for the potential point B
we sum up AB and BC


we save the maximum distance (AC = AB + BC) and what potential point B would fit best


For each potential point D:

For each each potential point C:

we calculate the distance CD
we lookup the distance AC for the potential point C
we sum up AC and CD


we save the maximum distance (AD = AC + CD) and what potential point C would fit best


...

For each potential point G:

For each each potential point F:

we calculate the distance FG
we lookup the distance AF for the potential point F
we sum up AF and FG


we save the maximum distance (AG = AF + FG) and what potential point F would fit best
we find the point G with the highest distance AG, by looking at the corresponding point F, point E, ... point A we can figure out what the best path is


Complexity: somewhere between O(n) and O(n^2) ?
This solution ignores the third constraint though. If we only discard solutions in the last step we might have missed better solutions in the intermediate steps.
Working solution

We use the algorithm above, but not for A-G. Instead we only run it on B-F, to reduce the part of the graph in the middle where we do not have any other constraints. This way the problem reduces to:

For each potential point A:

For each potential subsolution BF:

For each potential point G:

Skip if A.Z >= G.Z + 1000
Compare to previous best solution for AB + BF + FG and save if better


Complexity: somewhere between O(n^2) and O(n^3) ?
UPDATE: Turns out I missed something and this solution does not work either 🤦‍♂️