| ENG RUS | Timus Online Judge |
Обсуждение задачи 1449. Кредитные операции 2Alias aka Alexander Prudaev it is right answer for sample? [1] // Задача 1449. Кредитные операции 2 4 сен 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 winger Re: it is right answer for sample? // Задача 1449. Кредитные операции 2 5 сен 2008 13:03 No. A[1,2]=8 > 0 + 6 SPIRiT Does this problem require linear programming? [3] // Задача 1449. Кредитные операции 2 24 май 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. Retired Out solutions are not about simplex at all. But you may try to use it anyway (-) [2] // Задача 1449. Кредитные операции 2 24 май 2006 23:29 SPIRiT Re: Out solutions are not about simplex at all. But you may try to use it anyway (-) [1] // Задача 1449. Кредитные операции 2 29 май 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 (-) // Задача 1449. Кредитные операции 2 30 июл 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] // Задача 1449. Кредитные операции 2 10 фев 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 // Задача 1449. Кредитные операции 2 30 июл 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. Kraev Alexey How to solve this not through simplex method [3] // Задача 1449. Кредитные операции 2 27 июн 2006 18:07 Is it reduced to flow or matching ? Sandro (USU) Re: How to solve this not through simplex method [2] // Задача 1449. Кредитные операции 2 13 июл 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! Kraev Alexey Re: How to solve this not through simplex method [1] // Задача 1449. Кредитные операции 2 19 июл 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 // Задача 1449. Кредитные операции 2 30 июн 2007 05:00 It is solvable by simplex algorithm!? Result must be non-negative integers, and integer resulted simplex is NP-complete problem. EFREMOV[USU] Please, give me idea, how to solve it! // Задача 1449. Кредитные операции 2 2 окт 2006 21:14 Ilya Razenshteyn Nice problem, thanks a lot! (-) // Задача 1449. Кредитные операции 2 3 авг 2006 11:54
|