ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1735. Theft of the Century

Posted by Leks 2 Nov 2009 00:14
Re: give me some test please
Posted by Armen Tsirunyan 2 Nov 2009 01:46
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
Re: give me some test please
Posted by svr 2 Nov 2009 20:14
I think your ideas absolutely right.

Edited by author 02.11.2009 20:29
Re: give me some test please
Posted by bsu.mmf.team 3 Nov 2009 22:57
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".
Re: give me some test please
Posted by bsu.mmf.team 3 Nov 2009 23:00
And can anybody tell me, what answer on this test:
20 332403 1 2
And this?
20 332404 1 2
Thank you very much
Re: give me some test please
Posted by svr 4 Nov 2009 09:57
All such statements are hypothesis only.
Correct approach:
Let we have 1<=a<...<a[m]<=k
We can add a[m+1] if  a[m+1] not in
{e*a+e*a...+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
Re: give me some test please
Posted by bsu.mmf.team 6 Nov 2009 02:57
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.