https://www.acmicpc.net/problem/16401
initial
So rmb that binary search is literally making mid our guess answer? So mid will be the maximum length of snack that we can allocate to each cousin.
Somehow i was thinking in terms of area, where mid multiplied by number of cousins is the guess area, and if this guess area is greater than the sum of the snakcs, then our guess is too big so we shift our right pointer to mid-1. Then I also had to check if mid is smaller or equal to iter snack cuz if it is bigger, then our guess is too big.
But this logic is complicated and my impl was fucked so i googled
solution
The crucial hint that i missed in the question is we can split the snack up. So instead of doing it by the area, we can do by the number of split snacks. As we iterate through the snack, we add number of split snacks by snack//mid. If this number of split snacks is greater or equal to number of cousins, we have to increase our mid by incrementing left to mid+1 to maximise our guess mid.
I tried optimising via if snack is less than our mid, we break out of the loop. But if we have 1 2 3 4 5 snacks and our mid is 3, we prematurely break out of the loop at 1 instead of calculating 3,4,5. So we have to reverse sort for this action but it is n log n and it is less efficient so the above solution is the best.
revisited nov 27th 24
I tried using my template of left<right.
We define the range as [left, right). Here, left is inclusive, and right is exclusive. So we have to put right = maximum possible value +1.
We're searching for the largest valid length (mid) that satisfies the condition (in this case, dividing the candies into at least M pieces of equal length).
If mid satisfies the condition, we move left to mid + 1 to try a longer length.
If mid doesn't satisfy the condition, we move right to mid to try shorter lengths.
Final State of left and right
When the loop ends, left == right. This happens because:
left has been pushed to the smallest invalid value — the first value that fails the condition.
The largest valid value is therefore left - 1.
import sys
input = sys.stdin.readline
m,n=map(int,input().split())
lst=list(map(int,input().split()))
left,right=1,max(lst)+1
ans=0
while left<right:
mid = left + (right-left)//2
total=0
for i in lst:
total += i//mid
if total>=m:
ans=max(ans,mid)
left=mid+1
else:
right=mid
print(left-1)complexity
normally binary search is log n but since we did end = max(lst), where max() is n time, it is n log n time.
Time Complexity:
The time complexity is primarily determined by the binary search loop. In each iteration of the loop, a binary search operation is performed, and the total sum of the elements in lst is calculated. The binary search has a time complexity of O(log(max(lst))), and for each iteration, a linear scan of the lst is performed, resulting in a time complexity of O(n). Therefore, the overall time complexity is O(n log(max(lst))) for the given code.
Space Complexity:
The space complexity is relatively low as it only uses a constant amount of additional space, regardless of the size of the input. The space complexity is O(1).
In summary:
Time Complexity: O(n log(max(lst)))
Space Complexity: O(1)
