https://www.acmicpc.net/problem/1300
initial
At first glance, dafuq why is it gold 1? But we cant store all the elements in a given list or else we get space issues. So i saw a hint and there was binary search question. But I was so stuck in making it a sorted list cuz binary search works on sorted numbers. BUT!! It doesnt necessarily have to be a LIST. As long as the numbers that we are searching in a range is sorted is fine. So actually we dont have to manually store all the matrix values in a list. Instead, rmb that binary search can be used to literally guess an answer. Here, we are gonna guess the minimum value answer to have m elements that are smaller than or equal to that minimum value answer that we guessed.
So our left starts at 1 cuz it is 1-indexed and right is n*n value and our mid is gonna be our guess. Now how do we count how many elements there are in that 2x2 matrix that have smaller value than our mid guess? As we iterate through the rows i, we see that mid//i , which is mid divided by the row number would tell us the maximum number of elements in that column that satisfies our condition.
Take mid as 10 for example and n=3. When i is 1, 10//1 = 10. So this means that for any value of j, product of ij will be less than 10. So we increment count by that much. BUT we cant increment count by 10 cuz our column elements can only store 3. So we do min(value//i, n). Then if i is 3, 10//3 =3, so 31, 32, 33 they are all less than 10. So we can increment count by that much.,
Once we get the total count, if count is too high we shift right pointer to mid and else we shift left pointer to mid+1. I always get confused with whether to return left or left -1 but here it is left Im not sure why.
solution
def count_valid(num, n):
count = 0
for i in range(1, n + 1):
count += min(num // i, n)
return count
def binary_search_smallest_element(n, m):
left, right = 1, n * n
while left < right:
mid = left + (right - left) // 2
count = count_valid(mid, n)
if count >= m:
right = mid
else:
left = mid + 1
return left
n = int(input())
m = int(input())
result = binary_search_smallest_element(n, m)
print(result)
complexity
Time Complexity:
log n^2 cuz firstly range is n^2 but binary search reduces time via log so it is log n^2
The time complexity of the binary search algorithm is O(log(n^2)) since you are performing a binary search on the range from 1 to n^2.
The count_valid function has a time complexity of O(n) because it iterates over all possible values of i from 1 to n.
Therefore, the overall time complexity of the binary search algorithm is dominated by the binary search itself, resulting in O(log(n^2)).
Space Complexity:
The space complexity is O(1) because the algorithm uses a constant amount of extra space. The only variables used are left, right, mid, and count, and their space requirements do not depend on the input size.
In summary:
Time Complexity: O(log(n^2))
Space Complexity: O(1)
