CHBLLS - Editorial

PROBLEM LINK:

Contest
Practice

Author: Vasya Antoniuk
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

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.
On the second pan, place two balls of color 1 and one ball of color 2.
The answer is then the result of the scale, plus three.

EXPLANATION:

Scoring

What’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:

  • There are five test cases. (Each case corresponds to each color being the heaviest.)
  • In each test case where you get the correct answer, if you used the scale K times, you get 100/K points. (If K = 0, then you get 100 points.)
  • The total sum of these points will be your score. (This means that the maximum score is 500.)
  • The score you get for this problem that will be counted in the leaderboard will be (\text{your score}) / (\text{best score in the contest}) \times 100.

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 Solutions

Getting 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:

print 2
print 1

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 if-then-else chain for this one:

import sys
def get_weight(color):
    print 1
    print 1, color
    print 0
    sys.stdout.flush() # we need to flush stdout
    return input() # get the answer of the judge

def answer(color):
    print 2
    print color
    sys.exit() # exit the program

if get_weight(1) == 2:
    answer(1)
elif get_weight(2) == 2:
    answer(2)
elif get_weight(3) == 2:
    answer(3)
elif get_weight(4) == 2:
    answer(4)
elif get_weight(5) == 2:
    answer(5)

Alternatively, you can just use a loop:

import sys
def get_weight(color):
    print 1
    print 1, color
    print 0
    sys.stdout.flush() # we need to flush stdout
    return input() # get the answer of the judge

def answer(color):
    print 2
    print color
    sys.exit() # exit the program

for color in [1,2,3,4,5]:
    if get_weight(color) == 2:
        answer(color)

Here are some implementation notes:

  • We made some auxiliary functions to make our program less error-prone: Writing the get_weight code multiple times gives more possibility of a human error and thus incorrect solutions.
  • Notice that we called sys.stdout.flush() before taking the input using input(), which forces a “flush”. Other programming languages have similar functions. We need to flush because the output of programs is usually being buffered before being printed out (printing to the standard output is quite costly, so programs try to minimize the number of prints), so without forcing a flush, the judge program will be waiting for an indefinite amount of time.
  • Notice that we called sys.exit() inside our answer function, so calling answer automatically ends the whole program.

For comparison, in C++, we can implement it this way:

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int get_weight(int color) {
    cout << 1 << endl;
    cout << 1 << " " << color << endl;
    cout << 0 << endl; // note that 'endl' automatically does a flush
    int result;
    cin >> result;
    return result;
}

void answer(int color) {
    cout << 2 << endl;
    cout << color << endl;
    exit(EXIT_SUCCESS);
}

int main() {
    for (int color = 1; color <= 5; color++) {
        if (get_weight(color) == 2) {
            answer(color);
        }
    }
}

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:

int main() {
    for (int color = 1; color <= 4; color++) {
        if (get_weight(color) == 2) {
            answer(color);
        }
    }
    answer(5);
}

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 solutions

Let’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:

  • If color 1 was heavy, then the result would be (2 + 1) - (1 + 1) = 1.
  • If color 2 was heavy, then the result would be (1 + 2) - (1 + 1) = 1.
  • If color 3 was heavy, then the result would be (1 + 1) - (2 + 1) = -1.
  • If color 4 was heavy, then the result would be (1 + 1) - (1 + 2) = -1.
  • If color 5 was heavy, then the result would be (1 + 1) - (1 + 1) = 0.

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:

  • Compare [1,2] and [3,4].
  • If the result is 1, then compare 1 and 2, and answer with the heavier one.
  • If the result is -1, then compare 3 and 4, and answer with the heavier one.
  • If the result is 0, then answer with color 5.

Here’s a possible implementation in Python:

import sys

def print_pan(pan):
    print len(pan), ' '.join(str(color) for color in pan)

def compare(pan1, pan2):
    print 1
    print_pan(pan1)
    print_pan(pan2)
    sys.stdout.flush()
    return input()

def answer(color):
    print 2
    print color
    sys.exit()

result = compare([1,2], [3,4])
if result == 1:
    if compare([1], [2]) > 0:
        answer(1)
    else:
        answer(2)
elif result == -1:
    if compare([3], [4]) > 0:
        answer(3)
    else:
        answer(4)
else:
    answer(5)

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:

... # 'compare' and 'answer' definitions here

result = compare([1], [2])
if result == 1:
    answer(1)
elif result == -1:
    answer(2)
else:
    result = compare([3], [4])
    if result == 1:
        answer(3)
    elif result == -1:
        answer(4)
    else:
        answer(5)

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 solution

In 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:

  • If color 1 was heavy, then the result would be (2 + 1 + 1) - (1 + 1 + 1) = 1.
  • If color 2 was heavy, then the result would be (1 + 2 + 2) - (1 + 1 + 1) = 2.
  • If color 3 was heavy, then the result would be (1 + 1 + 1) - (2 + 1 + 1) = -1.
  • If color 4 was heavy, then the result would be (1 + 1 + 1) - (1 + 2 + 2) = -2.
  • If color 5 was heavy, then the result would be (1 + 1 + 1) - (1 + 1 + 1) = 0.

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:

result = compare([1,2,2], [3,4,4])
if result == 1:
    answer(1)
if result == 2:
    answer(2)
if result == -1:
    answer(3)
if result == -2:
    answer(4)
if result == 0:
    answer(5)

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:

result = compare([4,5,5], [1,1,2])
answer(result + 3)

Or, more compactly,

answer(compare([4,5,5], [1,1,2]) + 3)

Time Complexity:

O(1)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

1 Like

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: CodeChef: Practical coding for everyone

1 Like

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