BADTUPLE Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

3115

PREREQUISITES:

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:

Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2

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
3

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