Instead of thinking about “alternating every two steps”, define four explicit turns:
- Alice1 (current is Alice, next is also Alice)
- Alice2 (current is Alice, but next is Bob)
- Bob1 (current is Bob, next is also Bob)
- Bob2 (current is Bob, but next is Alice)

These repeat in a cycle.

If we encode these states as numbers:
- Alice1 = 0
- Alice2 = 1
- Bob1 = 2
- Bob2 = 3

Then after each step: turn = (turn + 1) % 4

This means if turn < 2, it is Alice's turn else it is Bob's turn.

We simulate distributing cards one by one.

We maintain:
- cards (how many cards will be given in this turn)
- cards_given (how many cards we’ve given in this turn)
- turn (whose turn it is (from 0 to 3))

We start from turn = 1 # Alice2

For each card:
- if it is Alice's turn, we increment Alice's card count by one
- if it is Bob's turn, we increment Bob's card count by one

When we finish a turn (cards_given == cards):
- Increase cards
- Reset cards_given
- Move to next turn with (turn + 1) % 4

Time Complexity: O(n) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    
    alice = 0
    bob = 0
    
    cards = 1
    cards_given = 0
    turn = 1
    
    for _ in range(n):
        if turn < 2:
            alice += 1
        else:
            bob += 1
        
        cards_given += 1
        
        if cards_given == cards:
            cards += 1
            cards_given = 0
            turn = (turn + 1) % 4
    
    print(alice, bob)

In Approach 1, we distribute cards one by one.
Can we avoid iterating over every single card?

During a turn, the same player receives all cards cards.
So instead of incrementing one by one, we can directly add the whole amount at once.

At a given turn:
- The number of cards to give is cards.
- These cards all go to the same player in this turn.
- But if the remaining cards are fewer than cards, we give only the remaining cards and stop.

So instead of looping n times, we can:
- Give min(cards, remaining)
- Decrease remaining
- Move to the next turn

How many turns can there be?
Since: 1 + 2 + 3 + ... + k ≈ k² / 2
To reach n cards, k is approximately √(2n)

Time Complexity: O(√n) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    
    alice = 0
    bob = 0
    
    cards = 1
    turn = 1
    remaining = n
    
    while remaining > 0:
        give = min(cards, remaining)
        
        if turn < 2:
            alice += give
        else:
            bob += give
        
        remaining -= give
        cards += 1
        turn = (turn + 1) % 4
    
    print(alice, bob)

A1 — Approach 1

The deck is:

W B W B W B W B ...

So:
- Position 1 → White
- Position 2 → Black
- Position 3 → White
- Position 4 → Black
- Position 5 → White ...

Notice a pattern? Odd positions are White and Even positions are Black.

We simulate distributing cards one by one.

We maintain:
- cards (how many cards will be given in this turn)
- cards_given (how many cards we’ve given in this turn)
- turn → (whose turn it is (from 0 to 3))

We start from turn = 1 # Alice2

For each card:
- if it is Alice's turn and if the current card position is odd, we increment Alice's White card count by one
- if it is Alice's turn and if the current card position is eve, we increment Alice's Black card Count by one
- if it is Bob's turn and if the current card position is odd, we increment Bob's White card count by one
- if it is Bob's turn and if the current card position is eve, we increment Bob's Black card Count by one

When we finish a turn (cards_given == cards):
- Increase cards
- Reset cards_given
- Move to next turn with (turn + 1) % 4

Time Complexity: O(n) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    
    white_alice = 0
    black_alice = 0
    white_bob = 0
    black_bob = 0
    
    cards = 1
    cards_given = 0
    turn = 1
    
    for pos in range(1, n + 1):
        if turn < 2:
            if pos % 2 == 1:
                white_alice += 1
            else:
                black_alice += 1
        else:
            if pos % 2 == 1:
                white_bob += 1
            else:
                black_bob += 1
        
        cards_given += 1
        
        if cards_given == cards:
            cards += 1
            cards_given = 0
            turn = (turn + 1) % 4
    
    print(white_alice, black_alice, white_bob, black_bob)

A1 – Approach 2 and A2 – Approach 1

In A1 – Approach 2, instead of distributing cards one by one, we distribute an entire turn at once.

In A2 – Approach 1, we determined that:
- Odd positions → White
- Even positions → Black

Can we combine both ideas?

Suppose we are giving k consecutive cards starting from position pos.

We want to count how many of those k positions are even.

There are two cases:

Case 1: pos is even The sequence looks like: Even, Odd, Even, Odd, ...

In this case:
- Number of even positions = (k + 1) // 2
- Number of odd positions = k // 2

Case 2: pos is odd The sequence looks like: Odd, Even, Odd, Even, ...

In this case:
- Number of even positions = k // 2
- Number of odd positions = (k + 1) // 2

Since:
- Even positions → Black
- Odd positions → White

We can compute white and black cards in O(1).

We combine the optimized turn simulation from A1 – Approach 2 with the color counting observation.

We maintain:
- cards → size of current turn
- turn → from 0 to 3 (start from 1)
- remaining → cards left
- pos → starting position of current block (initially 1)

At each turn:
- Compute give = min(cards, remaining)
- Compute how many whites and blacks are inside this block
- Assign these counts to Alice's and Bob's White and Black cards count depending on turn
- Update the variables

Time Complexity: O(√n) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    
    white_alice = 0
    black_alice = 0
    white_bob = 0
    black_bob = 0
    
    cards = 1
    turn = 1
    remaining = n
    pos = 1
    
    while remaining > 0:
        give = min(cards, remaining)
        
        if pos % 2 == 1:
            white = (give + 1) // 2
            black = give // 2
        else:
            white = give // 2
            black = (give + 1) // 2
        
        if turn < 2:
            white_alice += white
            black_alice += black
        else:
            white_bob += white
            black_bob += black
        
        remaining -= give
        pos += give
        cards += 1
        turn = (turn + 1) % 4
    
    print(white_alice, black_alice, white_bob, black_bob)

If the final array is a permutation, then it must contain exactly:

1, 2, 3, ..., N for some integer N.

So every number starting from 1 must appear exactly once. This means its length is also N.

We already have some numbers in b. So the only numbers we can append are the numbers missing from the permutation.

Try iterating from 1 upward:
- If the number is already in b, skip it.
- Otherwise, subtract it from s (since it must be one of the lost numbers).

Stop when s ≤ 0.

We simulate constructing the permutation from 1 upward.

Convert b into a set for fast lookup.

Starting from x = 1, until s ≤ 0:
- If x is not in the set: Subtract x from s and Append x to b
- Increase x by 1

If s == 0 and b is a permutation, it is YES, otherwise it is NO.

Time complexity: O(m + √s) (Can you tell why?)

t = int(input())

for _ in range(t):
    m, s = map(int, input().split())
    b = list(map(int, input().split()))
    
    present = set(b)
    
    x = 1
    while s > 0:
        if x not in present:
            s -= x
            b.append(x)
        x += 1
    
    if s == 0 and len(b) == max(b):
        print("YES")
    else:
        print("NO")

If you type the string using only append, you need exactly n operations.

To use strictly less than n operations, you must use at least one copy-paste operation.

Copy-paste is useful only if some substring appears at least twice in the string, and the two occurrences do not overlap.

You type the first occurrence normally, then copy it to produce the second one.

To actually save operations, the copied substring must have length ≥ 2.

Copying a substring of length 1 costs the same as appending one character, so it gives no benefit.

If any substring of length ≥ 2 appears twice (non-overlapping), then its first two characters also form a substring of length 2 that appears twice (non-overlapping).

So it is enough to check only substrings of length 2.

We iterate over all substrings of length 2.

For each substring:
- Store its ending index in a dictionary. (to avoid overlapping similar substrings like 'aaa')
- When we see it again: If the current starting index is strictly greater than the previous ending index, it is YES.

If we didn't get any substring that was repeated correctly, the answer is NO.

t = int(input())

for _ in range(t):
    n = int(input())
    s = input()
    
    seen = {}  # substring -> ending index
    
    for i in range(n - 1):
        sub = s[i:i+2]
        
        if sub in seen:
            # previous ending index
            prev_end = seen[sub]
            
            # current starting index is i
            if i > prev_end:
                print("YES")
                break
        else:
            seen[sub] = i + 1  # store ending index
    
    else:
        print("NO")

If the grid must look the same after 0°, 90°, 180° and 270° rotations, then any cell must have the same value as all the cells it maps to under these rotations.

So instead of thinking about the whole grid at once, think in terms of rotation groups.

If a cell is at position (i, j), its rotated positions are:
- 0° → (i, j)
- 90° → (j, n — 1 — i)
- 180° → (n — 1 — i, n — 1 — j)
- 270° → (n — 1 — j, i)

So every cell belongs to a group of 4 symmetric cells.

All 4 cells in such a group must have the same value in the final grid.

If among those 4 cells:
- k cells contain '1'
- 4 − k cells contain '0'

Then to make them equal, we need: min(k, 4 − k) flips.

Each group of 4 cells would be counted 4 times if we iterate over the entire grid. So we need to divide the total number of flips by 4.

Cells with the same color and letter in these two matrices belong to the same rotation group — they map to each other under 90°, 180°, and 270° rotations and therefore must be equal.

We process each rotation group independently.

For every cell (i, j), We collect its 4 symmetric positions:
- (i, j)
- (j, n − 1 − i)
- (n − 1 − i, n − 1 − j)
- (n − 1 − j, i)

We count how many of these are '1'. If there are k ones, then we need min(k, 4 − k) operations to make them equal.

We sum this value for all groups.

Then we divide the total by 4 since we counted each group 4 times.

Time Complexity: O(n²) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    grid = [list(map(int, list(input().strip()))) for _ in range(n)]
    
    ans = 0
    
    for i in range(n):
        for j in range(n):
            ones = grid[i][j]
            ones += grid[j][n - 1 - i]
            ones += grid[n - 1 - j][i]
            ones += grid[n - 1 - i][n - 1 - j]
            
            ans += min(ones, 4 - ones)

    ans //= 4

    print(ans)

The carpet is divided into layers.

Each layer is a closed strip around the border of the remaining matrix.

So instead of checking the entire grid at once, process one layer at a time.

For each layer, traverse it clockwise starting from the top-left corner of that layer and build a string representing the digits in traversal order.

Be careful with the traversal order:
1. Top row (left → right)
2. Right column (top+1 → bottom-1)
3. Bottom row (right → left)
4. Left column (bottom-1 → top+1)

The layer is circular.

So after building the string s, append its first 3 characters to the end:

s += s[:3]

This allows detecting occurrences of "1543" that wrap around the end of the layer.

We process the carpet layer by layer.

Let i be the current layer index.

For each layer:
- Extract its boundary in clockwise order into a string s.
- Append the first 3 characters to s to simulate circular traversal.
- Count how many times "1543" appears using s.count("1543").
- Add to the total answer then move to the next inner layer.

We stop when: i < n // 2 (we reached half mark in height of carper) or i < m // 2 (we reached half mark in width of carpet)

Since both n and m are even, every layer is well-defined.

Time Complexity: O(n × m) per test case, because every cell belongs to exactly one layer and is visited once.

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    grid = [input() for _ in range(n)]
    
    ans = 0
    i = 0
    
    while i < n // 2 and i < m // 2:
        chars = []
        
        # top row
        for col in range(i, m - i):
            chars.append(grid[i][col])
        
        # right column
        for row in range(i + 1, n - i - 1):
            chars.append(grid[row][m - i - 1])
        
        # bottom row
        for col in range(m - i - 1, i - 1, -1):
            chars.append(grid[n - i - 1][col])
        
        # left column
        for row in range(n - i - 2, i, -1):
            chars.append(grid[row][i])
        
        s = "".join(chars)
        
        # circular handling
        s += s[:3]
        
        ans += s.count("1543")
        
        i += 1
    
    print(ans)

The key observation for solving this problem is that any occurrence of 2025 can be converted into 2026 using a single operation. Therefore, if the given string does not already satisfy any of the conditions stated in the problem, only one operation is needed to create an occurrence of 2026 (since the string contains 2025 when it is not already a New Year string).

As a result, the answer is always either 0 or 1. To determine whether the answer is 0, simply check if the string satisfies at least one of the required conditions. This can be done using the in operator method in Python.

t = int(input())
for _ in range(t):
   n = int(input())
   s = input()
   if '2025' not in s or '2026' in s:
      print(0)
   else:
      print(1)

We can iterate over all possible ways to split ab into a and b. For each split, first check whether b has a leading zero. If it does not, compare the integer values of a and b.

To convert a string into an integer, you can use int(s) in Python.

t = int(input())
for _ in range(t):
    ab = input()
    for i in range(1, len(ab)):
        if ab[i] != '0' and int(ab[:i]) < int(ab[i:]):
            print(ab[:i], ab[i:])
            break
    else:
        print(-1)

For each element in the array, we iterate over the entire array and count how many elements are strictly greater than the current one. After computing this count, we add one and include the result in the total sum.

To achieve this, we use two nested loops: the outer loop selects the current element, and the inner loop compares it with every other element in the array. By repeating this process for all elements, we obtain the final answer.

n  = int(input())
arr = [int(i) for i in input().split()]
position = []
 
for i in range(n): 
    count = 0
    for j in range(n): 
        if arr[i] < arr[j]:
            count += 1 
    position.append(count + 1) 
 
print(*position)   

1. Check for infinite movement:
   • If the string contains two consecutive asterisks **,
   • If an asterisk is next to an arrow in the “wrong” direction (*< or >*),
   • If there is a >< pattern (an arrow pointing right immediately followed by an arrow pointing left),
   then Mash can move back and forth forever. In this case, the answer is -1.
2. Calculate the maximum sailing distance if movement is finite:
   • For a < at position i, Mash can move left to the start, passing i + 1 cells.
   • For a > at position i, Mash can move right to the end, passing len(s) — i cells.
   • For a * at position i, Mash can choose the direction that allows him to pass more cells. We take the maximum of i + 1 and len(s) — i.
   The maximum number of cells Mash can traverse is the largest value obtained among all positions.

t = int(input())
for _ in range(t):
    s = input()
    if '**' in s or '*<' in s or '>*' in s or '><' in s:
        print(-1)
 
    else:
       max_ = 0
       for i in range(len(s)):
           if s[i] == '<':
               max_ = max(max_, i + 1)
        
           elif s[i] == '>':
               max_ = max(max_, len(s) - i)
        
           else:
            max_ = max(max_, i + 1, len(s) - i)
    
       print(max_)

To determine if we can form the string t using characters from s and p, we need to check two key conditions:

1. Subsequence Condition: The string s must be a subsequence of t. This means all characters of s should appear in t in the same order. We can verify this using a two-pointer approach, scanning through both strings simultaneously.
2. Frequency Condition: Let f(str, a) represent the number of occurrences of character a in str. For each character a, the condition f(s, a) + f(p, a) ≥ f(t, a) must hold. This ensures that any characters missing from s can be supplied by p to form t.

If both conditions are satisfied, the answer is YES; otherwise, it is NO.

def solve():
    # Read the input strings s, t, and p for the current query
    s = input()
    t = input()
    p = input()

    # Check if s is a subsequence of t
    i, j = 0, 0  
    while i < len(s) and j < len(t):
        # If characters match, move to the next character in s
        if s[i] == t[j]:
            i += 1
        # Always move to the next character in t
        j += 1  

    # If we couldn't match all characters of s in t, then s is not a subsequence of t
    if i != len(s):
        print("NO")
        return

    # Count the frequency of each character in t
    freq_t = {}
    for char in t:
        freq_t[char] = freq_t.get(char, 0) + 1

    # Count the frequency of each character in both s and p combined
    freq_s_p = {}
    for char in s + p:
        freq_s_p[char] = freq_s_p.get(char, 0) + 1

    # Ensure that for every character in t, we have enough occurrences in s and p
    for char, required_count in freq_t.items():
        available_count = freq_s_p.get(char, 0)
        if required_count > available_count:
            print("NO")
            return

    # If all checks pass, s can be transformed into t using characters from p
    print("YES")


# Read the number of queries and process each one
q = int(input())  
for _ in range(q):
    solve()

Note that a[i] + a[i + 1] = b[i]. Use the initial condition b[n] = a[n] and we can figure out the entire array b. Time Complexity: O(n)

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

answer = []

for i in range(n):
    if i == n-1:
        answer.append(nums[i])
    else:
        answer.append(nums[i] + nums[i + 1])

print(*answer)
   

What is the maximum possible gcd that we can get?

We need the number of permutations P of length N such that gcd⁡(1 * P1, 2 * P2, …, N * PN) > 1.

Key idea:

Let g = gcd⁡(1 * P1, 2 * P2, …, N * PN). It can be shown that g can not be greater than 2. If g had any odd prime factor p > 2, there wouldn’t be enough multiples of p to cover all indices and values. → So only g = 2 is possible.

When is g = 2 possible?

Every product i * Pi must be even → each position i or value Pi must be even.

• If n is odd, there are more odd positions than even numbers → impossible.
• If n is even, we can:
  • Assign even numbers to odd positions → (n/2)! Ways
  • Assign odd numbers to even positions → (n/2)! Ways

MOD = 998244353
fact = [1] * 1001
for i in range(2, 1001):
    fact[i] = fact[i-1] * i % MOD

