A) odd Sum
When is it impossible to reorder the elements?
Maybe sorting the elements might help.
If all elements in the array are equal, there's no solution. Otherwise, sort the array. The sum of the second half will indeed be greater than that of the first half.
def main():
half = int(input())
nums = list(map(int, input().split()))
nums.sort()
if nums[0] == nums[-1]:
print(-1)
else:
print(*nums)
main()
C) Number of Pairs
Lets sort boys and girls by skill. Let’s say
- boys_ptr = represents the index of boys_skill array
- girls_ptr = represents the index of girls_skill array
And let’s assume that the programming skill of a boy at boys_ptr is greater than the programming skill of the girl at girls_ptr index.
If the absolute difference in skill levels between a boy at boys_ptr and a girl at girls_ptr does not exceed 1, we add 1 to our answer and increment both boys_ptr and girls_ptr by 1.
If the absolute programming skill difference between a boy at the boys_ptr index and a girl at the girls_ptr index is found to be greater than one, then it is certain that any boy at an index beyond boys_ptr will also have an absolute skill difference of more than one when paired with the same girl at girls_ptr. Therefore, it is impossible to pair this girl with any of these boys. So we have to increment the girls_ptr and check the same thing.
Vice versa if the skill of a girl is greater than skill of a boy
-Time Complexity: O(n.log n)
def main():
num_boys = int(input())
boys_skill = list(map(int, input().split()))
num_girls = int(input())
girls_skill = list(map(int, input().split()))
boys_skill.sort()
girls_skill.sort()
boys_ptr = 0
girls_ptr = 0
num_pairs = 0
while boys_ptr < num_boys and girls_ptr < num_girls:
cur_boy_skill = boys_skill[boys_ptr]
cur_girl_skill = girls_skill[girls_ptr]
if abs(cur_boy_skill - cur_girl_skill) <= 1:
num_pairs += 1
boys_ptr += 1
girls_ptr += 1
elif cur_boy_skill < cur_girl_skill:
boys_ptr += 1
else:
girls_ptr += 1
print(num_pairs)
main()
D) Toys
In order to minimize the cost:
- We must assign the lowest price from a list of prices to the toy that appears most often.
- We must assign the second lowest price from the list of prices to the toy that appears the second most number of times.
- We must assign the third lowest price from the list of prices to the toy that appears the third most number of times.
- …
In order to minimize the cost:
- We must assign the highest price from a list of prices to the toy that appears most often.
- We must assign the second highest price from the list of prices to the toy that appears the second most number of times.
- We must assign the third highest price from the list of prices to the toy that appears the third most number of times.
- …
from collections import defaultdict
def main():
num_prices, num_toys = map(int, input().split())
prices = list(map(int, input().split()))
toys = defaultdict(int)
for i in range(num_toys):
toy = input()
toys[toy] += 1
count = list(toys.values())
prices.sort()
count.sort(reverse = True)
min_price = 0
max_price = 0
toy = 0
i = 0
while toy < num_toys:
min_price += (prices[i] * count[i])
max_price += (prices[num_prices - 1 - i] * count[i])
toy += count[i]
i += 1
print(min_price, max_price)
main()