Two Printers

Hi! Thanks for your message!

I can just vaguely recollect this problem - but re-reading it I could not see how in the second case we can achieve a time of 8 seconds.

See, we have 4 pages to print. We can print 3 of them on the first printer spending 3 seconds for each, and meanwhile print the single remaining page with another printer (spending 5 seconds). So one printer will work for 9 seconds and another for just 5.

I'm afraid I have no idea how we can do better... :(

Well, I think this could be bit more tricky - probably you need to check what could be ceiled and what floored. At least it is how I solved the problem when it was offered to me at some interview. I'm not sure, if some more elegant way exists... :)

This problem is making me extremely frustrated... you see, when I run my code, most of my answers are correct, but as was the case with the Point to Segment Distance problem (which I still have not solved :(.), a few are incorrect. I see that you mention checking what could be floored or ceiled, but I'm not sure exactly what to check; I have tried:

if ((x * y * n) / (x + y)) % 1 >= 0.5:
    return ...
etc...

and also:

if ((y * n) / (x + y)) % 1 >= 0.5:
    return...

but either way doesn't seem to work... I must be checking for the wrong thing, it seems, although since for most of the test cases I get correct answers, I am assuming that I've got the final equation correct. I just don't know what to check for in order to decide when to floor or ceil... I would sure appreciate any tips or suggestions :'(

Always,
Christopher P. Matthews

Hi, Christopher!

My own (not very elegant idea) is to find the approximate ratio of pages which should be printed on both printers and then to variate the resulting values to see whether we can get better overal time.

Hope I can explain it clear enough:

E.g. suppose we have to print 100 pages and according to printer speeds you found that exact proportion is to print 37.3 pages with one printer and remaining with the other.

Ok, let us simply try several "close" integers solutions, i.e.:

 first      second
printer     printer
  36          64
  37          63
  38          62
  39          61

For each of these few cases we find the time like max(36*X, 64*Y) and we will be able to choose the case for which this time is minimal.

I.e. if we can print non-integer amounts of pages on each printer, then the time will be a smooth function with perfect minimum. However since we are restricted to use only integer values, function is distorted with steps and minimum could be shifted a bit to left or right.

BTW, have you seen that our colleague Quandray have found a great article at TopCoder about "point to segment" problem (and attached the link to that forum post). Probably you will find it useful one day :)

Here is something i found useful while doing the problem

This seems to be a math question rather than algorithm question. The job distribution would be YN/(X+Y) pages to X, XN/(X+Y) pages to Y. Total time would be XYN/(X+Y) which is optimal (note that it is equivalent to N/(1/X + 1/Y). Since YN/(X+Y) might not be integer, you can just calculate a few values (if X is rounded up and Y is rounded down, and vice versa) , then take the minimum. Or as you said, you can round down both and give any remaining jobs to the faster machine.

Source : at StackOverflow

Hi, I'm quite new in Python (and programming), I have been looking at some solutions, and I don't understand that ceil and floor stuff. This is what I've done:

t = N / (1.0 / X + 1.0 / Y)
r0, r1 =  t % X, t % Y
if r0 and r1:
    return int(t + min(X - r0, Y - r1))
else:
    return int(t)

r0 and r1 is the time printers need to complete other page, and then I add the smallest. Could anyone explain how it works with ceil/floor?