for _ in range(int(input())):
    n = int(input())
    print(0 if n % 2 else fact[n//2] * fact[n//2] % MOD)

The problem asks us to divide a string into exactly k parts, where each part’s length lies between a and b.we can use a dynamic programming (DP) approach to solve this problem. The idea is to recursively decide where to cut the string at each position, we try all possible segment lengths within $$$[a, b]$$$ and check if the remaining substring can be split into the remaining parts. The DP state $$$(i, j)$$$ represents whether the substring from start $$$i$$$ can form $$$j$$$ valid parts, allowing us to efficiently explore all possibilities and avoid recomputation.

k, a, b = map(int, input().split())
sentence = input()
n = len(sentence)


memo = {}
def dp(start, cut):
    if(start, cut) in memo:
        return memo[(start, cut)]


    if cut == 1:
        if a <= len(sentence[start:]) <= b:
            return [sentence[start:]]
        return []
    
    answer = []
    
    for i in range(start+a, min(n, start+b+1)):
        word = sentence[start:i]
        result = dp(i, cut - 1)
        
    
        if len(result) + 1 == cut:
            answer.extend(result)
            answer.append(word)
            break
     

    memo[(start, cut)] = answer
    return answer

answer = dp(0, k)[::-1]

if not answer:
    print("No solution")
else:
    for word in answer:
        print(word)



# CHALLENGE: Make it bottom up !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

If we divide the string as evenly as possible into k parts, then the minimum length of a segment will be $$$⌊n/k⌋$$$ and the maximum length will be $$$⌈n/k⌉$$$. The core insight is that for a solution to exist, this natural distribution must already satisfy the constraints: the minimum segment length ⌊n/k⌋ must be at least $$$a$$$ (otherwise some lines would be too short), and the maximum segment length $$$⌈n/k⌉$$$ must be at most $$$b$$$ (otherwise some lines would be too long).

When the conditions are satisfied, we can simply implement this natural distribution: the first $$$n MOD k$$$ lines will contain $$$⌈n/k⌉$$$ characters each, and the remaining lines will contain $$$⌊n/k⌋$$$ characters each.

k, a, b = map(int, input().split())
sentence = input()
n = len(sentence)


maximum_possible = (n + k - 1) // k # n ceil division by k 
minimum_possible = n // k
remaining_part = n % k

if maximum_possible > b or minimum_possible < a:
    print("No solution")
else:
    maximum_possible *= remaining_part
    
    
    length = 0 # keep track of the length of the current word
    for i in range(maximum_possible):
        length += 1
        print(sentence[i], end="")
        
        if length == maximum_possible // remaining_part:
            # print a line break and reset length since we have printed out one fully valid word
            print()
            length = 0
    
    
    for i in range(maximum_possible, n):
        length += 1
        print(sentence[i], end="")
        
        if length == minimum_possible:
            # print a line break and reset length since we have printed out one fully valid word
            print()
            length = 0
 

Use trie

At first, build a trie containing all suffixes of given string (this structure is also called explicit suffix tree). Let's iterate over all substrings in order of indexes' increasing, i. e. first [1...1],  then [1...2], [1...3], ..., [1...n], [2...2], [2...3], ..., [2...n], ... Note, that moving from a substring to the next one is just adding a single character to the end. So we can easily maintain the number of bad characters, and also the "current" node in the trie. If the number of bad characters doesn't exceed k, then the substring is good. And we need to mark the corresponding node of trie, if we never did this before. The answer will be the number of marked nodes in the trie.

There is also an easier solution, where instead of trie we use Rabin-Karp rolling hash to count substrings that differ by content. Just sort the hashes of all good substrings and find the number of unique hashes (equal hashes will be on adjacent positions after sort). But these hashes are unreliable in general, so it's always better to use precise algorithm.

from collections import defaultdict
 
st = input()
nums = input()
k = int(input())
 
 
Node = lambda : defaultdict(Node)
 
root = Node()
 
 
def add(ind):
    curr = root
    
    for i in range(ind, len(st)):
        if st[i] not in curr:
            curr[st[i]] = Node()
         
        
        curr = curr[st[i]]
 

ans = 0
 
def dfs(node, bad):
    global ans
    stack = [(node, bad)]
 
 
    while stack:
        curr, b = stack.pop()
        
        if b > k:
            continue
 
        ans += 1
        for l, nbr in curr.items():
            ind = ord(l) - ord('a')
            ad = int(nums[ind] == '0')
            stack.append((nbr, b + ad))
 
 
for i in range(len(st)-1, -1, -1):
    add(i)
    
 
for l, node in root.items():
    ind = ord(l) - ord('a')
    ad = int(nums[ind] == '0')
    dfs(node, ad)


print(ans)

Each vertex’s beauty is defined as the greatest common divisor (GCD) of all numbers on the path from the root to that vertex. Additionally, Ilya is allowed to change one vertex’s value to 0, which can potentially increase the beauty of some vertices.

We handle this in two parts:

1. Case 1 – Root value = 0:
   If the root is set to 0, we can easily compute the beauty of each vertex by performing a DFS traversal. The beauty of each node is simply gcd(a[i], beauty[parent]), where beauty[parent] is the GCD value up to the parent node.

2. Case 2 – Root value ≠ 0:
   When the root is not zero, every possible beauty value must be a divisor of the root’s number, because all paths include the root.
   During DFS, for each divisor of the root’s value, we track how many vertices on the current path are divisible by it.
   If a divisor divides at least (depth - 1) vertices along the path, then that divisor is a valid beauty for the current vertex.
   The beauty of a node is the largest such divisor that satisfies this condition.

This ensures we consider both possibilities—keeping or zeroing the root—to maximize each vertex’s beauty.

Complexity:

• Time Complexity: O(n × √a₁) — since we iterate over all divisors of the root for each node during DFS.
• Space Complexity: O(n + √a₁) — for storing the tree and divisor counts.

import sys, math
read = sys.stdin.readline

n = int(read())
values = list(map(int, read().split()))
edges = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, read().split())
    u -= 1
    v -= 1
    edges[u].append(v)
    edges[v].append(u)

beauty = [0] * n

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# ---------- Iterative DFS1 (root set to 0) ----------
original_root = values[0]
values[0] = 0
beauty[0] = 0

stack = [(0, -1, 0)]  # (node, parent, current_gcd)
while stack:
    node, parent, cur_gcd = stack.pop()
    cur_gcd = gcd(cur_gcd, values[node])
    beauty[node] = max(beauty[node], cur_gcd)
    for child in edges[node]:
        if child != parent:
            stack.append((child, node, cur_gcd))

# ---------- Iterative DFS2 (using divisors of root) ----------
values[0] = original_root
divisors = []
i = 1
while i * i <= values[0]:
    if values[0] % i == 0:
        divisors.append(i)
        if i * i != values[0]:
            divisors.append(values[0] // i)
    i += 1
divisors.sort()
count = [0] * len(divisors)

stack = [(0, -1, 0, False)]  # (node, parent, depth, processed_flag)
while stack:
    node, parent, depth, processed = stack.pop()
    if not processed:
        # Entering node
        for i, d in enumerate(divisors):
            count[i] += (values[node] % d == 0)
            if count[i] >= depth:
                beauty[node] = max(beauty[node], d)
        stack.append((node, parent, depth, True))  # add back for backtracking
        for child in reversed(edges[node]):
            if child != parent:
                stack.append((child, node, depth + 1, False))
    else:
        # Leaving node (backtracking)
        for i, d in enumerate(divisors):
            count[i] -= (values[node] % d == 0)

print(*beauty)

Keep two counters, one for Mishka and one for Chris. For each round, compare the two dice values and if Mishka’s is higher, increment her counter; if Chris’s is higher, increment his. At the end, compare the totals: if Mishka has more, she wins; if Chris has more, he wins; if they’re equal, it’s a draw, so print “Friendship is magic!^^”.

from collections import Counter

wins = Counter()
for _ in range(int(input())):
    a, b = map(int, input().split())
    if a > b:
        wins['Mishka'] += 1
    elif a < b:
        wins['Chris'] += 1

if wins['Mishka'] > wins['Chris']:
    print("Mishka")
elif wins['Chris'] > wins['Mishka']:
    print("Chris")
else:
    print("Friendship is magic!^^")

What is the only way to change the parity of a number?

To build a beautiful array b (all elements positive and of the same parity), we consider two cases:

• Case 1: All elements in a have the same parity Simply set bi = ai for all i

  All elements in b will have the same parity → YES

• Case 2: Mixed parities (some even, some odd)
  
  • We cannot make all numbers even, because to change an odd to even, we must subtract another odd but subtracting from the smallest odd number would make it zero or negative, which is invalid.
  • We can try to make all numbers odd by subtracting an odd number from an even (since even − odd = odd). This is valid only if the smallest number in the array is odd, so we can subtract it from all even numbers without making results non-positive.

• If all numbers have the same parity → YES
• Else, if the minimum number is odd → we can make all elements odd → YES
• Else → NO
Time Complexity: O(N) per test case

t = int(input()) 
for _ in range(t): 
   n = int(input()) 
   a = list(map(int, input().split()))
   has_odd = any(x % 2 == 1 for x in a)
   has_even = any(x % 2 == 0 for x in a)

   if not (has_odd and has_even):
       print("YES")

   else:
       if min(a) % 2 == 1:
           print("YES")
       else:
           print("NO")

The graph is constructed from a hidden permutation p such that an undirected edge exists between p[i] and p[j] if and only if i < j and p[i] < p[j]. This means each node is connected to the nodes that come after it in the permutation and are larger in value. To reconstruct the permutation, we observe that a node with no unchosen neighbors smaller than itself must appear last among the remaining elements. So we iteratively pick the largest unchosen node that has no unchosen neighbors with smaller values—ensuring the relative order constraints are respected.

By maintaining the count of unchosen smaller neighbors for each node, and updating it as nodes are selected, we can efficiently reconstruct the permutation in reverse. The final result is the correct permutation.

from collections import defaultdict

def solve():
    n = int(input())
    adj = defaultdict(set)
    
    for r_zeroidx in range(n):  # r_zeroidx from 0 to n-1
        row_str = input()
        for c_zeroidx in range(n):  # c_zeroidx from 0 to n-1
            if row_str[c_zeroidx] == '1':
                # Convert 0-indexed matrix coordinates to 1-indexed node IDs
                node_u = r_zeroidx + 1
                node_v = c_zeroidx + 1
                
                # Add edges for an undirected graph
                adj[node_u].add(node_v)
                adj[node_v].add(node_u)

    # small_degree[i] will store the count of neighbors 'j' of node 'i' 
    # such that 'j < i' AND 'j' is currently unchosen.
    # Initially, all nodes are unchosen, so we count all neighbors 'j' with 'j < i'.
    small_degree = [0] * (n + 1)  # Using 1-based indexing, so index 0 is unused
    for i in range(1, n + 1):
        for neighbor_node in adj[i]:
            if neighbor_node < i:
                small_degree[i] += 1

    ans = []
    is_chosen = [False] * (n + 1) # Using 1-based indexing

    # We need to select n nodes for the permutation
    for _ in range(n):
        chosen_node_this_iteration = -1
        
        # Find the largest unchosen node 'c' such that small_degree[c] == 0.
        # This means 'c' has no unchosen neighbors smaller than itself.
        for node_val in range(n, 0, -1): # Iterate from n down to 1
            if not is_chosen[node_val] and small_degree[node_val] == 0:
                chosen_node_this_iteration = node_val
                break
        
        # According to the problem's constraints and logic, 
        # a suitable node should always be found in each step.
        # If chosen_node_this_iteration remained -1, it would imply an issue.

        ans.append(chosen_node_this_iteration)
        is_chosen[chosen_node_this_iteration] = True

        # Now, update the small_degree counts for the neighbors of the chosen_node.
        # When chosen_node_this_iteration (let's call it X) is picked:
        # Consider an unchosen neighbor V of X.
        # If X < V, then X was a "small neighbor" for V. Since X is now chosen, 
        # it no longer contributes to V's small_degree.
        for neighbor in adj[chosen_node_this_iteration]:
            if not is_chosen[neighbor]: # Only affect unchosen neighbors
                if chosen_node_this_iteration < neighbor:
                    small_degree[neighbor] -= 1
    
    print(*(ans))

if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()

You're trying to maximize the XOR between two substrings.
Try fixing one of them — particularly a suffix starting from the first '0' in the string.

You're given a binary string s that starts with 1. You need to pick two non-empty substrings (they may overlap) and maximize their XOR value when interpreted as binary numbers.

Observations:

1. Leading Substrings Have Higher MSB Weight

• Since XOR values are just number differences, longer prefixes/suffixes with higher bits turned on can lead to large XOR values.

1. We Can Fix One Substring to Reduce Complexity

• Instead of checking all O(n²) substrings (too slow), we fix one of the substrings and slide a window across the string to find the other that gives maximum XOR.

• We choose the suffix starting at the first '0' because:

  • Any string starting with '1' will be numerically large.
  • A suffix starting with the first '0' ensures we get a different structure from the prefix (increases XOR chance).

1. Sliding Window + Bitmasking

• We fix the right substring: the suffix from the first 0 to the end.
• Convert it to a number: suffix_val = int(s[first_zero_idx:], 2)

• Slide a window of the same length from the start of the string and keep the binary number in the window up to date using bit operations:

  • Left shift to add a new bit.
  • Mask to keep only the last k bits.
• XOR the current window value with the fixed suffix value and track the maximum.

1. Why This Works Efficiently

• Each test case is processed in linear time w.r.t the string length.
• Since total input length over all test cases is ≤ 5000, the solution runs in O(total_length) time.

Steps:

1. For each test case:

• If the string contains only 1s, just return the full string and any single character (e.g., 1 1).

• Else:

  • Fix the suffix starting from the first 0.
  • Slide a window of same length from the beginning of the string.
  • Track the window with maximum XOR.

Example Walkthrough:

Input:

s = 1000

• Suffix: 000 (starts from index 2), value = 0
• Try windows of length 3:

• 100 → 4 ⊕ 0 = 4

• 000 → 0 ⊕ 0 = 0 → Best XOR = 4 → return (1, 3) and (1, 4)

Complexity:

• Per test case: O(n)
• Total: O(5000)

t = int(input()) 
for _ in range(t):
    s = input()
first_zero_idx = s.find('0')
if first_zero_idx == -1:
    print(1, len(s), 1, 1)
else:
    window_len = len(s) - first_zero_idx
    window_mask = (1 << window_len) - 1
    msb_mask = 1 << (window_len - 1)

    fixed_suffix_numeric_val = int(s[first_zero_idx:], 2)
    current_window_numeric_val = int(s[:window_len], 2)

    max_xor_val = current_window_numeric_val ^ fixed_suffix_numeric_val
    best_window_indices = [0, window_len - 1] 

    for window_end_idx in range(window_len, len(s)):
        current_window_numeric_val <<= 1
        current_window_numeric_val &= window_mask
        if s[window_end_idx] == '1':
            current_window_numeric_val |= 1

        current_xor_result = current_window_numeric_val ^ fixed_suffix_numeric_val

        if current_xor_result > max_xor_val and (current_window_numeric_val & msb_mask):
            max_xor_val = current_xor_result
            window_start_idx = window_end_idx - window_len + 1
            best_window_indices = [window_start_idx, window_end_idx]
    
    print(1, len(s), best_window_indices[0] + 1, best_window_indices[1] + 1)

To minimize a bitwise OR sum, you want as many bits as possible to be 0, especially the most significant ones. Consider processing the bits from most significant to least significant. For each bit, decide if it must be set in the final answer to maintain connectivity.

The problem asks us to find a spanning tree of a given connected weighted undirected graph such that the bitwise OR of the edge weights (referred to as "ority") is minimized.

Observations:

1. Bitwise OR Property: If any edge in the chosen spanning tree has a specific bit set to 1, that bit will also be 1 in the final "ority" sum. To minimize the ority, we prioritize keeping higher (more significant) bits as 0.

2. Greedy Approach by Bit: This suggests a greedy strategy: determine the bits of the minimum ority from MSB down to LSB. For each bit, we try to keep it 0, only setting it to 1 if necessary to maintain connectivity.

Strategy: Iterating Through Bits

Initialize min_ority_so_far = 0 and vis (a boolean array for edges, initially all 0s, where vis[j]=1 means edge j is "banned" because using it would force a higher bit to become 1). Iterate from bit 29 down to 0:

For each bit b:

1. Hypothesis: Tentatively assume the $$$b$$$-th bit of min_ority_so_far can be 0, consistent with higher bits already determined.

2. Candidate Edges: Create a new DSU structure. Consider only edges $$$(u, v, w)$$$ where:

   • The $$$b$$$-th bit of $$$w$$$ is 0.
   • The edge is not "banned" by previous decisions (i.e., vis[j] == 0).
   • Edges that have their $$$b$$$-th bit set, or are already banned, are temporarily stored in a temp list.

3. Connectivity Check: Use DSU to check if all $$$N$$$ vertices can be connected using only these candidate edges.

4. Decision for Bit b:

   • If Connected: All vertices can be connected using only edges that keep bit $$$b$$$ as 0.
     • The $$$b$$$-th bit of min_ority_so_far remains 0.
     • Crucially: Mark all edges in temp (those that had their $$$b$$$-th bit set but were not yet banned) as vis[j] = 1. This bans them because using them would unnecessarily set bit $$$b$$$ to 1.
   • If Not Connected: We must use at least one edge with the $$$b$$$-th bit set to form a spanning tree.
     • The $$$b$$$-th bit of min_ority_so_far must be 1. Update: min_ority_so_far = min_ority_so_far | (1 << b).
     • Edges from temp that were active and had their $$$b$$$-th bit set are not banned by this step, as they are now consistent with min_ority_so_far having bit b set.

After iterating through all bits, min_ority_so_far holds the minimum possible ority.

Complexity:

• Outer loop: bl iterations (approximately 30 for typical integer sizes).
• Inner loop (per bit):
  • DSU initialization: $$$\mathcal{O}(N)$$$.
  • Iterating through $$$M$$$ edges: $$$\mathcal{O}(M \cdot \alpha(N))$$$, where $$$\alpha(N)$$$ is the inverse Ackermann function (which is practically constant).
• Total Complexity: $$$\mathcal{O}(\text{bl} \cdot (N + M \cdot \alpha(N)))$$$. This approach is efficient for the given constraints.

import sys

class dsu:
    def __init__(self, size):
        self.parent = [i for i in range(size + 1)]
        self.size = [1 for i in range(size + 1)]

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)

        if px != py:
            if self.size[px] > self.size[py]: # Union by size
                px, py = py, px 
            self.parent[px] = py
            self.size[py] += self.size[px]

def solve():
    s = sys.stdin.readline().strip().split() # empty line 
    n, m = list(map(int, sys.stdin.readline().strip().split()))
    edges = []
    bl = 30 
    for _ in range(m):
        edges.append(tuple(map(int, sys.stdin.readline().strip().split())))

    ans = 0
    vis = [0] * (m + 1) # vis[j]=1 if edge j is "banned"

    for i in range(bl - 1, -1, -1): # Iterate from MSB downwards
        graph = dsu(n)
        temp = [] # Stores indices of edges that have the i-th bit set AND are not yet banned

        for j in range(m):
            u_node, v_node, w_val = edges[j]
            # If (bit_i is 0 AND edge_j is active), add to DSU
            # Else (bit_i is 1 OR edge_j is banned), add edge_j_index to temp
            if (w_val >> i) & 1 == 0 and vis[j] == 0:
                graph.union(u_node, v_node)
            else:
                temp.append(j)
        
        # Check connectivity: can we connect the graph using only edges with i-th bit = 0?
        can_connect_without_setting_bit_i = False
        if n == 0: # Problem constraints n >= 3, so this case is mostly theoretical
            can_connect_without_setting_bit_i = True
        elif n > 0 and graph.size[graph.find(1)] == n : 
             can_connect_without_setting_bit_i = True
        
        if can_connect_without_setting_bit_i:
            # Yes, we can connect without setting the i-th bit.
            # The i-th bit of 'ans' remains 0.
            # Ban all edges in 'temp' that were active and would set bit i.
            for val_idx in temp:
                vis[val_idx] = 1
        else:
            # No, we must use an edge that sets the i-th bit.
            # The i-th bit of 'ans' must be 1.
            ans += (1 << i)
            # Edges in 'temp' that were active and set bit i are NOT banned,
            # as they are now consistent with 'ans' having bit 'i' set.

    print(ans)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    solve()

Recall the basic properties of the $$$⊕$$$ operation: $$$A⊕0=A$$$, $$$A⊕A=0$$$, $$$A⊕B=B⊕A$$$.

Consider the cases of even and odd array lengths.

Note that $$$(a_1⊕x)⊕(a_2⊕x)⊕$$$... equals $$$a_1⊕a_2⊕…⊕a_n$$$ if $$$n$$$ is even, or $$$a_1⊕a_2⊕…⊕a_n⊕x$$$ if $$$n$$$ is odd. Then, if the length of the array is odd, you must print ⊕ of the whole array. And if the length is even, we can't change the value of the expression with our operation. It turns out that if ⊕ of the whole array is 0, we can output any number, but otherwise there is no answer.

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    xor = 0
    for x in a:
        xor ^= x
    if xor == 0:
        print(0)
    else:
        if n % 2 == 1:
            print(xor)
        else:
            print(-1)

Think what happens to the bitwise OR of the array elements when you perform the allowed operation. Can the overall OR value ever decrease?

Let m = a[1] | a[2] | ... | a[n].

• This value m is the lower bound of the array sum, since: m ≤ a[1] + a[2] + ... + a[n]
• This value is also achievable using valid operations:
  • Repeatedly pick two elements a[i], a[j]
  • Replace one of them with 0, and the other with a[i] | a[j] (which preserves the total OR)
  • Keep doing this until all but one element are 0, and one element holds the total OR m.
So, no matter how you do the operations, you can always reduce the array to [0, 0, ..., m], giving you a total sum of m.

Time Complexity: O(N)

t = int(input())
for _ in range(t):
   n = int(input())
   nums = [int(i) for i in input().split()]
   
   answer = 0
   for num in nums:
      answer |= num
            
   print(answer)

Try to compute the result of ai | z for each element.
You’ll notice z only gets worse (decreases or stays the same) with every operation.

You're given an array a and an integer z. You can perform the following operation any number of times:

• Pick an index i (1 ≤ i ≤ n)
• Set a[i] = a[i] | z
• Set z = a[i] & z

The key insight lies in understanding how the value of z changes after each operation.

Observations:

1. z is Monotonically Decreasing (Bitwise)

• The operation z = a[i] & z only unsets bits in z.
• Once a bit in z becomes 0, it can never become 1 again.
• This means z is most powerful (has the most 1s) at the beginning, and gets strictly worse the more you use it.

1. Best Use of z is at the Start

• Since z weakens over time, using it even once changes its value forever.
• So the most strategic approach is to try all possible a[i] | z without modifying z, and pick the maximum.

1. Why Not Simulate All Operations?

• With the above point, it becomes clear that using z even once may prevent reaching optimal results later.
• Trying all operation sequences would be overkill and unnecessary.

Approach:

1. For each ai in the array:

• Compute ai | z
• Track the maximum value among these.

1. Output the maximum value for each test case.

Example Walkthrough:

Input:

2 3  
3 4

• 3 | 3 = 3
• 4 | 3 = 7

Max is 7 — That’s our answer.

Complexity Analysis:

• For each test case, we do a single pass through the array: O(n)
• Total operations across all test cases: O(10⁴) (within limits)

t = int(input())
for _ in range(t):
    n, z =  map(int, input().split())
    a = list(map(int, input().split()))
    max_value = 0
    for ai in a:
        max_value = max(max_value, ai | z)
    print(max_value)

Try calculating $$$f(l,r)$$$ bit by bit

Which condition has to hold true for all elements on a subsegment $$$[l,r]$$$, and for a certain bit, for that bit to be present in $$$f(l,r)$$$?

How can we check if that condition is true for a certain bit fast?

Try prefix sums.

Try binary search.

1. Calculating Prefix Sums of Bits:
   • We start by counting how many times each bit appears in the array up to a certain point. For example, how many 1s or 0s are there in the first few elements of the array.
   • We do this efficiently in $$$O(n \log(\text{max}(a)))$$$ time. Here, '$$$n$$$' is the length of the array, and '$$$\text{max}(a)$$$' is the maximum value in the array.
2. Understanding Bit Presence in a Range:
   • If the count of a particular bit (like the $$$j$$$-th bit) from index $$$l$$$ to index $$$r$$$ in the array is exactly the same as the length of that range $$$(r - l + 1)$$$, it means that bit appears in all the elements within that range.
3. Calculating $$$f(l,r)$$$:
   • Now, we want to find out for which bits this condition holds true within a certain range $$$[l, r]$$$ of the array.
   • We sum up the counts of all the bits where this condition holds true. This gives us the value of $$$f(l,r)$$$.
4. Solving Queries Efficiently:
   • For each query, given $$$l$$$ and $$$k$$$, we want to find the rightmost index $$$r$$$ such that $$$f(l,r)$$$ is greater than or equal to $$$k$$$.
   • We can use binary search to efficiently find $$$r$$$.
   • If $$$f(l,\text{mid})$$$ is greater than or equal to $$$k$$$, we move towards the right to find a larger $$$r$$$.
   • If not, we move towards the left to find a smaller $$$r$$$.
5. Overall Time Complexity:
   • This entire approach takes $$$O(Q \log(N) \log(\text{max}(a)))$$$ time to process all the queries, where $$$Q$$$ is the number of queries, $$$N$$$ is the length of the array, and $$$\text{max}(a)$$$ is the maximum value in the array.
   • For typical values, this works out to about $$$4 \times 10^7$$$ operations, which is pretty efficient.

So, by using this method, we efficiently handle queries about the presence of certain bits in specific ranges of the array.

t = int(input())
for _ in range(t):
    n = int(input()) 
    nums = list(map(int, input().split()))  
    q = int(input()) 

    arr = [0] * 32
    prefix = [arr]  # Initialize prefix array with zeros

    # Calculate prefix sums of bits
    for num in nums:
        arr = prefix[-1].copy()
        for i in range(32):
            # If the i-th bit is set in num, increment the corresponding count in arr
            if num & (1 << i) != 0:
                arr[i] += 1
        prefix.append(arr)

    # Function to find the bitwise AND of all numbers within a range
    def rangeAnd(l, r):
        ans = 0
        for i in range(32):
            bit_count = prefix[r][i] - prefix[l - 1][i] if l > 0 else prefix[r][i]
            if bit_count == (r - l + 1):
                ans |= (1 << i)
        return ans

    # Binary search to find the rightmost index satisfying the condition
    def bin_search(l, k):
        left = l
        right = n
        while left <= right:
            mid = (right + left) // 2
            if rangeAnd(l, mid) >= k:
                left = mid + 1
            else:
                right = mid - 1

        if right < l:
            return -1
        return right

    ans = []
    # Process queries
    for _ in range(q):
        l, k = map(int, input().split())
        ans.append(bin_search(l, k))

 
    print(*ans)

The formula given in this task looks difficult to calculate, so we can rewrite it:

$$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i \, \& \, x_j) \cdot (x_j \, | \, x_k) = \sum_{j=1}^n \sum_{i=1}^n (x_i \, \& \, x_j) \sum_{k=1}^n (x_j \, | \, x_k) = \sum_{j=1}^n \left[ \sum_{i=1}^n (x_i \, \& \, x_j) \right] \cdot \left[ \sum_{k=1}^n (x_j \, | \, x_k) \right]$$$

