Show all threads Hide all threads Show all messages Hide all messages  I solve with simple recursion!!!!  xurshid_n  1381. Cockroaches in the Building  13 Aug 2012 14:47  1  after 2 days, found DP solution, and AC with 0.046 s. Edited by author 15.08.2012 16:07  WA 38. Something special? ()  Vedernikoff Sergey (HSE: АОП)  1381. Cockroaches in the Building  16 Mar 2012 01:36  2  I think in this test there is some big loop with small weight. So u need go through cicle many times to decrease (increase) population of cockroaches.  I don't understand, why this simple problem, solved only 25 coders!  EfremovAleksei  1381. Cockroaches in the Building  24 Aug 2008 17:57  11  I will try tomorrow and will be in one of two parties As for me, this problem has quite unusual idea. BTW, I heard what famous "hard life" has fairly simple solution :) May be you one of the best coders:) an it's simple for you? 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(ak1,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(ak1,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 ak1,ak and z1(k2). History fogotten this is "fishka" in my prog Ac(1.3 cek) Ho make 0.015 don't now . AC(0.109) using DP, but i was really surprised, when my program got AC dp with bfs  i think it is very standart algo My method also standart. It is Bellmanmethod for shortest path when functional of length rather specific but have main property of fogotten history I think, this method is DP It's quite obvious DP. Search for positive/negative loop around (0,0) in graph with transfers (i,j) > (j,k)  Sample#2  Sandro  1381. Cockroaches in the Building  24 Sep 2005 18:01  1  Be careful! Sample input and output #2 have changed. F(0,0,0)=0 in all tests in this problem. 

