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 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)