We fix the element $$$x_j$$$. Now the task is to calculate two sums $$$\sum_i (x_i \, \& \, x_j)$$$ and $$$\sum_k (x_j \, | \, x_k)$$$, and multiply them by each other.

Let's define function $$$f(x, c)$$$ as the value of $$$c$$$-th bit in $$$x$$$. For example $$$f(13, 1) = 0$$$, because $$$13 = 11\underline{0}1_2$$$, and $$$f(12, 2) = 1$$$, because $$$12 = 1\underline{1}00_2$$$. Additionally, define $$$M$$$ as the smallest integer such that $$$\forall_i \, x_i \lt 2^M$$$. Note that in this task $$$M \leq 60$$$.

We can rewrite our sums using function $$$f$$$:

$$$\sum_i (x_i \, \& \, x_j) = \sum_{c = 0}^{M} 2^c \sum_i f(x_i, c) \cdot f(x_j, c) = \sum_{c = 0}^{M} 2^c f(x_j, c) \sum_i f(x_i, c)$$$

$$$\sum_k (x_j \, | \, x_k) = \sum_{c = 0}^{M} 2^c \sum_k 1 - (1 - f(x_j, c)) \cdot (1 - f(x_k, c)) = \sum_{c = 0}^{M} 2^c \left[ n - (1 - f(x_j, c)) \sum_k (1 - f(x_k, c)) \right]$$$

In other words, we just split elements $$$x_i$$$, $$$x_j$$$, $$$x_k$$$ into the powers of two.

If we memorize the values of $$$\sum_i f(x_i, c)$$$, for each $$$c \in {0, 1, \ldots, M }$$$, then we can calculate the desired sums in $$$\mathcal{O}(M)$$$ for fixed $$$x_j$$$ using the above equations.

So the final solution is to iterate over all elements in the array and fix them as $$$x_j$$$, and sum all of the results obtained. Complexity is $$$\mathcal{O}(nM) = \mathcal{O}(n \log \max_i(x_i))$$$

from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())

for _ in range(T):
    N = int(input())
    x = list(map(int, input().split()))

    MOD = 1000_000_007
    bit_counts = [0]*60
    for xi in x:
        for i in range(60):
            if xi&(1<<i):
                bit_counts[i] += 1
    ans = 0
    for xi in x:
        tot_or = tot_and = 0
        for i in range(60):
            if xi&(1<<i):
                tot_or += (1<<i)%MOD*N
                tot_or %= MOD
                tot_and += (1<<i)%MOD*bit_counts[i]
                tot_and %= MOD
            else:
                tot_or += (1<<i)%MOD*bit_counts[i]
                tot_or %= MOD
        ans += tot_or*tot_and
        ans %= MOD

    print(ans)

1 sounds like the minimum value we can get. Why? Is it always true?

When n ≤ 2, we can do nothing. When n ≥ 3, since , n - 1 isn't a divisor of n, so we can choose it and get 1 as the result.

n = int(input())
	
if n == 2:
    print(2)
else:
	print(1)

You're given a permutation p of n elements. Each person i gives their item to p[i]. The process continues daily. For each person, compute the number of days it takes to get their own item back.

This is equivalent to finding the length of the cycle each element is part of

Can u check the constraints

For each element, follow the permutation until it loops back to the original position

def check(p, n):
    res = [0] * n
    for i in range(n):
        cnt = 1
        cur = p[i] - 1
        while cur != i:
            cur = p[cur] - 1
            cnt += 1
        res[i] = cnt
    return res

q = int(input())
for _ in range(q):
    n = int(input())
    p = list(map(int, input().split()))
    print(*check(p, n))

For each element, follow the permutation until it loops back to the original position

from collections import defaultdict, deque

q = int(input())
for _ in range(q):
    n = int(input())
    p = list(map(int, input().split()))
    graph = defaultdict(list)
    for i in range(1, n + 1):
        graph[i].append(p[i - 1])

    ans = []
    for i in range(1, n + 1):
        queue = deque([i])
        visited = {i}
        days = 0
        while queue:
            node = queue.popleft()
            for neighbour in graph[node]:
                if neighbour not in visited and neighbour != node:
                    visited.add(neighbour)
                    queue.append(neighbour)
                    days += 1
        ans.append(days + 1)
    print(*ans)

Can we see that every element belonging to the same cycle actually forms a group together?

To solve the problem efficiently, we can use the Disjoint Set Union (DSU) data structure, also known as Union-Find, which is ideal for managing groups of connected elements. The core idea is to treat each cycle in the permutation as a group and then track these groups as we process the permutation.

The DSU allows us to efficiently group elements together and later find the size of each group. For this problem, we will use path compression in the find operation to speed up future queries, and union by size to ensure we merge smaller groups into larger ones, which optimizes the union operation.

We start by initializing the DSU for each test case, where each element is its own parent. Then, for each element in the permutation, we union the element with the one it points to. After processing all elements, we can use the find operation to determine the root of each element's cycle and then count the size of each cycle by checking the size of the connected group it belongs to.

This approach ensures that we can efficiently handle the problem even with large inputs, as the time complexity for both union and find operations is nearly constant, due to the inverse Ackermann function, which grows extremely slowly. Thus, the solution is both time-efficient and space-efficient for large values of n.

Time Complexity: O(n * α(n)) per test case, where n is the number of elements and α(n) is the inverse Ackermann function. For practical input sizes, α(n) is very small, often treated as a constant.

Space Complexity: O(n) for storing the parent, rank (or size), and other DSU-related arrays.

import sys

input = sys.stdin.readline

# Input helpers
I = lambda: int(input())
ILT = lambda: list(map(int, input().split()))

class DSU:
    def __init__(self, n):
        self.rank = [0] * (n + 1)
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, node):
        if node == self.parent[node]:
            return node
        stack = []
        while node != self.parent[node]:
            stack.append(node)
            node = self.parent[node]
        for n in stack:
            self.parent[n] = node
        return node

    def Sunion(self, u, v):  # Union by size
        rep_u = self.find(u)
        rep_v = self.find(v)
        if rep_u == rep_v:
            return
        if self.size[rep_u] < self.size[rep_v]:
            self.parent[rep_u] = rep_v
            self.size[rep_v] += self.size[rep_u]
        else:
            self.parent[rep_v] = rep_u
            self.size[rep_u] += self.size[rep_v]

    def Runion(self, u, v):  # Union by rank
        rep_u = self.find(u)
        rep_v = self.find(v)
        if rep_u == rep_v:
            return
        if self.rank[rep_u] < self.rank[rep_v]:
            self.parent[rep_u] = rep_v
        elif self.rank[rep_v] < self.rank[rep_u]:
            self.parent[rep_v] = rep_u
        else:
            self.parent[rep_v] = rep_u
            self.rank[rep_u] += 1

def solve():
    n = int(input())
    p = list(map(int , input().split()))
    uf = DSU(n)
    for i in range(n):
        uf.Sunion(p[i], i + 1)
    print(*[uf.size[uf.find(i)] for i in range(1, n + 1)])

for _ in range(int(input())):
    solve()

Instead of simulating destruction from the beginning, try reversing the process. Imagine you start with an empty array, and at each step you restore one element.

When you restore an element, you want to join it with its neighbors (if they are already restored), to form a continuous segment. To track segments and their sums efficiently, you can use a structure that merges and finds connected components.

Use a disjoint set (also called union-find) to keep track of connected segments and their total sums. Each restored position is its own segment initially. Then, if neighboring positions are restored, you merge them and update the total.

Here's the idea:

• Process the array in reverse destruction order (i.e., imagine "restoring" the numbers).
• Keep track of which positions are active using a union-find structure.
• For each newly added number:
• Set its value.
• If neighbors are already restored, merge the segments.
• Update the maximum segment sum seen so far.
• Store the maximum sum after each restoration. At the end, reverse the answer to match the original destruction order.

This approach works in O(n * α(n)) where α is the inverse Ackermann function — effectively constant.

import sys

# Union-Find (Disjoint Set Union) with segment sum tracking
class Dsu:
    def __init__(self, size):
        self.parent = [i for i in range(size + 1)]  # parent[i] = leader of the set containing i
        self.size = [1 for i in range(size + 1)]    # size[i] = size of set with leader i
        self.total = [-1 for i in range(size + 1)]  # total[i] = sum of the segment with leader i

    def find(self, x):
        # Path compression to find leader
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Merge two segments
        px = self.find(x)
        py = self.find(y)

        if px != py:
            # Union by size (smaller into larger)
            if self.size[px] > self.size[py]:
                px, py = py, px
            self.parent[px] = py
            self.size[py] += self.size[px]
            self.total[py] += self.total[px]  # Update total segment sum

  
def solve():
    n = int(sys.stdin.readline().strip())
    nums = [0] + list(map(int, sys.stdin.readline().strip().split()))  # 1-indexed
    queries = list(map(int, sys.stdin.readline().strip().split()))     # destruction order

    dsu = Dsu(n)
    ans = [0]  # answer after 0 restorations
    maxi = 0   # current maximum segment sum

    # Process in reverse: simulate "restoring" elements
    for val in queries[::-1]:
        dsu.total[val] = nums[val]  # restore the value at position `val`

        # Try to join with the left neighbor
        if val - 1 > 0 and dsu.total[val - 1] > -1:
            dsu.union(val - 1, val)

        # Try to join with the right neighbor
        if val + 1 <= n and dsu.total[val + 1] > -1:
            dsu.union(val + 1, val)

        # Get the sum of the segment that includes this restored value
        cursum = dsu.total[dsu.find(val)]
        maxi = max(maxi, cursum)
        ans.append(maxi)  # save current max after this restoration

    # Remove the last dummy value and reverse to match destruction order
    ans.pop()
    for val in ans[::-1]:
        print(val)
    

Let’s use graph to represent the facts given in the problem. A node in the graph represents a snack flavour. Every guest likes exactly two different snack flavours, so an edge can be used to represent a guest by connecting two nodes(snack flavours) that the guest likes.

For each connected component element, the first person will always eat two snacks. Then we can find an order in which every other person eats one until all the snacks are eaten. So the number of happy guests is ,N — 1 where N is the number of nodes in that connected component. It’s guaranteed that such a sequence of guests always exist and there is no better way to make more guests happier.

So, a simple dfs/bfs can be used to find the answer. We can find the total number of happy guests by traversing each connected component separately. Then the number of unhappy guest will be the total number of guests minus the total number of happy guests.

Time and space complexities

• Time Complexity: O(n)
• Space Complexity: O(n)

from collections import  defaultdict, deque

n, k = map(int, input().split())
graph = defaultdict(list)
for _ in range(k):
    l, r = map(int, input().split())
    graph[l].append(r)
    graph[r].append(l)

def bfs(start):
    q = deque([start])
    visited.add(start)

    count = 0
    while q:
        node = q.popleft()
        count += 1

        for child in graph[node]:
            if child not in visited:
                q.append(child)
                visited.add(child)
        
    return count


happy = 0
visited = set()
for i in range(1, n + 1):
    if i not in visited:
        happy += bfs(i) - 1

print(k - happy)

    

The problem can be reduced to finding the number of edges that form cycles in a graph where nodes are snacks and edges are guests (connecting their two favorite flavors). In a tree (a connected component without cycles), we can always order guests so that no one is sad each guest arrives when at least one favorite snack is still available. However, cycles force at least one sad guest because, no matter the order, some guest will find both snacks already eaten. For this we can use DSU.

Each time we try to connect two already linked nodes, it means we’ve found a cycle, and thus a sad guest. The total number of such edges gives the minimum sad guests, as trees contribute zero and each cycle adds exactly one unavoidable sad guest.

Time and space complexities

• Time Complexity: O(k)
• Space Complexity: O(k)

class UnionFind:
    def __init__(self, size):
        self.parent = {i:i for i in range(size)}
        self.sizes = {i:1 for i in range(size)}
        
    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
        
    def union(self, x, y):
        root1 = self.find(x)
        root2 = self.find(y)
        
        if root1 == root2:
            return False
        
        if self.sizes[root2] > self.sizes[root1]:
            root1,root2 = root2,root1
        
        self.parent[root2] = root1
        self.sizes[root1] += self.sizes[root2]
        
        return True
        

n, k = map(int, input().split())

answer = 0

dsu = UnionFind(n + 1) 

for _ in range(k):
    u, v = map(int, input().split())
    
    if not dsu.union(u, v):
        answer += 1


print(answer)
    

What if we think in reverse: from a graph with no edges to adding edges based on distance?

We are given a tree, and for each integer $$$k$$$ from 1 to $$$n$$$, we must count the number of connected components in a graph $$$Gk$$$​, where an edge exists between two nodes only if their distance in the tree is at least $$$k$$$. Instead of checking all pairs of nodes for each $$$k$$$, which would be too slow $$$O(n^2)$$$, we take advantage of tree properties:

• In a tree, there's a unique path between any two nodes. So we can define the "distance" easily using BFS or DFS.

• Let’s fix a special node the farthest node from any random node (say, node $$$0$$$). From that, perform BFS to find the node furthest from it this gives one endpoint of the diameter. Do a final BFS from this endpoint to get the actual diameter and each node’s distance from it. We then compute the maximum distance for each node from either endpoint of the diameter. If the maximum distance of a node is less than $$$k$$$, then this node becomes isolated in $$$Gk$$$ since no other node is at distance ≥ $$$k$$$.

