You are to collect a total of $N$ litres of red and $M$ litres of blue liquid. For doing job $i$ for time $t$, you get $a_i t$ litres of red and $b_i t$ litres of blue liquid. $t$ need not be an integer. At a time you can only do one job. You can choose some (or all) of the jobs and do it for your desired time. Given such $n$ jobs in the input and their respective $a_i$ and $b_i$ find the lowest total time in which you can get $N$ litres of red and $M$ litres of blue liquid.

How do I solve this problem using convex hull?


Perhaps you want a hint first? Of course you start by considering all vectors $(a_i,b_i)$ first. The vector $(a_i,b_i)$ indicates the amounts you earn by working one hour on job $i$.

What is the meaning of any point on the line segment between points $(a_i,b_i)$ and $(a_j,b_j)$?

If any point $(a_k,b_k)$ is within the triangle $(0,0)$, $(a_i,b_i)$, $(a_j,b_j)$ why can you discard it?

  • $\begingroup$ the line segment between points $(a_i,b_i)$ and $(a_j,b_j)$ means in one hour you can get to any point here, but why discard points in the triangle? $\endgroup$ – emmy Dec 25 '15 at 14:55
  • $\begingroup$ how do I find what I can do in two hours or more? $\endgroup$ – emmy Dec 26 '15 at 8:41
  • $\begingroup$ Vectors $(a_k,b_k)$ within the triangle (or the convex hull in general) are not efficient enough. Draw a line from origin $(0,0)$ to the vector $(a_k,b_k)$ and find the intersection $I$ with the hull. Then $I$ is reachable in one hour but will in fact give a multiple of liquids compared to $(a_k,b_k)$. $\endgroup$ – Hendrik Jan Dec 26 '15 at 12:27
  • $\begingroup$ Same idea works when you want to investigate problems that need more than one hour. Scale. Solve the problem with the same $M/N$ proportion but in one hour. Then multiply. Again line through the origin. $\endgroup$ – Hendrik Jan Dec 26 '15 at 12:31
  • $\begingroup$ so I add points $a_i,b_i$ for all i, find the convex hull and then draw a ray from (0,0) to (N,M). Find its last intersecting point with the hull and that would be the most I can do in an hour. That's it right? $\endgroup$ – emmy Dec 27 '15 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.