| ENG RUS | Timus Online Judge |
Discussion of Problem 1421. Credit OperationsMartin_fmi O(V^3) - OK in C++ , tl4 in Java ... [3] // Problem 1421. Credit Operations 12 May 2009 01:48 The same algo gives tl 4 in java ... In C++ I use vector of vectors for the capacity matrix as well as in java and the input is with the Scanner class . How can I optimize ? Thanks in advance. N.M.Hieu ( DHSP ) Re: O(V^3) - OK in C++ , tl4 in Java ... [2] // Problem 1421. Credit Operations 12 May 2009 13:04 Did you read the FAQ (Frequently Asked Questions) ? Roman Furko Re: O(V^3) - OK in C++ , tl4 in Java ... [1] // Problem 1421. Credit Operations 15 Jan 2012 20:28 I have TLE4 in pascal! why? die_young Re: O(V^3) - OK in C++ , tl4 in Java ... // Problem 1421. Credit Operations 4 Aug 2018 20:21 I don't know. Using C++ and good old Dinic you can get 0.015ms. Actually, you can perform greedy initialization in linear time (of matrix size) and get AC with most suboptimal flow algorithms. Lebedev_Nicolay[Ivanovo SPU] When the matrix can't be constructed? [1] // Problem 1421. Credit Operations 1 Aug 2009 20:13 I have WA 4, and I think because I never write "NO". When answer is NO? Wnen Sum of SR and SC are different or when MaxFlow = 0 or when credit can't be < 100? indawl Re: When the matrix can't be constructed? // Problem 1421. Credit Operations 20 Mar 2015 00:45 for example: 2 201 201 201 201 Answer is: "NO" Becouse one of solve: 100 101 101 100 but 101 more then 100 nemat why does my answer for first test is incorrect? [1] // Problem 1421. Credit Operations 8 Feb 2012 13:11 YES 193 74 0 0 0 157 0 0 0 0 188 0 0 89 158 12 Tranvick Re: why does my answer for first test is incorrect? // Problem 1421. Credit Operations 21 Feb 2012 21:34 "Доподлинно известно, что размер любого кредита является целым числом от 0 до 100. " But you have 193, 157, 158 and 188. maxsakharuk Test // Problem 1421. Credit Operations 5 Dec 2011 17:46 Give me some tests please. I got WA3, but i dont understand why. Vedernikoff Sergey (HSE: EconomicsForever!) O(V^2*E) passes TL! (+) [4] // Problem 1421. Credit Operations 22 Jul 2008 00:43 Usual generic preflow algo got AC in 0.093 sec. Maybe, it worth to decrease timelimit? Chmel_Tolstiy Re: O(V^2*E) passes TL! (+) [3] // Problem 1421. Credit Operations 22 Jul 2008 01:05 I think it is a bad idea. BS Flow by dfs not works. So it's very nice problem. maksay Re: O(V^2*E) passes TL! (+) // Problem 1421. Credit Operations 17 Mar 2009 21:53 Even simple bfs & dfs combination gets AC in 0.187=) (using scaling, of course). And its' complexity is higher than O(V^2*E).I think, it is closer to (E^2*logU) Ripatti [Ufa] Re: O(V^2*E) passes TL! (+) [1] // Problem 1421. Credit Operations 26 Nov 2010 12:03 Dfs works. I got AC with 0.21 sec by using some tricky dfs with scalling. Strekalovsky Oleg [Vologda SPU] Re: O(V^2*E) passes TL! (+) // Problem 1421. Credit Operations 17 Jun 2011 12:34 Simple preflow push algo O(N^2*E) passed on Java in 0.14. hoan TO ADMINS: BUG in the rating. [2] // Problem 1421. Credit Operations 28 Dec 2010 14:31 the time-limit for this problem is 0.25s but in the rating only 350 person have the time less than this time and other have the time more than this. sorry for my poor english. Sergey Lazarev (MSU Tashkent) Re: TO ADMINS: BUG in the rating. [1] // Problem 1421. Credit Operations 28 Dec 2010 14:49 All authors who have time more than 0.25s submitted their solutions during the contest and these solutions haven't been rejudged after decreasing time limit. hoan Re: TO ADMINS: BUG in the rating. // Problem 1421. Credit Operations 28 Dec 2010 15:06 thanks. disa tasks on maxflow // Problem 1421. Credit Operations 11 Oct 2010 08:35 Can you give me links to another tasks solved by maxflow algorithm? On Timus or other problemset it does not matter. Mukhametianov Den [USU] ** [1] // Problem 1421. Credit Operations 9 May 2010 13:26 Test: 2 1 2 3 4 My Ac program gives YES 1 0 2 0 I dont know if other solutions will fail on this test, but.. =) Sandro (USU) Read site news (-) // Problem 1421. Credit Operations 13 May 2010 02:51 Abbas Mehrabian WA #12 [1] // Problem 1421. Credit Operations 18 Aug 2006 22:06 Hi! I used greedy, but I get WA on #12! Can somebody help me? sedream1 Re: WA #12 // Problem 1421. Credit Operations 23 Apr 2010 18:28 Me 2...So,what's the matter? Ibragim Atadjanov TL 14 with O(n^3)(relable to front) algo in java. [1] // Problem 1421. Credit Operations 6 Oct 2009 13:59 please help who solve this problem in java with that algo or give me a better algo. Ibragim Atadjanov Re: TL 14 with O(n^3)(relable to front) algo in java. // Problem 1421. Credit Operations 6 Oct 2009 15:17 I got AC with First-in First-out algo. It can be AC in Java without TL. You can find the alto at http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel MYV Checker is Wrong [2] // Problem 1421. Credit Operations 25 Jul 2008 21:01 code .... cout << "YES\n100 55 100 12\n0 70 87 0\n0 95 93 0\n93 100 66 0"; .... take WA on test #2 and code .... cout << "YES\n0 0 255 12\n0 66 91 0\n0 188 0 0\n193 66 0 0"; ... take WA on test #1. "If the problem has several solutions, you should output any of them." But answer for: YES 0 0 255 12 0 66 91 0 0 188 0 0 193 66 0 0 for test #1 (test in example) is not accepted. Sandro (USU) Re: Checker is Wrong [1] // Problem 1421. Credit Operations 25 Jul 2008 23:57 "Amount of any credit is an integer number between 0 and 100". Sure, your answer for test#1 is incorrect (numbers 255, 188 and 193). MYV Re: Checker is Wrong // Problem 1421. Credit Operations 26 Jul 2008 15:41 thank you :) Anton [SUrSU] Idea? [5] // Problem 1421. Credit Operations 4 Feb 2007 18:40 Tell me pls the idea. Alexander Kouprin You need idea? [4] // Problem 1421. Credit Operations 4 Feb 2007 20:26 Maxflow Edited by author 25.10.2008 08:19 svr Re: You need idea? [3] // Problem 1421. Credit Operations 4 Feb 2007 21:56 O(n^3) MaxFlow, Cormen Anton [SUrSU] Re: You need idea? [2] // Problem 1421. Credit Operations 5 Feb 2007 00:51 Maxflow... how? What network is here? svr Re: You need idea? [1] // Problem 1421. Credit Operations 5 Feb 2007 07:54 n-sources- banks of 1-st policman n- sinks- banks of second policemen bipartite graf capacities of sources and demands of sinks are given flow must satisfiy them add artificial one big source and one sink to make problem classical. Use standard Maxflow algorithm-O(N^5) and you will have TLE8. Replace standart (classical) algo by O(n^3) method from Cormen and you will have Ac. Edited by author 05.02.2007 07:55 Anton [SUrSU] Re: You need idea? // Problem 1421. Credit Operations 5 Feb 2007 12:36 Thanks! leaf Help.......Wa#1 // Problem 1421. Credit Operations 26 Jan 2007 18:52 I don't know what is wrong with my code. i've tried some tests,but all are OK. Can you give me some special tests? Sorry for my poor English. xuyiwen help!wa#4 // Problem 1421. Credit Operations 24 Jan 2007 16:40 I had tried for many times but get wa all the time,can you give me some test? Thanks. {sorry for my bad English}; Fyodor Menshikov Please add the test [3] // Problem 1421. Credit Operations 14 Jan 2007 22:04 I know ac solution that works much more than 0.25s on maximal test: 100 10000 10000 10000... (100 times) 10000 10000 10000... (100 times) Please add this test. Ilya Grebnov[Ivanovo SPU] Re: Please add the test [2] // Problem 1421. Credit Operations 15 Jan 2007 12:01 Added. Waiting for rejudge ... Vladimir Yakovlev (USU) No rejudge will be held because all AC-submissions passed this test (-) [1] // Problem 1421. Credit Operations 16 Jan 2007 00:33 Fyodor Menshikov Re: No rejudge will be held because all AC-submissions passed this test (-) // Problem 1421. Credit Operations 17 Jan 2007 05:30 Intel C++ compiler creates too fast code :-( Dzhulgakov Dmitry Please, help me with one more solution [3] // Problem 1421. Credit Operations 15 Jun 2006 22:54 I already have AC for this task with two different solutions. Now I submited new optimal n^3 solution, but it has WA5. Help me please. It is my solution. It built on Preflow-Push algorithm. [code deleted] Edited by moderator 16.06.2006 01:48 Burunduk1 Re: Please, help me with one more solution [2] // Problem 1421. Credit Operations 16 Jun 2006 02:40 When I wrote Preflow-Push algo (it got WA at first time) simple tester which uses AC solution momently helped me... Dzhulgakov Dmitry Re: Please, help me with one more solution [1] // Problem 1421. Credit Operations 21 Jun 2006 13:41 Thank you. I correct my solution, and now it gets AC in 0.031 sec. http://acm.timus.ru/status.aspx?space=1&num=1421&author=44762 elmariachi1414 (TNU) Re: Please, help me with one more solution // Problem 1421. Credit Operations 16 Jan 2007 17:52 Can you tell me (elmariachi1414(at)mail.ru) how to implement solution, that works for 0.031 sec? My implementation of Relabel-To-Front works for 0.25 Thank you! elmariachi1414 (TNU) Help (TLE #12, O(V*E^2)) [2] // Problem 1421. Credit Operations 11 Jan 2007 04:47 I implemented O(V*E^2) and received TLE #12. Please, give me any hint! My program runs very slow (about 7 sec) on maximal test 100 10000 10000 10000 ... 10000 10000 10000 ... Edited by author 11.01.2007 05:35 Fyodor Menshikov Re: Help (TLE #12, O(V*E^2)) [1] // Problem 1421. Credit Operations 14 Jan 2007 22:07 elmariachi1414 (TNU) Re: Help (TLE #12, O(V*E^2)) // Problem 1421. Credit Operations 15 Jan 2007 22:52 Thank you! I'll try to study this algo from CLR RoBa @ TJU What's test #10 ? It seems no one trapped by it except me :( ... // Problem 1421. Credit Operations 1 Sep 2006 15:26 My algo is something about maximum network flow. At first I used an O(V*E^2) method, and got TLE on test #12, then I tried another O(E*V^2), but got many WAs on test #10... My program passed much random data generated by myself. I really don't know what's wrong. Plz give me some information about test #10, thx very much. Alexey Help me, please! WA#6 [1] // Problem 1421. Credit Operations 23 Jun 2006 16:06 Do U know some sly tests? Thanks. Edited by author 23.06.2006 19:26 Edited by author 26.06.2006 14:40 Alexey Re: Help me, please! WA#6 // Problem 1421. Credit Operations 26 Jun 2006 14:41 Petr WA 28 Help pleeeeeeease! // Problem 1421. Credit Operations 2 Jun 2006 20:29 Can anybody give me some difficult tests please? I can't understand my mistake.My sol is O(N^2). Edited by author 02.06.2006 20:31 Edited by author 02.06.2006 20:31
|