Hence, for each $$$k$$$, we count how many nodes become isolated (i.e., their max distance $$$k$$$, and increment the number of components accordingly. This gives an $$$O(n)$$$ solution using just a few BFS traversals and basic counting.

from collections import deque

def bfs(tree, start):
    n = len(tree)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        node = q.popleft()
        for neighbor in tree[node]:
            if dist[neighbor] == -1:
                dist[neighbor] = dist[node] + 1
                q.append(neighbor)
    return dist

def main():
    n = int(input())

    tree = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        # Convert to 0-based index  
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    # Step 1: BFS from arbitrary node (0) to find one endpoint of diameter
    d1 = bfs(tree, 0)
    far1 = d1.index(max(d1))

    # Step 2: BFS from far1 to get distances and find farthest point (diameter)
    d2 = bfs(tree, far1)
    diameter = max(d2)
    far2 = d2.index(diameter)

    # Step 3: BFS from far2 to get second set of distances
    d3 = bfs(tree, far2)

    # For each node, take the maximum distance to either end of diameter
    max_dist = [max(d2[i], d3[i]) for i in range(n)]

    # Count how many nodes have max_dist < k
    isolated_count = [0] * (n + 2)
    for d in max_dist:
        isolated_count[d] += 1

    result = [1]  # G_1 has 1 component (the whole tree)
    for k in range(2, n + 1):
        if k > diameter:
            result.append(n)
        else:
            result.append(result[-1] + isolated_count[k - 1]) 

    print(' '.join(map(str, result)))

main()

We don’t have to check the common prefixes of all the given strings

We only need to find the longest common prefixes of the lexicographically smallest and largest strings among the given n strings.

First let’s accumulate the given strings in an array and sort them. Then if a prefix is common for both the first and the last strings, then it’s known for sure that it’s also a prefix for all the strings in between as the array is in sorted order the strings are binary strings. We can use one for loop and check up to which point the first and the last strings are identical and that will be our answer.

Time and space complexities

• Time Complexity: O(n)
• Space Complexity: O(n)

n = int(input())
strings = []
for _ in range(n):
    strings.append(input())

strings.sort()
length = 0
for i in range(len(strings[0])):
    if strings[0][i] == strings[-1][i]:
        length += 1
    else:
        break

print(length)

    

We have a forest of undirected trees on $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$. For each vertex $$$i$$$, we know $$$p_i$$$, the ID of its most distant relative in the same tree (ties broken by the smallest ID). We need to count the number of trees (connected components) consistent with this information.

1. Add an undirected edge between each $$$i$$$ and $$$p_i$$$.
2. This links all vertices within each tree; extra cycles don't affect connectivity.
3. Run DFS on the resulting graph, counting a new component whenever you start DFS at an unvisited vertex.

Time Complexity: $$$O(n)$$$ for building adjacency and DFS both linear.

Space Complexity: $$$O(n)$$$ for adjacency list and visited array.

import sys
sys.setrecursionlimit(10**7)

def main():
    input = sys.stdin.readline
    n = int(input())
    p = [0] + list(map(int, input().split()))

    # Build adjacency list: i <-> p[i]
    adj = [[] for _ in range(n+1)]
    for i in range(1, n+1):
        if p[i] != i:
            adj[i].append(p[i])
            adj[p[i]].append(i)

    visited = [False] * (n+1)

    def dfs(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)

    components = 0
    for i in range(1, n+1):
        if not visited[i]:
            components += 1
            dfs(i)

    print(components)

if __name__ == '__main__':
    main()

1. Initialize a DSU for vertices $$$1\ldots n$$$.
2. For each $$$i$$$, union $$$i$$$ with $$$p_i$$$.
3. Count distinct roots at the end to get the number of trees.

Time Complexity: $$$O(n \alpha(n))\approx O(n)$$$ for nearly constant per union/find.

Space Complexity: $$$O(n)$$$ for parent and rank arrays.

import sys

class DSU:
    def __init__(self, n):
        self.parent = list(range(n+1))
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.rank[a] < self.rank[b]:
            self.parent[a] = b
        elif self.rank[b] < self.rank[a]:
            self.parent[b] = a
        else:
            self.parent[b] = a
            self.rank[a] += 1


def main():
    input = sys.stdin.readline
    n = int(input())
    p = [0] + list(map(int, input().split()))

    dsu = DSU(n)
    for i in range(1, n+1):
        dsu.union(i, p[i])

    roots = set(dsu.find(i) for i in range(1, n+1))
    print(len(roots))

if __name__ == '__main__':
    main()

To minimize the size of the array after repeatedly removing pairs of different elements, consider how the frequency of the most common element affects your ability to perform such pairings.

The goal is to remove as many pairs of different elements as possible. The key idea is that each operation removes two elements of different values. To solve this efficiently, we observe:

• Use a frequency map to count occurrences of each distinct element in the array.
• The most frequent element determines the "bottleneck" — if one value occurs far more than the sum of the rest, we won’t be able to pair all of it.
• If the frequency of the most common element ≤ total number of other elements, we can fully pair up the entire array, leading to a final size of 0 (because each pairing removes two distinct elements).
• Otherwise, we’ll be left with an unpaired number of the most frequent element. Specifically, the answer is 2 * max_freq — n.

There’s an alternative way to simulate this using a max-heap, where we repeatedly remove the two highest-frequency elements and reduce their counts (since we pair one of each). This is reflected in the provided implementation.

from collections import Counter
from heapq import heappush, heappop

def solve():
    n = int(input())
    nums = list(map(int, input().split()))
    count = Counter(nums)
    heap = []
    
    for freq in count.values():
        heappush(heap, -freq)
    
    while len(heap) > 1:
        a = -heappop(heap)
        b = -heappop(heap)
        a -= 1
        b -= 1
        if a:
            heappush(heap, -a)
        if b:
            heappush(heap, -b)
    
    if heap:
        return -heap[0]
    else:
        return 0

for _ in range(int(input())):
    print(solve())

Consider an $$$N$$$-vertex directed graph where for each $$$i$$$ $$$(1 \leq i \leq M)$$$, there is an edge from vertex $$$a_i$$$ to vertex $$$b_i$$$. The goal is to find the lexicographically smallest sequence of topologically sorted vertices.

Topological sorting can be applied to the directed graph we have built. By choosing the vertex with the smallest index and indegree 0 at each step, we obtain the lexicographically smallest sequence $$$S$$$.

To choose the vertex with the smallest index and indegree, we can use a heap data structure.

import heapq

N, M = map(int, input().split())
indeg = [0] * N
out = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    indeg[b] += 1
    out[a].append(b)

heap = []
for i in range(N):
    if indeg[i] == 0:
        heapq.heappush(heap, i)

ans = []
while heap:
    i = heapq.heappop(heap)
    ans.append(i)
    for j in out[i]:
        indeg[j] -= 1
        if indeg[j] == 0:
        	heapq.heappush(heap, j)

if len(ans) != N:
    print(-1)
else:
    print(*[x + 1 for x in ans])

When building a graph edge by edge using Union-Find, encountering an edge that connects two already linked vertices reveals a fundamental cycle property. That is if vertices u and v are already connected when we attempt to add edge $$$(u,v)$$$, there must exist at least one alternate path between them. Hence, we can solve this problem by finding such an edge with the lightest weight by iterating in a sorted list of the edges, and finding the cycle that connects $$$u$$$ to $$$v$$$ by using BFS or DFS,

Complexity Analysis: - Time: $$$O(m log m)$$$ for sorting + $$$O(m α(n))$$$ for Union-Find - Space: $$$O(n)$$$ for Union-Find + $$$O(n + m)$$$ for graph storage

class UnionFind:
    def __init__(self, size):
        self.parent = {i:i for i in range(size)}
        self.sizes = {i:1 for i in range(size)}
    
    
    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
        
    def union(self, x, y):
        root1 = self.find(x)
        root2 = self.find(y)
        
        if root1 == root2:
            return False
        
        if self.sizes[root2] > self.sizes[root1]:
            root1,root2 = root2,root1
        
        self.parent[root2] = root1
        self.sizes[root1] += self.sizes[root2]
        
        return True



def find_cycle_path(start, end, graph):
    que = [start]
    visited = set([start])
    
    parent = {start : -1} # this will be useful to track our path back
    
    while que:
        curr = que.pop()
        
        if curr == end:
            break
        
        for nbr in graph[curr]:
            if curr == start and nbr == end: 
                # we dont want the direct path we want to cycle back so
                continue
            
            if nbr not in visited:
                parent[nbr] = curr # mark the next nodes come after curr
                
                visited.add(nbr)
                que.append(nbr)
    
    
    #now let’s track our path back
    path = []
    
    curr = end
    while curr != -1:
        path.append(curr)
        curr = parent[curr]
    
    
    return path[::-1] # since this path is a cycle there is no need for reversing.
    
        
        
def solve():
    n,m = map(int, input().split())
    
    edges = [] #lets store the edges
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        u, v, w =  map(int, input().split())

        #for the graph we realy don't need the weights
        graph[u].append(v)
        graph[v].append(u)
        
        edges.append((u, v, w))
    
    edges.sort(key = lambda x : x[2], reverse = True)
    
    
    dsu = UnionFind(n+1)
    
    start = end = b = -1
    for u, v, w in edges:
        if not dsu.union(u, v):
            #already connected
            #now we know there must be a cycle 
            #we can just find a way from u to v the other way around
            start = u
            end = v
            b = w
            #this can be an answer but we might find better answer
    
    path = find_cycle_path(start, end, graph)
    
    print(b, len(path))
    print(*path)
    
    



for _ in range(int(input())):
    solve()

In graph theory, bridges (or cut edges) are connections whose removal would disconnect the graph meaning they cannot be part of any cycle. Hence we can solve this problem by finding a non-bridge edge with the minimum weight. For this we will have to utilize a bridge finding algorithm (Like, Tarjan's Bridge finding Algorithm), then we can find a cycle between a non-bridge edge with the minimum weight using BFS or DFS.

econstruction (BFS/DFS): O(V + E) Complexity Analysis: - Time: $$$O(n + m)$$$ - Space: $$$O(n + m)$$$

from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc


def find_bridges(graph, N):
    discovered_time = [0] * (N+1)
    lowest_reach = [float('inf')] * (N+1)
    seen = [0] * (N+1)
    
    time = 1
    
    bridges = set()
    
    @bootstrap
    def dfs(node, parent):
        nonlocal time
        
        discovered_time[node] = time
        lowest_reach[node] = time
        time += 1
        seen[node] = 1
        
        for nbr in graph[node]:
            if nbr == parent: 
                continue

            if not seen[nbr]:
                yield dfs(nbr, node)
                
                lowest_reach[node] = min(lowest_reach[node], lowest_reach[nbr])
                
                if lowest_reach[nbr] > discovered_time[node]:
                    #this is a bridge edge
                    bridges.add((node, nbr))
                    bridges.add((nbr, node))
                    
            else:
                lowest_reach[node] = min(lowest_reach[node], discovered_time[nbr])

        yield
        
    for node in range(1, N+1):
        dfs(node, 0)
    
    return bridges
    

def find_cycle_path(start, end, graph):
    que = [start]
    visited = set([start])
    
    parent = {start : -1} # this will be useful to track our path back
    
    while que:
        curr = que.pop()
        
        if curr == end:
            break
        
        for nbr in graph[curr]:
            if curr == start and nbr == end: 
                # we dont want the direct path we want to cycle back so
                continue
            
            if nbr not in visited:
                parent[nbr] = curr # mark the next nodes come after curr
                
                visited.add(nbr)
                que.append(nbr)
    
    
    #now let’s track our path 
    path = []
    
    curr = end
    while curr != -1:
        path.append(curr)
        curr = parent[curr]
    
    
    return path[::-1] # since this path is a cycle there is no need for reversing.
    
        
        
def solve():
    n,m = map(int, input().split())
    
    edges = [] #lets store the edges
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        u, v, w =  map(int, input().split())

        #for the graph we realy don't need the weights
        graph[u].append(v)
        graph[v].append(u)
        
        edges.append((u, v, w))
    
    
    bridges = find_bridges(graph, n)
    
    min_edge = (-1 , -1)
    b = float('inf')
    
    # lets find the lightest non-bridge edge
    for u, v, w in edges:
        if (u, v) not in bridges:
            if w < b:
                min_edge = (u , v)
                b = w
    
    
    start, end = min_edge
    #cycle back from start to end the other way
    path = find_cycle_path(start, end, graph)
    
    print(b, len(path))
    print(*path)
    
        
for _ in range(int(input())):
    solve()
    
                    

Think about who starts the game and what numbers each player is allowed to subtract.

Mahmoud starts first and can subtract even numbers.

Ehab goes next and can subtract odd numbers.

Now consider what happens depending on the parity of n.

• If n is even, Mahmoud can subtract n on his first turn and leave n = 0 — Ehab can't play.
• If n is odd, Mahmoud can't subtract the entire n (since it's not even), so the game goes longer.

Regardless of the number chosen in each turn, the key idea is that the parity of n determines who makes the last move.

Since they subtract at least 1 each turn, the number of moves is exactly n. Mahmoud starts, so:

• If n is even, Mahmoud moves last.
• If n is odd, Ehab moves last.

The game lasts exactly n moves, since in each move exactly 1 is subtracted (minimum).

• If n is even: Mahmoud makes the first and last move — he wins.
• If n is odd: Ehab makes the last move — he wins.

n = int(input())
if n % 2 == 0:
    print("Mahmoud")
else:
    print("Ehab")

We are working with a grid where each non-zero region of connected cells (up/down/left/right) forms a lake. The goal is to find the maximum volume (sum of cell values) among all such lakes.

We must explore these connected components efficiently.

To explore connected components, we can use DFS or BFS. Since you asked for iterative, we'll use a stack-based DFS.

For each unvisited cell with a value > 0, we simulate DFS using a stack to explore the lake and sum its total volume.

We need to: - Keep a visited matrix to avoid reprocessing cells. - For each new starting point, push it to a stack and explore all 4-directionally connected water cells. - Update the max_volume after exploring each lake.

This guarantees each cell is visited exactly once.

Time Complexity: - O(n * m) per test case — each cell is visited at most once. - Since the sum over all test cases is ≤ 10⁶ cells, this is efficient.

Space Complexity: - O(n * m) for the visited matrix. - Up to O(n * m) for the DFS stack in the worst case (entire grid is one lake).

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    
    max_volume = 0
    directions = [(-1,0), (1,0), (0,-1), (0,1)]

    for i in range(n):
        for j in range(m):
            if grid[i][j] > 0 and not visited[i][j]:
                stack = [(i, j)]
                visited[i][j] = True
                volume = 0

                while stack:
                    x, y = stack.pop()
                    volume += grid[x][y]

                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < n and 0 <= ny < m:
                            if not visited[nx][ny] and grid[nx][ny] > 0:
                                visited[nx][ny] = True
                                stack.append((nx, ny))
                
                max_volume = max(max_volume, volume)
    
    print(max_volume)

Let $$$ways v$$$ array be the number of ways from which an apple can fall if it is in the vertex v. Then the answer to the query is $$$ways[v]⋅ways[u]$$$.

Note that the value of $$$ways[v]$$$ is equal to the number of leaves in the subtree of vertex $$$v$$$. Then, these values can be computed using the DFS or BFS. The value $$$ways$$$ for a vertex will be equal to 1 if this vertex is a leaf, otherwise it will be equal to the sum of these values for all children of the vertex.

Total complexity: $$$O(n+q)$$$.

from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc



testcase = int(input())

for _ in range(testcase):
    n = int(input())
    
    graph = [[] for _ in range(n+1)]
    

    for _ in range(n-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    
    ways = [0 for _ in range(n + 1)] #the number of ways each apple will fall
    
    seen = [0 for _ in range(n + 1)]
    
    @bootstrap
    def dfs(node, parent):
        
        seen[node] = 1 
        
        for nbr in graph[node]:
            if not seen[nbr]:
                yield dfs(nbr, node)
        
        #this part is done once the dfs is returning
        is_leaf = True
        for nbr in graph[node]:
            if nbr != parent:
                ways[node] += ways[nbr]
                #if node has a neighbour other than its parent 
                #it means it is not a leaf node
                is_leaf = False 
        
        #if node is a leaf node we have to set its ways to 1
        if is_leaf:
            ways[node] = 1
        
        yield
    
    dfs(1, 0) 
    
    
    q = int(input())

    # now for each pair a b we just return ways of a * ways of b
    for _ in range(q):
        a, b = map(int, input().split())
        
        print(ways[a] * ways[b])

testcase = int(input())

for _ in range(testcase):
    n = int(input())
    
    graph = [[] for _ in range(n+1)]
    
    for _ in range(n-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    
    ways = [0 for _ in range(n + 1)] #the number of ways each apple will fall
    
    
    
    
    def dfs(root):
        # The stack is holding (node, parent, state)
        # state means are we returning to the node or is it the first time we visit it 
        stack = [(root, 0, 0)]  # since the root node has no parent  
        seen = [0 for _ in range(n + 1)]
        
        # here we mark whatever is in the stack as seen so . . .
        seen[root] = 1 
        
        while stack:
            node, parent, state = stack.pop()
            
            if state == 1:
                # This means we are returning from a call 
                
                is_leaf = True
                
                for nbr in graph[node]:
                    if nbr != parent:
                        is_leaf = False
                        ways[node] += ways[nbr]
                
                if is_leaf:
                    ways[node] = 1 
                        
        
                # WE HAVE TO CONTINUE SINCE WE DO NOT WANT TO RE APPEND 
                continue 
            
            stack.append((node, parent, 1))
            
            for nbr in graph[node]:
                if not seen[nbr]:
                    stack.append((nbr, node, 0)) # append with state 0 since this is the first time we visit it
                    seen[nbr] = 1
            
    
    dfs(1)
    
    
    
    
    q = int(input())

    # now for each pair a b we just return ways of a * ways of b
    for _ in range(q):
        a, b = map(int, input().split())
        
        print(ways[a] * ways[b])

                           

How do we find all lakes with their corresponding indices?

Which part of the lakes should we change to land?

We need exactly k lakes to remain on the grid. A lake is a group of water cells (.) connected by sides that do not touch the border. Any water body connected to the border is considered part of the ocean and must be ignored.

DFS IS OFTEN USED TO FIND CONNECTED COMPONENTS IN A GRID. THAT's ONE APPLICATION WE'VE SEEN.

We use DFS to explore each unvisited water cell and gather its size and positions. If any part of the component touches the border, we discard it; otherwise, we store it as a valid lake.

After collecting all valid lakes, we sort them by size and fill the smallest (total_lakes — k) by turning their . cells into *. This ensures we preserve the largest lakes while making the minimum number of changes.

We then print the number of modified cells and the updated grid.

import sys
import threading

def solve():
    n, m, k = map(int, input().split())
    grid = [input() for _ in range(n)]

    def is_border(x, y):
        return x == 0 or y == 0 or x == n - 1 or y == m - 1

    def in_bounds(x, y):
        return 0 <= x < n and 0 <= y < m

    def dfs(x, y):
        vis.add((x, y))
        nonlocal size, is_lake, lake_cells
        lake_cells.add((x, y))
        if is_border(x, y):
            is_lake = False
        size += 1

        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if in_bounds(nx, ny) and (nx, ny) not in vis and grid[nx][ny] == ".":
                dfs(nx, ny)

    vis = set()
    lakes = []
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    for i in range(n):
        for j in range(m):
            if grid[i][j] == "." and (i, j) not in vis:
                size = 0
                is_lake = True
                lake_cells = set()
                dfs(i, j)
                if is_lake:
                    lakes.append([size, lake_cells])

    lakes.sort()
    to_fill = len(lakes) - k
    cnt = 0

    ans = [list(row) for row in grid]
    for i in range(to_fill):
        cnt += lakes[i][0]
        for x, y in lakes[i][1]:
            ans[x][y] = "*"

    print(cnt)
    for row in ans:
        print("".join(row))

input = lambda: sys.stdin.readline().strip()

def main():
    solve()

if __name__ == '__main__':
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)
    threading.Thread(target=main).start()

The problem gives us an undirected graph where every node has at least $$$k$$$ neighbors, and our task is to find a simple cycle (no repeated nodes) that has length at least $$$k + 1$$$. A cycle is a path that starts and ends at the same node, and all nodes in between are distinct.

The solution uses Depth-First Search (DFS) to explore the graph and try to find a cycle. While walking through the graph, we keep track of which nodes we've visited using a visited set, and we also keep a list called path_stack that stores the current path we're exploring in DFS. This path helps us reconstruct a cycle if we find one.

The key trick is to look for what's called a back edge. A back edge connects the current node to a node that has already been visited and is somewhere earlier in the current DFS path. When we find such a back edge, it means there is a cycle, and we can extract it from the path stack. But we have to be careful not to mistake a back edge to the immediate parent node for a real cycle. That's why the code checks if neighbor == parent and skips it. Otherwise, we'd wrongly think a node going back to its parent is a cycle of length $$$2$$$, which is not valid.

When we find a cycle, we check its length. If it's longer than $$$k$$$, then it's a valid answer, and we print it right away and stop the program. Since the problem guarantees that such a cycle exists, we don't need to search the whole graph—once we find one, we can safely exit.

Because the graph can be very large, we also increase the recursion limit and stack size using sys.setrecursionlimit and threading.stack_size. Python has a small default recursion stack, and without this change, the program could crash for big graphs.

Overall, the idea is simple: do a DFS, look for back edges that form cycles, and make sure the cycle is long enough. The parent check avoids false cycles, and the stack helps us extract the correct path.

import sys
import threading
from collections import defaultdict

# Increase the recursion limit and stack size to handle deep DFS
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)


def main():
    def solve():
        # Read number of nodes (n), number of edges (m), and minimum cycle length (k)
        n, m, k = map(int, sys.stdin.readline().strip().split())

        # Build the undirected graph as an adjacency list
        graph = defaultdict(list)
        for _ in range(m):
            u, v = map(int, sys.stdin.readline().strip().split())
            graph[u].append(v)
            graph[v].append(u)

        visited = set()
        path_stack = []

        # Depth-First Search to find a cycle of length > k
        def dfs(current, parent):
            visited.add(current)
            path_stack.append(current)

            for neighbor in graph[current]:
                if neighbor == parent:
                    continue
                if neighbor not in visited:
                    dfs(neighbor, current)
                else:
                    # A back edge found, which indicates a cycle
                    if neighbor in path_stack:
                        cycle_start_index = path_stack.index(neighbor)
                        cycle = path_stack[cycle_start_index:]
                        if len(cycle) > k:
                            print(len(cycle))
                            print(*cycle)

                            # Exit the program immediately after finding the valid cycle
                            sys.exit(0)

            path_stack.pop()

        # Start DFS from node 1
        dfs(1, -1)

    solve()


# Run the main function in a new thread to support increased stack size
if __name__ == "__main__":
    thread = threading.Thread(target=main)
    thread.start()
    thread.join()

Since we can only utilize either the length or width of all the blankets, the best choice for creating the longest possible rope is to first utilize all the blankets and use the longest side (length or width) of each blanket.

• Time Complexity: $$$O(n)$$$
• Space Complexity: $$$O(1)$$$

import sys
input = lambda : sys.stdin.readline().strip()


for _ in range(int(input())):
    n, h = map(int, input().split())
   
    rope = 0
    for i in range(n):
        l, w = map(int, input().split())
        rope += max(l, w)
   
    if rope >= h:
        print('YES')
    else:
        print('NO')

Output binary search.

The key insight is that if we have a wagon size greater than or equal to $$$\max(d_1, d_2, \dots, d_n)$$$, we only need to go once for every village. Hence, the sum of all $$$a_i$$$ is the minimum achievable time to deliver the water with any size.

If $$$\sum_{i=1}^{n} a_i$$$ is already greater than $$$k$$$, we can't make Empress Taytu happy with any size. If not, starting from 1 (left) up to $$$\max(d_1, d_2, \dots, d_n)$$$ (right), we can perform a binary search by checking whether it's achievable with a given size within $$$k$$$ hours.

For a single village, we can calculate the number of trips the wagon has to make by ceil dividing its demand by the wagon size. Then, we can calculate the total time needed for one village by multiplying the number of trips with the time it takes for one trip ($$$a_i$$$). After adding the total time for all villages, we will check if it is less than or equal to $$$k$$$. Overall, the complexity of the checker is $$$O(n)$$$.

The complexity of the binary search algorithm used in this solution is $$$O(\log(\max(d_1, d_2, \dots, d_n)))$$$. Since we need to check for each possible size of the wagon, the overall complexity of the algorithm is $$$O(n \log m)$$$, where $$$m = \max(d_1, d_2, \dots, d_n)$$$.

• Space Complexity: $$$O(1)$$$

from math import ceil
from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    d = list(map(int, input().split()))
    a = list(map(int, input().split()))

    if sum(a) > K:
        print(-1)
        continue

    def checker(size):
        time = 0
        for i in range(N):
            time += ceil(d[i]/size)*a[i]
        return time <= K
    
    left = 1
    right = max(d)
    while left <= right:
        mid = left + (right - left)//2
        if checker(mid):
            right = mid - 1
        else:
            left = mid + 1
    print(left)

Observation: After an increment operation, there is always a corresponding decrement operation.

Let's represent the characters with numerical values, such as their ASCII values. During an increment operation, the ASCII value of that character increases by $$$1$$$, and during a decrement operation, it decreases by $$$1$$$. Importantly, after an increment operation, the total sum of ASCII values of the word decreases by $$$1$$$, and after a decrement operation, the total sum increases by $$$1$$$. However, since one operation combines both increment and decrement, the total ASCII sum remains unchanged.

Therefore, to decrypt the message, we only need to check if there exists a substring with a size equal to the size of the sensitive word (let's denote it as $$$m$$$) and the sum of ASCII values of its characters is equal to that of the sensitive word. For this, we can employ a fixed-size sliding window approach with size $$$m$$$.

• Time Complexity: $$$O(n)$$$ where $$$n$$$ is the size of the decrypted message.
• Space Complexity: $$$O(1)$$$

from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    s = input()
    w = input()

    target = 0
    window_sum = 0
    for i in range(M):
        target += ord(w[i])
        window_sum += ord(s[i])
    
    found = False
    for i in range(M, N):
        if window_sum == target:
            found = True
            break
        window_sum += ord(s[i])
        window_sum -= ord(s[i - M])
    
    if window_sum == target or found:
        print("YES")
    else:
        print("NO")

In the first round, each group consists of two teams. Then, in the second round, every two consecutive groups are merged, and so on. This problem resembles a typical divide and conquer approach. Now, the question is, given the left group and the right group, how can we merge them and calculate the number of wins for every team efficiently?

One possible solution is to perform a binary search on the right team for each team in the left group, determining the number of players with strength strictly less than the current player's strength. Repeat this process for all players in the right group. Then, combine the two arrays using two pointers. The time complexity for this solution is $$$O(2^n * log^2(2^n))$$$, where $$$2^n$$$ is the size of the array.

Another approach is to use two pointers to calculate the wins. After calculating and updating both arrays, we can merge them together. This approach has a time complexity of $$$O(2^n*log(2^n)))$$$.

• Space Complexity: $$$O(2^n)$$$

def mergeSort(arr,l,r):
    if l == r:
   	 return
    
    # get the mid point of the current array and merge sort it
    mid = (l + r)//2
    mergeSort(arr,l,mid)
    mergeSort(arr,mid + 1, r)
    # merge the two halves after sorting them and calculating the answer
    merge(arr,l,mid,r)
 
def merge(arr,l,mid, r):
    # wins array to hold the number of wins each team have
 
    wins = [0]*(r - l + 1)
    # array to hold merged list
    merged = []
    
    # calculate the wins for the first group
    ptr = mid + 1
 
    # for every element of the first group
    for i in range(l,mid + 1):
   	 # move the second groups point to an element which is greater or equal to it
  	 
   	 while ptr <= r and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
 
   	 # the total numbe of wins for the current element
   	 #is the nubmer of element in the second group
   	 #that is lower than it
   	 wins[i - l] = ptr - (mid + 1)
 
    # same thing for the second group
    ptr = l
    for i in range(mid + 1,r+1):
   	 while ptr <= mid and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
   	 wins[i - l] = ptr - l
 
    # merge the two groups based on the new value
    pt1 = l
    pt2 = mid + 1
 
    while pt1 <= mid or pt2 <= r:
   	 if (pt2 > r) or (pt1 <= mid and arr[pt1][1] + wins[pt1 - l] < arr[pt2][1] + wins[pt2 - l]):
   		 arr[pt1][1] += wins[pt1 - l]
   		 merged.append(arr[pt1])
   		 pt1 += 1
   	 else:
   		 arr[pt2][1] += wins[pt2 - l]
   		 merged.append(arr[pt2])
   		 pt2 += 1
 
    arr[l:r + 1] = merged
 
 
 
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr = [[i,j] for i,j in enumerate(arr)]
    mergeSort(arr,0,2**n - 1)
    ans = [i[1] for i in sorted(arr,key = lambda x: x[0])]
    
    print(*ans)
 
t = int(input())
for _ in range(t):
    solve()

Find the time each gun explodes then you can take the maximum one.

Use monotonic stack to track the damage a gun receives for a gun behind him.

To determine the time it takes for each gun to explode, we can employ a monotonic stack approach. Starting from the first gun, which we know for sure will explode at infinity, we can represent each gun as a tuple $$$(t_i, p_i)$$$, where $$$t_i$$$ is the life of the $$$i$$$-th gun and $$$p_i$$$ is its power. These tuples are then pushed onto the stack.

For each gun $$$i$$$, we can understand that it receives a hit from the last gun on the stack. The damage it receives can be calculated as stack[-1][-1] * (stack[-1][0] - d), where stack[-1][0] and stack[-1][-1] represent the life and power of the gun at the end of the stack, respectively. Here, $$$d$$$ represents the duration of gun $$$i$$$ before it encounters the gun at the end of the stack. If the gun at the end of the stack cannot reduce the health of gun $$$i$$$ to zero, we decrement the received damage with the gun's health and pop from the stack.

• Time Complexity: $$$O(n)$$$
• Space Complexity: $$$O(n)$$$

import sys
from math import ceil, inf
input = lambda : sys.stdin.readline().strip()


for t in range(int(input())):
    n = int(input())
    health = list(map(int, input().split()))
    power = list(map(int, input().split()))


    stack = [(inf, power[0])]
    ans = 0
    for i in range(1, n):
        duration = 0
        while health[i] - (stack[-1][0] - duration)*stack[-1][-1] > 0:
            t, p = stack.pop()


            health[i] -= (t-duration)*p
            duration += (t-duration)
       
        duration += ceil(health[i]/stack[-1][-1])
        stack.append((duration, power[i]))
        ans = max(ans, duration)
   
    print(ans)

What if we have every sorted prefix.

Do we need every sorted prefix? and is there a fast way to compute it?

If we had every sorted prefix of the array, answering queries would be trivial, we could simply use binary search to count elements less than $$$X$$$ in the first $$$K$$$ elements. However, storing all sorted prefixes would require:

• $$$O(n² log n)$$$ time to preprocess
• $$$O(n²)$$$ space to store

This is clearly very inefficient.

An observation that will help us is that any positive integer $$$K$$$ can be represented as a sum of distinct powers of 2. This is essentially the binary representation of $$$K$$$. For example:

• $$$K = 5 = 4 + 1 (2² + 2⁰)$$$
• $$$K = 7 = 4 + 2 + 1 (2² + 2¹ + 2⁰)$$$
• $$$K = 10 = 8 + 2 (2³ + 2¹)$$$

This property allows us to decompose any prefix of length $$$K$$$ into $$$log K$$$ segments, each being a power of 2 in length,So we don't need every sorted prefix. Okay so now we only need to make these segments sorted.

If we can save this structure we will be able to calculate on each segment that makes up $$$K$$$, how many elements are less than $$$X$$$.

Complexity Analysis

Preprocessing

• Time: $$$O(N log N)$$$ — Each element appears in $$$O(log N)$$$ sorted segments
• Space: $$$O(N log N)$$$ — Storing all sorted segments

Queries

• Time: $$$O(log² N)$$$ per query ($$$O(log N)$$$ segments × $$$O(log N)$$$ binary search)
• Total for Q queries: $$$O(Q log² N)$$$

from bisect import bisect_left

for _ in range(int(input())):
    n, Q = map(int, input().split())
    soldiers = list(map(int, input().split()))
    
    '''
    calculate size as the smallest power of 2 
    greater than or equal to n
    '''
    size = 1
    level = 0
    while size * 2 < n:
        size *= 2
        level += 1
        
    size *= 2
    level += 2
    
    # lets extend the given array's size to a power of 2 
    while len(soldiers) < size:
        soldiers.append(float('inf'))
    
    n = len(soldiers) # Update n

    tree = [[] for _ in range(level)]
    tree[0].append(sorted(soldiers)) # the first leve(0) is the whole sorted array



    def merge(left, right):
        # standard merge of two sorted lists
        # we can do other things here if needed :)
        return sorted(left + right)




    def mergeSort(left, right, arr, level):
        if left == right:
            return [arr[left]]
        
        mid = (left + right) // 2
        
        left_half = mergeSort(left, mid, arr, level + 1)
        right_half = mergeSort(mid + 1, right, arr, level + 1)
        
        # save each sorted segment at its corresponding level
        tree[level].append(left_half) 
        tree[level].append(right_half)

        return merge(left_half, right_half)

    '''
    query function takes:
    k - number of elements to consider
    level - current level in the tree
    node - current node/segment index
    x - warriors strength value

    Each level contains segments of length 2^level
    We recursively find which segments make up the prefix of length k
    For each segment, we use binary search to count elements < x
    '''

    def query(k, level, node, x):
        # base case: no more elements or exceeded tree levels
        if level >= len(tree) or not k:
            return 0
        
        # calculate segment length at current level
        length = n 
        for _ in range(level):
            length //= 2 
        
        if length <= k:
            #count elements < x in this segment
            lesser_elements = bisect_left(tree[level][node-1], x)
            
            #recurse for remaining elements
            return lesser_elements + query(k - length, level + 1, (node*2) + 1, x)

        # if segment is larger than needed, go deeper
        return query(k, level + 1, 2*node - 1, x)
            
    # build the merge sort tree starting from level 1
    mergeSort(0, n-1, soldiers, 1)


    #Finally now we can process queries
    for _ in range(Q):
        k, x = map(int, input().split())
        print(query(k, 0, 1, x)) 

For each query, we need to count how many elements in a prefix A[0..K-1] are strictly less than $$$X$$$. Naively, for each query, iterating through the prefix would cost $$$O(K)$$$ per query, which is too slow when $$$Q$$$ and $$$K$$$ are large. We need something faster, ideally logarithmic time per query.

A powerful way to handle such queries efficiently is to use divide and conquer, or specifically merge sort logic. We are going to apply a modified merge sort on the array. The main idea is to group queries based on their indices (that is, the prefix limit $$$K$$$). For each index $$$i$$$, collect all the different values $$$X$$$ that will be queried against the prefix up to $$$i$$$.

A standard merge sort is used to both, sort the array, and merge and count how many left-side elements are less than $$$X$$$ for every query on the right side. This allows for efficiently processing all queries offline. We can store the answer for every possible ($$$K$$$, $$$X$$$) pairs. And then we will iterate through all the queries and then print the answer.

For the time complexity of this approach the operations is similar to regular merge sort, in the sense that we have $$$O(\log N)$$$ layers, and on each layer we will have $$$O(N + Q)$$$ operations per layer. Therefore, the overall time complexity will be $$$O((N + Q) \log N)$$$.

For the space complexity, since merge sort is not in-place, we will have $$$O(N)$$$ memory consumption for sorting. And there is also $$$O(Q)$$$ memory for storing the queries, and the dictionary that stores the $$$X$$$s. Therefore, the overall space complexity will be $$$O(N + Q)$$$.

from collections import Counter
import sys


def input():
    return sys.stdin.readline().strip()


# Utility to read list of integers
def readList():
    return list(map(int, input().split()))


def solve():
    array_length, query_count = readList()
    array = readList()

    queries = []
    for _ in range(query_count):
        index, value = readList()
        queries.append((index - 1, value))  # 0-based indexing

    # Track required query values per index
    query_values_at_index = [set() for _ in range(array_length)]
    for index, value in queries:
        query_values_at_index[index].add(value)

    # Sort required values for each index for binary search/merge purposes
    for index in range(array_length):
        query_values_at_index[index] = sorted(query_values_at_index[index])

    # Dictionary to store the result of each (index, value) query
    query_results = Counter()

    def merge_sort_count(start, end):
        """
        Recursive divide and conquer function that returns:
        - a sorted list of elements in array[start:end+1]
        - a sorted list of (value, index) query pairs for that segment
        Also populates query_results with counts of elements less than 'value' to the left of 'index'.
        """
        if start == end:
            current_elements = [array[start]]
            current_queries = [(value, start) for value in query_values_at_index[start]]

            for value, idx in current_queries:
                if array[start] < value:
                    query_results[(idx, value)] += 1

            return current_elements, current_queries

        mid = (start + end) // 2
        left_elements, left_queries = merge_sort_count(start, mid)
        right_elements, right_queries = merge_sort_count(mid + 1, end)

        merged_elements = []
        merged_queries = []

        # Count how many left_elements are < each right query's value
        i = j = count = 0
        while i < len(left_elements) and j < len(right_queries):
            value, idx = right_queries[j]
            if left_elements[i] < value:
                count += 1
                i += 1
            else:
                query_results[(idx, value)] += count
                j += 1

        # For remaining right queries
        while j < len(right_queries):
            value, idx = right_queries[j]
            query_results[(idx, value)] += count
            j += 1

        # Merge the sorted arrays
        i = j = 0
        while i < len(left_elements) and j < len(right_elements):
            if left_elements[i] <= right_elements[j]:
                merged_elements.append(left_elements[i])
                i += 1
            else:
                merged_elements.append(right_elements[j])
                j += 1

        merged_elements.extend(left_elements[i:])
        merged_elements.extend(right_elements[j:])

        # Merge the sorted query lists
        i = j = 0
        while i < len(left_queries) and j < len(right_queries):
            if left_queries[i] <= right_queries[j]:
                merged_queries.append(left_queries[i])
                i += 1
            else:
                merged_queries.append(right_queries[j])
                j += 1

        merged_queries.extend(left_queries[i:])
        merged_queries.extend(right_queries[j:])

        return merged_elements, merged_queries

    # Run the divide and conquer process
    merge_sort_count(0, array_length - 1)

    # Print the answers in the order of input queries
    for index, value in queries:
        print(query_results[(index, value)])


t = int(input())
for _ in range(t):
    solve()

The numbers we consider are "boring" numbers, meaning they consist of the same digit (e.g., (1, 11, 111, 1111, \dots)).

Instead of checking every number, note that numbers are called in order: all 1s first, then all 2s, and so on.

To find the total keypresses, we count: - All previous digits' keypresses (full sequences for numbers before (x)). - The keypresses needed for numbers up to (x) using a simple sum formula.

Each "boring" number is called in a structured order: all numbers made of 1s first, then 2s, then 3s, and so on. Instead of iterating through every number, we can break the total keypresses into two parts: 1. Counting keypresses for previous digits: — Before reaching (x), all numbers made of smaller digits (e.g., (1, 11, 111, 1111) if (x) is in the 2s) are fully called. — Each digit contributes (10) keypresses for its full sequence. Thus, for a digit (d), the total keypresses before it is: [ 10 *(d-1) ] 2. Counting keypresses for numbers leading up to (x): — If (x) has (n) digits (e.g., (x = 222) has (n = 3)), we count keypresses for forming each prefix: [ 1 + 2 + ... + n ] — This is directly computed using a simple loop summing (1) to (n). By combining these two values, we get the total keypress count in (O(1)) time.

t = int(input())
for _ in range(t):
    x = int(input())
    val = x % 10  # Get the digit (since x consists of the same digit)
    ans = 10 * (val - 1)  # Count keypresses for previous digits
    sz = len(str(x))  # Get the number of digits in x
    ans += sum(range(1, sz + 1))  # Add keypresses for the current digit
    print(ans)

Sort the bases by their defensive power and maintain a running sum of gold. For each spaceship, find the maximum number of bases it can attack efficiently.

The problem requires us to determine how much gold each spaceship can steal based on its attacking power.

Approach:

1. Sort the Bases by Defensive Power

• This allows us to efficiently find all bases a spaceship can attack using a two-pointer technique.
• Keep track of the cumulative gold collected as we iterate through the bases.

1. Sort the Spaceships and Process Them in Order

• Sorting spaceships ensures that we process weaker spaceships first, maintaining efficiency in tracking available bases.
• Maintain the original indices of spaceships so that we can return the results in the correct order.

1. Use Two-Pointer Technique

• Iterate through the sorted spaceships, and for each spaceship, move a pointer (l) to include all bases it can attack.
• Keep a running sum of gold to quickly determine the total amount available.

1. Store Results and Print in Original Order

• Since we modified the order of spaceships during sorting, we store results in an array indexed by their original positions.

Example Walkthrough:

Input:

5 4  
1 3 5 2 4  
0 1  
4 2  
2 8  
9 4  

Processing:

• Sort bases: [(0,1), (2,8), (4,2), (9,4)]
• Sort spaceships with indices: [(1,0), (2,3), (3,1), (4,4), (5,2)]
• Maintain a cumulative gold sum:
• Spaceship (1): Can attack base (0,1), steals 1.
• Spaceship (2): Can attack bases (0,1), (2,8), steals 9.
• Spaceship (3): Can attack bases (0,1), (2,8), steals 9.
• Spaceship (4): Can attack bases (0,1), (2,8), (4,2), steals 11.
• Spaceship (5): Can attack bases (0,1), (2,8), (4,2), steals 11.

Output:

1 9 11 9 11  

Complexity Analysis:

• Sorting bases: O(b log b)
• Sorting spaceships: O(s log s)
• Two-pointer traversal: O(s + b)
• Overall complexity: O((s + b) log(s + b))

def solve():
    # Read input values: number of spaceships (s) and number of bases (b)
    s, b = map(int, input().split())
    
    # Read the attacking power of each spaceship
    ships = list(map(int, input().split()))
    
    # Read the defensive power and gold of each base
    bases = [list(map(int, input().split())) for _ in range(b)]
    
    # Step 1: Sort bases by defensive power to process them efficiently
    bases.sort()
    
    # Step 2: Sort spaceships by attacking power while keeping track of original indices
    ships = sorted((ships[i], i) for i in range(s))
    
    # Array to store the maximum gold each spaceship can steal
    ans = [0] * s
    
    # Two-pointer approach to efficiently determine how much gold each spaceship can steal
    l, max_gold = 0, 0
    
    # Step 3: Process each spaceship in increasing order of attacking power
    for i in range(s):
        # Move the pointer 'l' to include all bases that the spaceship can attack
        while l < b and bases[l][0] <= ships[i][0]:
            max_gold += bases[l][1]  # Add the gold from the base
            l += 1  # Move to the next base
        
        # Store the total gold that this spaceship can steal
        ans[ships[i][1]] = max_gold  # Store result at original index
    
    # Step 4: Print the results in the original order of spaceships
    print(*ans)

if __name__ == "__main__":
    solve()

Consider that the player's position after each move must lie within the intersection of the reachable area from the previous position (given ( k )) and the current segment's bounds.

Use binary search to efficiently determine the minimal ( k ). For each candidate ( k ), simulate the player's movement through all segments to check feasibility.

1. Binary Search Setup: The minimal ( k ) lies between 0 and a sufficiently large upper bound.
2. Feasibility Check: For each candidate ( k ):

• Start at position 0.
• For each segment, compute the reachable interval after moving at most ( k ) units from the previous position.
• Intersect this interval with the current segment's bounds.
• If the intersection is empty, ( k ) is too small.

1. Binary Search Adjustment: Adjust the search range based on feasibility results to find the minimal ( k ).

import sys def can_complete_level(n, segments, k): L, R = 0, 0 # The range of reachable positions for l, r in segments: # Compute the new reachable range L = max(l, L — k) R = min(r, R + k) if L > R: # If no valid landing position exists return False return True def find_min_k(n, segments): left, right = 0, 10**9 # Binary search for k while left <= right: mid = (left + right) // 2 if can_complete_level(n, segments, mid): right = mid — 1 else: left = mid + 1 return left def main(): t = int(input()) results = [] for _ in range(t): n = int(input()) segments = [] for _ in range(n): l, r = map(int, inpit().split()) segments.append((l, r)) results.append(str(find_min_k(n, segments))) sys.stdout.write(" ".join(results) + "\n") if name == "__main__": main()

• Binary Search: The search runs in ( O(\log(\text{max_distance})) ) iterations, where (\text{max_distance}) is the upper bound (( 10^9 )).
• Feasibility Check: Each check processes ( n ) segments in ( O(n) ) time.
• Total Complexity: ( O(t \cdot n \cdot \log(10^9)) ), which is efficient given the constraints (sum of ( n ) across test cases is ( 2 \cdot 10^5 )).

Consider selecting Farmer John's room first and then placing the cows in the nearest available unoccupied rooms.

If the farthest distance is ( x ), can you calculate the maximum number of cows that can be placed?

Try using prefix sum to efficiently calculate how many cows can be placed within a given range.

This problem might have another solution where we can calculate the answer directly. But for a moment, let's think about whether this can be solved without binary search.

The first thing we do when solving output binary search problems is check: Can we easily verify if a given answer is valid or not? If someone told us the answer in advance, could we efficiently check its validity? If so, we can use binary search to guess the answer. For this to work, the function must be monotonic (i.e., if a certain ( x ) is possible, all larger values are also possible). Since this function is monotonic, we can use binary search to efficiently find the minimum ( x ) that satisfies the conditions.

The binary search must start with ( l = 0 ) and ( r = n ), as this ensures we explore the full possible range of distances. To check feasibility for a given distance ( d ), we calculate how many available rooms exist in the range ( left, right ), where: - ( left = max(0, i — d) ) - ( right = min(n, i + d + 1) )

We use the prefix sum array to efficiently compute the number of unoccupied rooms within this range.

Complexity Analysis

• Binary Search: The search runs in ( O(\log n) ) iterations since we are halving the search space each time.
• Feasibility Check: Each check processes ( n ) rooms in ( O(n) ) time.
• Prefix Sum Computation: Constructing the prefix sum array takes ( O(n) ) time.
• Total Complexity: The overall complexity is ( O(n log n) ), which is efficient given the constraints.

import sys

def solve():
    n, k = map(int, sys.stdin.readline().strip().split())
    s = sys.stdin.readline().strip()
    prefix = [0]
    
    # Compute prefix sum for counting free rooms quickly
    for val in s:
        prefix.append(prefix[-1] + (1 if val == '0' else 0))
    
    def max_cows_in_range(d):
        """Given max distance d, calculate the maximum number of cows that can be placed"""
        max_cows = 0
        for i in range(n):
            if s[i] == '0':  # Consider only unoccupied rooms
                left = max(0, i - d)
                right = min(n, i + d + 1)
                max_cows = max(max_cows, prefix[right] - prefix[left])
        return max_cows
    
    # Binary search for the minimum possible maximum distance
    l, r = 0, n
    while l < r:
        mid = (l + r) // 2
        if max_cows_in_range(mid) >= k + 1:
            r = mid  # Try a smaller maximum distance
        else:
            l = mid + 1
    
    print(l)

if __name__ == "__main__":
    solve()

The problem asks for the k-th largest number in the multiplication table. However, listing all numbers and sorting them in descending order is too slow. Instead, think about how to find the k-th smallest number first—since the k-th largest in a sorted list is the same as the (n*m — k + 1)-th smallest.

To efficiently find the k-th smallest number without generating all elements, use binary search on possible values (from 1 to n*m). For a given mid-value, count how many numbers in the table are ≤ mid by checking each row.

The problem requires finding the k-th smallest number in an n × m multiplication table where each cell (i, j) contains i * j. Since generating and sorting all n * m elements is too slow for large n and m, we use binary search on the possible values (from 1 to n * m).

For a given mid-value during binary search, we count how many numbers in the table are ≤ mid by iterating through each row i and calculating min(mid // i, m). This gives the count of valid numbers in that row.

If the total count is less than k, the k-th smallest number must be larger than mid, so we adjust the search to higher values.

If the count is ≥ k, the k-th smallest number could be mid or smaller, so we search lower values.

The binary search efficiently narrows down the correct value in O(n log(n * m)) time, making it suitable for large constraints.

def solve():
    n, m, k = map(int, input().split())

    def find(mid):
        count = 0
        for i in range(1, n + 1):
            add = min(mid // i, m)
            if add == 0:
                break
            count += add
        return count < k

    low, high = 1, n * m
    answer = 0

    while low <= high:
        mid = (low + high) // 2
        if find(mid):
            low = mid + 1
        else:
            answer = mid
            high = mid - 1

    print(answer)

t = 1
for _ in range(t):
    solve()

You should count the number of parentheses at the end of the string, suppose there are $$$x$$$ such parentheses. Then if $$$X$$$ is greater than $$$n - X$$$ the answer is “Yes”, otherwise “No”.

testcase = int(input())
for _ in range(testcase):
    n = int(input())
    S = input()
    count = 0
    for i in range(n-1,-1,-1):
        if S[i] != ')':
            break
        count += 1
    if count > n - count:
        print("Yes")
    else:
        print("No")

Consider two cases:

The array is already sorted. THe array is not sorted.

In the first case, sorting any prefix and any suffix does not change the array. So the array will always remain sorted so the answer is "NO".

In the second case, it is guaranteed that there will be two elements with indexes $$$i$$$ and $$$j$$$, such that $$$i \lt j$$$ and $$$ai \gt aj$$$. So choose len so that these two elements will be in different parts. For example — $$$len = i$$$. Note that after operation $$$ai$$$ will remain to the left of $$$aj$$$, which means the array will not be sorted. So the answer is "YES".

Then the solution is to check if the array is sorted, which can be done in O(n), or O(nlogn) by sorting a copy of the array using built-in sorting algorithms.
.

testcase = int(input())

for _ in range(testcase):
    n = int(input())
    nums = list(map(int, input().split()))
    
    for i in range(1, n):
        if nums[i] < nums[i-1]:
            print("YES")
            break
    else:
        print("NO")

n will always be beautiful because we can take the entire given array. What must happen for n — 1 to be beautiful?

Either the first n — 1 elements should be a permutation of n — 1 or the last n — 1.

Doesn’t that mean the maximum of the first and the last element should be n?

Can we extend this for n — 1, n — 2, … 1 ?

We can use the deque data structure to solve this problem. Initially we know that n is always beautiful. To check if n — 1 is beautiful, we compare the first and the last elements in our deque, and remove the maximum of the two. We pop from the left or right accordingly. Then all the numbers from 1 uo to n — 1 must be present in the deque. For that to be the case the minimum element we have popped so far must be strictly greater than n — 1. We do the same thing for n — 2 as well. We pop the maximum of the first and the last elements from the leftover elements in our deque, and keep track of the minimum element we have popped so far. That element should be strictly greater than n — 2 for n — 2 to be beautiful. If that is not the case, it means some number in the range 1 to n — 2 (inclusive) was popped. Therefore our deque is not a permutation of n — 2 as we need all the numbers from 1 to n — 2 to say so.

Time and space complexities

• Time Complexity: O(n)
• Space Complexity: O(n)

from collections import deque

t = int(input())
for _ in range(t):

    n = int(input())
    permutation = deque(map(int, input().split()))

    is_beautiful = ['0'] * n
    is_beautiful[n - 1] = '1' # n(n - 1 for 0 - indexed) is beautiful
    
    min_popped = float('inf')
    for num in range(n - 2, -1, -1):

        if permutation[0] > permutation[-1]:
            min_popped = min(min_popped, permutation.popleft())
        else:
            min_popped = min(min_popped, permutation.pop())
        
        if min_popped > num + 1: # num is 0-indexed so we need num + 1 for 1-indexed
            is_beautiful[num] = '1'
    
    print(''.join(is_beautiful))
    

1 will always be beautiful. What must happen for 2 to be beautiful?

2 must be present right after 1 or just before 1.

How can we extend this for 3, 4, 5, … n ?

Let’s first have the indices of each number stored in a dictionary. Let’s also have two pointers l, r. Initially we will assign the index of 1 for both. r — l + 1 indicates the size of the subarray that starts at l and ends at r. Now to check if 2 is beautiful, we first update l and r to include both $$$1$$$ and $$$2$$$. To do this we replace l with min(l, index of 2) and r with max(r, index of 2). After the updates we know both 1 and 2 are included in the subarray that starts at l and ends at r, and that subarray is the smallest sized subarray to do so. So if r — l + 1 is equal to 2, then 2 is beautiful, but if that’s not the case r — l + 1 is greater than 2 which indicates that there is no subarray of size two that includes both 1 and 2 assuring us that a permutation of 2 is not present in the given array as a subarray. We keep doing this for all the other numbers.

Time and space complexities

• Time Complexity: O(n)
• Space Complexity: O(n)

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))

    indices = {}
    for i in range(n):
        indices[arr[i]] = i
    
    l, r = indices[1], indices[1]
    is_beautiful = ['0'] * n
    is_beautiful[0] = '1' # 1 is beautiful

    for i in range(2, n + 1):
        
        l = min(l, indices[i])
        r = max(r, indices[i])

        if r - l + 1 == i: 
            is_beautiful[i - 1] = '1' 
    
    print(''.join(is_beautiful))

    

To efficiently determine the minimum number of moves, consider how to group elements based on their remainders when divided by ( k ) and track how many elements need to be adjusted to the same remainder.

The problem requires modifying an array such that all elements become divisible by ( k ) using two types of operations. A naive approach would involve brute-force testing every possible modification, leading to inefficiency. Instead, we can use the following optimized strategy:

• For each element ( a_i ), compute its remainder when divided by ( k ) (i.e., ( r = a_i \mod k )). If ( r = 0 ), the element is already valid.
• For all elements where ( r \neq 0 ), calculate the required increment ( k — r ) to make them divisible by ( k ).
• Use a hashmap to count how many times each increment value appears since we can only apply each increment once per element.
• The key observation is that for each unique remainder value, we must adjust multiple elements in steps of ( k ). The maximum time required is given by the highest calculated increment considering the repeated occurrences.
• Thus, for each unique remainder ( r ), the maximum move count is determined by ( k — r + (count — 1) \times k ), where ( count ) is the frequency of that remainder in the array.

Finally, the answer for each test case is the maximum move count among all remainder groups plus one (to account for the starting move).

from collections import defaultdict
def solve():
    n, k = map(int, input().split())
    table = defaultdict(int)
    nums = list(map(int, input().split()))
    for num in nums:  
                r = num % k  
                if r:  
                    table[k - r] += 1  

    ans = 0  
    for key, val in table.items():  
            ans = max(ans, key + (val - 1) * k)  

    print(ans + 1 if ans else 0)  
for _ in range(int(input())):
 	solve()

Let's consider three offsets of string "RGB": "RGB", "GBR" and "BRG".

Let's compare our string s with infinite concatenation of each offsets of "RGB". However, we don't need an infinite string to compare. n-sized string could be enough. We don't either need to create n-sized string. We can observe that in the concatenated string the first character of the offset will always be on an index which is a multiple of 3 (whose modulo 3 is 0), the second character will be on an index whose modulo 3 is 1, the third character will be on an index whose modulo 3 is 2.

We can use fixed sliding window and compare the character in that window. While comparing we will count the matches and keep track of the maximum matches in k -sized window. We can then find the minimum number of changes we need to make by subtracting the number of maximum matches from k .

T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    s = input()

    offsets = ["RGB", "GBR", "BRG"]
    ans = float('inf')

    for offset in offsets:
        matches = 0
        for right in range(K): # Calculate the matches for first K elements
            if offset[right%3] == s[right]:
                matches += 1
        
        max_matches = matches
        for right in range(K, N):
            left = right - K
            if offset[right%3] == s[right]:
                matches += 1
            if offset[left%3] == s[left]:
                matches -= 1
            
            max_matches = max(matches, max_matches)
        
        ans = min(ans, K - max_matches)
    
    print(ans)

Polycarpus has two circular sequences of hieroglyphs $$$a$$$ and $$$b$$$. Since a computer stores sequences linearly, he must flatten each circle into a string. However, the cut position (where the circle is broken) can vary, affecting the order of hieroglyphs in the resulting string.

Our goal is to determine the longest contiguous substring of the first sequence that appears as a subsequence in the second sequence, considering the optimal way to "cut" the circle.

We can first create a set to store the position of each element in the $$$b$$$. This allows us to quickly check if an element from $$$a$$$ exists in $$$b$$$ and retrieve its position in constant time.

We maintain two pointers. A left_pointer that marks the start of the current valid substring of $$$a$$$. And a right_pointer expands the substring to find the longest valid one. We also track the sum of index differences in $$$b$$$ to ensure the substring respects the order of the $$$b$$$ and doesn't exceed its length ($$$b$$$'s length).

