[problem:422945A]
Try sorting.
Sort the three numbers and return the second number.
Time Complexity — O(1) Space Complexity — O(1)
test_cases = int(input())
for i in range(test_cases):
numbers = list(map(int, input().split()))
numbers.sort()
print(numbers[1])
[problem:422945B]
Try sorting.
Sort the laptops based on their price, and for laptops with the same price sort based on quality. Check if a pair of neighboring laptops have different prices and decreasing quality exist.
Time Complexity — O(N*log(N)) Space Complexity — O(1)
length = int(input())
laptops = []
for i in range(length):
price, quality = map(int, input().split())
laptops.append((price, quality))
laptops.sort()
for i in range(length - 1):
cur_laptop_price, cur_laptop_quality = laptops[i]
next_laptop_price, next_laptop_quality = laptops[i + 1]
if (
cur_laptop_price != next_laptop_price
and cur_laptop_quality > next_laptop_quality
):
print("Happy Alex")
exit()
print("Poor Alex")
[problem:422945C]
Find an example that can't be sorted by reversing a subarray of it.
Create a sorted copy of the given array. Find the first and the last position where the two arrays differ, and reverse the segment between these positions. Check if the two arrays are equal.
Time Complexity — O(N log(N)) Space Complexity — O(N)
from math import inf
n = int(input())
array = list(map(int, input().split()))
sorted_array = sorted(array)
start, end = inf, -inf
for idx in range(n):
if array[idx] != sorted_array[idx]:
start = min(start, idx)
end = idx
if start == inf:
print("yes")
print(1, 1)
else:
i, j = start, end
while i <= end:
if array[i] != sorted_array[j]:
print("no")
exit()
i += 1
j -= 1
print("yes")
print(start + 1, end + 1)
[problem:422945D]
How does sorting help?
What improvement can we make on the sorted array?
After sorting, if arr[-1] >= arr[-2] + arr[-3], what does this tell us?
To summarize, it involves 1) Sorting the array in non-decreasing order 2) Checking if the last element of the array is greater than or equal to the sum of the second-to-last and third-to-last elements. 3) If it is, print "NO" as there is no solution. 4) If it is not, swap the last and second-to-last elements of the array and print the new array.
Time Complexity — O(N log(N)) Space Complexity — O(1)
length = int(input())
nums = list(map(int, input().split()))
nums.sort()
if nums[-1] >= nums[-2] + nums[-3]:
print("NO")
else:
print("YES")
nums[-1], nums[-2] = nums[-2], nums[-1]
print(*nums)
[problem:422945E]
Try to see the difference between two consecutive elements in the sequence below:
1, 2, 4, 8 ...
2^0, 2^1, 2^2, 2^3 ...
We are required to find the number of windows which could be increasing given the condition below: - If you multiply the first element by 2^0, the second element by 2^1, ..., and the (k+1)-st element by 2k, then this subarray is sorted in a strictly increasing order. Multiplying the first element by 2^0, the second by 2^1 ... and (k + 1)th element by 2^k means multiplying [i + 1]th element by 2 and checking if it's greater than [i]th element. Check if nums[i] < 2 * nums[i + 1] if the above condition is satisfied widen the window and check if the window is greater than k, if the above condition failed to hold, start the search from the index that failed the condition.
Time Complexity — O(N) Space Complexity — O(1)
def inpNum():
return int(input())
def inpSepNum():
return map(int, input().split())
def inpNumList():
return list(map(int, input().split()))
test_cases = inpNum()
for _ in range(test_cases):
n , k = inpSepNum()
nums = inpNumList()
subarrays = 0
left = 0
for right in range(1,n):
# If the required condition failed move the left pointer to right
if nums[right]*2 <= nums[right-1]:
left = right
# When the window size exceeds k increment subarrays
if right - left >= k:
subarrays += 1
print(subarrays)