4
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:
S having n distinct elements
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:
The numbers b1, b 2-b 1, , b 3-b 2, ..., b n-b n-1 are permutation of the elements of S
J and T are disjoint
- Your code should use O(P(t)) search time, where P(t) is a polynomial with degree <4
- This is a code golf, so shortest maintaining the rule wins.
Good luck golfing ! Thanks to @MartinEnder for the suggestion !
katana_0
Posted 2017-10-06T15:34:50.853
Reputation: 209
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 – 2017-10-06T16:04:26.757
@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 *cn^2** searches, where c is a constant.
– katana_0 – 2017-10-06T16:08:21.633So 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
– user202729 – 2017-10-07T07:21:05.623t?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 – 2017-10-07T08:23:33.380
@Sanchises, I've rolled back your edit because it required at least quartic complexity, which definitely isn't what OP wants. – Peter Taylor – 2017-10-07T08:43:06.787
@PeterTaylor Whoops, yeah, my bad. Do you agree with just "The algorithm must run in O(n^k) with k<4"? As it stands, it makes zero sense (the OP obviously meant n rather than t, and O(P(n)) by definition equals O(n^k) with k the degree of P) – Sanchises – 2017-10-07T08:48:22.263
1@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 – 2017-10-07T08:53:02.867
@PeterTaylor Fair enough. VTC as unclear until fixed. – Sanchises – 2017-10-07T08:58:16.433
What does
tmeans in the formulaO(P(t))? – tsh – 2017-10-07T09:56:34.223@Sanchises It seems that "The algorithm must run in O(n^k) with k<4" has no difference from "The algorithm must run in O(n^4)". Did I understand correctly? – tsh – 2017-10-07T09:59:33.810
@tsh No. An algorithm that runs in O(n⁴) is disqualified, but an algorithm that runs in O(n^3.9) is valid by that rule. But it seems unlikely that a golfing answer would have a time complexity with a non-integer k, so perhaps the OP just meant O(n⁴) (if they don't know the difference between smaller than and strictly smaller than) or O(n^3) (if they are unaware that algorithms may have a complexity with O(n^k) with k a non-integer). Until they come back, we can only guess. – Sanchises – 2017-10-07T10:53:38.880