On Thursday, June 11, 2015 at 11:02:40 PM UTC+3, Luke Pebody wrote: > Indeed I did. The linear programming library I used did not give accurate > enough answers on the small data set to pass, so I solved the dual problem > instead, which turned out to be quite easy. > > > On Tue, Jun 9, 2015 at 9:50 PM, Edward Lockhart <[email protected]> wrote: > Yes - see for example linguo's solution. > > He solved bilingual as an integer linear programming problem too. > > > > Edward > > > > > > > On 9 Jun 2015, at 21:09, bigOnion <[email protected]> wrote: > > > > > > During round 2 I recognized that problem B can be described as a Linear > > Programming problem. > > > > > > There are two restrictions: > > > R_1 * t_1 + ... + R_n * t_n = V > > > C_1 * R_1 * t_1 + ... + C_n * R_n * t_n = V * X > > > > > > t_1, ..., t_n are all non-negative > > > > > > Finally the objective is: > > > Minimize (max{t_1, ..., t_n} ) > > > > > > That's quite a regular LP problem. > > > > > > I know that obviously coding a solution to LP is much harder than the > > simple analysis of this specific problem. Nevertheless, I was wondering – > > did anyone tried to solve it this way? I know that LP might need more time > > to solve. Is it doable in the GCJ time constraints (i.e., does it take less > > than 8 minutes to get the full output?) Does anyone know? > > > > > > -- > > > You received this message because you are subscribed to the Google Groups > > "Google Code Jam" group. > > > To unsubscribe from this group and stop receiving emails from it, send an > > email to [email protected]. > > > To post to this group, send email to [email protected]. > > > To view this discussion on the web visit > > https://groups.google.com/d/msgid/google-code/e782962e-7d0e-4fb0-b46d-d39f850e346b%40googlegroups.com. > > > For more options, visit https://groups.google.com/d/optout. > > > > -- > > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CD8F176F-A884-4F52-8CD6-30C1E8BE60D1%40gmail.com. > > > > For more options, visit https://groups.google.com/d/optout.
Wow! Thanks guys. You are total beasts! ... And a very neat score, Luke! I've seen you around in the forum in the past years. I've never been able to pass round 2, though... I always get stuck here. I definitely should check out this PULP library. It seems like the easiest solution for a python programmer so far. I'd never think of problem C as an LP problem. B is quite easy to translate to LP, but I'd never see the 'linearity' in C myself. And come to think of the solution analysis published by Google, this LP method seems like a great workaround, since their solution is not so easy to think of at all. I've been reading your solution for now. It seems awesome(!) and short. It's like it's almost simple.... Can you explain a few things about the choices you made: 1. Did the small data set require the dual problem to get accuracy but the large one not? That's quite surprising 2. Why didn't you force the variables ewor, fwor, bwor to also be integers between 0 and 1? It seems like you wanted them to be Boolean, but required it only of the esen variables.... 3. Why is the equation "ewor[wind] + fwor[wind] <= 1 + bwor[wind]" with the less-or-equal operator and not the equality operator? Great coding techniques 'under fire'. When I have to code fast I usually end with very cumbersome code -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/2394582d-3aa0-4d48-8bd1-cfa84551b84f%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
