| ENG RUS | Timus Online Judge |
Discussion of Problem 1449. Credit Operations 2Alias aka Alexander Prudaev it is right answer for sample? [1] // Problem 1449. Credit Operations 2 4 Sep 2008 00:24 it is right answer for sample? input 4 5 8 4 3 3 6 2 1 4 6 4 1 4 3 5 4 my answer 0 0 0 0 5 6 4 4 [SPbSU ITMO] WiNGeR Re: it is right answer for sample? // Problem 1449. Credit Operations 2 5 Sep 2008 13:03 No. A[1,2]=8 > 0 + 6 SPIRiT Does this problem require linear programming? [3] // Problem 1449. Credit Operations 2 24 May 2006 16:22 Funny to say, but once I've read this problem, I remembered the simplex method we were taught last year. The classic problem of simplex method is like this: find min(max)f(X)=C1*X1+C2*x2+c3*x3.. where ci - constants Also where is a system of conditions: a11*x1+..<=(>=)b1 a21*x1+..<=(>=)b2 and so on. The simplex method finds the solution very fast, but it can be a real value, not an integer. There is also a modification of SM called integer SM - it will find an integer solution. Is the problem based on this algo or not? Dmitry 'Diman_YES' Kovalioff Out solutions are not about simplex at all. But you may try to use it anyway (-) [2] // Problem 1449. Credit Operations 2 24 May 2006 23:29 SPIRiT Re: Out solutions are not about simplex at all. But you may try to use it anyway (-) [1] // Problem 1449. Credit Operations 2 29 May 2006 20:37 Thanks for allowing. I think I've seen in Kormen a chapter how to model linear programming with graphs (unbelievable, isn't it?). I'll see what will happen Denis Koshman Re: Out solutions are not about simplex at all. But you may try to use it anyway (-) // Problem 1449. Credit Operations 2 30 Jul 2008 23:00 I think you may round all BR down and all BC up to get integer solution. svr 1449- Hungarian weighted maching algorithm [1] // Problem 1449. Credit Operations 2 10 Feb 2007 18:53 Hungarian method of weighted matching! It's interesting that I solved 1449 by first version of program without any optimization. It,s rather strange because commonly challange team prepear most difficult tests with respect to time and memory. Now the problem has junior level. This is a pity, because matching frequently using on various contests. For information: Let W- weight of maximal matching in A[][] Graph. Then W- our answer. Denis Koshman Re: 1449- Hungarian weighted maching algorithm // Problem 1449. Credit Operations 2 30 Jul 2008 22:52 I don't consider myself a weak problem solver (even been to ACM WF twice), but it's still not obvious for me how does this problem resolve to maximal matching, and how should I convert that matching into result :) So, the problem is worth it. Krayev Alexey (PSU) How to solve this not through simplex method [3] // Problem 1449. Credit Operations 2 27 Jun 2006 18:07 Is it reduced to flow or matching ? Sandro (USU) Re: How to solve this not through simplex method [2] // Problem 1449. Credit Operations 2 13 Jul 2006 22:24 Hint: you can find the minimum total amount of all bribes (but not the optimal values of bribes) if you know the solution of problem 1076. Good luck! Krayev Alexey (PSU) Re: How to solve this not through simplex method [1] // Problem 1449. Credit Operations 2 19 Jul 2006 21:06 Thank you, i tried to construct algo using this idea, but the second stage of that algo was wrong. Now i fixed it and got ac. Thank you! Lomir Re: How to solve this not through simplex method // Problem 1449. Credit Operations 2 30 Jun 2007 05:00 It is solvable by simplex algorithm!? Result must be non-negative integers, and integer resulted simplex is NP-complete problem. EfremovAleksei Please, give me idea, how to solve it! // Problem 1449. Credit Operations 2 2 Oct 2006 21:14 Ilya Rasenstein (Lyceum #40) Nice problem, thanks a lot! (-) // Problem 1449. Credit Operations 2 3 Aug 2006 11:54
|