I myself haven't solved this problem, but it seems VERY interesting to me. Well, the obvious thing is that if k>=2^(n-1) then 1, 2, 4, .... 2^(n-1) is a solution. The thing is, that even if k<2^n there still may be solutions. For instance, if n = 5 and k=13, then 3 6 10 11 13 is a solution. The solution doesn't seem to depend on x and y at all. If I am not much mistaken(and I would like someone who has solved this problem to tell me if I in fact am) the problem is to print a set S of natural numbers from the range 1...k, such that for any two nonintersecting subsets A and B of S, the sum of Elements in A is different from that of B. But HOW to do it, that remains a mystery to me. My email is LordN3mrod@gmail.com. If anybody would be so kind as to share their opinion, I'd be very glad. Thank you.
*Edited by author 03.11.2009 01:29*
*Edited by author 03.11.2009 01:30* I think your ideas absolutely right.
*Edited by author 02.11.2009 20:29* It is interesting, that vector (1,2,2^2,...,2^(n-1)) always satisfies the condition if k weren't a fixed integer. The task is to find the least p, such, that vector (p-a1,p-a2,...,p-a(n-1),p) satisfies the condition, written above, where ai>0. For example, if n=4, (1,2,4,8) is a solution, but (3,5,6,7) is a solution too. So, p=7 for n=4, and if k<7 the answer is "NO". And can anybody tell me, what answer on this test: 20 332403 1 2 And this? 20 332404 1 2 Thank you very much All such statements are hypothesis only. Correct approach: Let we have 1<=a[1]<...<a[m]<=k We can add a[m+1] if a[m+1] not in {e[1]*a[1]+e[2]*a[2]...+e[m]*a[m]} where e[m] in {-1,0,1}. For it we use DP. After it is backtracking in attempt to achieve m=n. Using this algo it is easy (if n<=8) to find good tests crashind many Ac and classical :1,2,4,8....
*Edited by author 04.11.2009 10:12* I think using this algo you'll always obtain 1,2,4,8,... - solution. Or, maybe, I didn't understand you... My algo gives less values (but I have WA#8 because of they're not the least) For example, for n=15 I got 10444 as maximum number, not 2^14 = 16384, and for n=12 my answer is 1321. |