Stock Exchange Losses puzzle discussion

Puzzles
#42

I do not understand what went wrong.

Maximum Loss between the first and last values (10 6 8 4 6 2) -> -8 (100 pts)

I pass all the tests, but after it is marked as not completed. Please tell me where to look?

#43

What is your answer for such a case?

#44

If I debug code on my computer with the data set ā€œ10 6 8 4 6 2ā€, I have the answer -8. Why it does not work online?

#45

Have you tried your code with another similar data set?

#46

There was an error in the assignment of a variable input string. I used the ā€œ$$string = str_replace (ā€\n", ā€œā€, $inputString);".

Two dollar sign is incorrect assignment. On the other examples, it worked fine, but in a sequence of ā€œ10 6 8 4 6 2ā€ do not escaped characters ā€œ\ nā€.

Thank you for your participation. But the mistake was only my carelessness.

#47

Hi everyone, seems my code is timing out, when it seems to be O(n)

Hereā€™s how it works : initialise 2 integer : mx as vs 1st integer and maxdif as 0;
then loop over every integer in vs
if mx < current integer then mx = current integer
maxdif = max between maxdif and mx - current integer
end of loop

return -1 maxdif* ( for the minus sign)

Does someone have and idea ? Iā€™ve used stoi and substr to get the integer from string vs

EDIT : The problem came from stoi, which is a O(log(n)) algorithm. Thanks to previous comments, i saw i can change the input from string to int. !

#48

Could you pastebin your code? So we can help.

#49

No full code allowed in the forum, use Private Message or the IRC chan :slight_smile:

#50

Itā€™s already solved, see the EDIT line.

1 Like
#51

My c++ o(n) solution, store the index of min, max point may easier.

 struct StockInfo
{
Ā  int index;
Ā  int value;
Ā  StockInfo() : index(-1), value(-1)
Ā  {}
Ā  StockInfo(int i, int v) : index(i), value(v)
Ā  {}
};
#52

I have encountered a problem with test 5.
All the other tests finish successfully, and test 5 finishes in time.
The problem is i get the result of -956205247;
I am really confused. Has anyone else got this result?

#53

i need you to check for a possible bug
in Go, 5th test not passing - input vs string is empty

scanner.Scan()
vs := strings.Split(scanner.Text(), " ")
fmt.Fprintln(os.Stderr, len(vs))
#54

As others have said you can use the brute force method if you put in a pretty simple trick. Think about it.

#55

Itā€™s worth noting that the template provided for Go is unsuitable for Test 5. scanner has a hard coded limit for scanner.Text(). Even using reader.ReadLine() is a pain due to it not reading in one call (possibly splitting a number between two calls).

Anyway, I switched to using reader.ReadString(ā€™ ') in a loop till I had read n values. (The last picks up the newline, so strings.TrimSpace() ontop of that.)

I would advise changing the templateā€¦ unless thatā€™s part of the puzzleā€¦

2 Likes
#56

How it can be On complexity?

I solve this problem overlapping FOR sentence ,which means O(N^2).

Can anyone give hints to me?

#57

Thankyou, I was banging my head about this till i read your comment. There is an easy fix though if you switch to a different Split function for the Scanner (based on words instead of lines) before you call .Scan()

#58

In my O(n) solution I did this:
For every number you read just keep register of a couple of values. A very important one is your last ā€œdropā€. That means the last time the current value was less than your previous one.

For every value you read:

A) If you go down (against a previous value) keep track of min/max values against the current one.
Simultaneously I kept track of a difference value between the current-max and the current one, keeping always the highest one.

B) When you go up you read one extra value ahead (if itā€™s available) and check if itā€™s a drop (smaller than the current one). If itā€™s so you can check against your last ā€œdropā€ and update it.
(Also update your current-max value in these cases.)

At the end youā€™ll got a last drop value, a scoped min/max value and a drop-diff value. With those three you can calculate the puzzleā€™s loss. Itā€™s just a couple of conditions.

Just wanted to give you some hints as you asked. Hope I didnā€™t spoiled it.

1 Like
#59

Hi, Iā€™ve got problem with the big set. This is my algoritam for it . Iā€™m writing it on C# . Can somebody tell me whats wrong with my logic, because Iā€™m stuck :confused: :

for (int i = 0; i < listOfIntegers.Count - 1; i++)
{
if (listOfIntegers[i] - listOfIntegers[i + 1] > 0)
{
listB.Add(listOfIntegers[i]);
}
else
{
listB.Add(listOfIntegers[i]);
difference2 = listB[listB.Count - 1] - listB[0];
listOfDifferences.Add(difference2);
listB.Clear();
}
}

        biggestDifference = listOfDifferences.Min();
#60

Hi, @iordan_g:

As you can read in the replies provided above, i can see your algorithm is O(n^2), and that is too slow for the solution. You have to find the way to get solution with O(n) (Using just the initial for clause ;-), in example).

Other point to solve, is refactoring. As you see, the line:

listB.add(listOfIntegers[i]); is called both in if and else clauses, then you can put it before the if clause, like this:

for (int i = 0; i < listOfIntegers.Count - 1; i++)
{
listB.Add(listOfIntegers[i]);
if (listOfIntegers[i] - listOfIntegers[i + 1] <= 0){

difference2 = listB[listB.Count - 1] - listB[0];
listOfDifferences.Add(difference2);
listB.Clear();
}

and, lastly, this exercise is about the maximum ABSOLUTE lost, not a relavite one, between all the wins and losses ;-). I hope it can help you,

#61

Hi guys,

I liked this puzzle a lot and wanted to share my solution and how i did it. I coded in C#

As all of you guys did, i put all the values in a list ( array would also work ). I found the solution with only one for loop. Outside of the for loop, i defined 4 variables, 3 being integer and 1 being a boolean. Those variables are: int heighestValue, lowestValue, deltaValue and bool valuesChanged.

I initiated this variables with;

heighestValue = 0
lowestValue = int.MaxValue
deltaValue = 0
valuesChanged = false

In the for loop, i first compared the value in the list with the heighestValue, if the value in the list is higher than the highestValue (which in the first time it would always be higher because highestValue initiated with the value of 0 ) i set the heighestValue to value on the list. I also set the boolean valuesChanged to true.

If the value on the list is not higher than the heighestValue, i compared it with the lowestValue. If the value on the list is lower than lowestValue, i set lowestValue to the value on the list and i set the boolean valuesChanged to true.

After comparing those integers, i checked if valuesChanged variable is true. If it is true i calculated the currentDelta

int currentDelta = lowestValue - heighestValue

Because of the solution wants the answer in negatve, i decided to just substract the heigher value from the lower value.

After finding currentDelta, i compared it with the deltaValue variable that i defined before the for loop. If currentDelta is smaller than the deltaValue, i set the deltaValue to currentDelta. After this if statement i reseted the value of lowestValue to int.MaxValue, the reason behind that is i dont want any other higher values after this value to interact with this lowestValue. If you do not set the lowestValue to int.MaxValue ( it doesnā€™t have to be int.MaxValue, but it is good to be safe), as can be seen in the first example, it would subtract the last value of 5 from the previous value 1 and resulting a currentDelta of -4. That is why you need to reset the lowest value for each valuesChanged.

I will write my code down just in case of if i couldnā€™t explained it well. I am a non-english speaking person, so i really suffer writing anything in English. Good luck :slight_smile:

[[EDIT: NO FULL CODE]]

2 Likes