Discussion @ 1381. Cockroaches in the Building @ Timus Online Judge

Timus Online Judge

Online Judge	Problems	Authors	Online contests
About Online Judge Frequently asked questions Site news Webboard Links	Problem set Submit solution Judge status Guide	Register Update your info Authors ranklist	Current contest Scheduled contests Past contests Rules

Discussion of Problem 1381. Cockroaches in the Building

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

Posted by EfremovAleksei 14 Feb 2007 22:39

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

Posted by svr 14 Feb 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!

Posted by Kit 15 Feb 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!

Posted by KIRILL(ArcSTU) 15 Feb 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 (-)

Posted by Dmitry 'Diman_YES' Kovalioff 15 Feb 2007 09:12

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

Posted by svr 16 Feb 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 (-)

Posted by diver[rus] 16 Feb 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 (-)

Posted by EfremovAleksei 8 Mar 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 (-)

Posted by svr 8 Mar 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 (-)

Posted by [SPbSU ITMO] WiNGeR 9 Mar 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 (-)

Posted by Denis Koshman 24 Aug 2008 17:57

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