ADMAG - Editorial

PROBLEM LINK:

Contest
Practice

Author: Abhra Dasgupta
Tester: Hiroto Sekido
Editorialist: Kevin Atienza

DIFFICULTY:

Simple

PREREQUISITES:

Fibonacci numbers, Zeckendorf representation

PROBLEM:

You have a sequence of C cards, each containing a (nonempty) list of integers from 1 to N. Furthermore, this list can identify any integer 1 to N this way: the integer i can be obtained by adding the first integer in all cards containing i. Also, an integer cannot appear in two consecutive cards.

For a given N, what is the minimum possible C for which such a card sequence exists?

QUICK EXPLANATION:

C is simply the largest integer such that F_{C+1} \le N, where F_i is the i th Fibonacci number (F_0 = 0 and F_1 = 1). One such possible set of C cards is as follows:

  • The j th card (1 \le j \le C) contains the integer i (1 \le i \le N) if and only if F_{j+1} is in the Zeckendorf representation of i.
  • Each card’s list of integers is sorted (so that the smallest integer in the j th card is F_{j+1}).

It’s easy to see why this set of cards is valid. Proving that this is the optimal solution is also easy.

EXPLANATION:

A simplified problem

The problem is made a bit harder by the following constraints:

  • Each integer must be the sum of the first integer in all cards containing it.
  • An integer cannot appear in two consecutive cards.

Thus, we start by solving a simplified version of the problem first. In other words:

  • Each integer need not be the sum of the first integer in all cards containing it (but it should be identified by which cards it appears in).
  • There is no restriction on the cards which an integer can appear in.

With these in mind, let’s see how we can set up the minimum number of cards to identify the integers from 1 to N.

Of course, in this problem, the order of the integers in each card doesn’t matter, so we can represent each card by a bit string of length N, where the i th bit is on if and only if the card contains i. Furthermore, a sequence of C cards can be represented by a matrix of C rows and N columns. Each row represents a card and the integers it contains, and each column represents an integer and the cards it appears in.

We say that two integers are indistinguishable if they appear in exactly the same set of cards. Clearly, if there is any pair of indistinguishable integers, then there isn’t enough information to identify either integer in the pair. Therefore, there must be no indistinguishable pairs of integers from 1 to N. It’s easy to see that having no such pairs is also sufficient to identify the integers from 1 to N.

In our matrix representation, an indistinguishable pair of integers correspond to a pair of equal columns. If there are C cards, then there are 2^C possible distinct columns. Therefore, C cards can identify at least 2^C different integers. Thus, we have shown that you don’t need more than \lceil \log_2 N \rceil cards to identify N integers.

On the other hand, it’s not possible to do it with strictly less than \lceil \log_2 N \rceil cards, because there aren’t enough distinct columns to identify N integers. Therefore, we have shown that the answer is exactly \lceil \log_2 N \rceil :slight_smile:

To create a set of C = \lceil \log_2 N \rceil such cards, simply create a C\times N matrix with the property that no two columns are equal. For example, If N = 14, then C = 4. An example of such a matrix is the following:

01010101010101
00110011001100
00001111000011
00000000111111

This matrix corresponds to the following sequence of cards:

Card 1: 2 4 6 8 10 12 14
Card 2: 3 4 7 8 11 12
Card 3: 5 6 7 8 13 14
Card 4: 9 10 11 12 13 14

It’s easy to see that this set of cards can identify all integers from 1 to 14 :slight_smile: (Note that the integer 1 appears in no cards, but it’s the only such integer, so it can still be identified) Note that there are other sets of cards that also work.

A slightly harder problem

Now, let’s add the following restriction:

  • An integer cannot appear in two consecutive cards.

Note that we’re getting closer to the original problem. Also, note that the answer we get by solving this problem is automatically a lower bound for the answer to the original problem.

To answer this problem, we first convert the new restriction in terms of our matrix representation. An integer appears in two consecutive cards if and only if its bit string (i.e. the bit sequence in the column corresponding to it) contains two consecutive on bits. Thus, we cannot use all 2^C such bit strings for the columns; we can only use those not containing two consecutive 1 s.

How many such bit strings are there? Let f(N) be the number of such strings of length N. Let’s assume first that N \ge 2. Notice that such a string starts in a 0 or a 1. If it starts in a 0, then the remaining bit string of length N-1 can be chosen among the f(N-1) valid strings. If it starts in a 1, then the next one should be a 0, but the remaining bit string of length N-2 can be chosen among the f(N-2) valid strings. Therefore, we have the following recurrence:

