#six hours later so Im threading the answer

1 messages · Page 1 of 1 (latest)

slow thistle
#

The optimization is recognizing that while you might have a shit ton of possible paths you could iterate through, the guaranteed longest path goes the same direction the entire time. If you start at pos 1 and go backwards to pos 0, you're decreasing the likelihood that there are things pos>1 that are within reach. On the flipside, starting at 0 and moving to 1 means that you're increasing the likelihood that the next number is within reach. Bouncing back and forth won't get the longest path (unless the diff is humongous)

#

Actually wait I might have read this question wrong holdup

#

J > I+diff

#

Yikes

#

Okay yeah sorry the algorithm we described earlier was close but not right, but the logic still stands

#

Your longest path is always left to right, and you can greedily take the first path every time, no branching

#

So you keep a dictionary of <value, (last pos, current length)>

#

And you ignore numbers if you can't add them to your longest chain

#

^ the proof that that works is, given that you're at an index i where you could add the number to your current chain, and there exists an index j < i+diff that you could also add:

The remaining set of numbers you can potentially add after using pos i is a superset of the remaining set of numbers you can potentially add after using pos j, since j is closer to all remaining numbers in the list

sacred python
#

Still the potential worst case is n^2 even with a greedy approach.

#

It can grow arithmetically to n/2. So you’re iterating through each visited index and will get 1 + 2 + 3 + … + n/2 + n/2 - 1 + … + 1 iterations

slow thistle
#

There's no iterating it's one single pass

#

Only keep track of the most recent visited index

#

Your dictionary contains tuples of (last visited index, current length)

#

At each pos,
lastpos, length = dictionary [ n[pos] ]
if lastpos + diff < j
dictionary [ n[pos] ] = (pos, length+1)

hazy idol
#

I think a simpler way to visualize this is you can break down the original array into buckets, where the key of the bucket is the value, and the entries in each bucket are the indices where said value occurs in the original array

#

insert numbers in each bucket in-order, ofc

#

then just iterate and skip numbers that aren't >= diff units apart

#

more memory, but prob easier to code in some languages cuz u don't need to deal with tuples 🤮

slow thistle
#

that was our first explanation yea