Cool problem! My method.

Wow. This problem is really cool. Try using the naive method and you're sure to get TLE#26.

Well, my solution(AC 0.234) goes this way:

if the first term is not 1 then the ans is 1.

if the first i terms are 1<<0, 1<<1, 1<<2, ... 1<<(i-1) then all numbers from 1 to (1<<i) - 1 can be expressed as a sum of some of the above terms. Thus if a number k is present all numbers from k to k+((1<<i) - 1) can be skipped. Proceed using this approach.

By the way 1<<i represents pow(2, i).

Re: Cool problem! My method.

And how do you plan to proceed with this approach? :)

Re: Cool problem! My method.

Posted by

Juve45 11 Mar 2017 02:19

how is your algorithm working on this test:

6

1 2 3 6 9 18

Re: Cool problem! My method.

My brain burned in notebook on that algorithm!