Обсуждение @ 1735. Похищение века @ Timus Online Judge

Programmer Who can explain the right solution?(-) [1] // Задача 1735. Похищение века 9 ноя 2009 02:00

Felix_Mate if k<=n-2 then no solution? // Задача 1735. Похищение века 26 июн 2016 10:59

Mickkie Some little hint // Задача 1735. Похищение века 10 июн 2015 21:48

skumar7777 Problem with WA#11 - Is there a way to find what the test data is? Thanks in advance for replies // Задача 1735. Похищение века 31 мар 2010 19:20

enoyps Can someone explain the sample to me plz? // Задача 1735. Похищение века 6 ноя 2009 07:41

Leks give me some test please [6] // Задача 1735. Похищение века 2 ноя 2009 00:14

Armen Tsirunyan Re: give me some test please [5] // Задача 1735. Похищение века 2 ноя 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

svr Re: give me some test please [4] // Задача 1735. Похищение века 2 ноя 2009 20:14

I think your ideas absolutely right.

Edited by author 02.11.2009 20:29

bsu.mmf.team Re: give me some test please [3] // Задача 1735. Похищение века 3 ноя 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".

bsu.mmf.team Re: give me some test please // Задача 1735. Похищение века 3 ноя 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

svr Re: give me some test please [1] // Задача 1735. Похищение века 4 ноя 2009 09:57

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

bsu.mmf.team Re: give me some test please // Задача 1735. Похищение века 6 ноя 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.

k_zaki What's test 6 // Задача 1735. Похищение века 1 ноя 2009 22:24

Вид форума: плоский | древовидный | классический
Сортировка веток: всплывающая | фиксированная

Обсуждение задачи 1735. Похищение века