[problem:430380A]↵
↵
<spoiler summary="Hint">↵
Try Binary Search.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Use binary search to find the position of the smallest name larger than the given name.↵
</spoiler>↵
↵
↵
<spoiler summary="Code 1">↵
~~~~~↵
from sys import stdin↵
↵
n = int(stdin.readline().strip())↵
queue = list(stdin.readline().strip().split())↵
q = int(stdin.readline().strip())↵
↵
↵
for _ in range(q):↵
left, right = 0, n — 1↵
val = stdin.readline().strip()↵
best = len(queue)↵
↵
while left <= right:↵
mid = (left + right) // 2↵
↵
if queue[mid] < val:↵
left = mid + 1↵
else:↵
best = mid↵
right = mid - 1↵
↵
print(best)↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Code 2">↵
~~~~~↵
from sys import stdin↵
import↵
↵
n = int(stdin.readline().strip())↵
queue = list(stdin.readline().strip().split())↵
q = int(stdin.readline().strip())↵
↵
↵
for _ in range(q):↵
left, right = 0, n — 1↵
val = stdin.readline().strip()↵
print(bisect_right(queue, val))↵
~~~~~↵
</spoiler>↵
↵
[problem:430380B]↵
↵
<spoiler summary="Hint">↵
Given a choice of dividers which one would give you the most outlets and how much.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Given a choice of dividers the one with the maximum value of outlets would have the most outlets, if we say the chosen divider has ai outlets and we initially have s outlets after using the divider we would have s + ai — 1 since we have to use one of the existing outlets. Until we have enough outlets repeat this.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
testcases = int(input())↵
for i in range(testcases):↵
students, m = map(int, input().split())↵
dividers = list(map(int, input().split()))↵
↵
dividers.sort(reverse=True)↵
↵
outlets = 2↵
dividers_used = 0↵
↵
while dividers_used < m and outlets < students:↵
outlets += dividers[dividers_used] - 1↵
dividers_used += 1↵
↵
if outlets < students:↵
print(-1)↵
else:↵
print(dividers_used)↵
~~~~~↵
</spoiler>↵
↵
[problem:430380C]↵
↵
<spoiler summary="Hint 1">↵
Try to see the different kinds of ways of using the elevator and stairs.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
There are 2^4 ways of arranging elevators and stair moves. Out of these arrangements, there are only some that make sense.↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
These are a different kind of arrangements:↵
e, e, s, s; e, s, s, s; s, e, e, e...↵
↵
Out of these configurations we can see that once we start using the elevator it doesn't make sense to go back to the stairs since if the elevator is less efficient than the stairs you shouldn't take the elevator but if not you should continue using the elevator since going back to the stairs wouldn't give you any better time. So the configurations you have to check are: use stairs only, walk to the elevator then use it, and use the elevator only.↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
t = int(input())↵
↵
for i in range(t):↵
wt, et, ef = list(map(int, input().split()))↵
# stairs, walk then elevator, use elevator only↵
print(min(wt * 4, wt * (ef) + et * (4 — ef), et * (ef + 4)))↵
</spoiler>↵
↵
[problem:430380D]↵
↵
<spoiler summary="Hint">↵
Find a way to count subarrays with a sum less than some value x.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
To find subarrays with a sum less than some value x we will use a sliding window, we expand our window until adding the next element would make its sum exceed x then we can be sure there are len(sliding window) subarrays with sum less than x since all the numbers are positive. To find subarrays with a sum between l and r, find the number of subarrays with a sum less than r + 1 and l then the answer would be the difference.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~↵
n, start, end = map(int, input().split())↵
nums = list(map(int, input().split()))↵
↵
↵
def sub_arrays_with_sum_less_than(target):↵
runningSum = answer = left = 0↵
↵
for right in range(len(nums)):↵
runningSum += nums[right]↵
↵
while runningSum >= target:↵
runningSum -= nums[left]↵
left += 1↵
↵
answer += right - left + 1↵
↵
return answer↵
↵
↵
print(sub_arrays_with_sum_less_than(end + 1) - sub_arrays_with_sum_less_than(start))↵
~~~~↵
</spoiler>↵
↵
[problem:430380E]↵
↵
<spoiler summary="Hint">↵
Think of merge sort.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
↵
↵
↵
We can notice that single-elimination bracket and merge sort have a similar process. We can leverage our knowledge in implementing the simulation for the game. But we have other rules, namely, we say a player has a possibility of moving forward if either there is a player with a lower rating or with absolute diff less than k. So if we can plug the check for winning possibility we can successfully simulate the game and find our possible winners.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~↵
from sys import stdin, stdout↵
↵
# Reading input values from standard input↵
n, k = map(int, stdin.readline().split())↵
arr = list(map(int, stdin.readline().split()))↵
↵
# Function to recursively solve the problem↵
def solve(i, count, k):↵
# Base case, when only one element is left in a sub-array↵
if count == 1:↵
return [i]↵
↵
# Divide the sub-array into two halves and solve each recursively↵
left = solve(i, count // 2, k)↵
right = solve(i + (count // 2), count // 2, k)↵
↵
# Merge the two sorted halves while checking the difference between elements↵
merged = []↵
l_ptr = r_ptr = 0↵
left_min, right_min = arr[left[0]], arr[right[0]]↵
↵
while l_ptr < len(left) and r_ptr < len(right):↵
if arr[left[l_ptr]] <= arr[right[r_ptr]]:↵
if right_min - arr[left[l_ptr]] <= k:↵
merged.append(left[l_ptr])↵
l_ptr += 1↵
else:↵
if left_min - arr[right[r_ptr]] <= k:↵
merged.append(right[r_ptr])↵
r_ptr += 1↵
↵
# Add any remaining elements from left or right halves while checking the difference between elements↵
while l_ptr < len(left) and right_min - arr[left[l_ptr]] <= k:↵
merged.append(left[l_ptr])↵
l_ptr += 1↵
↵
while r_ptr < len(right) and left_min - arr[right[r_ptr]] <= k:↵
merged.append(right[r_ptr])↵
r_ptr += 1↵
↵
# Return the merged and sorted sub-array↵
return merged↵
↵
↵
# Print the sorted and transformed sub-array obtained by calling the solve() function↵
print(*sorted(map(lambda x: x + 1, solve(0, 2**n, k))))↵
~~~~↵
</spoiler>↵
↵
[problem:430380F]↵
↵
<spoiler summary="Hint 1">↵
Try to see how to check if x persons can be transported using buses of sizes 18 and 12.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Any multiple of 6 greater than 6 can be described as a linear combination of 12 and 18.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Find the sum of a subarray with size 12 that started at 0 or 6 * b + 1, b being a positive integer.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~↵
from sys import stdin↵
↵
t = int(stdin.readline().strip())↵
↵
for _ in range(t):↵
n = int(stdin.readline().strip())↵
nums = list(map(int, stdin.readline().split()))↵
↵
prefix_sums = []↵
running_sum = 0↵
↵
for num in nums:↵
running_sum += num↵
prefix_sums.append(running_sum)↵
↵
# To avoid having to check if i - 1 is out of bounds↵
prefix_sums.append(0)↵
↵
# The best we can do is to take the first 12↵
best = prefix_sums[min(n - 1, 11)]↵
↵
for i in range(12, n, 6):↵
# Check if the next 12 is better than the current best↵
best = min(best, prefix_sums[min(i + 11, n - 1)] - prefix_sums[i - 1])↵
↵
print(best)↵
~~~~↵
</spoiler>↵
↵
[problem:430380G]↵
↵
<spoiler summary="Hint">↵
Try to see what kinda pairing creates optimal time.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The optimal matching starts by considering the smallest 2 ^ n — 1 as a base and changing the elements to be paired, then moving the window by 2 ^ n — 2, 2 ^ n — 3... and so on. The element determining the session time will be the largest among the elements in the current window and we can run the 2 ^ n — 1 then 2 ^ n — 2 then 2 ^ n -3... session for each window respectively.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~↵
n, k = list(map(int, input().split()))↵
↵
nums = sorted(list(map(int, input().split())), reverse=True)↵
↵
curr = 1 << n↵
total = 0↵
while k > 0:↵
curr //= 2↵
total += min(k, curr) * nums[curr]↵
k -= min(k, curr)↵
print(total)↵
~~~~↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Hint">↵
Try Binary Search.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Use binary search to find the position of the smallest name larger than the given name.↵
</spoiler>↵
↵
↵
<spoiler summary="Code 1">↵
~~~~~↵
from sys import stdin↵
↵
n = int(stdin.readline().strip())↵
queue = list(stdin.readline().strip().split())↵
q = int(stdin.readline().strip())↵
↵
↵
for _ in range(q):↵
left, right = 0, n — 1↵
val = stdin.readline().strip()↵
best = len(queue)↵
↵
while left <= right:↵
mid = (left + right) // 2↵
↵
if queue[mid] < val:↵
left = mid + 1↵
else:↵
best = mid↵
right = mid - 1↵
↵
print(best)↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Code 2">↵
~~~~~↵
from sys import stdin↵
import↵
↵
n = int(stdin.readline().strip())↵
queue = list(stdin.readline().strip().split())↵
q = int(stdin.readline().strip())↵
↵
↵
for _ in range(q):↵
left, right = 0, n — 1↵
val = stdin.readline().strip()↵
print(bisect_right(queue, val))↵
~~~~~↵
</spoiler>↵
↵
[problem:430380B]↵
↵
<spoiler summary="Hint">↵
Given a choice of dividers which one would give you the most outlets and how much.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Given a choice of dividers the one with the maximum value of outlets would have the most outlets, if we say the chosen divider has ai outlets and we initially have s outlets after using the divider we would have s + ai — 1 since we have to use one of the existing outlets. Until we have enough outlets repeat this.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
testcases = int(input())↵
for i in range(testcases):↵
students, m = map(int, input().split())↵
dividers = list(map(int, input().split()))↵
↵
dividers.sort(reverse=True)↵
↵
outlets = 2↵
dividers_used = 0↵
↵
while dividers_used < m and outlets < students:↵
outlets += dividers[dividers_used] - 1↵
dividers_used += 1↵
↵
if outlets < students:↵
print(-1)↵
else:↵
print(dividers_used)↵
~~~~~↵
</spoiler>↵
↵
[problem:430380C]↵
↵
<spoiler summary="Hint 1">↵
Try to see the different kinds of ways of using the elevator and stairs.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
There are 2^4 ways of arranging elevators and stair moves. Out of these arrangements, there are only some that make sense.↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
These are a different kind of arrangements:↵
e, e, s, s; e, s, s, s; s, e, e, e...↵
↵
Out of these configurations we can see that once we start using the elevator it doesn't make sense to go back to the stairs since if the elevator is less efficient than the stairs you shouldn't take the elevator but if not you should continue using the elevator since going back to the stairs wouldn't give you any better time. So the configurations you have to check are: use stairs only, walk to the elevator then use it, and use the elevator only.↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
t = int(input())↵
↵
for i in range(t):↵
wt, et, ef = list(map(int, input().split()))↵
# stairs, walk then elevator, use elevator only↵
print(min(wt * 4, wt * (ef) + et * (4 — ef), et * (ef + 4)))↵
</spoiler>↵
↵
[problem:430380D]↵
↵
<spoiler summary="Hint">↵
Find a way to count subarrays with a sum less than some value x.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
To find subarrays with a sum less than some value x we will use a sliding window, we expand our window until adding the next element would make its sum exceed x then we can be sure there are len(sliding window) subarrays with sum less than x since all the numbers are positive. To find subarrays with a sum between l and r, find the number of subarrays with a sum less than r + 1 and l then the answer would be the difference.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~↵
n, start, end = map(int, input().split())↵
nums = list(map(int, input().split()))↵
↵
↵
def sub_arrays_with_sum_less_than(target):↵
runningSum = answer = left = 0↵
↵
for right in range(len(nums)):↵
runningSum += nums[right]↵
↵
while runningSum >= target:↵
runningSum -= nums[left]↵
left += 1↵
↵
answer += right - left + 1↵
↵
return answer↵
↵
↵
print(sub_arrays_with_sum_less_than(end + 1) - sub_arrays_with_sum_less_than(start))↵
~~~~↵
</spoiler>↵
↵
[problem:430380E]↵
↵
<spoiler summary="Hint">↵
Think of merge sort.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
↵
↵
↵
We can notice that single-elimination bracket and merge sort have a similar process. We can leverage our knowledge in implementing the simulation for the game. But we have other rules, namely, we say a player has a possibility of moving forward if either there is a player with a lower rating or with absolute diff less than k. So if we can plug the check for winning possibility we can successfully simulate the game and find our possible winners.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~↵
from sys import stdin, stdout↵
↵
# Reading input values from standard input↵
n, k = map(int, stdin.readline().split())↵
arr = list(map(int, stdin.readline().split()))↵
↵
# Function to recursively solve the problem↵
def solve(i, count, k):↵
# Base case, when only one element is left in a sub-array↵
if count == 1:↵
return [i]↵
↵
# Divide the sub-array into two halves and solve each recursively↵
left = solve(i, count // 2, k)↵
right = solve(i + (count // 2), count // 2, k)↵
↵
# Merge the two sorted halves while checking the difference between elements↵
merged = []↵
l_ptr = r_ptr = 0↵
left_min, right_min = arr[left[0]], arr[right[0]]↵
↵
while l_ptr < len(left) and r_ptr < len(right):↵
if arr[left[l_ptr]] <= arr[right[r_ptr]]:↵
if right_min - arr[left[l_ptr]] <= k:↵
merged.append(left[l_ptr])↵
l_ptr += 1↵
else:↵
if left_min - arr[right[r_ptr]] <= k:↵
merged.append(right[r_ptr])↵
r_ptr += 1↵
↵
# Add any remaining elements from left or right halves while checking the difference between elements↵
while l_ptr < len(left) and right_min - arr[left[l_ptr]] <= k:↵
merged.append(left[l_ptr])↵
l_ptr += 1↵
↵
while r_ptr < len(right) and left_min - arr[right[r_ptr]] <= k:↵
merged.append(right[r_ptr])↵
r_ptr += 1↵
↵
# Return the merged and sorted sub-array↵
return merged↵
↵
↵
# Print the sorted and transformed sub-array obtained by calling the solve() function↵
print(*sorted(map(lambda x: x + 1, solve(0, 2**n, k))))↵
~~~~↵
</spoiler>↵
↵
[problem:430380F]↵
↵
<spoiler summary="Hint 1">↵
Try to see how to check if x persons can be transported using buses of sizes 18 and 12.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Any multiple of 6 greater than 6 can be described as a linear combination of 12 and 18.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Find the sum of a subarray with size 12 that started at 0 or 6 * b + 1, b being a positive integer.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~↵
from sys import stdin↵
↵
t = int(stdin.readline().strip())↵
↵
for _ in range(t):↵
n = int(stdin.readline().strip())↵
nums = list(map(int, stdin.readline().split()))↵
↵
prefix_sums = []↵
running_sum = 0↵
↵
for num in nums:↵
running_sum += num↵
prefix_sums.append(running_sum)↵
↵
# To avoid having to check if i - 1 is out of bounds↵
prefix_sums.append(0)↵
↵
# The best we can do is to take the first 12↵
best = prefix_sums[min(n - 1, 11)]↵
↵
for i in range(12, n, 6):↵
# Check if the next 12 is better than the current best↵
best = min(best, prefix_sums[min(i + 11, n - 1)] - prefix_sums[i - 1])↵
↵
print(best)↵
~~~~↵
</spoiler>↵
↵
[problem:430380G]↵
↵
<spoiler summary="Hint">↵
Try to see what kinda pairing creates optimal time.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The optimal matching starts by considering the smallest 2 ^ n — 1 as a base and changing the elements to be paired, then moving the window by 2 ^ n — 2, 2 ^ n — 3... and so on. The element determining the session time will be the largest among the elements in the current window and we can run the 2 ^ n — 1 then 2 ^ n — 2 then 2 ^ n -3... session for each window respectively.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~↵
n, k = list(map(int, input().split()))↵
↵
nums = sorted(list(map(int, input().split())), reverse=True)↵
↵
curr = 1 << n↵
total = 0↵
while k > 0:↵
curr //= 2↵
total += min(k, curr) * nums[curr]↵
k -= min(k, curr)↵
print(total)↵
~~~~↵
</spoiler>↵
↵
↵
