|
|
| Show all threads Hide all threads Show all messages Hide all messages | | Levit algorithm | Igor Parfenov | 1237. Evacuation Plan | 11 Apr 2023 03:28 | 1 | I firstly tried to solve it with Ford-Bellman algorithm, but got TL and could not make it pass. Then I found here https://e-maxx.ru/algo/min_cost_flow Levit algorithm, and it passed. | | Any tips on solving this problem? | Sap | 1237. Evacuation Plan | 14 Aug 2022 22:22 | 4 | hi,
im trying to solve this problem and would like to get tips in the right direction of solving this problem.
would a grapha matching solution work? or perhaps a minimum cost flow solution? or anything else?
thanks in advance. My solution is to find really optimal matching with min-cost max-flow. Then compare it to one from input. I solved it with negative cycle searching.
My algo have following complexity: (N+M)*(2*N*M + M*M) It can also be a chain ending up in shelter with residue capacity.
It is also possible to make it N*M*M + M*M*M by jumping from shelter to shelter through one preselected building which grants maximum yield for that pair of shelters (hence the first N*M*M step), M*M*M is Bellman-Ford. | | WA8 | 👨💻tproger👨💻[GTGU] | 1237. Evacuation Plan | 10 Jun 2018 09:44 | 1 | WA8 👨💻tproger👨💻[GTGU] 10 Jun 2018 09:44 I always have WA8, can you give me some tips about this test? | | Mistake in description | Semyon Grendel' | 1237. Evacuation Plan | 14 Dec 2015 13:02 | 1 | I suppose there is a mistake in the word 'there'. I believe, it must be 'three'
"Each line contains there integer numbers Xi, Yi, and Bi" | | First Test Response | Wolfgang | 1237. Evacuation Plan | 16 Apr 2010 08:24 | 1 | Hi, could you please tell me what was the response of my program to the first test since it gives me a "Wrong Answer"? | | 2 Admins. | Alexander Fedulin | 1237. Evacuation Plan | 8 Apr 2010 20:31 | 4 | 2 Admins. Alexander Fedulin 18 Nov 2009 13:13 Could you verify test #1 and my output for this test? I stressed my solution with earlier one (AC solution) and have not found any bad test or mistake. Also i tested my solution on sample test from statement. May be it connected with difference of compiler i use and your compiler. The 1st test is a 1st sample test. Your last solution gives the following incorrect answer on it:
SUBOPTIMAL
0 0 0 0
0 0 6 0
0 0 0 0
Edited by author 18.11.2009 14:05 I have tested it again. Result is as in the statement. Could you place somewhere you compiler.. I can't find it for free.
Edited by author 18.11.2009 14:22
Edited by author 18.11.2009 14:22 Why my solution has Stack Overflow on test case #7? Could you admins please just tell me where the overflow happens (on which stack/array)? Or is it an infinite recursion in a function? | | WA5 ? | Grujah | 1237. Evacuation Plan | 5 Apr 2010 01:05 | 1 | WA5 ? Grujah 5 Apr 2010 01:05 I get WA5? Whats that test about? | | Please set up another C++ compiler, for example GNU C++. | Alexander Fedulin | 1237. Evacuation Plan | 15 Nov 2009 17:42 | 1 | | | The problem condition doesn't make snese | LSBG | 1237. Evacuation Plan | 4 Aug 2008 12:00 | 2 | In this problem we want to minimize the total time needed for all workers as if they run to the shelters one by one. I think this is illogical as in case of a bombardment all workers will run to the shelters simultaneously. Noone else can run until documents are checked at the destination. | | ACC! happy | linhduong | 1237. Evacuation Plan | 25 Oct 2006 16:14 | 1 | I have acc this Pb.It is so interesting.
if you acc this ,I want to know your solution.
sorry my bad english.
(ah , my email :linhduong55@yahoo.com
Edited by author 25.10.2006 16:29 | | What does the message "Fail (Validator)" mean? | Igor Dex | 1237. Evacuation Plan | 22 Mar 2005 23:11 | 2 | What's the difference between that message and "Wrong answer at test N..."?
Edited by author 21.03.2005 23:07 Problem with validator was fixed |
|
|
|
