Re: [gcj] a Linear Programming approach to problem B of round 2
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 edward@gmail.com 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 haibr...@gmail.com 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 google-code...@googlegroups.com.
To post to this group, send email to googl...@googlegroups.com.
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 google-code...@googlegroups.com.
To post to this group, send email to googl...@googlegroups.com.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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.
Re: [gcj] a Linear Programming approach to problem B of round 2
Check out my (linguo, 36th) solution to C-Large. Python solution using linear programming tool. Make that runnable on your machine and you could do the same. On 10 Jun 2015 09:38, bigOnion haibren...@gmail.com wrote: On Wednesday, June 10, 2015 at 10:16:19 AM UTC+3, M.H. wrote: I know that obviously coding a solution to LP is much harder than the simple analysis of this specific problem. I think, GNU Octave + GLPK are acceptable tools in this contest (as both of them are open-source and free), so solving a LP (and MILP) problem is as hard as filling three matrices and calling one function. Correct me if I am wrong. Obviously you are right. A few questions, if you may: 1. Do you know if octave and GLPK run smoothly on windows? Never heard of GLPK and I always had the impression that Octave is only for linux, but I search around and see that I may have been wrong about that. 2. Is it possible to call such methods from another language? Specifically python, which is my bestest and most favorite language of use? Is it easy? 3. Is it possible to have complete accuracy in octave/glpk when handling fractions? I have that option in python using the Fraction class, but I am not sure how many other languages have such classes... Thanks -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/10f414c5-ccf0-4f58-b27f-2773b3a58712%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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-M%3D4fvqt7bbCsMOTKuWJX%2Bnpfq9POfAjZX3UbZipZx%3DAw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] a Linear Programming approach to problem B of round 2
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 edward.lockh...@gmail.com
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 haibren...@gmail.com 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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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.
--
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CAECKw-MYAQ-b_f9hfhD%2BOx3ozj7Q-OaaS9vraNrtGyqmkVby7w%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
Re: [gcj] a Linear Programming approach to problem B of round 2
1. Do you know if octave and GLPK run smoothly on windows? Yes, both of them run on Windows, however I experienced several 'corner-cases'. E.g., I am not aware if modern Octave GUI (introduced in 3.8.x) is already available for Windows without Cygwin. I also had some problems with running it on Windows 8, but I must say, I wasn't too persistent to solve that problems. On the other hand, I worked with stable enough configuration of Octave 3.6.4 on Windows 7 - everything was fine. GLPK is both a standalone program for solving LP/MILP and a dynamic library for that purpose. Both of its forms are available on Windows. GLPK is actually used by Octave to solve LP/MILP in the form of glpk() function. So, you don't have to think about installing GLPK separately, if you have a working Octave installation, you already have glpk() function in it which uses GLPK dynamic library under the hood. However, you may prefer to use GLPK without Octave, it may be beneficial in some cases. So, to clarify my original proposal, Octave OR (not +) GLPK may be used. (I'am also aware that there are plenty of other LP/MILP solvers with permissive licenses - brightest minds can actually brew them in the contest time frame ;) - I just did not happen to use them.) 2. Is it possible to call such methods from another language? 1. Octave. Well, I didn't use anything of the kind, so my browsing of Octave documentation won't be more informative than anyone else's. However, there is always quick-and-dirty solution, that is to generate .m file, run it by subprocess.call (if it is Python) and parse the output. 2. GLPK. Yes, you can certainly use the mentioned quick-and-dirty way with the standalone form of GLPK, or use dll, or use java wrapper for that dll, or even Python module (PULP, as far as I remember - but that's quite another story). 3. Is it possible to have complete accuracy in octave/glpk when handling fractions? A very good question! As far as I understand, it is impossible with Octave's glpk() function. But if you use GLPK API directly, there is a function that solves LP in rational numbers - I didn't use it and the documentation says that it is tentative implementation. Kind regards, Andrew 2015-06-10 11:38 GMT+03:00 bigOnion haibren...@gmail.com: On Wednesday, June 10, 2015 at 10:16:19 AM UTC+3, M.H. wrote: I know that obviously coding a solution to LP is much harder than the simple analysis of this specific problem. I think, GNU Octave + GLPK are acceptable tools in this contest (as both of them are open-source and free), so solving a LP (and MILP) problem is as hard as filling three matrices and calling one function. Correct me if I am wrong. Obviously you are right. A few questions, if you may: 1. Do you know if octave and GLPK run smoothly on windows? Never heard of GLPK and I always had the impression that Octave is only for linux, but I search around and see that I may have been wrong about that. 2. Is it possible to call such methods from another language? Specifically python, which is my bestest and most favorite language of use? Is it easy? 3. Is it possible to have complete accuracy in octave/glpk when handling fractions? I have that option in python using the Fraction class, but I am not sure how many other languages have such classes... Thanks -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/10f414c5-ccf0-4f58-b27f-2773b3a58712%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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CANBUrM86Qq28uWt1ikQjGCbb%3Db9%3DTJ_G1kED421H%3Du-ZdLbbTg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] a Linear Programming approach to problem B of round 2
I know that obviously coding a solution to LP is much harder than the
simple analysis of this specific problem.
I think, GNU Octave + GLPK are acceptable tools in this contest (as both of
them are open-source and free), so solving a LP (and MILP) problem is as
hard as filling three matrices and calling one function. Correct me if I am
wrong.
2015-06-09 23:50 GMT+03:00 Edward Lockhart edward.lockh...@gmail.com:
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 haibren...@gmail.com 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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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.
--
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CANBUrM_6aXtoLb-x%2BxWcZQsqxtyYPvLmy9yEMrhdbk-8xYMw4w%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
Re: [gcj] a Linear Programming approach to problem B of round 2
On Wednesday, June 10, 2015 at 10:16:19 AM UTC+3, M.H. wrote: I know that obviously coding a solution to LP is much harder than the simple analysis of this specific problem. I think, GNU Octave + GLPK are acceptable tools in this contest (as both of them are open-source and free), so solving a LP (and MILP) problem is as hard as filling three matrices and calling one function. Correct me if I am wrong. Obviously you are right. A few questions, if you may: 1. Do you know if octave and GLPK run smoothly on windows? Never heard of GLPK and I always had the impression that Octave is only for linux, but I search around and see that I may have been wrong about that. 2. Is it possible to call such methods from another language? Specifically python, which is my bestest and most favorite language of use? Is it easy? 3. Is it possible to have complete accuracy in octave/glpk when handling fractions? I have that option in python using the Fraction class, but I am not sure how many other languages have such classes... Thanks -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/10f414c5-ccf0-4f58-b27f-2773b3a58712%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] a Linear Programming approach to problem B of round 2
On Wednesday, June 10, 2015 at 2:37:00 PM UTC+3, M.H. wrote: 1. Do you know if octave and GLPK run smoothly on windows? Yes, both of them run on Windows, however I experienced several 'corner-cases'. E.g., I am not aware if modern Octave GUI (introduced in 3.8.x) is already available for Windows without Cygwin. I also had some problems with running it on Windows 8, but I must say, I wasn't too persistent to solve that problems. On the other hand, I worked with stable enough configuration of Octave 3.6.4 on Windows 7 - everything was fine. GLPK is both a standalone program for solving LP/MILP and a dynamic library for that purpose. Both of its forms are available on Windows. GLPK is actually used by Octave to solve LP/MILP in the form of glpk() function. So, you don't have to think about installing GLPK separately, if you have a working Octave installation, you already have glpk() function in it which uses GLPK dynamic library under the hood. However, you may prefer to use GLPK without Octave, it may be beneficial in some cases. So, to clarify my original proposal, Octave OR (not +) GLPK may be used. (I'am also aware that there are plenty of other LP/MILP solvers with permissive licenses - brightest minds can actually brew them in the contest time frame ;) - I just did not happen to use them.) 2. Is it possible to call such methods from another language? 1. Octave. Well, I didn't use anything of the kind, so my browsing of Octave documentation won't be more informative than anyone else's. However, there is always quick-and-dirty solution, that is to generate .m file, run it by subprocess.call (if it is Python) and parse the output. 2. GLPK. Yes, you can certainly use the mentioned quick-and-dirty way with the standalone form of GLPK, or use dll, or use java wrapper for that dll, or even Python module (PULP, as far as I remember - but that's quite another story). 3. Is it possible to have complete accuracy in octave/glpk when handling fractions? A very good question! As far as I understand, it is impossible with Octave's glpk() function. But if you use GLPK API directly, there is a function that solves LP in rational numbers - I didn't use it and the documentation says that it is tentative implementation. Kind regards, Andrew Great! Thanks for all the useful info. I think I'll try out GLPK in the near future. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/3d73fc4e-e7a1-4f0e-a120-64fa1bdd1003%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] a Linear Programming approach to problem B of round 2
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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.
Re: [gcj] a Linear Programming approach to problem B of round 2
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 haibren...@gmail.com 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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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.
