Feel free to send your feedback or ask some help here!
Well, someone should start this topic too. At First I thought this was a linear programming problem, but it timed out even before I could read all the input into a matrix. Then I managed to solve this with a more back to earth method.
Linear programming only required to solve a more general problem version of this challenge when starting dates could be delayed.
I just tried to solve this with an iterative dynamic programming method. It looks like it is way too long as well.
Dynamic programming method is often used to solve integer linear problems, like knapsack or cutting-stock problem.
Yep. Well the method can be applied there and works pretty well. But it is way slowlier than the “good” method which is kind of … “dumb” unfortunately.
I came here to see if other people found this problem “hard”. I believed it would be more appropriate to put it in the “medium” section of problems.
It took me much much less time than the other “hard” problems to solve (and probably less time than even all “medium” problems). But maybe I’m biased by the fact I know a lot about algorithms.
Something wrong with submit time counter. It wasn`t 11 minutes!
I can’t find a solution myself, to which algorithm you know is this one similar to ?
(replying to myself…)
Ok got it, had some bug in my implementation, but my algo is correct. Done with C++/STL, filing a vector : O(n), sorting that vector : O(nlog(n)), testing elements in that vecor in one pass : O(n). Overall : O(nlog(n))
I think the same as Sparhong. This is a very easy problem. It took me 20 minutes and only 15 lines of code with Python
Explain pls!. How I can optimize this JS code? I have no idea… Final Score 87%
// Moderated : No full code please
I use python too. When I read your post, I couldn’t believe it. I was hours and 80 lines into it and it still was too slow.
But then I thought I must have missed something simple. And the solution came.
You were right : 20 minutes, 15 lines. I would never have thought it possible !
I can’t figure out why my algorithm is not optmized enough…
edit: a missing “break” inside the loop was causing the problem. Now it takes a few miliseconds to run it using Python
Computer2000 DataСenter is very popular, as far as i can see
people plan calculations there 2740 years ahead, and total amount of bids for calculations is as high as 13700 years!
My first thought was also to use dynamic programming and I was proud of my implementation but then I realised that N could reach 100000 and 100000^2 = 10000000000, which means that a O(N^2) solution can’t pass all the tests.
I think this problem can stays here (hard problems), it’s not because the solution is freaking easy to implement that the solution is easy to find.
I also spent a week thinking about this challenge, trying to transform it into a color problem on graphs, but my incomplete solution was too long to compute for the last test. And trying to optimize it, I realized that I was just doing EDF.
I first though about EDF, but since I’ve not used it since I was a student, I thought it didn’t apply because I was more an algorithm to minimize how late you are at the end of each task. And I thought it wouldn’t be a hard problem if it was that simple.
In the end, it is one of the shortest program I’ve made for codingame.
the fact that this problem is in hard section kept me thinking that the solution can’t be too simple so i spent a couple of days trying a lot…then i checked the forum discussion and i got to know that the solution is simple so i tried something simple and it took me 21 lines (literally) for this code in python…had this problem been in medium section i wouldn’t have tried so much…i needed a vector to input the starting and ending days and then sorting and comparing did the job for me…feeling happy since i was trying too much and the solution came out to be simple
If you spend days thinking by yourself how to do it, even if the final solution is trivial, then I think the problem deserve to be in the hard section.
yup…i think you get learn new methods of solving problems…as the more you try the more you learn