ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

give me some test please
Послано Leks 2 ноя 2009 00:14
Re: give me some test please
Послано Armen Tsirunyan 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
Re: give me some test please
Послано svr 2 ноя 2009 20:14
I think your ideas absolutely right.

Edited by author 02.11.2009 20:29
Re: give me some test please
Послано bsu.mmf.team 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".
Re: give me some test please
Послано bsu.mmf.team 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
Re: give me some test please
Послано svr 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
Re: give me some test please
Послано bsu.mmf.team 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.