Show all threads Hide all threads Show all messages Hide all messages |
it is right answer for sample? | Alias aka Alexander Prudaev | 1449. Credit Operations 2 | 5 Sep 2008 13:03 | 2 |
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 |
Does this problem require linear programming? | SPIRiT | 1449. Credit Operations 2 | 30 Jul 2008 23:00 | 4 |
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? 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 I think you may round all BR down and all BC up to get integer solution. |
1449- Hungarian weighted maching algorithm | svr | 1449. Credit Operations 2 | 30 Jul 2008 22:52 | 2 |
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. 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. |
How to solve this not through simplex method | Krayev Alexey (PSU) | 1449. Credit Operations 2 | 30 Jun 2007 05:00 | 4 |
Is it reduced to flow or matching ? 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! 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! It is solvable by simplex algorithm!? Result must be non-negative integers, and integer resulted simplex is NP-complete problem. |
Please, give me idea, how to solve it! | EfremovAleksei | 1449. Credit Operations 2 | 2 Oct 2006 21:14 | 1 |
|
Nice problem, thanks a lot! (-) | Ilya Rasenstein (Lyceum #40) | 1449. Credit Operations 2 | 3 Aug 2006 11:54 | 1 |
|