Forum ► Technical Corner ► Programming Problems Revival
Hello all,
I had a question about a programming problem and noticed that the old thread was totally dead, so I'm posting it here. I'm pretty new to programming in general so please go easy on me.
The problem in question is CSES' Factory Machines.
The solution I came up with was to use binary search to cut down the maximum possible searches to under 1 second, but I'm still having issues exceeding the time limit.
def main():
    n, t = map(int, input().split())
    arr = list(map(int, input().strip().split()))
 
    low = 0
    hi = 1e18
 
    while low <= hi:
        mid = (low + hi) // 2
        sum = 0
 
        for i in range(n):
            sum += mid // arr[i]
 
        if sum > t:
            hi = mid
        elif sum < t:
            low = mid
        else:
            return int(mid)
 
print(main())

Any recommendations at all would be very much appreciated.
38.014 days ago
Sep 20, 2021 - 7:22 PM
  
Your code there runs plenty fast on my machine, less than 50 milliseconds on the example they give. I struggle to see it running more than 20x slower on their end, maybe I'm missing something.
36.742 days ago
Sep 22, 2021 - 1:54 AM
  
That's what I was thinking, in the example they give the input is very small but my code should have O(log n) of running time, unless I'm doing something wrong.
36.567 days ago
Sep 22, 2021 - 6:06 AM
  
Track what's going on with the value in `sum`; you're adjusting it based on values from the input when you use `arr` (what's given on the second line?) and if those aren't as expected then you could be setting the bounds wrong, which would invalidate the usual runtime analysis of a binary search.

Edit:
I read the problem and I don't think you need to search the machine-speeds list since each of them contributes to the outcome; you're going to have to do something with each element.
18.328 days ago
Oct 10, 2021 - 11:50 AM
  
I'm taking each iteration of the midpoint and dividing it by i: the seconds per product. If I compare that output to the given t, I should be able to find the time by just returning low. I think my bounds should be fine as the maximum time allotted should be 1e18 (1<=t<=109 * 1 <=k<=109). I'm still not sure what I'm doing wrong on a conceptual level.
17.19 days ago
Oct 11, 2021 - 3:08 PM
  
I don't think you're accounting for multiple products finishing simultaneously - for example, the input:
3 7
1 1 1
would finish at time=3, when 9 products have been made. It doesn't look like you're handling that case, and so you could be ending up in an infinite loop, testing mid=2 or mid=3 over and over again.
15.827 days ago
Oct 12, 2021 - 11:52 PM
  
I don’t know if this is the thread, but how does
brew tap
detect dependencies?
11.532 days ago
Oct 17, 2021 - 6:56 AM
  
You've lost me. From a glance at the manpage,
brew tap
does nothing but list the currently "tapped" repositories. It lists the places that it'll look in to install new things.
11.055 days ago
Oct 17, 2021 - 6:23 PM
  
Brew knows how to install software from "formula" files. When I type
brew install cppcheck
, it checks the installed "taps" for a matching formula. In this case, it would resolve to this recipe file. The lines I've highlighted indicate dependencies on other software - cmake and python3.9 to build it, and pcre & tinyxml2 at runtime. The "brew install" command will repeat this installation process with each of those 4 items, to make sure that the installation goes smoothly. Once all dependencies are ready, brew will run the "install" function in the formula file, which issues some cmake commands to make sure everything gets compiled correctly.
11.008 days ago
Oct 17, 2021 - 7:31 PM
  
Reply to this thread
Forum > Technical Corner > Programming Problems Revival