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 for i in range(m)]

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