Solutions for Round 7

Problem 1: Once upon a Time...
Problem 2: Colonies on Mars
Problem 3: Zeroes Again...


Problem 1: Once upon a Time...

Here's the solution for "Once upon a time...".

   First of all, the statement is not mine. You can find it in the book
"Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson &
Ronald L. Rivest, published by McGraw-Hill Company (problem 4-7, page 85)
You'll only find the statement there. Here's the solving method:

 1. The main idea is to use at most N-1 tests to find a good chip. Then we can
use this chip as a witness and find the truth about the other N-1 chips.
The most you'll need is therefore 2N-2 tests (see, I've been generous :) ).
Let's see how exactly we can find a good chip.
--------------------

 2. The problem admits a "divide & conquer" algorithm. We set ourselves the
task of reducing the problem to one of (at most) half the size (at most N/2
chips) by the use of N/2 tests. In other words, our target is to select N/2
chips, more than half of which are good, using N/2 tests. If we can do this,
we can repeat it for the selected chips: we make N/4 tests and select at most
N/4 chips, more than half of which are good and so on. How many tests do we
use in the end ?

      N/2 + N/4 + N/8 + ... + 2 + 1 = N-1

(we assumed for the beginning that all divisions have integer quotients).

What do we get after these consecutive splits ? A set of only one chip,
"more than half of which is good" :) i.e. we spotted a good chip.

--------------------

  3. We're getting to the most exciting part: how can we retain N/2 chips of
the N chips such that we can guarantee that more than half of what we
retained are good chips ?

We start by pairing up the chips: 1 & 2, 3 & 4 etc. (we will consider that N
is even and we'll discuss later what happens if N is odd). Then we test the
N/2 couples. Like we said, if the answer is "Good-Good" (we'll spell it "11")
then either both chips are good or they're both bad. Anyway, they're
IDENTICAL. If the answer if "Good-Bad" (spelled "10") or "Bad-Bad" (spelled
"00"), then we can tell that at least one of the chips is bad.

How do we pick out the chips using this information ? If the answer we get
for two chips is "10" or "00", we can just "throw away" both of them. Why ?
Because we initially had N chips, the good ones being a majority. Of these,
we throw away:

- either a good chip and a bad chip, in which case the good chips will remain
a majority,
- or two bad chips, in which case the good chips will be even a larger
majority.

This way, only N'<=N chips will remain, the rest being thrown away. These N'
chips are grouped in pairs of IDENTICAL chips, more than half of them being
good. Here's an example:

00 11 00 00 11 11 11 00 11 11    (1 = good chip, 0 = bad chip)

We have no idea what kind (good/bad) every chip is. But if we pick a chip
from every pair and throw away the other, we will surely pick a majority of
good chips. In our example, we'll pick the chips:

0 1 0 0 1 1 1 0 1 1

If, of the N' chips, N1 were good and N0 were bad, and N1>N0, then of the
N'/2 chips we kept, N1 / 2 will be good and N0 / 2 will be bad, and of course
N1 / 2 > N0 / 2. Therefore we reduced the problem to one of the size:

N'/2 <= N/2.
--------------------

  4. If the pairing always works (N is always even), the algorithm is fairly
easy. What do we do if at some moment we keep an odd number of chips ? Here's
a 7 chip example:

11 11 00 0

If we select three chips from the three pairs and we also keep the seventh,
then we'll get the configuration 1100, where not more than half of the chips
are good (and in this situation it can be shown that we cannot determine the
good chips). Still, take a look at another example where we cannot throw away
the unmathced chip:

11 11 00 00 1

If we only select a chip of each pair, we'll get to the same configuration
1100. It appears that we need to keep the unmatched chip only when it is a
good one. Only... we don't know whether it is or not a good one ! :)

The correct solution is: let's assume there are P pairs which answer "11" and
one unmatched chip. Then:

 a) If P is even, we will select a chip from every pair and we will also keep
the unmatched chip;

 b) If P is odd, we will select a chip from every pair and we will throw away
