PROBLEM LINK:
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 
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 (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:
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:
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)