Hi, I am working on this problem and I am a little confused about the last line of the editorial: " Then the actual answer should be adjusted by (K−T)∗x because all the extra / less workers will be providing marginal value x. This is what the last few lines of the code below are doing."
If you look at the solution code, clearly the ‘ct’ function is finding the maximum C for each i such that a[i]/(C * (C + 1)) >= X, where C is rounded down. Thus, C is the max and if you increase C by any amount, a[i]/(C * (C + 1)) < X. Doesn’t this mean that the K - T extra cows might each contribute a marginal value of less than X?
Technically, yes. However, the binary search which led to finding lo was down to the decimals. Specifically, a C++ double holds up to 15 decimal points, and the binary search went between 0 and 1e18. The base 2 logarithm of 10^(15 + 18) is ~110. The program iterates the binary search 200 times. This means that the binary search will compute the value of X with precision to the 15th decimal place.
This means that the marginal value less than X will be less than 10^(-15), which is so low it will not affect the solution if we adjust by (K-T) * X instead of the exact values. (The problem also specifically mentions that the answer is >0.1 away from the boundary of two integers, so this will definitely not impact the answer upon rounding).