the unmatched chip.

 Prove that, no matter if the last chip is good or bad, we will select more
good chips than bad chips if we follow the alternative above.

Ca y est !
--------------------

 5. Example. Let's assume the following 25-chip configuration:

1111111100001111001010011

(And let's also assume that any pair of bad chips will answer "11" trying to
trick us)
We pair them up:

11 11 11 11 00 00 11 11 00 10 10 01 1           --> 12 tests
                           ** ** **

We throw those marked **, because the answer is either "00" or "10":

11 11 11 11 00 00 11 11 00 1

There are nine answers of "11" so we can ignore the unmatched chip:

111100110

Repeat:

11 11 00 11 0                                   --> 4 tests

Four answers of "11", so we also keep the unmatched chip:

11010

Again:

11 01 0                                         --> 2 tests
   **

We throw away the second pair as it doesn't answer with "11":

110

And for the last time:

11 0                                            --> 1 test

There's only one pair which says "11" so we throw away the third chip:

1

At this moment we can say that we identified a good chip by the use of 19
tests. We can use this chip as a witness in order to detect the other chips.

Send any questions at   ** fcatalin@sundy.cs.pub.ro **.
Tough luck from now on !

The tests are sent as attached documents:
   input.zip
   output.zip.

There was no problem in C to get the maximum score.
The following programs (C++ and Pascal) are examples of maximum scored programs.
We also attach the two libraries C++ and Pascal that we used.



Input files: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
Output files: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


Author: Catalin Andrei Francu

Solution no. 1 (Pascal) Solution no. 2 (C)


Problem 2: Colonies on Mars

The difficulty of the problem was, probably, in the used algorithm.
The Greedy algorithm didn't lead to the best solution in this case.
There was a simple text of application of the Ungar Algorithm (name with
which it is very well-known in our country).
Because one of the sources made this algorithm, step by step, we commented
(without asking for permission from the one who made the program) the
received source.In fact, we were very much helped by the "tidy" and clear
manner in which this source was realized, source belonging to Mr.George
Stoianov.

No source in C obtained the maximum score.
We afford to give another example (also in Pascal), as the source is very
short.

Input files: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Output files: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
The maximum given score, respectively for the tests that got it, was:
1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 = 25 points.

We wish you lots of luck further on.

Solution (Pascal)

                         Teachers
                             Prof. Maria si Adrian Nita
                         Liceul Teoretic "Emanuil Gojdu"
                                   Oradea

Problem 3: Zeroes Again...

For a number made up of the figures:
c c c ....c
1 2 3 n
the algorithm could be the following:
- it is read figure by figure from the last figure;
- if c <> 0, then in Number_zero := c c c ....c
n 1 2 3 n-1
- if c <> 0, then Number_zero := Number_zero + c c c ...c 0
n-1 1 2 3 n-2
- the same if c <> 0,
i
Number_zero := Number_zero + c c c ...c 00000 ;
1 2 3 i-1 0 n-i times
- if c = 0, then,in order to continue the algorithm, we consider
i
the number b b b ....b ..... = c c c ... c - 1
1 2 3 i-1 1 2 3 i-1
and to Number_zero we add the number:
c c .... c + 1
i+1 i+2 n
Example:

for 123456
Number_zero = 12345 + 12340 + 12300 + 12000 + 10000 = 58985
for 1001
Number_zero = 100 + 2 + 90 = 192
To correct the problems, we used a checking program that compared the
files .OUT figure by figure.
Input files: 1 2 3 4 5 6 7 8 9 10
Output files: 1 2 3 4 5 6 7 8 9 10 
Solution no. 1 (Pascal) Solution no. 2 (C)
We wish you good luck further on.

                           Teachers
                               Maria and Adrian Nita
                           "Emanuil Gojdu" - Highschool
                                    Oradea

[The problems] [First Round] [Previous Round] [Next Round] [Current Round] [Romāna] [Go Back!]

Go Back!