Setter: Tejas Pandey
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

3115

None

# PROBLEM:

A tuple of positive integers (a, b, c) is said to be a bad tuple if a, b, c are distinct, a divides b, and b divides c. For example, (1, 2, 4) and (7, 21, 42) are bad tuples while (1, 2, 3) and (2, 4, 4) are not.

Chef has the N integers from 1 to N with him. He wants to pick a subset of these numbers such that it doesnâ€™t contain a bad tuple. How many distinct subsets can he pick?

# EXPLANATION:

WLOG, we can assume in a tuple (a,b,c),\; a \leq b \leq c,
Observation 1: The numbers greater than \frac{N}{2} would not divide any other number and hence they can act only as c in the tuple.

Observation 2: Numbers greater than \lfloor \frac{N}{3} \rfloor can only divide 2 \times themselves so they can only be present in tuples of form (i, x, 2 \times x), where i is a divisor of x.

We will begin by finding all subsets not containing bad tuples consisting only of number from 1 to \lfloor \frac{N}{3} \rfloor. After finding such a tuple we will find pairs of numbers which have a divisor also present. Say numbers of form (i,y), where i divides y.

Now we will mark all multiples of such y greater than \lfloor \frac{N}{3} \rfloor as bad as including them in the subset would lead to formation of a bad tuple. After excluding such numbers it is easy to see by Observation 2 that the tuples would be of the form of (i, x, 2 \times x), we can find all such x which would be paired with their twice. Hence finally we will have two types of numbers. One which have been paired and others which havenâ€™t.

The number which have been paired we can either include x or 2 \times x or none so we have three choices. For the numbers which havenâ€™t been paired we can either include the or exclude them so we have two choices. Hence the answer for this good subset would be:

2^{unpaired\;numbers} \times 3^{paired \; numbers}

The summation of all the answers of each good subset would be the final answer.

# TIME COMPLEXITY:

O(N \times 2^{\lfloor \frac{N}{3}\rfloor} )

# SOLUTION:

It seems that most of the accepted submissions had an array with the answers copy-pasted (perhaps from some online database).

Can someone tell me how they were able to find it on the internet? I was not able to find the pattern on oeis.org and I was wondering how so many people were able to find it.

2 Likes

No, it is not copy pasted from the internet. For hardcoding you have to code a suboptimal solution and run it locally for a longer duration say something like 10 minutes just for example to generate all the answers.

For this problem, coding the naive bruteforce would be too slow but using observation 1 only you can code a solution with complexity (N/2) * 2^(N/2) which most probably will generate all the results in a few minutes. I donâ€™t know what approaches the other participants went for to hardcode this specifically but it is totally possible to do so.

1 Like