To solve the problem, we reverse the input string (since it's seen from the other side of a glass) and then replace each character with its mirrored version: 'p' becomes 'q', 'q' becomes 'p', and 'w' stays the same. We repeat this for each test case.

t = int(input())
mirror_map = {'p': 'q', 'q': 'p', 'w': 'w'}

for _ in range(t):
    a = input()
    b = ''.join(mirror_map[ch] for ch in reversed(a))
    print(b)

We're given a list of integers and need to determine the largest number that is not a perfect square. A perfect square is any number that can be expressed as the square of an integer (e.g., 1, 4, 9, 16, etc.). Negative numbers can never be perfect squares, so they automatically qualify. For each number in the list, we check whether it is a perfect square by computing the square root and checking if its square (after converting to an integer) equals the original number. If it's not a perfect square, we consider it for our result. After filtering all non-perfect squares, we take the maximum among them and print it. This guarantees the most "un-square" value in the list.

def is_square(x):
    if x < 0:
        return False
    low, high = 0, x
    while low <= high:
        mid = (low + high) // 2
        square = mid * mid
        if square == x:
            return True
        elif square < x:
            low = mid + 1
        else:
            high = mid - 1
    return False

n = int(input())
a = list(map(int, input().split()))

max_non_square = -10**6 - 1

for num in a:
    if not is_sq(num):
        max_non_square = max(max_non_square, num)

print(max_non_square)

To determine when Robin Hood will appear, we need to identify the minimum extra gold x that the richest citizen must receive such that more than half the population becomes discontent. A citizen is discontent if their wealth is strictly less than half of the average wealth after the richest receives x extra gold. For each test case, we calculate the total wealth and sort the list of citizens' wealth. We then perform a binary search on x to find the smallest value that causes more than half the citizens to be discontent. For each x, we compute the new average wealth and determine how many citizens have wealth below half of that average using binary search. If such an x is found, we output the smallest valid x; otherwise, we return -1. This method is efficient and ensures that we meet the problem’s constraints even for large input sizes.

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    
    if n <= 2:
        print(-1)
        continue
    
    left, right = 0, 10 * sum(arr)
    total = sum(arr)
    
    while left < right:
        mid = (left + right) // 2
        average_half = (total + mid) / (2 * n)
        
        if arr[n // 2] < average_half:
            right = mid
        else:
            left = mid + 1
    
    print(left)

To solve this problem: Sort the array a.

For each element b_j in array b, use binary search to find how many elements in a are less than or equal to b_j. This is the index of the first element strictly greater than b_j in the sorted array a.

We can use upper_bound logic for that.

Time Complexity:

Sorting a: $$$O(n \log n)$$$

For each of the $$$m$$$ elements in b, we perform binary search in $$$O(\log n)$$$

Total: $$$O((n + m) \log n)$$$

import sys 
input = sys.stdin.readline 

def bs(target, a):
    left, right = 0, len(a) - 1
    
    while left <=  right:
        mid = left + (right - left) // 2
        if a[mid] == target:
            left = mid + 1
        elif a[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    return left
        
def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.sort()
    result = [0] * m

    for i in range(m):
        result[i] = bs(b[i], a)
        
    print(*result)
if __name__ == '__main__':
    solve()

First, let's calculate how many different values we can have. The maximum value of k is 8, so the maximal number of distinct values K we need to consider is 2^k. To avoid overflow issues, it's safe to use K = 2^min(20, k), since 2^20 is already greater than any reasonable n.

We begin by sorting the array and compressing equal values. The goal is to choose no more than K consecutive distinct values such that they cover the maximum number of original elements. If K is greater than the number of unique values in the array, the answer is simply 0.

To solve this efficiently, we can: - Precompute prefix sums over the frequencies of the compressed values. - Try all possible intervals of K consecutive values and select the one covering the most elements.

The overall time complexity is O(n log n), due to the initial sort and preprocessing steps.

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

carr = []
i = 0
while i < n:
    count = 1
    j = i + 1
    while j < n and arr[j] == arr[i]:
        count += 1
        j += 1
    carr.append((arr[i], count))
    i = j

limit = min(pow(2, 8 * m // n), pow(2, 20))
ans = 0
l = 0
curr = 0

for r in range(len(carr)):
    curr += carr[r][1]
    while r - l + 1 > limit:
        curr -= carr[l][1]
        l += 1
    ans = max(ans, curr)

print(n - ans)

Let's look at sorts, for which there is more than one flower in the bouquet. We can prove, that there can be only one such sort. Let's assume that there are sorts x and y with bx≥by , such that for both sorts there are at least 2 flowers. Let's exclude flower of sort y from bouquet and add flower of sort x . The total happiness will change by bx−by , so it will not decrease. Repeating this, we can leave bouquet with only one flower of sort y without decreasing the total happiness. So, there always exists an answer where there is only one sort with multiple flowers.

Using this fact, we can solve the problem the following way. Let's iterate over each sort of flowers and for every x suppose that there are multiple flowers of sort x . It is obvious, that if some sort y has ay>bx , then we should take one flower of such sort, and if ay≤bx , then we would better take another flower of sort x . So, we need to know sum of ai for all flowers that have ai>bx . To do it in O(logm) , we can sort all flowers by ay in decreasing order, calculate prefix sums on that array, and using binary search find maximum k , such that ak>bx and get prefix sum of ai for first k sorts. All the rest n−k flowers will be of the sort x .

Also we should take into account the case when for each sort only one flower of that sort is taken. In that case we should take n sorts with largest ai .

That way we can get the answer in O(mlogm) time.

import bisect

def solve():
    inputCount = int(input())
    while inputCount:
        ip = input()
        if not ip: continue
        n, m = map(int, ip.split())

        flowers, a = [], []
        for _ in range(m):
            x, y = map(int, input().split())
            flowers.append((x, y))
            a.append(x)
        
        a_sorted = sorted(a)
        pre = [0] * (m + 1)
        for i in range(m - 1, -1, -1):
            pre[i] = pre[i + 1] + a_sorted[i]
        
        ans = 0
        
        for i in range(m):
            x, y = flowers[i]
            pos = bisect.bisect_right(a_sorted, y)
            count = m - pos
            sum_ = pre[pos] if pos < m else 0
            
            if x <= y:
                sum_ += x
                count += 1
            
            if count >= n:
                current = pre[m - n] if (m - n) >= 0 else 0
            else:
                current = sum_ + (n - count) * y
            
            if current > ans:
                ans = current
        
        print(ans)
        inputCount -= 1

solve()