Two Cans & String

{ "thread_id": "11509", "posts": [ { "id": "1167563", "time": "1632165742", "html": "Hello all,<br />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. <br />The problem in question is <a href=\"https://cses.fi/problemset/task/1620/\">CSES' Factory Machines</a>. <br />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.<br /><div style=\"text-align:left;background-color:#e8e8e8;padding:12px;-moz-border-radius:8px;border-radius:8px;font-family:"Courier New", monospace;overflow:auto;\"><span style=\"color:#008;\">def</span> main():<br />    n, t = map(int, input().split())<br />    arr = list(map(int, input().strip().split()))<br /> <br />    low = <span style=\"color:#a60;\">0</span><br />    hi = 1e18<br /> <br />    <span style=\"color:#008;\">while</span> low <= hi:<br />        mid = (low + hi) // <span style=\"color:#a60;\">2</span><br />        sum = <span style=\"color:#a60;\">0</span><br /> <br />        <span style=\"color:#008;\">for</span> i <span style=\"color:#008;\">in</span> range(n):<br />            sum += mid // arr[i]<br /> <br />        <span style=\"color:#008;\">if</span> sum > t:<br />            hi = mid<br />        <span style=\"color:#008;\">elif</span> sum < t:<br />            low = mid<br />        <span style=\"color:#008;\">else</span>:<br />            <span style=\"color:#008;\">return</span> int(mid)<br /> <br /><span style=\"color:#008;\">print</span>(main())</div><br />Any recommendations at all would be very much appreciated.", "user": "cc" }, { "id": "1168068", "time": "1632275680", "html": "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.", "user": "different55" }, { "id": "1168133", "time": "1632290783", "html": "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.", "user": "cc" }, { "id": "1172322", "time": "1633866657", "html": "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.<br /><br />Edit:<br />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.", "user": "gws" }, { "id": "1172526", "time": "1633964931", "html": "I'm taking each iteration of the midpoint and dividing it by <span style=\"font-style:italic;\">i</span>: the seconds per product. If I compare that output to the given <span style=\"font-style:italic;\">t</span>, I should be able to find the time by just returning <span style=\"font-style:italic;\">low</span>. I think my bounds should be fine as the maximum time allotted should be 1e18 (1<=t<=10⁹ * 1 <=k<=10⁹). I'm still not sure what I'm doing wrong on a conceptual level.", "user": "cc" }, { "id": "1173220", "time": "1634082735", "html": "I don't think you're accounting for multiple products finishing simultaneously - for example, the input:<br />3 7<br />1 1 1<br />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.", "user": "fwip" }, { "id": "1174321", "time": "1634453774", "html": "I don\u2019t know if this is the thread, but how does <div style=\"text-align:left;background-color:#e8e8e8;padding:12px;-moz-border-radius:8px;border-radius:8px;font-family:"Courier New", monospace;overflow:auto;\">brew tap</div> detect dependencies?", "user": "fattythefatguy" }, { "id": "1174338", "time": "1634494989", "html": "You've lost me. From a glance at the manpage, <div style=\"text-align:left;background-color:#e8e8e8;padding:12px;-moz-border-radius:8px;border-radius:8px;font-family:"Courier New", monospace;overflow:auto;\">brew tap</div> does nothing but list the currently "tapped" repositories. It lists the places that it'll look in to install new things.", "user": "different55" }, { "id": "1174347", "time": "1634499106", "html": "Brew knows how to install software from "formula" files. When I type <div style=\"text-align:left;background-color:#e8e8e8;padding:12px;-moz-border-radius:8px;border-radius:8px;font-family:"Courier New", monospace;overflow:auto;\">brew install cppcheck</div>, it checks the installed "taps" for a matching formula. In this case, it would resolve to <a href=\"https://github.com/Homebrew/homebrew-core/blob/f7ece95ffa72b77eb25986998add7a500a08b95f/Formula/cppcheck.rb#L17-L22\">this recipe file</a>. 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.", "user": "fwip" } ], "users": { "cc": { "name": "CC", "key": "cc", "url": "/users/cc", "avatar": "/uploads/drawn/28383.png", "rankClass": "civilian", "rankText": "", "posts": "62" }, "different55": { "name": "Different55", "key": "different55", "url": "/users/different55", "avatar": "/uploads/drawn/5716.png", "rankClass": "civilian", "rankText": "", "posts": "121" }, "gws": { "name": "gws", "key": "gws", "url": "/users/gws", "avatar": "/uploads/drawn/29928.png", "rankClass": "civilian", "rankText": "", "posts": "5768" }, "fwip": { "name": "Fwip", "key": "fwip", "url": "/users/fwip", "avatar": "/uploads/drawn/583.png", "rankClass": "admin", "rankText": "Admin", "posts": "3726" }, "fattythefatguy": { "name": "Fatty the fat guy", "key": "fattythefatguy", "url": "/users/fattythefatguy", "avatar": "/uploads/drawn/16460.png", "rankClass": "civilian", "rankText": "", "posts": "2535" } }, "page_num": 1, "locked": 0, "total_pages": 1 }

Follow TCaS on Twitter. The fate of the world depends on it.