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.
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.
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 ?
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.
[SPOILER!!!]
Here is a 4-step linear-time solution:
Load prices into an array (prices), size n
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
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.
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 !
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.
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