Stock Exchange Losses puzzle discussion

Puzzles
#129

Can anyone help with the code because I just keep trying and I just can’t pass all the tests and I ran out of ideas. Please

#130

I could really use some help on this one. (5th case to be precise).

So I create one loop to go through all the values and find the highest peak.
That being 1073738403 on the 77399 position (starting from 0 obviously).

Then, I made another loop that goes from [77399] to n and looks for the greatest difference between 1073738403 and every value after [77399]. And that gives me -1073710171.
Lowest value is [98396] => 28232.
But according to the test case, the result should be -1073730311.

What am I missing here?

#131

Check test case 6 - the algorithm you’ve described won’t work there and it’s much simpler to debug.

#132

it passes the 6th one

#133

I don’t see how if your description is correct (peak would be 15, only value after peak is 14).

For test 5 the maximum loss is buying at position 24504 ($1073734557) and selling at position 30750 ($4246)

1 Like
#134

ok. I get where I made the wrong initial assumption. back to the drawing board. thanks

1 Like
#135

Hello coders, I need some help on the theory for this one. So for context I defined member point(time,price) Passing the first 5 tests was pretty straight forward by choosing P0 as the point with the lowest price, but of course that doesn’t help me pass test6. I was able to pass test 6 by choosing p0 to be the point in the line with the lowest slope, however the first 5 tests failed. It is clear to me that P0 is not a constant but how do I go about choosing it correctly. Please help me understand what it is I am missing.

Thanks in Advance :slight_smile:

#136

So, I have the logic set up perfectly fine in my program, but test case 5 still won’t work due to a overtime error, any ideas on how to fix it?

#137

My solution is pretty straight forward (sorry for the ugly MS paint diagram):

image
image922×546 4.69 KB

Spoiler

First, find the pivot point which is the min value of the array.
Then calculate the max loss for the left part of the array and assign it to the current max loss.

If the max stock value on the left is greater or equal the max stock value on the right, return the max loss and exit.

If the max stock value of the array on the right is greater than the max stock on the left, then there is a chance the the right array contain the max loss, repeat the process to calculate max loss for the array on the right.

Finally, compare the left and right max loss, we will get the result.
An implementation using recursive is very easy to understand, the hard part is make a tail call version to not blow up the stack.

The complexity of this solution is from O(n) in the best case (you exit at the first recursive call) to O(n^2) if there is only profit and no loss hence preventing you from dividing the array.

For the average case, it it O(kn), 1 < k < n. I am not sure if k can be calculated base on n or not.

#138

My solution was simple in a loop for each iteration
just update the maximum value of till now and maximum dist of array till now
and max dist = max(max dist, max value - curr value)

#139

That cannot be true, since, the most min value could appear before the moxt max value.

#140

sorry for the confusion i have created here just update max value and max difference only

#141

Puzzle is performed without arrays! “WHAT YOU LEARNED” lies :roll_eyes:

#142

Or you can just leave the box unticked if you think you have not learned it by solving the puzzle.

#143

One problem can be solved by many different approaches. The tags are suggestions of possible approaches but they do never meant to be mandatory.

Instead of defaming someone/something lies, it is better to boast how innovative you are to “think-out-of-the-tags”.

#144

I m sorry! I didn’t even try to insult anyone. :pray:
I first wanted to solve with the array, and it only confused me and I spent a lot of time, since it is impossible to perform test case 5 on C++

#145

Never mind.
Array is optional in this simple problem. For more complex problems you may prefer to store all data before processing because you may need to reference previous or next data on-the-fly. In that case, have an array or list of data is handy.

#146

I have no doubt it is! I will also try to resolve issues without using hints. It was a pretty good experience.

#147

After thinking for a while I found that this is easy to do in O(n)

  • Consider your first value the PEAK
  • While you’re iterating the values if the current value is lower than the PEAK, count your CURRENT_LOSS as being the biggest difference from the peak to there
  • If the current value is higher than the PEAK then set the PEAK to that value and reset your CURRENT_LOSS
  • Everytime you reach a new peak, or there are no more values, if your CURRENT_LOSS is higher than the MAXIMUM_LOSS then that is your new MAXIMUM_LOSS
1 Like
#148

This is a fun one. I can argue that I have one of the best solutions for this puzzle.