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()

Greedily take the smallest character in both strings. What's the exception to this?

We can't take the smallest character in both strings when we've already took k elements from the string we chose. Denote A as the number of characters we've took from string str1 in the last few consecutive moves and denote B the same for str2. If A = k, then we have to take the smallest character in string str2 instead of possibly str1. If B = k, then we have to take the smallest character in string str1 instead of possibly str2.

Remember to reset A to 0 when you take a character from b. Similarly, reset B to 0 when you take a character from a.

def solve():
    len_str1, len_str2, k = map(int, input().split())
 
    str1 = list(input())
    str2 = list(input())
    
    str1.sort()
    str2.sort()
    
    output = []
    str1_cnt = 0
    str2_cnt = 0
    i = 0
    j = 0
    
    while i < len_str1 and j < len_str2:
        
        if ((str1[i] < str2[j] and str1_cnt < k) or str2_cnt == k):
            output.append(str1[i])
            str1_cnt += 1
            str2_cnt = 0
            i += 1
            
        else:
            output.append(str2[j])
            str2_cnt += 1
            str1_cnt = 0
            j += 1
    
    print(''.join(output))
    
def main():
    num_tests = int(input())
    
    for i in range(num_tests):
        solve()
 
main()

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()

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 maximize 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()

We can find the number of ways to arrange k consecutive empty seats either in a row or a column by considering each row and column individually. For each row, we need to count the number of ways we can place k empty seats in consecutive order. Similarly, for each column, we need to calculate the number of ways we can place k empty seats in contiguous order. After counting the number of combinations for each row and column, we can simply add the two results together for our final answer.

How do we count the number of k consecutive empty seats in a row or column?

If the length of consecutive empty seats in a row or column is no smaller than k, we can count all the possible combinations of k consecutive empty seats adding up to that length. That is, for any given length len, (len-k+1) additional sets of k consecutive empty seats can be accounted for in our solution.

But, be careful. When k=1, the algorithm shown above is completely wrong. (Why?) So we need to deal with that situation separately.

def main():
    ROWS, COLS, k = map(int, input().split())
    
    seats = []
    for i in range(ROWS):
        seats.append(input())
     
    #find number of ways to arrange seats in each row   
    num_ways = 0
    for row in range(ROWS):
        empty_slots = 0
        
        for col in range(COLS):
            if seats[row][col] == '.':
                empty_slots += 1
            else:
                empty_slots = 0
            
            if empty_slots >= k:
                num_ways += 1
    
    #find number of ways to arrange seats in each column
    for col in range(COLS):
        empty_slots = 0
        
        for row in range(ROWS):
            if seats[row][col] == '.':
                empty_slots += 1
            else:
                empty_slots = 0
            
            if empty_slots >= k:
                num_ways += 1
    
    #handle k = 1 case
    if k == 1:
        num_ways //= 2
    
    print(num_ways)
 
main()