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\$

closed as unclear what you're asking by Sanchises, xnor, Toto, pajonk, NieDzejkob Oct 7 '17 at 13:14

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\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\$ – cdt 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