f(N) = f(N-1) + f(N-2)

Notice the similarity with the Fibonacci recurrence! In fact, for base cases, we have f(0) = 1 and f(1) = 2, which are also two consecutive Fibonacci numbers, so the sequence (f(0), f(1), f(2), \ldots) is just the Fibonacci sequence offset by two places! To be more specific, we have:

f(N) = F_{N+2}

Therefore, a sequence of C cards can identify F_{C+2} integers, and thus the answer for a given N is the smallest C such that F_{C+2} \ge N.

For example, if N = 15, then C = 6, and one such C\times N matrix is the following:

010010100100101
001000010010000
000110000001100
000001110000000
000000001111100
000000000000011

This matrix corresponds to the following sequence of cards:

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

The original problem

Finally, we can add the remaining restriction to get to the original problem:

  • Each integer must be the sum of the first integer in all cards containing it.

Remember that the answer is at least the answer to the previous problem, i.e. at least the smallest C such that F_{C+2} \ge N. But it could be more than that. For example, each integer must appear at least once in some card (or else it cannot be equal to the sum of the cards it appears in, which would be 0). Therefore, a column with a pure zero bit string is not allowed! We now have the following lower bound of the sum: the smallest C such that F_{C+2} > N.

The key insight is to use Zeckendorf’s theorem: Each integer can be uniquely represented as the sum of Fibonacci numbers from (F _ i) _ {i\ge 2} in such a way that the sum does not include any two consecutive Fibonacci numbers. To use this, we use a distinct Fibonacci number as the first number in each card, and place each integer i in card j if and only if F _ {j+1} is in the Zeckendorf representation of i. For example, the integer 17 should appear in cards 1, 3 and 6 because F _ {1+1} + F _ {3+1} + F _ {6+1} = 17. Note that each Fibonacci number appears in exactly one card, and we place this number at the beginning of the list, so that each integer is exactly the sum of the first integer in the cards it appears in, satisfying the conditions of the problem!

It’s easy to see that the solution described in the previous paragraph is optimal; i.e. the number of cards needed is exactly the lower bound that we have, i.e. the smallest C such that F_{C+2} > N. Thus, we have shown that this is the answer!

Here’s an implementation of this algorithm in Python:

F = [0,1]
while F[-1] <= 10**20:
    F.append(F[-2] + F[-1])

for cas in xrange(input()):
    n = input()
    c = 1
    while F[c+2] <= n:
        c += 1
    print c

Note that this simply computes enough Fibonacci numbers, and computes the answer according to its definition. It’s also possible to answer the problem without precomputing Fibonacci numbers, as shown in the following implementation:

for cas in xrange(input()):
    n, c, Fc1, Fc2 = input(), 1, 1, 2
    while Fc2 <= n:
        Fc1, Fc2, c = Fc2, Fc1+Fc2, c+1
    print c

In this implementation, Fc1 and Fc2 corresponds to F_{c+1} and F_{c+2}, respectively.

Time Complexity:

O(\log N)

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

4 Likes

The solution was too easy.

But the question was framed in such a beautiful way that while reading the question at first,I couldn’t understand a single thing(what was happening).All you need was a pen and a paper.Just follow the instructions and then you can see what happens :slight_smile:

Hats off to the author!

3 Likes

Two minute silence for those who just started thinking about logic and set theory etc. rather than picking up pen and paper to solve it for small value of M :slight_smile: it didn’t took more than 5-6 minute to get the logic

like this one There are many problem on fibonacci which seems like a very difficult at first sight but :slight_smile:

i have a link of such wonderful problems on fibonacci you would really enjoy it you will not find problems but logic and concept based on fibonacci http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibpuzzles.html

9 Likes

Thanks for sharing the link.

1 Like

“Also, an integer cannot appear in two consecutive cards.” I wonder how to solve if in case an integer is allowed in two consecutive cards. I misinterpreted this part at first and have difficulty before I reread the problem and able to solve it easily then.

@ninjascript, Read the editorial carefully. The query you are asking for is mentioned in the the editorial as the beginning problem for which the answer is ceil(log2(n)).

Solving with pen and paper instead of applying some high order concept is the way to go for such problems. At first sight the problem blew me off. It was only after hours of brainstorming that I could get the hidden fibonacci sequence. Cheers to the author.

Thanks for the link

1 Like

it would be better if we use binary search instead of checking for every fibonacci number.