Super Computer puzzle discussion

I must admit I used 61 lines of Java, but otoh I did it Properly™ with a smatter of object orientation. :wink:

And I agree, it is startingly simple once you find the right algorithm. Kind of a bummer, to be honest.

The simplicity of the solution will surprise you once you find the correct way of solving it. Honestly I got a bit annoyed after spending an hour to reach 88%, then went to the forum looking for hope that it can actually be solved. Read the comments praising how easy it was. Not much relief but got the belief I needed, went back to my code thinking how to make it even simpler. 15 minutes later - it worked! BEAUTIFUL

2 Likes

Hello,

I have a strange problem : when I submit my solution, I have 100%. But if I test with “Large number of scientists”, I don’t find the right solution (a difference of 1 with the right solution). Can someone help me?

Thanks !

This problem statement is clearly broken. The example has typos and is missleading.
It tells you one job cannot start on same day another job ends, which doesn’t match the solution accepted.

This can be a very simple and well classified hard problem.
Plz fix it.

-edit-
Ok, eventually I figured my missinterpretation about the off by 1 situation here. A simple example can demonstrate this. On a job that starts at day 2 and has duration 3, it ends at day 4 instead of day 5. It runs on days 2, 3 and 4, for a total of 3 days.

Still, plz consider fixing the little typo on the problem statement on calculation C.

2 Likes

For anyone getting stuck with this due to timeouts; the problem is likely more straightforward than you’re imagining.

Are we sure we need to schedule experiments that are going to start in more than 2 thousands years?

3 Likes

Not sure if someone has already mentioned it at this task or at different tasks, but I don’t find the timeout limit fair, if it’s set the same way for all programming languages. I implemented the algorithm in Groovy and got only 75% because of timeout. Then I rewrote it the very same way to Java and got 100%.

So I’d recommend either setting the timeout limit according to the language, or set it the way that the big test cases fail for any programming language, if it has let’s say quadratic time complexity, but let the slower programming languages pass.

1 Like

Omg, I took 11 months to understand why my code wasn’t working on the last testcase. That was only due to the way I was chosing my pivot in my quicksort…

this link helped me to solve this problem : http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/

3 Likes

Did someone try to solve the problem with a Genetic Algorithm, I think the task is perfect for classic GA with 0 and 1 encoding, but for the third test case I couldn’t get in the time frame just for initialization of the first random population.

This link is not just a hint, it is the solution itself to the very same problem, with example codes in 4 languages…
Without this hint I a bit overcomplicated it, and implemented Hudgson’s algorithm which is fine but timeouted for large datasets…

1 Like

Agree with @TBali. This link is direct solution. Anyway it’s common greedy algorithm problem :slight_smile: and the greedy agorithm is even mentioned in “skills” section, so it shouldn’t be that hard to find the solution.

I have succeeded also to implement the solution in Swift with this link also, thanks :slight_smile:

Is there a hint as to what the “Large number of satisfied scientists” means? And how it differs to the “Large number of scientists”

It’s the only validator mine is failing at, and I’m trying to work out if it’s an optimization issue, or if there’s an extra edge case I need to be considering.

same size as the other test but the expected output is much higher. Hope it helps!

1 Like

It does not help. While it is great to have the real tests hidden, you must request that the problem creators to have similar tests in the provided test cases. A simple solution will be to add a similar case with the one indicated in the test cases.

Creator is CodinGame for this one :rofl: .

1 Like

Hi,
ADVICE: Do not implement your own sort (except if you want to do a very complex one - better than standard quick sort)
I tried to write the quick sort myself in Java, C, and JavaScript. None passed the last test when submitted. Sure, I can start adding various optimizations to it and maybe it will pass.
I changed creating objects and using the Arrays default sort method in Java (more optimized than the typical quick sort). It worked. So, the issue is the difference between the standard array sort in the Java library, which is a little faster than a typical quicksort that you will write.
To have a puzzle that gives you 100% only if you use the standard library does not seem a good idea. Moreover, there is no error reporting to indicate that the issue is the speed and not the logic.
This is a classic puzzle (I wanted to give it to my students), but is so poorly designed that I will not…
Hope you will consider to improve it:

  • add more tests
  • if you want to keep the timing, add a test that will time-fail if not using a standard sort library.
  • in general, when a test fails, will be good to mention if it was wrong result, or over-time (5 minutes of coding on your side, saves hours of wondering for your users…)
1 Like

Thank you for your example. This threw me too.

I love the solution to this problem, it is very elegant but far from easy to think of. It shows the importance of knowing how to solve lots of different puzzles and algorithms.