Golden Choice - feedback

Definitely an interesting level, but I had some troubles -

1: It might help to mention that you can start anywhere on row 0; the hint that you have to

Choose only one from the nearest coins in the next row.

was kind of misleading in that respect. Maybe that was just me being stupid.

2: Is this level supposed to consume a huge amount of processing power? This was my biggest problem. With some 5,000 paths to choose from, it takes a lot of stops and pauses in between calculations to even process a section of it, without triggering the “Code too slow” error. I ended up having to just keep submitting until the correct solution was within the slice of the pie that I was analyzing. With a slower computer, I’d imagine this one would be nearly impossible.

Regardless, I thought it was a fun level; it just maybe needs a downsize to the sheer scale of things to calculate.

If you solved it with graph search or recursions, then - yes. It can be solved in O(N) time instead O(2^N).

It can be solved in O(N) time instead O(2^N).

So you’re rewarded if you have an efficient algorithm. I guess that makes sense. How might one go about solving the problem in O(N) time (not specifically, but just in terms of strategy)?

No special rewards, just self-respect because you can :wink:

Hint: Dynamic programming.