Stuck on seemingly trivial algorithm task

Question

Being given a positive integer n for the input, output a list of consecutive positive integers which, summed up, will make up this number or IMPOSSIBLE if it can't be done. In case of multiple possible anwers, output any with the least summands.

It's a problem from CERC competition held a few days ago and while I can solve it using some weird theories I made up, I have no idea how to tackle it elegantly.

I know that no number in the form 2^i where i is a non-negitve integer can be made and that any odd number can be presented in a two-summand form of floor(n/2)+(floor(n/2)+1) but when it comes to the even numbers, I'm clueless about some elegant solution and I heard it can be solved with some one formula. I thought about dividing the number till we're left with something odd and then trying to put the summands of this odd number in the center of the even one or trying to put the number divided by the odd one in the middle but it doesn't sound right, not to mention elegant. It was solved in under 10 minutes by some teams so the route I mention above is almost certainly wrong and I'm overthinking it way too much.

What would be the best and fastest way to solve this?

Answer 1

Ookay, since @Pokechu22 was interested in how my team solved it (and it seems even one more person was, judging by the upvote next to the message :)), here it goes. It works, it fit the time limit but beware that it's kinda twisted and even after those few days I have serious doubts if I still remember how it worked :D Let's get to it.

So first, we if two scenarios - if n is 1, output Impossible and if n is odd, output floor(n/2)+(floor(n/2)+1). Now for the real fun:

We know that any even number has to be a sum of at least three consecutive integers cause for it to be a sum of two, we'd need two consecutive odd or two consecutive even numbers and that's impossible. Thus, we derived a sequence of sequences and their corresponding sums in the form of:

Length | Sequence        | Sum
3        1-2-3             6
4        0-1-2-3           6
5        0-1-2-3-4         10
6        IMPOSSIBLE        N/A
7        1-2-3-4-5-6-7     28
8        0-1-2-3-4-5-6-7   28
9        0-1-2-3-4-5-6-7-8 36
10       IMPOSSIBLE        N/A

...and so on

As it turns out, every possible answer sequence is just one of those, shifted to the right by some number. To find out what the number is, for each element sum_i of the table above, we check if n-sum_i is divisible by length_i. If it is, we have our solution cause all that's left is to shift the given sequence by that many places (in other words, add (n-sum_i)/length_i to every element of sequence_i). In case of using the sequence with 0 at the beginning, we also have to remember to shift it one additional space right (start at the next integer). Thus, we arrive at a code looking like this:

bool shouldBeShifted = false;
bool foundSolution = false;
long long sum_i = 6, length_i = 3;

while(n - sum_i >= 0)
{
    long long tmp = n - sum_i;
    if(tmp % length_i == 0) {foundSolution = true; break;}

    ++length_i;
    if(tmp % length_i == 0) {foundSolution = true; shouldBeShifted = true; break;}

    sum_i += length_i;
    ++length_i;
    tmp = n - sum_i;
    if(tmp % length_i == 0) {foundSolution = true; break;}

    length_i += 2;
    sum_i = ((3 * length_i) - 3) + sum_i;
    shouldBeShifted = false;
}

If after the loop foundSolution turned out to be true, we've found a solution of length length_i which starts at number (n / length_i) - (length_i / 2) + (shouldBeShifted ? 1 : 0) :) Believe it or not, it does work and finds optimal solution... :D

Answer 2

The sum of a set of positive integers from m to n is

 n(n + 1)/2 - m(m - 1)/2

(ie. sum of numbers from 1 to n less the sum from 1 to m - 1) which is

((n^2 - m^2) +(n + m))/2

which is

 (n + m)( n - m + 1)/2

So if you need to make that equal x for some x

2x = (n + m)(n - m + 1)

So look for factors of 2x and see which fit that pattern