Обсуждение @ 1381. Тараканы в здании @ Timus Online Judge

Timus Online Judge

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

вернуться в форум

Обсуждение задачи 1381. Тараканы в здании

I don't understand, why this simple problem, solved only 25 coders!

Послано EfremovAleksei 14 фев 2007 22:39

Re: I don't understand, why this simple problem, solved only 25 coders!

Послано svr 14 фев 2007 22:46

I will try tomorrow and will be in one of two parties

Re: I don't understand, why this simple problem, solved only 25 coders!

Послано Kit 15 фев 2007 01:16

As for me, this problem has quite unusual idea. BTW, I heard what famous "hard life" has fairly simple solution :)

Re: I don't understand, why this simple problem, solved only 25 coders!

Послано KIRILL(ArcSTU) 15 фев 2007 01:53

May be you one of the best coders:) an it's simple for you?

The solution is really easy, but it is not that easy to think it out (-)

Послано Dmitry 'Diman_YES' Kovalioff 15 фев 2007 09:12

Re: The solution is really easy, but it is not that easy to think it out (-)

Послано svr 16 фев 2007 00:08

Could'n found very simple solution.
In final version calcul z1(k)= min [F(0,0,a1)+F(0,a1,a2)+
F(a1,a2,a3)+...+F(ak-1,ak,0)+F(ak,0,0)- a1-...-ak]
for all [a1....ak] k=1,....
z2(k)=min [-F(0,0,a1)-F(0,a1,a2)+
-F(a1,a2,a3)+...-F(ak-1,ak,0)+F(ak,0,0)+ a1-...+ak]
if (z1<0)&&(z2<0) <> and so on.
k from 1 to 10000 but functional depend only ak-1,ak
and z1(k-2). History fogotten this is "fishka" in my prog
Ac(1.3 cek) Ho make 0.015 don't now .

Re: The solution is really easy, but it is not that easy to think it out (-)

Послано diver[rus] 16 фев 2007 02:23

AC(0.109) using DP, but i was really surprised, when my program got AC

Re: The solution is really easy, but it is not that easy to think it out (-)

Послано EfremovAleksei 8 мар 2007 17:01

dp with bfs - i think it is very standart algo

Re: The solution is really easy, but it is not that easy to think it out (-)

Послано svr 8 мар 2007 17:24

My method also standart.
It is Bellman-method for shortest path when
functional of length rather specific but have
main property of fogotten history

Re: The solution is really easy, but it is not that easy to think it out (-)

Послано [SPbSU ITMO] WiNGeR 9 мар 2007 00:22

I think, this method is DP

Re: The solution is really easy, but it is not that easy to think it out (-)

Послано Denis Koshman 24 авг 2008 17:57

It's quite obvious DP. Search for positive/negative loop around (0,0) in graph with transfers (i,j) -> (j,k)