PROBLEM LINK:Author: Vasya Antoniuk DIFFICULTY:Simple PREREQUISITES:Logic PROBLEM:There are ten balls and five colors. There are two balls for each color. Each ball weighs 1kg, except for two balls of the same color, which each weighs 2kg. Your task is to determine which colored balls are heavier. You can use a weighing scale which measures the exact difference in the weights of the objects between its pans. Your score is determined by the number of times you used the scale. (The fewer times, the higher score.) QUICK EXPLANATION:On the first pan, place two balls of color 5 and one ball of color 4. EXPLANATION:ScoringWhat's noteworthy in this problem is the atypical scoring method. Instead of the usual subtasks where each subtask has different constraints and point allocation, here the points depend on the number of times you used the scale. Specifically, the scoring looks more like a "challenge" problem:
As we can see, the fewer times we use the scale, the higher points we get, so we strive to minimize the number of times we use the scale. Simple SolutionsGetting a positive score for this problem is actually quite easy. We can just guess that the heavier balls are of color 1, since this is true in one of the cases! This gives us $100$ points for that case and $0$ for the rest. Another advantage of this is that this is very easy to implement. In Python, this just requires two "print" statements:
But some might think that this solution is not very honorable because we're not guessing correctly for all problems. Thankfully, it's also easy to come up with an algorithm that gives us positive points for all test cases. We can just check the exact weight of each color type using the scale! You can write a long ifthenelse chain for this one:
Alternatively, you can just use a loop:
Here are some implementation notes:
For comparison, in C++, we can implement it this way:
Now, let's see how many points we get for this solution. If the heavier balls have color $c$, then we will use the scale exactly $c$ times, because we will have to use the scale for each color before $c$. Thus, we get $100/c$ points. Overall, we get $100/1 + 100/2 + 100/3 + 100/4 + 100/5 \approx 228.33$ points, which is much better than our earlier $100$ points! We can slightly improve this by noting that if the heavier balls have color $5$, then we don't have to do the fifth usage of the scale. After using the scale four times and knowing that none of the first four colors are heavy, we can infer that color $5$ must be the heavier balls! See the following implementation:
The number of points we get is $100/1 + 100/2 + 100/3 + 100/4 + 100/4 \approx 233.33$, which is a little better! Better solutionsLet's now try to reduce the number of uses of the scale some more. Strategy 1: First, let's place a ball of color $1$ and color $2$ on the first pan, and a ball of color $3$ and color $4$ on the second pan. What would happen then? There are five possibilities:
This means that if the result was $0$, then we immediately know that color $5$ was heavy. If the result was $1$, then either color $1$ or color $2$ is heavy, and if the result was $1$, then either color $3$ or color $4$ is heavy. In both cases, we can use just one more comparison to figure out which one it is! To summarize our algorithm:
Here's a possible implementation in Python:
Let's now figure out our score. In four out of five cases, we use the scale two times, but in the remaining case (color $5$), we use it only once. This gives us a score of $100/2 + 100/2 + 100/2 + 100/2 + 100/1 = 300$ points! Strategy 2: Let's try attacking the problem simplistically by comparing two balls at a time. First, try comparing color $1$ and color $2$. If one of them is heavier, then we already know the answer. Otherwise, we know that the answer must be either $3$, $4$, or $5$. In that case, let's try comparing color $3$ and color $4$. Again, if one is heavier, then we already know the answer. Otherwise, we know that the must be $5$. Done! Here's a sample implementation:
Now, let's see how many points this solution gets. If either color $1$ or color $2$ is heavy, then we only use the scale once. Otherwise, we use it twice. Therefore, the score is $100/1 + 100/1 + 100/2 + 100/2 + 100/2 = 350$ points. The best solutionIn fact, a score of $500$ points is achievable! To do so, however, we must figure out the correct answer within just one usage of the scale. To do that, we must find a usage of the scale with $5$ distinct results, depending on the color of the heavy balls. To begin, let's take a look at our $300$point solution above, where we initially compare $[1,2]$ and $[3,4]$. If color $5$ was heavy, then we don't need further usages of the scale. However, if color $5$ wasn't heavy, then we were left with two cases, each with two possibilities, and we were forced to use the scale another time to figure out which of these possibilities were the real one. For example, if the result of comparing $[1,2]$ and $[3,4]$ was $1$, then we know that either ball $3$ or ball $4$ was heavy, but we don't have any more information to figure out which one of them was heavier, based on the initial comparison alone! It would be great if we can distinguish these two cases somehow. Thankfully, there's a way to modify the initial comparison to do just that! Instead of comparing $[1,2]$ and $[3,4]$, we compare $[1,2,2]$ and $[3,4,4]$; in other words, we put one ball of color $1$ and two balls of color $2$ in the first pan, and one ball of color $3$ and two balls of color $4$ in the second pan. This way, the five possibilities are:
Notice that each case results in a distinct result! This means that we can know the answer with just one usage of the scale. Here's an implementation:
Since we only used the scale once, our score is the maximum possible: $500$ points! We can slightly modify this so that the solution looks cleaner:
Or, more compactly,
Time Complexity:$O(1)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 10 May '16, 02:34

This was a cute problem! At first, I took 4 attempts where I had to put the balls one by one on the left pan while I put nothing on the right pan. So if I get 2 as the difference, then I will determine that ball as the odd one out, and if I dont get a 2 on the first weighing then I will determine the unweighed ball to be the odd one out. But then I thought that there are 100 points and someone has to get a 100 points, it is not there for show only. And the bet I could come up with was 2 weighings where I took '1' and '2' in the two pans at first, and if there was a difference of 1 or 1 then I could immediately determine the ball which was odd. Else in the second weighing we will take ('3','4') in the left pan and ('4','5') in the right pan, and '3','4' or '5' is the odd one accordingly as the difference is 1,0 or 1. But suddenly, the second weighing I used gave me an idea, that I could actually cancel the odd one out with itself to get a '0', so a little bit of thinking gave way to the solution described at first. I take ('1','2','2') in the left pan, ('3','4','4') in the right pan, so that '2','1','5','3' or '4' is the odd one accordingly as the difference is 2,1,0,1 or 2. Here is my solution: https://www.codechef.com/viewsolution/10060839 answered 16 May '16, 20:40

is it not possible to make a submission to this problem now? All my submission show System Error!