Stock Exchange Losses puzzle discussion

Puzzles
#14

first test get error even if i print real answer (Python)

#15

Do you print it along with an end of line ?

#16

I must be somehow fundamentally misunderstanding the requirements on this one. All 5 of the tests pass in the IDE, but when I submit, then grading test #1 fails:

Case (4 3 5 2 1 6) -> -4 (300 pts)

Looking at the data, it seems to me that my algorithm is working correctly. The largest loss in this dataset is from 5 (3rd entry) to 1 (5th entry). My program prints out “-4”, as shown. Is this not the correct answer?

  • dan
#17

Never mind. I figured out the problem through trial and error (lots of submissions). There must be an extraneous space in the input of the first validation test for that problem. I had been just doing a split on " " (single space) to get the input integers and then looping through the result, but that made me overflow my array (more than n results from the split operation).

Once I put some defensive logic into this part of my program, then I’m able to pass all the validation tests. Unfortunately, since I can’t get any debugging info from the validation tests, it’s hard for me to know exactly what about the input my program didn’t like.

  • dan
#18

I found bag in this task (in first test) n==5 but array has 6 numbers

#19

Wow. Was using LINQ’s TakeWhile and Last methods, everything was fine, but fifth was failing.

It forced me to think a bit what i get in those number ranges :smiley:

Bug in "Stock Exchange Losses" puzzle?
#20

I agree with your assessment, @alexxx_was. I was wrong about extra spaces in the “vs” string. The first validation test has n=5. To test this theory, I submitted the following Java:

public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    in.nextLine();
    String vs = in.nextLine();
    System.out.println(Integer.toString(-(n-1)));
}

This code passes the first test only with “correct” output: “-4”. The test is providing invalid input.

  • dan
#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