MAKEALL - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Construct an array A of size 20 satisfying the following condition:

  • For each integer i from 1 to 5\cdot 10^4, there exists a subset of A having size at most 10, and whose sum equals i.

EXPLANATION:

We’re only allowed 20 numbers, but we need to be able to obtain every sum upto 5\cdot 10^4.
This suggests that the numbers we choose must be rather widely spaced out.

A natural first choice would be to try powers of 2 - after all, every number can be written as the sum of distinct powers of 2 (i.e. in binary), and there aren’t really that many powers of 2 till 5\cdot 10^4.
In fact, there are only 16 powers of 2 available to us; since 2^{16} = 65536 \gt 5\cdot 10^4.

However, we run into a problem here with the second restriction of needing to take a subset having size at most 10.
With the first 16 powers of 2, there are certainly numbers that will need more than 10 of them to write - in fact, we could just take any subset of the powers of 2 with size \gt 10, and run into trouble there - and there are actually quite a few such numbers.

We do have four values left to fix this, but it’s not really clear how we can do that.

Instead, we try to take our solution in a different direction - rather than binary, we’ll use ternary; that is, we’ll work with powers of 3 instead of 2.

Recall that in the ternary system, any number X can be written uniquely as

X = \sum_{k \ge 0} c_k 3^k

where 0 \le c_k \lt 3.

In particular, this means any number is written by adding up only integers of the form 3^k or 2\cdot 3^k.

This means, if we were to take all the numbers of the form 3^k and 2\cdot 3^k for 0 \le k \lt 10, we would be able to write every integer from 0 to 3^{10}-1 as a sum of at most 10 of them; because for each power of 3 from 0 to 9, we’d have to only decide whether we want to take 0, 3^k, or 2\cdot 3^k.

Now, observe that 3^{10} = 59049 \gt 5\cdot 10^4, so we can indeed write every value till 5\cdot 10^4 like this.
And we’re done!

Quite simply, the solution is to take the following set:

\{3^0, 3^1, 3^2, \ldots, 3^9, 2\cdot 3^0, 2\cdot 3^1, \ldots, 2\cdot 3^9\}

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
n = int(input())
for i in range(10):
    print(3**i, 2*3**i)
1 Like
2

Another solution is the following array: {1, 1, 2, 3, 6, 10, 20, 30, 60, 100, 200, 300, 600, 1000, 2000, 3000, 6000, 10000, 20000, 30000}

I had one place left and i put 0 in there that’s why i wasn’t able to solve it during the contest as A[i] had to be greater than or equal to 1.

2 Likes
3

Although this makes it hard-coding.
I solved it rather as a maths problem!

4

I misunderstood the question completely.

1 Like
5

This problem could have been done using binary numbers from 2^0 to 2^15 and 4 extra numbers (and if total 11 numbers were allowed instead of 10).

1 Like
6

Well we can do that with powers of 2 as well try to make 25000 and all integers from 1 to 25000 since we can right every no > 25000 as 25000 + i (i from 1 - 25000) … but since we can use upto 10 bits i.e. 2^10-1 = 1023 … think of this recursively … we have solve the problem for nombers above 25000 just find the answer for 25000 … Look for 12500 and make all no.s from 1 to 12500 … continue this 6250, 3125, 1565, … make 785 (approax 1565/2) and try to make 1 to 765 and Bingo we can make all no.s from 1 to 765 but printing power of 2’s from 0 to 10 … { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 25000 12500 6250 3125 1562 781 390}
for(int i = 0; i < 13; ++i) cout << (1 << i) << " ";
int t = 25000;
for(int i = 0; i < 7; ++i, t /= 2) cout << t << " ";

1 Like
7

CODE AND APPROACH: Explanation

8

I solved it in this way: {1, 2, 4, 7, 10, 20, 40, 70, 100, 200, 400, 700,…etc}
every digit in the target number can be achieved using only 2 elements, so in the worst case it would take 5 * 2 = 10 elements.

4 Likes