M
M
mr jeery2017-09-13 21:48:58
Python
mr jeery, 2017-09-13 21:48:58

How to optimize a simple code?

There is such a task
Printers work with unequal speed. One prints a page in X seconds and the other in Y.
So now John and Mary are trying to figure out the minimum time they can take to print the entire document.
The input contains the number of test cases in the first line.
The tests themselves follow, one on each line.
Each of them contains three integers - XYN, where N does not exceed 1,000,000,000.
The response must contain the minimum print times for each case, separated by a space.
I solved it for small input values.
But if we take s1=24342423 s2= 23423413 pages=45234524
then everything will be fine.
Prompt algorithm

def twoprinters(s1,s2,pages):
    seconds=1
    r=0
    while True:
            r=(int(seconds/s1)+int(seconds/s2))
            if r>=pages:break
            else:
                seconds=seconds+1
                
 
    return seconds

Answer the question

In order to leave comments, you need to log in

2 answer(s)
W
Wataru, 2017-09-13
@jeerjmin

Optimizing the wrong solution is useless. There are 2 options:
1) Implement a binary search. You already have the right idea how to determine that in a given number of seconds you can print as many or more pages (floor(seconds/s1)+floor(seconds/s2) >= n). Now, instead of increasing seconds linearly, double it. Those. instead of seconds = seconds+1 do seconds = seconds*2. Then do a binary search on the interval [1,seconds].
2) Apply math. We need to find the minimum x such that floor(x/s1)+floor(x/s2) >= n.
Let's round off and solve x/s1 + x/s2 >= n.
x = ceil(n*s1*s2/(s1+s2)).
But. this will be an upper estimate, because we have omitted rounding, which reduces the real value of the number of pages printed in x seconds. But, attention, the actual number of pages will be a maximum of 2 pages less, because rounding knocks off a maximum of 1 page.
Now let's increase x to increase the number of printed pages. If you just add 1 every time, then almost always the value will not change, because x / s1 will still be fractional. The increment will only occur when x/s1 or x/s2 is an integer. The next such number can be easily found (it will be x divisible by s1 or s2. So the solution is:

def twoprinters(s1,s2,pages):
    seconds= int(pages*s1*s2 + s1 + s2 - 1)/(s1+s2)
    while int(seconds/s1)+int(seconds/s2) < pages:
            a = seconds - seconds%s1 + s1
            b = seconds - seconds%s2 + s2
            seconds = min(a,b)

This code will work instantly for very large numbers. Because the while loop here will be executed a maximum of 2 times. Each time the printed pages value will increase by at least 1, and it will initially be a maximum of 2 less than the answer. The weird calculations a and b are the next numbers in seconds, which are divisible by s1 and s2 respectively. We subtract the remainder from the division and get the previous or equal to seconds number divisible by s1 and s2. By adding s1 or s2 we get the next number, as we need.

T
themedev, 2017-09-13
@thematdev

Of course, I understand that Python is slow (because it sucks to compile line by line), but I did the optimization anyway:

seconds=1
    r=0

Write outside the input because you do not need to initialize the variable every time.
Also why check for if/else? Put a check
if (r<pages):
    seconds += 1

And put the operator to start the cycle from the beginning (I forgot it))), and if it doesn’t work, then break -> checks by 1 less.
And forget about foo = foo+1, there is +=
And if everything gets up again, then write in Java!

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question