Stock Exchange Losses puzzle discussion

Puzzles
#21

My solution in Java just passed all the test cases and there doesn’t seem to be any extra spaces in the input string. So if your solution doesn’t pass then it’s probably a problem in your algorithm so don’t give up and keep trying.

#22

Hello, a problem on test 5 like everybody. I code with C++, and the test times out event before the end of the parsing.
Here is my code for the parsing, theorically in O(n), but still…

int pos=0,last_pos=0;
int stock[n];
for(int i=0;i<n;i++){
   pos=vs.find(' ',last_pos+1);
   stock[i]=stoi(vs.substr(last_pos,pos));
   last_pos=pos;
}

This stops after the 52XXXth iteration, so even if I integrate a very good optimized code it will never do.
If you have any idea,
Thank you.

PS: frustrating because I already solved this problem with an array as input during an interview.

#23

n isn’t defined, so it must have a default value of something like 52252135

#24

That’s not the matter, if n is well defined, it’s still too slow.
The matter is that you use wrong theoricals complexity (find, substr and stoi are not instant operations, it’s in O(n) with n the number of digits max on your integer, so num_digits(2^31)), and theoricals complexity don’t represent reality when you use this kind of function (string operations).
Why don’t you use a classical method to get input, instead of parsing a string? By following the example given on the code by default, you would increase greatly the performances.
There are no interest in parsing a string in this situation : you know how much numbers there will be, and each of them fit on integer. And even if you don’t know how much numbers there will be, use eof, not this.

1 Like
#25

In fact it’s not, a problem of definition, as I said I only send a part of the code for lisibility, no compilation problem here.
But thank’s =)

(maybe I should have quoted my code in a better way…)

#26

Aaaahhhh … Ok. Indeed I don’t know why I get stuck with this “getline” I don’t want…
You opened my eyes on the fact that we can modify the way we retrieve things from cin.

It seems that my computer school made me too scholastic…
Thank you a lot, that should solve my problem !

Just to be sure, the code by default is : (C++)

int n;
cin >> n; cin.ignore();
string vs;
getline(cin, vs);

With “n” number of elements, and “vs” the list with “\s” separators.
So I was following the code by default. The thing you want to told me is that I don’t have to follow it, right ?

Edit : problem solved

1 Like
#28

I solved this in O(n) by looking for the lowest point in the values. Then I go back through the list and look for the highest value before it.

One can trivialy come up with a set of values where this algorithm doesn’t work. Is there a correct O(n) way to do it?

1 Like
#29

I really enjoyed this. The 5th test case was where I was stuck. It turns out the solution was very simple… too simple…

Thanks!

1 Like
#30

I think this one is too easy. I got away with a simple hack ie. assuming the greatest loss always goes to the absolute minimum. I’d expect one testcase giving the following set of values: {4, 1, 1000, 200}.
In this case my code would give -3 though the obviously correct answer would be -800.

So I got my 100% but it felt like cheating.

#31

[SPOILER!!!]
Here is a 4-step linear-time solution:

  1. Load prices into an array (prices), size n
  2. Make a new array (priceDifs)-- could modify old but I’m keeping this as simple as possible – size (n-1) containing the differences between adjacent prices
  3. This is the rather unintuitive step – make an array (maxLosses) containing the minimum gain (maximum loss) to every point. This is done by setting maxLosses[0] = priceDifs[0] and maxLosses[i] to the minimum of priceDifs[i] and (maxLosses[i-1] + priceDifs[i]) for every index i > 0.
  4. Output the minimum in maxLosses.
    e.x.
    prices:
    5, 3, 2, 20, 6, 14
    priceDifs:
    -2, -1, 18, -14, 8
    maxLosses:
    -2, -3, 15, -14, -6
    output:
    -14
17 Likes
#32

I have the same issue as you Dan, I’m using js and doing a split on" "

I got this error which is a correct result…
“Maximum Loss between the first and last values (10 6 8 4 6 2) -> -8 (100 pts)”

Thanks for the answer I’ll try to do what you did and let you know how I go,
Flo

#33

Bonjour,
j’ai un problème avec le test5, n’y a t’il pas un petit soucis avec la réponse ?
je l’ai en erreur :
Fail
Found: “-1073734”
Expected: “-1073730”

Alors c’est peut etre mon code, mais avant de m’arracher les cheveux, je voudrais etre sur car, le problème est qu’il y a pas d’écart possible de -1073730 avec ce jeux de données …

Merci de votre réponse (en dessous le plus grand écart qui est bien 1073734.
Bravo pour le site !

30750 => ‘4246’,
98396 => ‘28232’,
9692 => ‘30241’,
89529 => ‘39669’,

37968 => ‘1073732477’,
24504 => ‘1073734557’,
77399 => ‘1073738403’,

#34

Il faut trouver la plus forte baisse, pas le plus grand écart. Entre 4246 et 1073738403, il s’agit d’une hausse (la première valeur est avant la seconde) mais la plus forte baisse se situe de 1073734557 à 4246, soit la réponse attendue de -1073730311.

1 Like
#35

Hint:Try sorting the array and elements and then think :smiley:

2 Likes
#36

Merci, effectivement,j’avais fait une erreur, mais j’ai encore un problème,je continue a chercher. Merci pour ton aide.

Thank for your help, i trie but, for the moment, i faild !
thank anyway

[EDIT] - j’ai compris mon erreur, merci pour votre aide.

#37

I am sure my code is correct for this puzzle. it satisfies all the tests.but in the validation it fails the last test. i dont understand why. i am so much fraustrated right now

#38

any1 interested to see my code and find the bug?i cant find a bug in my code

#39

@aritramalo Use pastebin in the IRC Chat if you want to.

#40

did you find an error already? i have solved this puzzle, can i have a look too?

#41

Problem solved, he forgot to initialize a variable “count”