Happy April Fool's!
Posted on by ejames
If you’d visited our site yesterday, you would have seen a command line interface, and a link to a premier Computer Science quiz competition called HackyWin! Here’s the email we sent out to the mailing list:
The NUS Hackers are proud to present a premier quiz competition that's targeted at computing students!Simply solve 3 questions to win an iPad 3.
They are guaranteed fun brainteasers, so give them a try. You might be able to solve them and win an iPad 3!
We gave three programming questions to people, all of which required solutions that worked under a minute and dealt with all cases to be correct. Here are the questions:
Problem 1: Dr. Black has been murdered. Detective Jill must determine the murderer, crime scene, and weapon. There are six possible murderers (numbered 1 through 6, Professor Plum to Mrs. Peacock), 10 locations (1 through 10, ballroom to cellar), and six weapons (1 through 6, lead pipe to spanner). Detective Jill tries to guess the correct combination (there are 360 possibilities). Each guess is a theory. She asks her assistant, Jack, to confirm or refute each theory. When Jack refutes a theory, he reports that one of the guesses — murderer, location, or weapon — is wrong. The contestants are tasked with implementing a procedure that plays the role of Detective Jill. A brute-force program that tests all 360 theories earns a mere 50 points. An efficient program that tests no more than 20 theories earns an additional 50.Problem 2: You have bins of capacity V, and n items each of size A1≤i≤n. Find the minimum number of bins you need such that the total size of items in each bin does not exceed its capacity. Hint: this is a packing problem.
Problem 3: You have any number of N points on a table. Your goal is to write a program to connect all of them by lines of minimum total length in such a way that any two points is interconnected by line segments — either directly, or indirectly via other points and line segments.
If you think about it for a bit, you will realize that the connecting segments do not intersect each other except at the endpoints and thus form a tree.
This was, of course, and April Fool’s joke. When you clicked submit, you were redirected to this page, which explained the answers to the 3 problems (2 of which were unsolvable given the constraints).
Solution for Problem 2: Also known as the Bin Packing problem, this problem is combinatorially NP-hard. That said, optimal solutions to very large instances can be produced with sophisticated algorithms, and non-optimal ones also exist, such as the first fit algorithm. Because this question demands an optimal solution for all cases, no solution you provide will be correct given a 1 minute constrain and an arbitrary number of items, each of any size. (Well, if you had access to a supercomputer it might, but that's a tad too much ...) Read more at Wikipedia!Solution for Problem 3: This problem, also known as the Steiner tree problem, is NP-hard for general N (which is exactly what this question was asking for)! In fact, an expression of this problem was among Karp’s original 21 NP-complete problems. As an interesting aside, computer science folklore has long held that soap film, applied to a series of glass plates may solve this problem where computers may not. See this paper for more.
We hope that you’ve spent some time thinking about Computer Science problems you might not have otherwise known of, and …
Happy April Fool’s!