We extend right_pointer while ensuring that the next element exists in $$$b$$$, the order in $$$b$$$ is maintained and the total shift does not exceed the length of $$$b$$$.

When the left_pointer moves, we update the sum of index differences to maintain correctness. This ensures that we explore all possible valid substrings efficiently.

The time complexity is going to be $$$O(l_a + l_b)$$$ because it processes both sequences linearly using a sliding window approach, ensuring efficient substring exploration.The space complexity is $$$O(l_b)$$$ because we store the positions of elements from $$$b$$$ in a set.

import sys

input = lambda: sys.stdin.readline().strip()

# Read input values
len_a, len_b = map(int, input().split())
arr_a = list(map(int, input().split()))
arr_b = list(map(int, input().split()))

# Store positions of elements in arr_b
position = {}
for index in range(len_b):
    position[arr_b[index]] = index

max_subarray_length = 0
current_sum = 0
right_pointer = 0

for left_pointer in range(len_a):
    if right_pointer < left_pointer:
        right_pointer = left_pointer
        current_sum = 0
    elif left_pointer > 0:
        difference = position[arr_a[left_pointer]] - position[arr_a[left_pointer - 1]]

        if difference < 0:
            difference += len_b

        current_sum -= difference

    if arr_a[left_pointer] not in position:
        continue

    while right_pointer < left_pointer + len_a - 1:
        value = arr_a[(right_pointer + 1) % len_a]
        if value not in position:
            break

        difference = (
            position[arr_a[(right_pointer + 1) % len_a]]
            - position[arr_a[right_pointer % len_a]]
        )

        if difference < 0:
            difference += len_b

        if current_sum + difference >= len_b:
            break

        right_pointer += 1
        current_sum += difference

    sub_array_length = right_pointer - left_pointer + 1
    max_subarray_length = max(sub_array_length, max_subarray_length)

