| Show all threads Hide all threads Show all messages Hide all messages |
| O(V^3) - OK in C++ , tl4 in Java ... | Martin_fmi | 1421. Credit Operations | 4 Aug 2018 20:21 | 4 |
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. Did you read the FAQ (Frequently Asked Questions) ? I have TLE4 in pascal! why? 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. |
| When the matrix can't be constructed? | Lebedev_Nicolay[Ivanovo SPU] | 1421. Credit Operations | 20 Mar 2015 00:45 | 2 |
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? for example:
2
201 201
201 201
Answer is: "NO"
Becouse one of solve:
100 101
101 100
but 101 more then 100 |
| why does my answer for first test is incorrect? | nemat | 1421. Credit Operations | 21 Feb 2012 21:34 | 2 |
YES
193 74 0 0
0 157 0 0
0 0 188 0
0 89 158 12 "Доподлинно известно, что размер любого кредита является целым числом от 0 до 100. "
But you have 193, 157, 158 and 188. |
| Test | maxsakharuk | 1421. Credit Operations | 5 Dec 2011 17:46 | 1 |
Test maxsakharuk 5 Dec 2011 17:46 Give me some tests please. I got WA3, but i dont understand why. |
| O(V^2*E) passes TL! (+) | Vedernikoff Sergey (HSE: EconomicsForever!) | 1421. Credit Operations | 17 Jun 2011 12:34 | 5 |
Usual generic preflow algo got AC in 0.093 sec. Maybe, it worth to decrease timelimit? I think it is a bad idea. BS Flow by dfs not works. So it's very nice problem. 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) Dfs works. I got AC with 0.21 sec by using some tricky dfs with scalling. Simple preflow push algo O(N^2*E) passed on Java in 0.14. |
| TO ADMINS: BUG in the rating. | hoan | 1421. Credit Operations | 28 Dec 2010 15:06 | 3 |
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. 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. |
| tasks on maxflow | disa | 1421. Credit Operations | 11 Oct 2010 08:35 | 1 |
Can you give me links to another tasks solved by maxflow algorithm? On Timus or other problemset it does not matter. |
| ** | Mukhametianov Den [USU] | 1421. Credit Operations | 13 May 2010 02:51 | 2 |
** Mukhametianov Den [USU] 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.. =) |
| WA #12 | Abbas Mehrabian | 1421. Credit Operations | 23 Apr 2010 18:28 | 2 |
WA #12 Abbas Mehrabian 18 Aug 2006 22:06 Hi!
I used greedy, but I get WA on #12!
Can somebody help me? Me 2...So,what's the matter? |
| TL 14 with O(n^3)(relable to front) algo in java. | Ibragim Atadjanov | 1421. Credit Operations | 6 Oct 2009 15:17 | 2 |
please help who solve this problem in java with that algo or give me a better algo. |
| Checker is Wrong | MYV | 1421. Credit Operations | 26 Jul 2008 15:41 | 3 |
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. "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). |
| Idea? | Anton [SUrSU] | 1421. Credit Operations | 5 Feb 2007 12:36 | 6 |
Idea? Anton [SUrSU] 4 Feb 2007 18:40 Maxflow
Edited by author 25.10.2008 08:19 Maxflow... how? What network is here? 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 |
| Help.......Wa#1 | leaf | 1421. Credit Operations | 26 Jan 2007 18:52 | 1 |
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. |
| help!wa#4 | xuyiwen | 1421. Credit Operations | 24 Jan 2007 16:40 | 1 |
I had tried for many times but get wa all the time,can you give me some test? Thanks.
{sorry for my bad English}; |
| Please add the test | Fyodor Menshikov | 1421. Credit Operations | 17 Jan 2007 05:30 | 4 |
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. Added. Waiting for rejudge ... Intel C++ compiler creates too fast code :-( |
| Please, help me with one more solution | Dzhulgakov Dmitry | 1421. Credit Operations | 16 Jan 2007 17:52 | 4 |
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 When I wrote Preflow-Push algo (it got WA at first time)
simple tester which uses AC solution momently helped me... 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! |
| Help (TLE #12, O(V*E^2)) | elmariachi1414 (TNU) | 1421. Credit Operations | 15 Jan 2007 22:52 | 3 |
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 Thank you! I'll try to study this algo from CLR |
| What's test #10 ? It seems no one trapped by it except me :( ... | RoBa @ TJU | 1421. Credit Operations | 1 Sep 2006 15:26 | 1 |
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.
|
| Help me, please! WA#6 | Alexey | 1421. Credit Operations | 26 Jun 2006 14:41 | 2 |
Do U know some sly tests?
Thanks.
Edited by author 23.06.2006 19:26
Edited by author 26.06.2006 14:40 |
| WA 28 Help pleeeeeeease! | Petr | 1421. Credit Operations | 2 Jun 2006 20:29 | 1 |
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 |
