# Those annoying grasshoppers [closed]

The problem #6 of IMO 2009 reads:

Let a 1, a 2, a 3, ..., a n, be distinct positive integers and let T be a set of n-1positive integers not containing a 1+a 2+a 3+...+a n, A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths a 1, a 2, a 3, ..., a n in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in T.

## Input

Two sets S, T positive integers, with:

1. S having n distinct elements

2. T having n-1 elements not containing the sum of the numbers in S

## Output

A montonically increasing sequence of positive integers J = b1, b 2, b 3, ..., b n, such that:

1. The numbers b1, b 2-b 1, , b 3-b 2, ..., b n-b n-1 are permutation of the elements of S

2. J and T are disjoint

1. Your code should use O(P(t)) search time, where P(t) is a polynomial with degree <4
2. This is a code golf, so shortest maintaining the rule wins.

Good luck golfing ! Thanks to @MartinEnder for the suggestion !

• I think the complexity bound is intended to be O(t^3) as opposed to o(t^4), but the non-standard way it's worded makes me reluctant to claim certainty. Could you clarify that? – Peter Taylor Oct 6 '17 at 16:04
• @PeterTaylor TBH I don't know what O(something) means, but you can see the discussion here (For the original question) to see that you can construct a good sequence within c*n^2 searches, where c is a constant. – katana_0 Oct 6 '17 at 16:08
• So you should read Wikipedia or some other resources. Having said that, what you have said means O(t^3), not o(t^4). And (if you didn't know) you can use the Sandbox to avoid generating unnecessary comments asking for clarification. | What is the parameter t? – user202729 Oct 7 '17 at 7:21
• I edited what you wrote to the standard way of expressing that. You should check if you agree, and if you did not just mean O(n^3). Right now, algorithms that run in O(n^3.9) are also allowed, which may or may not be what you want. – Sanchises Oct 7 '17 at 8:23
• @Sanchises, your point about n rather than t is well taken, but I still don't know whether OP wants O(n^3) or o(n^4) and it seems that OP doesn't either. Since O(n^2) is apparently possible, O(n^3) should allow at least some room for golfing at the expense of complexity. – Peter Taylor Oct 7 '17 at 8:53