print(max_subarray_length)

To solve this problem efficiently, we simulate the sequence of operations while maintaining two values: the current number of ice cream packs and the count of distressed children. We start with $$$x$$$ packs and iterate through $$$n$$$ operations. If a carrier ($$$+d$$$) arrives, we increase our stock by $$$d$$$. If a child ($$$-d$$$) requests d packs, we check if we have enough ice cream. If yes, we serve the request and decrease our stock; otherwise, we increment the count of distressed kids. By processing all operations sequentially, we determine the final ice cream count and the number of distressed kids. This approach runs in $$$O(n)$$$ time, making it efficient given the constraints.

def solve():
    n, cur = map(int, input().split())
    distress = 0
    
    for _ in range(n):
        op, d = input().split()
        d = int(d)
        
        if op == '+':
            cur += d
        elif cur >= d:
            cur -= d
        else:
            distress += 1
    
    print(cur, distress)

solve()

To solve this problem, we need to construct a sequence $$$b$$$ that satisfies the given conditions. The key idea is to ensure that $$$b$$$ is strictly increasing and does not contain any elements from $$$a$$$.

Steps to Solve:

1. Initialize a variable Last_elem to $$$0$$$, which will keep track of the last value added to the sequence $$$b$$$.
2. Iterate through each element in the sequence $$$a$$$.
3. For each element $$$a_i$$$:
   • Increment Last_elem by $$$1$$$.
   • If Last_elem is equal to $$$a_i$$$, increment Last_elem by $$$1$$$ again to ensure $$$b_i \neq a_i$$$.
4. After processing all elements, Last_elem will hold the minimum value of $$$b_n$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    last_elem = 0
    for num in a:
        last_elem += 1
        if last_elem == num:
            last_elem += 1
    print(last_elem)

In this problem, we are given a sequence of penalty kicks between two teams. Each team takes turns kicking, with the first team starting first. The goal is to determine the earliest possible moment when the penalty phase can be stopped. The phase stops if one team has scored more goals than the other team could possibly reach with their remaining kicks.

Each kick is represented by a character in a 10-character string. A 1 means the kick is a goal, a 0 means the kick is missed, and a ? means the outcome is uncertain, it could be either a goal or a miss. Our task is to find the minimum number of kicks required before the game can be stopped, considering all possible ways the ? values could be filled.

If we know the result of every kick in advance, how would we simulate the penalty phase?

Since ? can be either 0 or 1, how does this affect the number of possible outcomes?

One way to solve this is by replacing every ? with both possible values (0 and 1) and testing all resulting sequences. For each sequence, we simulate the match, tracking the score of both teams. At each step, we check if one team has gained an unbeatable lead, meaning the other team cannot catch up even if they score on all remaining kicks. The moment this happens, the game is stopped. The answer is the smallest number of kicks needed across all possible sequences.

This approach ensures we check every possible scenario, but it is slow because the number of cases grows exponentially with the number of ? characters.

Time Complexity: If there are at most $$$10$$$ characters and each ? can be either 0 or 1, the worst case has $$$2^{10}=1024$$$ possible cases. Each case requires checking all $$$10$$$ kicks, leading to a worst-case complexity of $$$O(10 \times 1024)$$$ per test case. This is slow but manageable for $$$t \leq 1000$$$.

Space Complexity: Since we only use a few integer variables to track scores, and also the recursion depth will not go more than 10, the space complexity is $$$O(1)$$$.

import sys
from math import ceil


def input():
    return sys.stdin.readline().strip()


def earliest_decision_point(s):
    length = len(s)
    ans = length

    def recurse(index, cur1, cur2):
        nonlocal ans
        if index >= length:
            return

        remaining = length - index
        if index % 2:
            if cur2 + ceil(remaining / 2) < cur1 or cur1 + remaining // 2 < cur2:
                ans = min(ans, index)
                return
            if s[index] == "1":
                recurse(index + 1, cur1, cur2 + 1)
            elif s[index] == "0":
                recurse(index + 1, cur1, cur2)
            else:
                recurse(index + 1, cur1, cur2 + 1)
                recurse(index + 1, cur1, cur2)
        else:
            if cur1 + ceil(remaining / 2) < cur2 or cur2 + remaining // 2 < cur1:
                ans = min(ans, index)
                return
            if s[index] == "1":
                recurse(index + 1, cur1 + 1, cur2)
            elif s[index] == "0":
                recurse(index + 1, cur1, cur2)
            else:
                recurse(index + 1, cur1 + 1, cur2)
                recurse(index + 1, cur1, cur2)

    recurse(0, 0, 0)
    return ans


t = int(input().strip())
for _ in range(t):
    s = input().strip()
    print(earliest_decision_point(s))

Instead of considering all possible ways to fill in the ? values, can we determine the earliest stopping point by only looking at the best or worst-case scenarios for each team?

A more efficient approach is to determine the earliest possible stopping point without checking all possibilities. We do this by considering two extreme cases:

1. The best case for the first team: Assume all ?s taken by the first team result in goals (1), and those taken by the second team result in misses (0).
2. The best case for the second team: Assume all ?s taken by the second team result in goals (1), and those taken by the first team result in misses (0).

For each case, we simulate the match while keeping track of the maximum possible score each team can still achieve. At each step, if one team’s score is greater than the highest possible score the other team could still reach, the game can be stopped. The answer is the minimum number of kicks required in these two cases.

This method is much faster because instead of trying all possibilities, we only check two scenarios, reducing unnecessary calculations.

Time Complexity: Since we only go through the string twice (once for each extreme case), the complexity is $$$O(10)$$$, which is actually $$$O(1)$$$ per test case.

Space Complexity: We only use a few integer variables to keep track of scores, so the space complexity is $$$O(1)$$$.

import sys
from math import ceil


def input():
    return sys.stdin.readline().strip()


def earliest_decision_point(s):
    length = len(s)
    x1, x2, cur1, cur2 = 0, 0, 0, 0

    for i in range(length):
        remaining = length - i

        if i % 2:
            if (
                cur2 + ceil(remaining / 2) < cur1 + x1
                or cur1 + remaining // 2 < cur2 + x2
            ):
                return i
            if s[i] == "1":
                cur2 += 1
            elif s[i] == "?":
                x2 += 1
        else:
            if (
                cur1 + ceil(remaining / 2) < cur2 + x2
                or cur2 + remaining // 2 < cur1 + x1
            ):
                return i
            if s[i] == "1":
                cur1 += 1
            elif s[i] == "?":
                x1 += 1

    return length


t = int(input().strip())
for _ in range(t):
    s = input().strip()
    print(earliest_decision_point(s))

Try breaking the problem into smaller subproblems by dividing the string into two halves and ensuring one half follows the rule while the other is recursively solved.

We define a recursive function calc(l, r, c), where:

• l and r represent the start and end indices of the current segment.
• c represents the character we are trying to make this segment follow.
• The function returns the minimum number of moves needed to convert the substring s[l:r] into a c-good string.

Base Case: If the length of the segment is 1 (r = l):

• If s[l] = c, return 0 (no changes needed).
• Otherwise, return 1 (we must change s[l] to c).

Recursive Case: We split the segment into two halves and consider two possible transformations:

• case 1: The first half should be fully filled with c, and the second half should be (c+1)-good.
• case 2: The second half should be fully filled with c, and the first half should be (c+1)-good.

For each case, we compute the number of changes needed:

• left_result: Changes required to make the first half fully filled with c + recursive call on the second half to make it (c+1)-good.
• right_result: Changes required to make the second half fully filled with c + recursive call on the first half to make it (c+1)-good.

The final result for this segment is: min(left_result,right_result)

Time Complexity: The function processes each segment by counting characters (in $$$O(n)$$$ time) and then recursively splitting it into two halves. Since each level of recursion does a total of $$$O(n)$$$ work and there are $$$\log n$$$ levels (because the segment size halves each time), the total complexity is $$$O(n \log n)$$$.

Space complexity: The only space used in this solution is the call stack due to recursion. Since the recursion divides the problem into two halves at each step, the maximum depth of the recursion tree is $$$\log n$$$. Therefore, the space complexity is determined by the depth of the recursion, which is $$$O(\log n)$$$.

def calc(l, r, c):
    if l == r:
        if s[l] == c:
            return 0
        return 1
    
    mid = (l + r) // 2
    
    left_changes = (mid - l + 1) - s[l:mid + 1].count(c)    
    left_result = left_changes + calc(mid + 1, r, chr(ord(c) + 1))
 
    right_changes = (r - mid) - s[mid + 1:r + 1].count(c)
    right_result = right_changes + calc(l, mid, chr(ord(c) + 1))
 
    return min(left_result, right_2result)
 
for _ in range(int(input())):
    n = int(input())
    s = input()
 
    print(calc(0, len(s) - 1, 'a'))

Instead of building the whole transformed string, find a way to track where each character comes from in the original string. Notice that each step doubles the string and follows a clear pattern.

The problem asks us to find the $$$k^{th}$$$ character after repeatedly transforming a string. Since the string grows extremely fast, it is impossible to generate the final version directly. Instead, we need a smarter way to determine the answer.

Each transformation doubles the string: the first half stays the same, and the second half is the same as the first but with uppercase and lowercase letters swapped. This means that any character in the final string can be traced back to its original position in the first version.

To find the character at position $$$k$$$, we work backwards to see where it came from. If $$$k$$$ is in the first half of a transformation step, it remains unchanged. If it is in the second half, we can shift it back to the first half of the previous step and apply a case swap. We repeat this process until we reach the original string.

For the time complexity, each query runs in $$$O(\log k)$$$, which is at most $$$60$$$ for $$$k \leq 10^{18}$$$. Since $$$q \leq 2 \times 10 ^ 5$$$, this is fast enough.

For the space complexity, the solution uses $$$O(\log k)$$$ extra space since we do not store the full transformed string. Our only space consumption is the call stack from the recursive calls.

import sys


def input():
    return sys.stdin.readline().strip()


def read_list():
    return list(map(int, input().split()))


# Recursive function to find the character at position k in the transformed sequence
def find_char(depth, k, m, original):
    if depth == 1:  # Base case: when depth is 1, return the original character
        return original[m]

    # Calculate the halfway point in the current sequence
    half_length = 2 ** (depth - 2)

    if k > half_length:
        # If k is in the second half, move to the previous depth and swap case
        return find_char(depth - 1, k - half_length, m, original).swapcase()

    # If k is in the first half, continue in the same depth
    return find_char(depth - 1, k, m, original)


def solve():
    original_str = input()  # Read the original string
    _ = int(input())
    queries = read_list()  # Read the list of queries
    n = len(original_str)  # Get the length of the original string

    results = []
    for k in queries:
        k -= 1  # Convert to zero-based index
        depth = k // n + 1  # Determine the depth level
        index = k % n  # Find the corresponding index in the original string
        results.append(find_char(61, depth, index, original_str))  # Compute the result

    print(*results)  # Print all results space-separated


t = int(input())
for _ in range(t):
    solve()

Simply put, the problem is asking us to represent $$$S$$$, as a summation of numbers from the set $$${1, 2, 3, … ,n }$$$.

Obviously there are many ways to do that, for example one might use $$$1$$$ $$$S$$$ times, but in this problem we are asked to use the minimum number of elements and output how many we used.

Since we have all the numbers from $$$1$$$ to $$$n$$$ and we can use each element repeatedly, we can afford to be greedy and always use the largest value less or equal to $$$S$$$, until we get the sum of the selected elements equal to $$$S$$$. This ensures that we use the fewest possible numbers.

This process can easily be represented by a ceil division of $$$S$$$ by $$$n$$$.

because $$$⌈S/n⌉$$$ tells us how many times we would need to add the largest possible number (which is $$$n$$$) to reach or exceed $$$S$$$.

Time complexity: $$$O(1)$$$. Space complexity: $$$O(1)$$$

n,S = map(int, input().split())
	
print((S + n - 1) //  n) 

The problem involves removing adjacent 01 or 10 pairs from a binary string until no more moves are possible. The goal is to find the minimum possible remaining length of the string.

Stack-Based Solution: Traverse the binary string while maintaining a stack. If the stack is non-empty and the current character forms a removable pair (01 or 10) with the top of the stack, pop the stack. Otherwise, push the current character onto the stack. The size of the stack at the end represents the minimum remaining length.

n = int(input().strip())
s = input().strip()
stack = []
for char in s:
    if stack and stack[-1] != char:
        stack.pop()  # Remove 01 or 10 pair
    else:
        stack.append(char)  # Push character if no pair found
print(len(stack))

We need the deque data structure to solve this problem. We iterate the given permutation starting from the first element and we append to the left of our deque either if it is empty or the element at the 0-th index of our deque is larger than the current element we are about to add to our deque. Otherwise we append to the end of our deque because appending a larger number than what we currently have at the 0-th index of our deque will definitly make our final answer lexicographically larger.

from collections import deque

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))

    ans = deque()
    for num in arr:
        if ans and num < ans[0]:
            ans.appendleft(num)
        else:
            ans.append(num)
    
    print(*ans)

