4
\$\begingroup\$

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.

Your task is to replicate it.


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 !

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Peter Taylor Oct 6 '17 at 16:04
  • \$\begingroup\$ @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. \$\endgroup\$ – katana_0 Oct 6 '17 at 16:08
  • \$\begingroup\$ 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? \$\endgroup\$ – user202729 Oct 7 '17 at 7:21
  • \$\begingroup\$ 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. \$\endgroup\$ – Sanchises Oct 7 '17 at 8:23
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Oct 7 '17 at 8:53