• Think of a queue (FIFO structure) to store the most recent k unique chats.
• Use a set to quickly check if a friend's chat is already on the screen.

When a new chat arrives and the screen is full, remove the oldest chat before adding the new one.

The problem requires maintaining the most recent k unique chat messages in order.
Key observations:
1. If a friend sends multiple messages, only the first occurrence matters.
2. If the chat screen is full (k elements), the oldest message is removed when a new unique message arrives.

Approach:

• Use a deque (chat_screen) to store recent unique chats while maintaining order.
• Use a set (seen) to track which friends are currently displayed.
• Process each message:
• If it's already in seen, ignore it.
• Otherwise:
  • If chat_screen is full, remove the oldest chat (last element).
  • Add the new chat to the front of chat_screen and update seen.
• Print the final chat list.

This method ensures an O(n) time complexity, which is efficient for large inputs.

from collections import deque

def chat_screen(n, k, messages):
    chat_screen = deque()
    seen = set()

    for id_i in messages:
        if id_i not in seen:
            if len(chat_screen) == k:
                removed = chat_screen.pop()
                seen.remove(removed)
            
            chat_screen.appendleft(id_i)
            seen.add(id_i)

    print(len(chat_screen))
    print(*chat_screen)

n, k = map(int, input().split())
messages = list(map(int, input().split()))
chat_screen(n, k, messages)

• Think of maintaining two lists to track subsequences ending in 0 and 1.
• A greedy approach helps in assigning characters to subsequences optimally.

• If a 1 appears, assign it to a subsequence that previously ended in 0.
• If a 0 appears, assign it to a subsequence that previously ended in 1.

The problem requires dividing the binary string into the minimum number of subsequences such that each follows an alternating 0-1 or 1-0 pattern.

1. Each character belongs to exactly one subsequence.
2. If a 1 appears, it should ideally continue a subsequence ending in 0, and vice versa.
3. We can efficiently track and assign subsequences using two lists:

• zero → Stores subsequences ending in 0.
• one → Stores subsequences ending in 1.

• Iterate through the binary string:

• If 1 is encountered:
  • Assign it to a subsequence from zero (if available).
  • Otherwise, create a new subsequence.
• If 0 is encountered:
  • Assign it to a subsequence from one (if available).
  • Otherwise, create a new subsequence.
• The maximum number used in our subsequences is the answer.

Complexity:

• Each character is processed once and assigned in O(n) time.
• Given the constraints, this approach is efficient.

import sys 

def solve():
    
    # Read input: length of binary string
    n = int(sys.stdin.readline().strip())
    
    # Convert input string into a list of integers (0s and 1s)
    nums = [int(i) for i in sys.stdin.readline().strip()]

    zero = []   # Tracks subsequences ending in 0
    one = []    # Tracks subsequences ending in 1
    ans = []    # Stores the assigned subsequence number for each character
    maxi = 0    # Keeps track of the total number of subsequences used

    # Process each character in the binary string
    for val in nums:
        if val == 1:  # If the current character is '1'
            if zero:
                # If there exists a subsequence ending in '0', use it
                temp = zero.pop()
            else:
                # Otherwise, create a new subsequence
                maxi += 1
                temp = maxi 
              
            # Mark that this subsequence now ends in '1'
            one.append(temp)
            ans.append(temp)

        else:  # If the current character is '0'
            if one:
                # If there exists a subsequence ending in '1', use it
                temp = one.pop()
            else:
                # Otherwise, create a new subsequence
                maxi += 1
                temp = maxi 

            # Mark that this subsequence now ends in '0'
            zero.append(temp)
            ans.append(temp)

    # Print the total number of subsequences used
    print(max(ans))
    
    # Print the assigned subsequence number for each character
    print(*ans)

q = int(sys.stdin.readline().strip())

for _ in range(q):
    solve()

If we have a list of subarrays where the element at index $$$i$$$ is the max, which subarrays should we check to be sufficient?

Checking subarrays which end or start at index $$$i$$$ is sufficient, so we can optimize our solution with this observation as the basis.

Let's look at the problem from the perspective of each $$$a_i$$$. We want to check whether the sum of the subarrays, where $$$a_i$$$ is the maximum element, exceeds $$$a_i$$$ or not.

Firstly, we must find out in which subarrays is $$$a_i$$$ the maximum. This involves finding the previous greater element index and the next greater element index of $$$i$$$, which can be done for all indices in $$$O(n)$$$ using monotonic stack. Take these indices as $$$x_i$$$, $$$y_i$$$.

Take $$$(j,k)$$$, which represents the sum of a subarray which starts at index $$$j$$$ and ends at index $$$k$$$, where $$$j∈[x_i +1, i]$$$, $$$k∈[i,y_i−1]$$$. If $$$(j,k) \gt a_i$$$, then $$$(j,i−1)+(i,i)+(i+1,k) \gt a_i$$$, giving us $$$(j,i−1)+(i+1,k) \gt 0$$$. Hence, at least one of the subarrays, $$$(j,i−1)$$$ or $$$(i+1,k)$$$ has a sum greater than $$$0$$$, which implies that one of subarrays $$$(j,i)$$$, $$$(i,k)$$$ has sum greater than $$$a_i$$$, so only checking subarrays which start or end at index $$$i$$$ suffices.

To determine whether there exists a subarray where the sum exceeds its maximum value, we utilize a Monotonic Stack to efficiently find the previous greater element indices and Prefix Sums to enable quick subarray sum queries.

For any index $$$i$$$, the monotonic stack ensures that:

While processing $$$a_i$$$ , we pop all elements from the stack that are less than or equal to $$$a_i$$$. This guarantees that for all popped indices, $$$a_i$$$ is the first greater element to their right. For the current popped index $$$v$$$, we check the sum from $$$v$$$ to $$$(i-1)$$$ > $$$0$$$ If true, it implies that some subarray sum exceeds its maximum, violating the required condition. In this case, we immediately return $$$NO$$$ since at least one problematic subarray exists.

$$$Why$$$ $$$This$$$ $$$is$$$ $$$Sufficient?$$$

The monotonic stack guarantees that we only check valid subarrays where the current element is the maximum, ensuring:

No problematic subarray is missed.

Minimal subarray checks, avoiding an exhaustive search.

Since we apply the same check on both the original and reversed array, we ensure correctness across all possible subarrays.

$$$Final$$$ $$$Steps$$$

Process the array from left to right: Use a monotonic stack to track the next greater elements. As elements are popped, check if the suffix sum (from the popped index up to $$$i−1$$$) is greater than 0. If true, print $$$NO$$$ and terminate early. Reverse the array and repeat the process to handle Next greater elements efficiently.

Time Complexity: $$$O(n)$$$

import sys

def solve():
    n = int(sys.stdin.readline().strip())
    nums = list(map(int, sys.stdin.readline().strip().split()))

    def prevGreater(nums):
        stack = []
        pref = [0]
        
        for num in nums:
            pref.append(pref[-1] + num)
    
        for i in range(n):

            while stack and nums[stack[-1]] <= nums[i]:
                v = stack.pop()

                if  pref[i] - pref[v]> 0:
                    return False
                
            stack.append(i)

        return True
    
    if prevGreater(nums) and prevGreater(nums[::-1]):
        return "YES"
    
    return "NO"

t = int(sys.stdin.readline().strip())
for _ in range(t):
    print(solve())

To determine the language of a sentence, you only need to check its last few characters. Since only four possible suffixes exist, a direct string comparison is the simplest and most efficient approach.

The problem provides a straightforward method for identifying the language of a sentence based on its ending. Since the constraints guarantee that each sentence ends with one of the given suffixes, we can simply check the last characters of the string and classify the language accordingly. To implement this, we observe the following rules:

• If a sentence ends with "po", it is Filipino and the last letter is “o”.
• If it ends with "desu" or "masu", it is Japanese and the last letter is “u”.
• If it ends with "mnida", it is Korean and the last letter is “a”

t = int(input())

for _ in range(t):
    string = input()
    if string[-1] == "u":
        print("JAPANESE")
    elif string[-1] == "o":
        print("FILIPINO")
    else:
        print("KOREAN")

Think about sorting both arrays and then mapping the actual temperatures to the correct days while maintaining the given constraints.

The problem requires us to rearrange the given temperatures in array b such that each temperature matches a day in array a while ensuring the absolute difference constraint |a[i] - b[i]| ≤ k holds.

Approach:

1. Pair Each Forecast with its Index:

• Create an array of pairs (a[i], i), where each pair stores the forecast temperature and its corresponding index.

1. Sort Both Arrays:

• Sort the forecasted temperatures (a) based on their values.
• Sort the actual temperatures (b) in ascending order.

1. Assign the Sorted Temperatures:

• Iterate through both sorted arrays and assign each temperature from b to the corresponding position in a based on their sorted order.
• Since b can always be rearranged to satisfy the condition, sorting ensures that the best possible match is made greedily.

1. Restore the Original Order:

• Since we initially sorted a, we need to place the values in b back into their original positions using the stored indices.

Example Walkthrough:

Case 1

Input:
5 2 1 3 5 3 9 2 5 11 2 4 - Original a: [(1,0), (3,1), (5,2), (3,3), (9,4)]
- Sorted a: [(1,0), (3,1), (3,3), (5,2), (9,4)]
- Sorted b: [2, 2, 4, 5, 11]
- Mapping them in order: [2, 2, 4, 5, 11]
- Restoring order: [2, 2, 5, 4, 11]
Output:
2 2 5 4 11

Case 2

Input:
6 1 -1 3 -2 0 -5 -1 -4 0 -1 4 0 0 - Sorted a: [(-5,4), (-2,2), (-1,0), (-1,5), (0,3), (3,1)]
- Sorted b: [-4, -1, 0, 0, 0, 4]
- Mapping: [-4, -1, 0, 0, 0, 4]
- Restoring order: [0, 4, -1, 0, -4, 0]
Output:
0 4 -1 0 -4 0

Complexity Analysis:

• Sorting a and b each takes O(n log n).
• Mapping elements and restoring order takes O(n).
• Thus, the total complexity per test case is O(n log n).
• Given that the sum of n over all test cases is at most 10^5, this is efficient.

t = int(input())
for _ in range(t):
    n, k =  map(int, input().split())
    a =  list(map(int, input().split()))
    b =  list(map(int, input().split()))
    
    # Pair forecast values with indices
    a = [(a[i], i) for i in range(n)]
    
    # Sort both arrays
    a.sort()
    b.sort()
    
    # Rearrange elements in the correct order
    ans = [0] * n
    for i in range(n):
        _, ind = a[i]
        ans[ind] = b[i]
    
    print(*ans)

Instead of checking all possible sub-arrays, think about how you can maintain a valid segment dynamically while iterating through the prisoners.

A brute-force approach would be to check all possible contiguous sub-arrays of size $$$c$$$, leading to an O($$$n$$$ * $$$c$$$) complexity, which is inefficient for large $$$n$$$. Instead, we can solve this efficiently using a two-pointer (sliding window) approach in O($$$n$$$) time:

• Maintain a window of prisoners that satisfies the severity constraint.
• Use a $$$left$$$ pointer to track the start of the valid segment.
• Iterate with pointer $$$right$$$, and whenever a prisoner exceeds $$$t$$$, reset $$$left$$$ to start a new valid window.
• Whenever the current window size is greater or equal to $$$c$$$, it contributes to a valid selection, so we increment our answer by one.

Time Complexity O($$$n$$$)

space complexity O(1)

n, t, c = [int(i) for i in input().split()]
prisoners = [int(i) for i in input().split()]

answer = 0
left = 0
for right in range(n):
    if prisoners[right] > t:
        left = right + 1 
    
    current_length = right - left + 1
    if  current_length >= c:
        answer += 1

print(answer)

Instead of checking every year (which is too slow), focus only on the years when the population actually changes—births and deaths.

Use a line sweep technique: treat birth years as +1 events and death years as -1 events, then process the years in sorted order.

Approach:

We need to find the year with the most people alive at once. Given the huge range of years (**1 to 10⁹**), checking each year individually is impossible.

Instead, we only care about years where a birth or death happens. We can track these changes efficiently using a dictionary:

1. Mark population changes:

• When someone is born at b, increase the count (+1).
• When someone dies at d, decrease the count (-1).
• Store these events in a dictionary.

1. Sort and process events:

• Extract all unique years, sort them, and process them sequentially.
• Maintain a running total of the population at each step.
• Track the maximum population and the earliest year that achieves it.

Why Use a Dictionary Instead of an Array?

A naive approach would be to use an array indexed by years, but since the range of years can go up to 10⁹, this would require an unfeasible amount of memory. Instead, we use a dictionary to store only the relevant years where changes occur, making the approach both memory-efficient and fast.

Why This Works:

By focusing only on important years (births and deaths), we avoid unnecessary calculations and solve the problem efficiently. This is a classic line sweep technique used in event-based problems.

This approach works in O(n log n) time due to sorting, which is efficient for n ≤ 10⁵.

from collections import defaultdict

n = int(input())
events = defaultdict(int)

# Mark birth and death events
for _ in range(n):
    birth, death = map(int, input().split())
    events[birth] += 1
    events[death] -= 1  # Death marks the end of life

# Sort event years
years = sorted(events.keys())

# Sweep through the years
max_people = 0
year = 0
current_population = 0

for y in years:
    current_population += events[y]
    if current_population > max_people:
        max_people = current_population
        year = y  # Pick the smallest year in case of ties

print(year, max_people)

To efficiently determine the temperature for each cell, consider how to propagate the air conditioner temperatures while minimizing unnecessary computations.

The problem requires finding the minimum temperature in each cell, given that each air conditioner contributes its temperature plus the absolute difference from its position. A naive approach would be to iterate over each cell and compute the minimum temperature using all air conditioners, resulting in an O(n * k) complexity, which is inefficient for large values of (n). Instead, we use a more optimized approach with two sweeps (forward and backward) in O(n)time:

• First, initialize an array with infinity and set the temperature at air conditioner positions.
• Perform a left-to-right sweep, propagating the minimum temperature possible at each position.
• Perform a right-to-left sweep to ensure that we get the minimum valid temperature at each position.

t = int(input())
for _ in range(t):
n, k = map(int, input().split()) 
pos = list(map(int, input().split())) temp = list(map(int, input().split()))
all = [float('inf')] * n  
for i in range(k):  
    all[pos[i] - 1] = temp[i]  

forward = [float('inf')] * n  
forward[0] = all[0]  
for i in range(1, n):  
    forward[i] = min(forward[i - 1] + 1, all[i])  

backward = [float('inf')] * n  
backward[-1] = all[-1]  
for i in range(n - 2, -1, -1):  
    backward[i] = min(backward[i + 1] + 1, all[i])  

result = [min(forward[i], backward[i]) for i in range(n)]  
print(*result)  

In this problem, you are given two integer arrays, $$$a$$$ and $$$b$$$, and the task is to maximize the sum of the products of corresponding elements from the two arrays. You are allowed to reverse at most one continuous subarray (subsegment) from the array $$$a$$$ to achieve the maximum possible sum. The challenge is to efficiently determine the best subarray to reverse in order to maximize this sum.

The first step is to calculate the original sum of the dot product between $$$a$$$ and $$$b$$$ without any reversals. This serves as the baseline. Then, we explore how reversing different subarrays of $$$a$$$ impacts the sum. The key observation is that reversing a subarray alters the interactions between elements of $$$a$$$ and $$$b$$$. By considering both odd-length and even-length subarrays centered around different points, we calculate how the reversal changes the sum. For each potential subarray, we compute the difference in the products of the elements before and after the reversal, which is referred to as the delta.

For odd-length subarrays, the reversal will be centered around a single element. The key is to consider each possible center of the subarray and expand outwards symmetrically. For example, if we have a center at index $$$i$$$, the subarray can be expanded outward to include $$$a_{i-1}$$$, $$$a_{i+1}$$$, and so on, forming an odd-length subarray like [ $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$], [$$$a_{i-2}$$$, $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$, $$$a_{i+2}$$$ ], and so on.

When we reverse this subarray, we swap the elements symmetrically, and we want to compute how this reversal changes the sum of the element-wise products. We calculate the difference between the products of $$$a$$$ and $$$b$$$ before and after the reversal. For each odd-length subarray, we check if this reversal gives us a better sum.

For even-length subarrays, the reversal is centered between two adjacent elements. For example, if we have a center between indices $$$i$$$ and $$$i+1$$$, the subarray will start at $$$a_i$$$ and end at $$$a_{i+1}$$$. This forms an even-length subarray that can be expanded symmetrically outwards. The subarrays could look like [ $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$, $$$a_{i+2}$$$ ], [ $$$a_{i-2}$$$, $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$, $$$a_{i+2}$$$, $$$a_{i+3}$$$ ], and so on.

Just like with odd-length subarrays, we reverse the elements of the subarray, compute the change in the sum of the product, and check if this reversal provides a better sum.

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

# Calculate the original sum S.
original_sum = sum(a[i] * b[i] for i in range(n))

best = 0  # Best improvement found by reversing a subarray

# Check odd-length reversals (centered at i)
for center in range(n):
    current_delta = 0
    l, r = center - 1, center + 1
    while l >= 0 and r < n:
        # Calculate the delta added by expanding to include a[l] and a[r]
        current_delta += a[l] * b[r] + a[r] * b[l] - a[l] * b[l] - a[r] * b[r]
        best = max(best, current_delta)
        l -= 1
        r += 1

# Check even-length reversals (center between i and i+1)
for center in range(n - 1):
    current_delta = 0
    l, r = center, center + 1
    while l >= 0 and r < n:
        current_delta += a[l] * b[r] + a[r] * b[l] - a[l] * b[l] - a[r] * b[r]
        best = max(best, current_delta)
        l -= 1
        r += 1

# Output the maximum sum achievable after at most one reversal
print(original_sum + best)

For each student, calculate how much they need to exceed the maximum score of the other two students. If they are already leading, no points are needed.

The required points for a student are the difference between the highest of the other two scores and their own score, plus one (to ensure strict inequality). If already higher, this value is zero.

To solve this problem, we need to determine the minimum additional points each student requires to have a strictly higher score than the other two.

1. For each student, identify the maximum score among the other two students.
2. Calculate the difference between this maximum score and the student's current score. If the student's score is already higher, the difference will be negative, so we take the maximum of zero and this value.
3. Add 1 to ensure the student's new score is strictly greater than the other two. If the student is already leading, no points are needed (result is zero).

This approach ensures each student's required points are computed independently and efficiently in constant time for each test case.

Time Complexity: O(1) per test case, resulting in O(t) overall time for t test cases.

t = int(input())
for _ in range(t):
    a, b, c = map(int, input().split())
    A = max(0, max(b, c) - a + 1)
    B = max(0, max(a, c) - b + 1)
    C = max(0, max(a, b) - c + 1)
    print(A, B, C)

With potentially large input sizes and many queries, recalculating damage for each query by iterating over the subarray would be inefficient. An efficient solution must process queries in constant time. So, think of some form of precomputations on the input array to answer queries efficiently.

Think of damage as a prefix sum

Precompute the total damage in both directions to answer queries in constant time.

Precompute the total damage for moving forward:

• Start at the first building and traverse from left to right.

• Whenever Yohannesll moves downward (i.e. from a taller building to a shorter one), add the damage (the difference in heights) to a cumulative total.

• Store these cumulative damage values so that any range query moving forward can be answered instantly.

Precompute the total damage for moving backward:

• Start at the last building and traverse from right to left.

• Whenever Yohannesll moves downward, add the damage to a cumulative total.

• Store these cumulative damage values for answering queries that move in the opposite direction.

Answer queries efficiently:

• If the query asks about moving forward ($$$a \to b$$$, where $$$a \lt b$$$), retrieve the total damage directly from the left-to-right precomputed values.

• If the query asks about moving backward ($$$a \to b$$$, where $$$a \gt b$$$), retrieve the total damage from the right-to-left precomputed values.

• Since these values are already stored, each query is answered in $$$O(1)$$$ time.

Time Complexity: $$$O(n + m)$$$

Space Complexity: $$$O(n)$$$

n, m = map(int, input().split())
arr = list(map(int, input().split()))
prefix = [0] * n
suffix = [0] * n

# Precompute prefix: cumulative damage when moving to the right
for i in range(1, n):
    # Damage is incurred only if the previous building is taller
    prefix[i] = prefix[i - 1] + max(0, arr[i - 1] - arr[i])
    
# Precompute suffix: cumulative damage when moving to the left
for i in range(n - 2, -1, -1):
    # Damage is incurred only if the next building is taller
    suffix[i] = suffix[i + 1] + max(0, arr[i + 1] - arr[i])
     

for _ in range(m):
    a, b = map(int, input().split())
    
    # If moving right (a to b), use the prefix array
    if b > a:
        print(prefix[b - 1] - prefix[a - 1])
    # If moving left (a to b), use the suffix array
    else:
        print(suffix[b - 1] - suffix[a - 1])

Let's call a prefix legal if it contains an equal number of 0 and 1 symbols. The key observation is that applying operations never changes which prefixes are legal. In fact, suppose we apply an operation to a prefix of length i, and consider a prefix of length j We want to show that if j was legal before, it remains legal. And if it wasn't legal, it won't become legal.

If j < i , then all bits in the length j prefix are inverted. The numbers of 0's and 1's swap, so it cannot change whether they are equal, and hence it cannot change whether j is legal. If j ≥ i, then i/2 of the 0 symbols become 1 and i/2 of the 1 symbols become 0. So the numbers of both symbols do not change, so it cannot change whether j is legal.

Using prefix sums, we can determine for each prefix whether it is legal.

Consider an index i If i = n and an ≠ bn, then we must flip the length n prefix at some point. If i < n and ai = bi, ai + 1 ≠ bi + 1, or ai ≠ bi, ai + 1 = bi + 1, then we must flip the length i prefix at some point. If we flip precisely these prefixes in any order, it will transform a into b. So we should simply check that every prefix that must be flipped is legal.

Complexity is O(n).

import sys

def solve():
    n = int(input())
    A = input()
    B = input()
    
    A += '0'
    B += '0'
    count = 0
    
    for i in range(n):
        # If count == 0, it means we have equal 1s and 0s
        if A[i] == '1':
            count += 1
        else:
            count -= 1
        
        if count != 0:
            if A[i] != B[i] and A[i+1] == B[i+1]:
                print("NO")
                return
            
            elif A[i] == B[i] and A[i+1] != B[i+1]:
                print("NO")
                return
        
        # Alternative way of writing the above condition
        # if ((A[i] == B[i]) != (A[i + 1] == B[i + 1])) and count != 0:
        #     print("NO")
        #     return
    
    print("YES")


t = int(input())
for _ in range(t):
    solve()

Do we really need to check every point in the given range?

Observation: We don’t need to consider all the points in the given range because choosing a point between any two of the given points is never beneficial—moving towards one of the given points will either keep the total distance the same or reduce it.

In this solution, we calculate the total distance for each given point and keep track of the best one. The idea is to compute the total distance efficiently using running sums.

Approach

• Sort the array: Sorting the array helps us easily manage the left and right sides of the current point as we iterate through the points.
• Calculate the distance for each point using running sums and update the answer variable.
  • Use two variables: $$$suml$$$ to store the sum of the points to the left of the current point, and $$$sumr$$$ to store the sum of the points to the right of the current point.
  • For a point $$$p$$$ that is on index $$$i$$$, we can find the total distance as:
    • left side distance = $$$i$$$ * $$$p$$$ — $$$suml$$$
    • right side distance = $$$sumr$$$ — ($$$n$$$ — $$$i$$$) * $$$p$$$
    • total distance = left side distance + right side distance
    where $$$n$$$ is the number of points given.

Time complexity: $$$O(nlogn)$$$

Space complexity: $$$O(1)$$$

n = int(input())
points = [int(i) for i in input().split()]
points.sort()

suml = 0
sumr = sum(points)
min_distance = float("inf")
answer = points[0]

for i, point in enumerate(points):
    left_side_distance = (point * i - suml)
    right_side_distance = sumr - (n - i) *  point
    current_total_distance = left_side_distance + right_side_distance
    if min_distance > current_total_distance:
        min_distance = current_total_distance
        answer = point

    suml += point
    sumr -= point

print(answer)

The absolute difference only depends on the relative position of numbers, so the first step is to sort the given points. Once sorted, we can analyze which position gives the smallest total distance.

Let’s assume we pick some $$$x$$$ as our answer and check if moving it left or right changes the total distance.

case 1: Suppose $$$x$$$ is currently at some position, and we move it leftward (decreasing $$$x$$$). This reduces the distance to all points on the left but increases the distance to all points on the right. Since there are generally more points on one side than the other, this movement results in a net increase in the total sum of distances.

case 2: If we move $$$x$$$ rightward (increasing $$$x$$$), the distances to all right-side points decrease, but the distances to all left-side points increase. Again, due to the imbalance in the number of points on each side, the total sum of distances increases.

Thus, the best choice is where moving left or right does not improve the total sum of distances—this happens at the middle point (by index) in the sorted list of the given points..

Time complexity: $$$O(nlogn)$$$

Space complexity: $$$O(1)$$$

n = int(input())
points = [int(i) for i in input().split()]
points.sort()

mid_index = (n - 1) // 2
print(points[mid_index])

How can you maintain monsters in a circle while allowing quick insertion and removal?

You can use a linked list to handle the monsters insertion and removal. But, how can you quickly find a monster’s position without searching the entire list?

The problem requires us to keep track of a group of monsters sitting in a circle, each with an ugliness score. Whenever two adjacent monsters have the same ugliness score, they merge into one, keeping the smaller index and doubling the ugliness score. Each newly added monster gets a unique increasing index, and after every insertion and all possible merges, we need to determine how many monsters remain in the table.

To handle this efficiently, we use a circular doubly linked list. Since each monster has a left and right neighbor, a doubly linked list allows easy movement in both directions. The circular part means that the last node's next pointer points to the first node, and the first node's previous pointer points to the last node. This makes it easier to manage the circle without needing extra checks. In addition to this, a dictionary is used to quickly find any monster's node by its index, so we don't have to search through the list every time.

When a new monster is added, it always appears to the right of the monster with the given index. Using the dictionary, we can find that monster's position immediately and insert the new one by updating a few pointers. After insertion, we check if the new monster can merge with the one on its left. If their ugliness scores are the same, they combine into one, with the remaining monster keeping the smaller index and doubling its ugliness score. This process repeats with the new left neighbor until no more merges are possible. After that, we check the right neighbor and continue merging in the same way. The merging keeps happening as long as there are adjacent monsters with the same ugliness score.

For time complexity, at the beginning, there is just one monster, and then we have $$$n$$$ insertions. Each insertion involves finding the right place in the list, which takes $$$O(1)$$$ time using the dictionary. Inserting a new monster also takes $$$O(1)$$$ time since it only involves pointer updates. After an insertion, we need to check for possible merges. In the worst case, each insertion may trigger up to $$$O(n)$$$ merges. However, since each adjacent monster pair can merge at most once, the total number of merges across all $$$n$$$ insertions will not exceed $$$n$$$. This means the overall time complexity for processing all insertions and merges is $$$O(n)$$$.

For space complexity, we need to store each monster as a node in the linked list, which takes $$$O(n)$$$ space. The dictionary also holds a reference to each monster, adding another $$$O(n)$$$ space. Since both structures grow at the same rate as the number of monsters, the overall space complexity is $$$O(n)$$$.

class ListNode:
    def __init__(self, index, ugliness):
        # Initialize a new monster node with an index and ugliness score.
        self.index = index
        self.ugliness = ugliness
        self.next = None
        self.prev = None


def merge_monsters(node, monster_map, count):
    # Try to merge the node with its adjacent neighbors (left and right) as long as they have the same ugliness score.
    while True:
        merged = False

        # Merge with the left neighbor if they have the same ugliness
        if node.prev != node and node.ugliness == node.prev.ugliness:
            left = node.prev
            if node.index > left.index:
                # Adjust the pointers to remove 'node' and merge with the left neighbor
                left.next = node.next
                node.next.prev = left
                left.ugliness *= 2
                count[0] -= 1  # Decrease the count of monsters after merging
                node = left  # Move 'node' to 'left' as it is now the active node
            else:
                # Adjust the pointers to remove 'left' and merge with 'node'
                node.prev = left.prev
                left.prev.next = node
                node.ugliness *= 2
                count[0] -= 1  # Decrease the count of monsters after merging
            merged = True

        # Merge with the right neighbor if they have the same ugliness
        elif node.next != node and node.ugliness == node.next.ugliness:
            right = node.next
            if node.index > right.index:
                # Adjust the pointers to remove 'node' and merge with the right neighbor
                node.prev.next = right
                right.prev = node.prev
                right.ugliness *= 2
                count[0] -= 1  # Decrease the count of monsters after merging
                node = right  # Move 'node' to 'right' as it is now the active node
            else:
                # Adjust the pointers to remove 'right' and merge with 'node'
                right.next.prev = node
                node.next = right.next
                node.ugliness *= 2
                count[0] -= 1  # Decrease the count of monsters after merging
            merged = True

        # Exit the loop if no merges happened
        if not merged:
            break


def solve():
    # Solve the problem for a single test case
    num_insertions, initial_ugliness = map(int, input().split())

    # Count is an array of 1 value because it is passed to the merge
    # function and we need to modify the value in that function
    count = [1]  # Initialize count to 1 since we have 1 monster initially

    head = ListNode(1, initial_ugliness)
    head.next = head  # Make the list circular by linking the head to itself
    head.prev = head
    monster_map = {1: head}  # Map to track the monsters by their index

    indices = list(map(int, input().split()))
    ugliness_values = list(map(int, input().split()))
    next_index = 2  # Start from the next available index for the new monsters
    results = []

    for i in range(num_insertions):
        monster_index, ugliness_score = indices[i], ugliness_values[i]
        monster = monster_map[monster_index]

        # Create and insert the new monster into the linked list
        new_monster = ListNode(next_index, ugliness_score)
        next_index += 1

        # Adjust the pointers to add the new monster
        new_monster.next = monster.next
        new_monster.prev = monster
        monster.next.prev = new_monster
        monster.next = new_monster

        monster_map[new_monster.index] = new_monster  # Add the new monster to the map
        count[0] += 1  # Increase the count after adding a new monster

        # Perform merges after insertion
        merge_monsters(new_monster, monster_map, count)

        # Store the current number of monsters after the insertion and merges
        results.append(count[0])

    print(*results)


t = int(input())
for _ in range(t):
    solve()

Problem Overview:

The problem involves identifying which song is playing at specific moments during a playlist where each song repeats a defined number of times. The playlist plays sequentially, with song $$$i$$$ playing $$$c_i$$$ times and each play lasting $$$t_i$$$ minutes. Given moments $$$v_i$$$, we need to determine which song is playing at each of those times.

Approach:

Prefix Sum Array: The key idea is to build a prefix sum array where prefix[i] represents the cumulative total duration of songs from the start to the end of song $$$i$$$. If $$$c_i$$$ is the repetition count and $$$t_i$$$ is the duration of song $$$i$$$, then the contribution of song $$$i$$$ to the prefix sum is $$$c_i \times t_i$$$. The prefix sum allows us to efficiently check which song is playing at any given moment by comparing the $$$v_i$$$ values against cumulative durations.

Linear Search: For each moment $$$v_i$$$, iterate through the prefix sum array until you find the first $$$i$$$ where prefix[i] >= vi.

Time Complexity:

• Prefix Sum Construction: $$$O(n)$$$
• Query Handling: $$$O(m)$$$ using linear search
• Overall: $$$O(n + m)$$$
• Space Complexity: $$$O(n)$$$ for storing the prefix sum array.

 n, m = map(int, input().split())
    prefix = []
    for i in range(n):
        c, t = map(int, input().split())
        prefix.append(c * t)
        if i > 0:
            prefix[i] += prefix[i - 1]
    moments = list(map(int, input().split()))
    i = 0
    for j in range(m):
        while prefix[i] < moments[j]:
            i += 1
        print(i + 1)

To efficiently calculate the average sleep time, consider how to sum values over sliding windows without recalculating the entire sum for each new window.

The problem requires calculating the average sleep time over all possible weeks in Polycarp's records. A naive approach would involve iterating through each possible starting index and summing up the next k elements. However, this results in an O(n × k) complexity, which is inefficient for large values of n. Instead, we can use the sliding window technique to efficiently compute the sum for each week in O(n) time:

• First, compute the sum of the first k days and store it as the current sum.
• Iterate from day k to day n, updating the sum by adding the new day's sleep time and removing the sleep time of the day that is no longer in the window.
• Keep a running total of these weekly sums and compute the final average.

n, k = map(int, input().split()) 
a = list(map(int, input().split()))
curr = sum(a[:k])
total = curr
for i in range(k, n):
    curr += a[i] - a[i - k]
    total += curr

print(total / (n - k + 1))

It's easy to see that letter $$$z$$$ appears only in "zero" and $$$n$$$ appears only in "one", so we should print $$$1$$$ $$$\text{count}(n)$$$ times and then $$$0$$$ $$$\text{count}(z)$$$ times.

n = int(input())  
s = input()  
ones = s.count('n')  
zeros = s.count('z')  
print('1 ' * ones + '0 ' * zeros)

Try to find the maximum number of people who can have at least x burles after redistributing the money among selected subsets of people. The key observation is that the redistribution must be fair among the chosen subset.

The problem requires us to maximize the number of people who have at least x burles after any number of redistribution reforms. The key observation is that any subset of people chosen for redistribution will end up with an equal amount of money per person.

Approach:

1. Sort the savings in descending order: This ensures that we consider the wealthiest individuals first.
2. Iterate through the sorted list and track cumulative wealth: We keep summing the wealth and checking if the average wealth of the first i people is at least x.
3. Break when the condition fails: If at any step the cumulative wealth divided by i + 1 is less than x, the answer is i. Otherwise, the answer is n if we can include all individuals.

Example Walkthrough:

1. Case 1 ([5,1,2,1], x=3):

• Sort: [5,2,1,1]
• Sum stepwise: 5, 5+2=7, 7+1=8, 8+1=9
• The condition fails at index 2, so the answer is 2.

1. Case 2 ([11,9,11,9], x=10):

• Sort: [11,11,9,9]
• Sum stepwise: 11, 22, 31, 40
• The condition holds for all, so the answer is 4.

1. Case 3 ([4,3], x=5):

• Sort: [4,3]
• The sum never reaches 5, so the answer is 0.

1. Case 4 ([9,4,9], x=7):

• Sort: [9,9,4]
• Sum stepwise: 9, 18, 22
• The condition holds for 3, so the answer is 3.

Complexity Analysis:

• Sorting takes O(n log n).
• Iterating through the array takes O(n).
• Thus, the total complexity per test case is O(n log n).
• Since the sum of n across all test cases is at most 10^5, this solution efficiently handles the constraints.

t = int(input())  # Read number of test cases  

for _ in range(t):  
    n, x = map(int, input().split())  # Read n (number of people) and x (wealth threshold)  
    nums = sorted(map(int, input().split()), reverse=True)  # Sort wealth in descending order  
    
    total = 0  # Track cumulative wealth  
    for i in range(n):  
        total += nums[i]  # Add wealth of the i-th person  
        if total < x * (i + 1):  # Check if the average wealth falls below x  
            print(i)  # Maximum number of wealthy people possible  
            break  
    else:  
        print(n)  # If we never break, all n people can be wealthy  

To solve this problem, we need to determine if there exists a TV segment that can be removed without reducing the total covered time. Intuitively, a segment is redundant if every moment it covers is still covered by at least one other segment. Our goal is to efficiently check for such a segment.

Since the given time values can be large (≤ 10^9), storing them directly is inefficient. Instead, we use coordinate compression to map time values into a smaller range (at most 6 × 10^5). We then use a difference array approach: for each segment [li, ri], we increment coverage at li and decrement at ri + 1. Taking prefix sums over this array gives us the number of active TV sets at each moment. From this, we compute pref[i], which stores how many moments up to i are covered by exactly one segment.

Finally, for each segment [l, r], we check if pref[r] - pref[l - 1] is 0. This means that every moment in this range is covered by at least one other segment, making it redundant. If we find such a segment, we print its index; otherwise, we print -1. This approach runs in O(n log n) due to sorting and coordinate compression, making it efficient.

def solve():
    n = int(input())
    segments = []
    coord_set = set()

    # Collecting segments and unique coordinates
    for _ in range(n):
        l, r = map(int , input().split())
        segments.append((l, r + 1))
        coord_set.add(l)
        coord_set.add(r + 1)

    # Coordinate compression
    coord_list = sorted(coord_set)
    coord_map = {v: i for i, v in enumerate(coord_list)}
    m = len(coord_list)

    # Prefix array to track coverage
    coverage = [0] * (m + 1)
    for l, r in segments:
        coverage[coord_map[l]] += 1
        coverage[coord_map[r]] -= 1

    # Compute prefix sums for coverage
    for i in range(1, m):
        coverage[i] += coverage[i - 1]

    # Compute `pref` array, which stores the count of moments covered exactly once
    pref = [0] * m
    for i in range(1, m):
        pref[i] = pref[i - 1] + (1 if coverage[i - 1] == 1 else 0)

    # Find redundant segment
    for i, (l, r) in enumerate(segments):
        if pref[coord_map[r]] - pref[coord_map[l]] == 0:
            print(i + 1)
            return

    print(-1)

solve()

• What would you do if the constraints for the coordinates were up to (10^5)?

• You could use the line sweep algorithm, but the coordinates go up to (10^9). So, what shall we do?

• What if you use a dictionary instead of an array to store only the relevant positions?

We perform a line sweep using a dictionary to record events at positions where the number of covering segments changes. Sorting the dictionary keys lets us compute the prefix sum between these "critical" points. For each interval ([prev, cur)), the number of integer points is ((cur — prev)) and they are all covered by the current number of segments. This way, we aggregate the answer for every (k) in ([1, n]) without iterating over every integer in a huge range.

import sys
from collections import defaultdict

n = int(sys.stdin.readline().strip())
events = defaultdict(int)

# Record events: +1 when a segment starts, -1 when it ends (at r+1)
for _ in range(n):
    l, r = map(int, sys.stdin.readline().split())
    events[l] += 1
    events[r + 1] -= 1

# Sort the event points
keys = sorted(events.keys())
coverage = 0
prev = keys[0]
result = defaultdict(int)

# Line sweep: update coverage and count points in intervals
for point in keys:
    result[coverage] += point - prev
    coverage += events[point]
    prev = point

# Output counts for points covered by exactly 1 to n segments
ans = [result[k] for k in range(1, n + 1)]
print(*ans)
    

Let's consider a very special case of equal distances. What if all distances were equal to $$$1$$$? It implies that if some letter appears exactly twice, both occurrences are placed right next to each other.

That construction can be achieved if you sort the string, for example: first right down all letters '$$$a$$$', then all letters '$$$b$$$' and so on. If a letter appears multiple times, all its occurrences will be next to each other, just as we wanted.

Overall complexity: $$$O(|s|log|s|)$$$ or $$$O(|s|)$$$ per testcase.

for _ in range(int(input())):
  print(''.join(sorted(input())))

This is a 2D prefix sum problem.

Do the 2D prefix sum for the horizontal and vertical arrangements separately.

h, w = map(int, input().split())

grid = []
for i in range(h):
    grid.append(input())


horizontal = [[0] * w for _ in range(h)]
vertical = [[0] * w for _ in range(h)]

# indicate valid arrangements by 1 and invalid arrangements by 0.
# horizontal[r][c] == 1 means we can place a domino horizontally from grid[r][c - 1] to grid[r][c]
# vertical[r][c] == 1 means we can place a domino vertically from grid[r - 1][c] to grid[r][c]
for r in range(h):
    for c in range(w):

        if c > 0 and grid[r][c] == grid[r][c - 1] == '.':
            horizontal[r][c] = 1

        if r > 0 and grid[r][c] == grid[r - 1][c] == '.':
            vertical[r][c] = 1


# perform row-wise prefix sums
for r in range(h):
    for c in range(1, w):
        horizontal[r][c] += horizontal[r][c - 1]
        vertical[r][c] += vertical[r][c - 1]

# perform column-wise prefix sums
for c in range(w):
    for r in range(1, h):
        horizontal[r][c] += horizontal[r - 1][c]
        vertical[r][c] += vertical[r - 1][c]


q = int(input())

for i in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    r1, c1, r2, c2 = r1 - 1, c1 - 1, r2 - 1, c2 - 1 # changing 1-indexed input to 0-indexed

    horizontal_count = horizontal[r2][c2] - horizontal[r2][c1]
    if r1 - 1 >= 0:
        horizontal_count += horizontal[r1 - 1][c1] - horizontal[r1 - 1][c2]
    
    vertical_count = vertical[r2][c2] - vertical[r1][c2]
    if c1 - 1 >= 0:
        vertical_count += vertical[r1][c1 - 1] - vertical[r2][c1 - 1]
    
    answer = horizontal_count + vertical_count

    print(answer)

We have an array ( a ) of length ( n ) and must answer ( q ) queries. Each query modifies all elements in a given range ( [l, r] ) by setting them to ( k ) and asks whether the sum of the updated array is odd.

Each query is independent, meaning changes do not persist for subsequent queries.

Observe that changing a subarray to a fixed value (k) affects the total sum in a predictable way. The effect on the total sum can be computed by removing the sum of the existing subarray and adding the contribution of the new values.

How can prefix sum help us here?

1. Compute the initial sum of the array.
2. Compute the prefix sum for quick range sum retrieval.
3. For each query:
   • Compute the sum of the range ( [l, r] ).
   • Replace it with ( (r — l + 1) \times k ).
   • Check if the new sum is odd.
   • Print "YES" if odd, else "NO".

t = int(input())
    
for _ in range(t):
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + a[i]
    
    total_sum = prefix[-1]
    results = []
    for _ in range(q):
        l, r, k = map(int, input().split())
        replaced_range_old_sum = prefix[r] - prefix[l - 1]
        replaced_range_new_sum = (r - l + 1) * k
        new_sum = total_sum - replaced_range_old_sum + replaced_range_new_sum
        
        if new_sum % 2 == 1:
            results.append("YES")
        else:
            results.append("NO")

    print("\n".join(results) + "\n")

• Computing the total sum: ( O(n) )
• Computing the prefix sum: ( O(n) )
• Each query: ( O(1) ) (using prefix sum)
• Total complexity: ( O(n + q) ) per test case, which is optimal given constraints.