• We are given a set $$$S = {l, l+1, \dots, r}$$$ and a positive integer $$$k$$$.
• We can repeatedly perform the operation:

1. Pick $$$x \in S$$$ such that there are at least $$$k$$$ multiples of $$$x$$$ in $$$S$$$.
2. Remove $$$x$$$ from $$$S$$$.

• The goal is to determine the maximum number of operations that can be performed.

Key Observation

1. Greedy removal from small to large:

   • Once a number $$$x$$$ is removed, it cannot interfere with the removability of larger numbers.
   • If $$$x \lt y$$$, then $$$x$$$ is never a multiple of $$$y$$$. Therefore, it is safe to consider numbers in increasing order.

2. Condition for removability:

   • A number $$$x$$$ can be removed if there are at least $$$k$$$ multiples of $$$x$$$ in $$$S$$$.
   • This can be simplified to the inequality:
     • $$$k \cdot x \le r \quad \implies \quad x \le \left\lfloor \frac{r}{k} \right\rfloor$$$
   • All numbers $$$x$$$ in the range $$$[l, \lfloor r/k \rfloor]$$$ can be removed. Numbers larger than this bound cannot satisfy the multiplicity requirement.

Approach 1: Constant-Time Computation

• Compute the largest removable number:

  • $$$x_{\max} = \left\lfloor \frac{r}{k} \right\rfloor$$$

• Count all removable numbers:

  • $$$\text{max_operations} = \max(x_{\max} - l + 1, 0)$$$

• If $$$x_{\max} \lt l$$$, no numbers can be removed, resulting in 0 operations.

• Time complexity: $$$O(1)$$$ per test case, since it only requires basic arithmetic.

Approach 2: Binary Search

• Search space: all numbers $$$x \in [l, r]$$$.
• Condition check: for a candidate $$$x$$$, it is removable if:
  • $$$k \cdot x \le r$$$

• Binary search procedure:

  • Perform a binary search to find the largest number $$$x_{\max}$$$ that satisfies the condition.
  • The number of operations is then:

• Time complexity:
  • Binary search requires $$$O(\log(r-l+1))$$$ operations per test case.
  • Efficient for very large ranges of $$$l$$$ and $$$r$$$ where direct arithmetic might be less intuitive or when additional constraints are present.

Summary

• Constant-Time Approach:

  • Directly compute $$$\lfloor r/k \rfloor$$$ and count numbers from $$$l$$$ to this bound.
  • Extremely fast and straightforward.

• Binary Search Approach:

  • Use when the condition may be more complex or when reasoning about the largest removable number iteratively is required.
  • More flexible and generalizable, though slightly slower than the constant-time formula.

Both approaches rely on the key insight: removing numbers from smallest to largest ensures previously removed numbers do not affect future choices, and the removability condition can be reduced to $$$x \le \lfloor r/k \rfloor$$$.

def solve(l, r, k):
    x_max = r // k         
    return max(x_max - l + 1, 0)

test = int(input())

for _ in range(test):
    l, r, k = map(int, input().split())
    print(solve(l, r, k))

def solve(l, r, k):
    low, high = l, r
    x_max = 0
    
    while low <= high:
        mid = (low + high) // 2
        if mid * k <= r:
            x_max = mid       
            low = mid + 1     
        else:
            high = mid - 1    
    return max(x_max - l + 1, 0)



test = int(input())

for _ in range(test):
    l, r, k = map(int, input().split())
    print(solve(l, r, k))

Key Insight

• Treat consecutive Es as groups of equal numbers.
• Each group can be assigned a single number because all elements in that group are equal.
• The Ns separate these groups.

Analysis of Ns

Let $$$c_N$$$ be the number of Ns in the string $$$s$$$.

• No N ($$$c_N = 0$$$):

  • All elements are in a single E group.
  • We can assign all elements the same value.
  • Possible.

• Exactly one N ($$$c_N = 1$$$):

  • Only one pair of neighbors must differ.
  • But since all other elements are connected by Es, they must be equal to each other.
  • This creates a contradiction: that single N requires two different numbers, but the rest are all equal.
  • Not possible.

• More than one N ($$$c_N \ge 2$$$):

  • The Ns divide the circle into multiple groups.
  • Alternate groups can be assigned different numbers to satisfy all Ns.
  • Possible.

Conclusion

• An array $$$a$$$ exists if and only if the number of Ns is not equal to 1:

• This gives a very simple solution:
  • Count the number of Ns in $$$s$$$.
  • If it’s 1 → print NO.
  • Otherwise → print YES.

Complexity

• Only needs counting Ns → $$$O(n)$$$ per test case.
• No need to assign actual values to array elements.

def solve(s):
    
    n_count = 0
    
    for char in s:
        if char == "N":
            n_count += 1
            
    
    if n_count == 1:
        return "NO"
    else:
        return "YES"

test = int(input())

for _ in range(test):
    s = input()
    print(solve(s))
    

Idea

We can solve the problem using Union-Find (Disjoint Set Union, DSU).

• Treat each index $$$i$$$ of the array as a node in a DSU.
• For every equality constraint $$$s_i = E$$$:
  • $$$a_i = a_{i+1}$$$
  • Union nodes $$$i$$$ and $$$i+1$$$.
• After processing all Es, connected components represent numbers that must be equal.
• For every inequality constraint $$$s_i = N$$$:
  • $$$a_i \neq a_{i+1}$$$
  • Check if $$$i$$$ and $$$i+1$$$ belong to the same component:
    • If yes → contradiction → impossible.
    • If no → constraint is satisfied.
• If all constraints are satisfied → array exists.

Advantages

• Handles generalized equality/inequality constraints.
• Tracks multiple equality groups dynamically.

Disadvantages

• Overkill for small $$$n$$$ and simple constraints.

• Simpler approach: just count the number of Ns:

  • If count_N == 1 → NO
  • Else → YES

Conclusion

• Union-Find can solve it.
• Counting Ns is faster and simpler.
• Use DSU if the problem has more complex or dynamic equality/inequality relations.

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
 
    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return self.par[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1
 

test = int(input())
for _ in range(test):
    s = input()
    n = len(s)
    union_find = UnionFind(n)
    
    for i in range(n):
        if s[i] == 'E':
            union_find.union(i, (i+1)%n)
    
    is_possible = True
    for i in range(n):
        if s[i] == 'N':
            if union_find.find(i) == union_find.find((i+1)%n):
                is_possible = False
                break
                
    print("YES" if is_possible else "NO")

• There are $$$n$$$ kids, each initially with a unique book.
• Each day, kid $$$i$$$ gives their book to kid $$$p[i]$$$.
• Goal: Determine for each kid the number of days until their book returns to them.

Key Observation

• The permutation $$$p$$$ forms disjoint cycles.
• A kid's book will return to them exactly after the length of the cycle containing that kid.

Union-Find Approach

Idea

• Treat each kid as a node in a graph.
• The relationship "kid $$$i$$$ gives book to kid $$$p[i]$$$" forms an edge.
• Each connected component (cycle) can be represented using Union-Find.

Steps

• Initialization:

  • Each kid is their own parent.
  • Maintain a size array to track the size of each cycle.

• Union Operation:

  • For each kid $$$i$$$, union $$$i$$$ with $$$p[i]$$$.
  • After all unions, each cycle corresponds to a connected component in the Union-Find structure.

• Cycle Size Calculation:

  • For each kid $$$i$$$, the size of the component containing $$$i$$$ gives the number of days for the book to return.
  • Use the find operation to get the root of $$$i$$$ and then look up its cycle size.

Summary

• Each book follows a fixed cycle determined by the permutation.
• Union-Find efficiently groups kids into cycles.
• The answer for each kid is simply the size of their cycle.
• This method works in nearly linear time, $$$O(n)$$$, using path compression for Union-Find.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
            x= self.parent[x]
        return self.parent[x]
    #  union by size
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            if self.size[px] < self.size[py]:
                px, py = py, px
            self.parent[py] = px
            self.size[px] += self.size[py]

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

    union_find = UnionFind(n)

    
    for i in range(n):
        union_find.union(i, arr[i] - 1)

    
    ans = []
    
    for node in range(n):
        root = union_find.find(node)
        ans.append(union_find.size[root])
    print(*ans)

We have:

• $$$n$$$ citizens with initial money $$$a_1, a_2, \dots, a_n$$$.
• $$$q$$$ events, each either:

1. 1 p x → citizen $$$p$$$ sets their balance to $$$x$$$ (receipt update)
2. 2 x → government payout: all citizens with balance less than $$$x$$$ are raised to $$$x$$$.

We need to compute the final balance for each citizen after all events.

Key Observations

• Only the last receipt matters for each citizen:

  • Suppose a citizen has multiple type 1 events: 1 p x1, 1 p x2, 1 p x3
  • Only the last one (x3) matters, because it overwrites all previous updates.
  • Why it works: Any earlier update is irrelevant; the citizen’s balance will be overwritten by the last receipt before any final government payouts.

• Government payouts act as a lower bound:

  • Any type 2 event with value $$$x$$$ raises all citizens with less than $$$x$$$.
  • Therefore, for each citizen, the final balance is:

• Why it works: The government payout can never reduce a citizen’s balance; it only enforces a minimum. So the final balance is constrained by the latest explicit receipt and the largest subsequent minimum imposed by type 2 events.

Step-by-Step Explanation

Step 1: Track the last type 1 query for each citizen

• Create an array last_type1 of size $$$n$$$.

• For every query 1 p x, set:

  • $$$\text{last_type1}[p] = x$$$
• After processing all type 1 queries, last_type1[i] holds the latest explicit balance for citizen $$$i$$$.

Why this works: By keeping only the last receipt, we simplify calculations, ignoring intermediate receipts that will be overwritten.

Step 2: Track maximum type 2 queries for suffixes

• Government payouts can happen after a citizen’s last receipt update.
• Create an array max_suffix_type2 of size $$$q$$$.
• Traverse the queries backwards (from last to first) and compute:
  • $$$\text{max_suffix_type2}[i] = \max(\text{max_suffix_type2}[i+1], x)$$$ if query $$$i$$$ is type 2
• This ensures that for any query, we know the largest government payout that comes after it.

Why this works: Since only the largest type 2 after a citizen’s last receipt can affect their final balance, computing suffix maximums efficiently tracks these minimum constraints.

Step 3: Compute final balances

• For each citizen $$$i$$$, the final balance is:
  • $$$\text{final_balance}[i] = \max(\text{last_type1}[i], \text{maximum type 2 after last type 1 for this citizen})$$$
• If a citizen never had a type 1 query, use their initial balance as last_type1[i].

Why this works: Each citizen’s balance is the greater of the last explicit receipt and the largest government-enforced minimum after that receipt. This guarantees correctness without processing every citizen at each type 2 event.

Step 4: Complexity

• Time complexity: $$$O(n + q)$$$

  • Tracking last type 1 queries → $$$O(q)$$$
  • Computing suffix maximums of type 2 → $$$O(q)$$$
  • Computing final balances → $$$O(n)$$$

• Space complexity: $$$O(n + q)$$$

  • last_type1 array → $$$O(n)$$$
  • max_suffix_type2 array → $$$O(q)$$$

Intuition Recap

1. Receipt updates overwrite previous values, so we only care about the last one per citizen.
2. Government payouts provide a lower bound, only affecting citizens with balances below the payout.
3. By combining these two:

we get the correct final balance in linear time, avoiding repeated updates for every citizen.

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

queries = []
for _ in range(q):
    curr_query = list(map(int, input().split()))
    queries.append(curr_query)

last_type1 = arr[:]  

max_type2_suffix = [0 for _ in range(q)]
max_val = 0

for i in range(q - 1, -1, -1):
    
    if queries[i][0] == 2:
        
        x = queries[i][1]
        
        max_val = max(max_val, x)
        
    max_type2_suffix[i] = max_val


last_type1_idx = [-1 for _ in range(n)]
for idx, query in enumerate(queries):
    if query[0] == 1:
        p = query[1] - 1  
        x = query[2]
        last_type1[p] = x
        last_type1_idx[p] = idx


ans = [0 for _ in range(n)]
for i in range(n):
    idx = last_type1_idx[i]

    max_type2_after = max_type2_suffix[idx + 1] if idx + 1 < q else 0
    ans[i] = max(last_type1[i], max_type2_after)


print(*ans)

We want, for each tree position $$$i$$$, the maximum height that the rabbit can reach if it starts at tree $$$i$$$.

The key observation is that the rabbit’s jumping rules naturally group indices into connected components:

• If $$$i$$$ can jump to $$$j$$$, then $$$i$$$ and $$$j$$$ must be in the same component.
• Within a component, the rabbit can eventually reach the maximum height of that component.

Thus, the task reduces to: 1. Group indices into components. 2. Assign to each index the maximum height of its component.

We achieve this with Disjoint Set Union (DSU) and a monotonic stack.

Step 1. Why DSU?

• Each index belongs to exactly one connected component.
• If $$$i$$$ and $$$j$$$ are connected via the jumping rules, we merge them into the same component.
• DSU (Union-Find) is perfect for maintaining and merging such groups dynamically.

At the end, every component will have its maximum height, and each index will map to that value.

Step 2. Using a Monotonic Stack

We process the array from left to right, keeping a monotonic increasing stack (heights stored in increasing order).

At index $$$i$$$ with value $$$a[i]$$$:

• While the top of the stack has value greater than $$$a[i]$$$:
  • Pop the stack element $$$j$$$.
  • Merge $$$j$$$ and $$$i$$$ with DSU, since the forward jump rule is satisfied:

• During this popping, we keep track of the index $$$x$$$ with the maximum value inside the group.
• After processing, we push $$$x$$$ back onto the stack, ensuring the stack always represents the current group’s maximum.

This way, the stack efficiently determines which indices should be united.

Step 3. Building Components

As we iterate:

• Every time we pop from the stack, we union the popped index with the current index.
• After merging, the stack top always points to the representative index holding the largest value in the current component.

By the end of the pass:

• All reachable indices are united into components.
• Each component is correctly represented in DSU.

Step 4. Computing Maximum Heights

After building the DSU:

1. For each root in the DSU, compute the maximum $$$a[i]$$$ in that component.
2. For each index $$$i$$$, set:

Complexity Analysis

• Time Complexity:

  • Each index is pushed/popped from the stack at most once → $$$O(n)$$$.
  • Each DSU find/union is $$$O(\alpha(n))$$$ (inverse Ackermann function, practically constant).
  • Total: $$$O(n)$$$.

• Space Complexity:

  • DSU arrays + stack + result array → $$$O(n)$$$.

Intuition Recap

• The monotonic stack enforces the rabbit’s forward-jump condition (smaller height to the right).
• The DSU groups indices into connected components as jumps are discovered.
• The maximum of each component gives the rabbit’s maximum reachable height.
• Finally, each index outputs the maximum of its component.

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

def solve(arr):
    n = len(arr)

    union_find = UnionFind(n)

    stack = []

    for index in range(n):
        last = stack[-1] if stack else index
        while stack and arr[stack[-1]] > arr[index]:
            union_find.union(stack.pop(), index)
        if arr[last] > arr[index]:
            stack.append(last)
        else:
            stack.append(index)
            
    stack = []
  
    for index in range(n -1, -1, -1):
        last = stack[-1] if stack else index
        while stack and arr[stack[-1]] < arr[index]:
            union_find.union(stack.pop(), index)
        if arr[last] < arr[index]:
            stack.append(last)
        else:
            stack.append(index)
    #  For Every Componet Representative make the max value as there value
    INF = 10**18
    comp_max = [-INF for _ in range(n)]
    for node in range(n):
        root = union_find.find(node)
        comp_max[root] = max(arr[node], comp_max[root])
    ans = [ 0 for _ in range(n)]
    for node in range(n):
        root = union_find.find(node)
        ans[node] = comp_max[root]
    return ans

test  = int(input())


for _ in range(test):
    n = int(input())
    
    arr = list(map(int, input().split()))
    
    ans = solve(arr)
    print(*ans)

        

For each starting index $$$i$$$ $$$(0 \leq i \lt n)$$$, determine the maximum tree height that the rabbit can eventually reach if it begins its sequence of jumps at tree $$$a[i]$$$.

What does "maximum reachable height" mean?

• The rabbit can jump backward only to a taller tree:

• The rabbit can jump forward only to a shorter tree:

• Thus, starting at $$$a[i]$$$, the rabbit may follow a chain of jumps:

and among all reachable positions, we want the tallest tree:

This is not a purely local property. jumps may allow the rabbit to step down on the right and then reach much taller trees on the left, so we need a global way to propagate reachability.

Step 1. Build Prefix Maximums

We compute:

• $$$\text{pref}[i]$$$ stores the tallest tree up to index $$$i$$$.
• Intuition: if the rabbit is at $$$i$$$, it may eventually reach some taller tree on the left. $$$\text{pref}[i]$$$ records that possibility.

Step 2. Build Suffix Minimums

We compute:

• $$$\text{suff}[i]$$$ stores the shortest tree from $$$i$$$ to the end.
• Intuition: since the rabbit can only jump forward to smaller trees, $$$\text{suff}[i]$$$ tells us how far it can step down on the right side.

Step 3. Propagation of Reachability

Now we compute the final answer array $$$\text{ans}$$$.

1. Start at the last index:

• $$$\text{ans}[n-1] = \text{pref}[n-1]$$$(At the very end, the maximum reachable is just the tallest tree so far.)

1. Move backward from $$$i = n-2$$$ down to $$$0$$$:

• Case 1: If $$$\text{pref}[i] \gt \text{suff}[i+1]$$$

  • There is a taller tree on the left of $$$i$$$.
  • There is a smaller tree to the right of $$$i$$$.
  • This means the rabbit at $$$i$$$ can chain through the right side and eventually reach the same maximum as starting at $$$i+1$$$.
  • So we set: $$$\text{ans}[i] = \text{ans}[i+1]$$$

• Case 2: Otherwise, the chain does not extend through the right side.
  The best reachable height is just the tallest seen up to $$$i$$$:

Step 4. Final Result

• After finishing the backward pass, every index $$$i$$$ has been assigned the maximum tree height the rabbit can reach starting at $$$a[i]$$$.

• This works because:

  • $$$\text{pref}[i]$$$ ensures backward jumps are respected,
  • $$$\text{suff}[i]$$$ ensures forward “step-downs” are considered,
  • and the backward propagation of $$$\text{ans}$$$ connects reachable chains together.

Complexity Analysis

• Time:

  • Prefix array: $$$O(n)$$$
  • Suffix array: $$$O(n)$$$
  • Backward pass: $$$O(n)$$$
  • Total: $$$O(n)$$$ per test case

• Space:

  • Arrays $$$\text{pref}$$$, $$$\text{suff}$$$, $$$\text{ans}$$$ → $$$O(n)$$$

Intuition Recap

• $$$\text{pref}[i] =$$$ tallest tree so far (handles backward jumps)
• $$$\text{suff}[i] =$$$ smallest tree to the right (handles forward jumps)
• If $$$\text{pref}[i] \gt \text{suff}[i+1]$$$, then $$$i$$$ connects into the same chain as $$$i+1$$$.
• Otherwise, the maximum reachable is just $$$\text{pref}[i]$$$.

def solve(arr):

    n = len(arr)

    pref_max = [0 for _ in range(n)]
    suff_min = [0 for _ in range(n)]

    
    pref_max[0] = arr[0]

    for index in range(1, n):
        pref_max[index] = max(arr[index], pref_max[index - 1])
    suff_min[ n -  1] = arr[n - 1]
    for index in range(n - 2, -1, -1):
        suff_min[index] = min(arr[index], suff_min[index + 1])
    ans = [0 for _ in range(n)]
    ans[-1] = pref_max[-1]
    for index in range(n - 2, -1, -1):
        if pref_max[index] > suff_min[index + 1]:
            ans[index] = ans[index + 1]
        else:
            ans[index] = pref_max[index]
    return ans
            
test = int(input())
for _ in range(test):
    n = int(input())
    arr = list(map(int, input().split()))
    ans = solve(arr)
    print(*ans)

To construct a Xorion with exactly $$$k$$$ peaks:

• Use the largest $$$k$$$ elements from $$$n$$$ down to $$$n-k+1$$$ to form the peaks.
• Place the smaller numbers between them to create valleys.

Peak Definition

An index $$$i$$$ is a peak if: - $$$a_i \gt a_{i-1} \quad \text{and} \quad a_i \gt a_{i+1}$$$

Construction Pattern

We can build the sequence as:

• $$$1, n, 2, n-1, 3, n-2, \dots, n-k+1, k+1, k+2, \dots, n-k$$$

  • $$$n, n-1, \dots, n-k+1$$$ → largest $$$k$$$ numbers → peaks
  • $$$1, 2, \dots, k$$$ → smaller numbers → valleys
  • Remaining numbers $$$(k+1, k+2, \dots, n-k)$$$ → fill the rest

Feasibility Condition

• For this construction to be valid:

  • $$$n - k + 1 \gt k + 1 \quad \implies \quad 2 \cdot k \lt n$$$

• If $$$2 \cdot k \ge n$$$, it is impossible to form exactly $$$k$$$ peaks → output -1.

Example

• Let $$$n = 7$$$, $$$k = 2$$$

  1. Largest 2 numbers for peaks: $$$7, 6$$$
  2. Smaller numbers for valleys: $$$1, 2$$$
  3. Remaining numbers: $$$3, 4, 5$$$

Construction:

• $$$1, 7, 2, 6, 3, 4, 5$$$

• Peaks at indices 2 and 4:

  • $$$a_2 = 7 \gt 1, 2$$$
  • $$$a_4 = 6 \gt 2, 3$$$

Summary

• Use largest numbers for peaks

• Interleave smaller numbers for valleys

• Check feasibility: $$$2 \cdot k \lt n$$$

• If not possible → output -1

test = int(input())
for _ in range(test):
    n, k = map(int, input().split())
    
    if 2 * k >= n:
        print(-1)
        continue
    
    ans = []
    left = 1          
    right = n         
    
    for i in range(k):
        ans.append(left)
        ans.append(right)
        left += 1
        right -= 1
    
    for num in range(left, right + 1):
        ans.append(num)
    
    print(*ans)

We are asked to find a number in an array $$$a = [a_1, a_2, \dots, a_n]$$$ such that all array elements are divisible by it. If no such number exists, print -1. If multiple exist, any is acceptable.

Approach 1: Using GCD

Idea

• A number that divides all elements is a common divisor of the array.
• The greatest common divisor (GCD) of the array is the largest number that divides all elements.
• Steps:

1. Compute $$$g = \text{GCD}(a_1, a_2, \dots, a_n)$$$

2. Check if $$$g$$$ exists in the array:

   • If yes, output $$$g$$$
   • If no, output -1

Approach 2: Using Minimum Value

Idea

• Observation: If $$$a_i$$$ divides $$$a_j$$$, then $$$a_i \le a_j$$$.
• Therefore, the number that divides all other elements must be the minimum element in the array.

• Steps:

1. Find the minimum element from the array

2. Check if every element in the array is divisible by min_val:

   • If yes, output min_val
   • If no, output -1

from math import gcd

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

# a_gcd --> GCD of the given array 'arr'
a_gcd = arr[0]

for curr_num in arr:
    a_gcd = gcd(a_gcd, curr_num)
    
# Check if the GCD Exists on the array
is_found = False
for curr_num in arr:
    if curr_num == a_gcd:
        is_found = True
        break


if  is_found :
    print(a_gcd)
else:
    print(-1)     
    
"""
Even though this code is a working solution, the time complexity is:
- For each element, we calculate the GCD iteratively.
- Time complexity of gcd(a, b) is O(log(min(a, b)))
- Overall time complexity: O(n log(max_value))
"""

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

# Find the minimum value in the array
min_value = float("inf")
for curr_num in arr:
    min_value = min(min_value, curr_num)
    
# Check if the minimum value divides all elements
is_valid = True
for curr_num in arr:
    if curr_num % min_value != 0:
        is_valid = False
        break

if is_valid:
    print(min_value)
else:
    print(-1)

"""
Time Complexity:
- Finding the minimum value: O(n)
- Checking divisibility for all elements: O(n)
- Overall: O(n) 
Space Complexity: O(1)


"""
  

We are given two integers $$$x$$$ and $$$y$$$, and we define two sequences:

• $$$a_n = n \oplus x, \quad b_n = n \oplus y$$$

where $$$\oplus$$$ denotes the bitwise XOR operation. We want to find the length of the longest common subsegment between $$$a$$$ and $$$b$$$.

Key Idea

Consider two numbers $$$v$$$ and $$$u$$$ such that:

• $$$x \oplus v = y \oplus u$$$

Now, look at the next elements in the sequences:

• $$$x \oplus (v+1) \quad \text{and} \quad y \oplus (u+1)$$$

We analyze the last bits of $$$v$$$ and $$$u$$$ to understand when the sequences continue to match.

Bit Analysis

Case 1: Both bits are 0

• Adding 1 flips the last bit of both numbers, so:

  • $$$x \oplus (v+1) = y \oplus (u+1)$$$

• The match continues.

Case 2: Both bits are 1

• Adding 1 flips the last bit of both numbers and carries over to the next bit, so we can continue analyzing the next bit.
• The match may continue depending on subsequent bits.

Case 3 : Bits are different (0 and 1)

• Adding 1 flips only one of the bits, while the other number changes differently.
• This breaks the matching.

Conclusion

• The length of the longest matching subsegment depends on the maximum matching suffix of $$$x$$$ and $$$y$$$ in binary.

• Let $$$k$$$ be the length of this matching suffix. Then the answer is:

  • $$$\text{Longest Common Subsegment Length} = 2 \cdot k$$$

Complexity Analysis

• For each test case, we only need to check the binary representation of $$$x$$$ and $$$y$$$.
• The number of bits is at most $$$O(\log C)$$$, where $$$C$$$ is the maximum value of $$$x$$$ or $$$y$$$.
• Therefore, the time complexity per test case is: $$$O(\log C)$$$
• Space complexity: $$$O(1)$$$ (only a few variables are needed)

Summary

1. Find the maximum matching suffix of $$$x$$$ and $$$y$$$ in binary.
2. Let the length of this suffix be $$$k$$$.
3. The longest common subsegment of sequences $$$a$$$ and $$$b$$$ is:

def get_bits(n):
    
    bits = [0] * 32
    index = 31
    while n > 0:
        bits[index] = n % 2
        n //= 2
        index -= 1
    return bits

test = int(input())
for _ in range(test):
    x, y = map(int, input().split())
    count = 0
    #  Bits Repr of X and Y
    x_bits = get_bits(x)
    y_bits = get_bits(y)
    ans = 1
    
    for i in range(31, -1, -1):
        if x_bits[i] == y_bits[i]:
            ans *= 2
        else:
            break
    
    print(ans)

Can you implement the above without generating bits for x and y?? (Hint: by Just using bitwise operators)

test = int(input())
for _ in range(test):
    x, y = map(int, input().split())
    
    diff = x ^ y
    ans = 1
    
    
    while diff & 1 == 0 and diff != 0:
        ans <<= 1
        diff >>= 1
    
    print(ans)

Xorion is traveling in a car along a number line from 0 to n.

• There are k+1 signs at positions: 0, a1, a2, ..., ak
• The car arrives at these signs at times: 0, b1, b2, ..., bk

The car moves at a constant speed between consecutive signs.

Query: Given a distance d, determine how many minutes have passed when the car reaches d (rounded down).

Approach

Step 1: Identify the segment

For a query distance d, find the last sign that the car has passed, which is the greatest position less than or equal to d.

Since the array of signs is sorted, this can be done efficiently using binary search. The time associated with this sign is the base time the car has already spent traveling.

Step 2: Compute the time within the segment

Between the last passed sign and the next sign, the car moves at a constant speed, which can be determined from the distance and time difference between these two signs.

Using this constant speed, we can calculate how much additional time it takes to travel from the last sign to the query distance. This additional time is always rounded down to ensure integer minutes.

Step 3: Compute total time

The total minutes passed when reaching distance d is the sum of:

1. Time already spent to reach the last passed sign
2. Additional minutes required to travel from that sign to distance d

Step 4: Repeat for all queries

For each query, repeat steps 1–3 to determine the time for the requested distance.

Complexity Analysis

• Time Complexity: O(q log k)

  • Binary search per query: O(log k)
  • q queries in total: O(q log k)

• Space Complexity: O(k)

  • To store arrays of positions and times

Key Insights

1. Binary search efficiently locates the segment containing the query distance.
2. Using linear interpolation between signs avoids floating-point operations and ensures accurate integer time calculations.
3. This approach scales well for large input sizes.

test = int(input())
for _ in range(test):
    n, k, q = map(int, input().split())
    arr = [0] + list(map(int, input().split()))
    brr = [0] + list(map(int, input().split()))

    for _ in range(q):
        dist = int(input())
        
        
        low, high = 0, k
        pos = 0
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] <= dist:
                pos = mid
                low = mid + 1
            else:
                high = mid - 1

        # Calculate time
        if arr[pos] == dist:
            print(brr[pos], end=" ")
        else:
            time = brr[pos] + (dist - arr[pos]) * (brr[pos+1] - brr[pos]) // (arr[pos+1] - arr[pos])
            print(time, end=" ")

    print()

Which values could help you know the “weight” of each subtree?

How can you combine a node’s children contributions efficiently?

If you pretend another node is the root, how would the sums change?

How do you combine the original and rerooted contributions for each node?

Step 1: Solve for a Single Root

Notation

• Let op(v, c) denote the operation in the problem statement.
• Let s_v denote the size of the subtree of vertex v.

Goal

• Make a_v ⊕ a_par_v = 0 for every non-root vertex v.

Observation

• The value a_v ⊕ a_par_v changes only when we select v in a spell.
• To make a_v ⊕ a_par_v = 0, we should perform:
  op(v, a_v ⊕ a_par_v)

Cost Calculation

• For a fixed root, the total cost is:
  Cost = Σ_{i ≠ root} s_i * (a_i ⊕ a_par_i)

Step 2: Rerooting the Tree

Idea:

• Once the answer for root 1 is computed, we can efficiently calculate the answer for all other roots by traversing the tree.

Observation

• If we move the root from vertex q to its adjacent vertex r, all other vertices retain the same parent and subtree size.

• Only vertices q and r contribute differently to the total cost.

Edge Division

• The edge (q, r) splits the tree into two parts of size X and Y.
• After changing root from q to r:
  • Subtract Y * (a_q ⊕ a_r)
  • Add X * (a_q ⊕ a_r)

Precomputation

• Subtree sizes X and Y can be precomputed in O(n).
• Each root change costs O(1).

Complexity Analysis

• Single root calculation: O(n)
• Rerooting to all vertices: O(n)
• Total Time Complexity: O(n)
• Space Complexity: O(n)

Summary

1. Compute the cost for an initial root.
2. Traverse the tree and use rerooting to update the cost for each adjacent vertex in O(1) per move.
3. This efficiently calculates the minimum cost for all roots in linear time.

import sys
import threading

def main():
    test = int(input())
    for _ in range(test):
        n = int(input())
        arr = [0] + list(map(int, input().split()))  # 1-indexed

        tree = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            u, v = map(int, input().split())
            tree[u].append(v)
            tree[v].append(u)

        size =  [0 for _ in range(n + 1)] 
        subtree_sum = [0 for _ in range(n + 1)] 
        reroot_sum =  [0 for _ in range(n + 1)] 

        # DFS to calculate subtree sizes and sums
        def dfs1(node, parent):
            size[node] = 1
            for neighbor in tree[node]:
                if neighbor != parent:
                    dfs1(neighbor, node)
                    size[node] += size[neighbor]
                    subtree_sum[node] += subtree_sum[neighbor] + size[neighbor] * (arr[node] ^ arr[neighbor])

        dfs1(1, 0)

        # DFS to calculate Re-rooting(changing the root node) and calculate sums
        def dfs2(node, parent):
            for neighbor in tree[node]:
                if neighbor != parent:
                    reroot_sum[neighbor] = (
                        subtree_sum[node] + reroot_sum[node] - subtree_sum[neighbor]
                        + (n - 2 * size[neighbor]) * (arr[node] ^ arr[neighbor])
                    )
                    dfs2(neighbor, node)

        dfs2(1, 0)

        ans = [subtree_sum[i] + reroot_sum[i] for i in range(1, n + 1)]
        print(*ans)

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

We want the minimum cost to buy exactly $$$n$$$ yogurts when:

• A single yogurt costs $$$a$$$ burles.
• A promotion lets you buy two yogurts for $$$b$$$ burles.

You may mix buying single yogurts and buying pairs. Let's reason through the options, compare costs, and derive a compact formula.

Key Observations

1. Always-available baseline:
   • You can always buy all yogurts one-by-one. That gives the cost.
     • Cost = n.a

2. When is the promotion useful?

   • Buying two yogurts with the promotion costs $$$b$$$. Compare this to buying those two separately:$$$2a$$$.
   • If $$$b \geq 2a$$$, the promotion is not beneficial (or is equal). Then buying every yogurt individually is at least as cheap:
     • $$$b \geq 2a \quad \Rightarrow \quad \text{min cost} = n \cdot a$$$
   • If $$$b \lt 2a$$$, the promotion saves money for pairs, so we should use as many promotions as possible.

Case Analysis

Case A: Promotion is not better ($$$b \geq 2a$$$)

• Optimal strategy is to buy everything one by one:
  • $$$\text{min cost} = n \cdot a$$$

Case B: Promotion is better ($$$b \lt 2a$$$)

• We should buy as many pairs as possible:
  • If $$$n$$$ is even ($$$n = 2k$$$), buy $$$k$$$ pairs: -$$$\text{cost} = k \cdot b = \frac{n}{2} \cdot b$$$
  • If $$$n$$$ is odd ($$$n = 2k+1$$$), buy $$$k$$$ pairs for $$$2k$$$ yogurts and one extra single:
    • $$$\text{cost} = k \cdot b + a = \left\lfloor \frac{n}{2} \right\rfloor \cdot b + a$$$
• We can combine both cases into a single formula:
  • $$$\text{Cost}_{\text{promo}} = \left\lfloor \frac{n}{2} \right\rfloor \cdot b + (n \bmod 2) \cdot a$$$

Final Formula

Now, the answer is the minimum between the baseline and the promotion strategy:

• $$$\text{min cost} = \min\Big( n \cdot a,\ \left\lfloor \frac{n}{2} \right\rfloor \cdot b + (n \bmod 2) \cdot a \Big)$$$

This handles both cases because:

• If $$$b \geq 2a$$$, then $$$n \cdot a$$$ will be cheaper.

• If $$$b \lt 2a$$$, then the promotion plan will be cheaper.

Example Walkthrough

Let $$$n=5,\ a=4,\ b=7$$$.

• All singles:

• Promotion strategy:

Minimum cost = 18

Complexity

• Each test case is solved in $$$O(1)$$$ time (just arithmetic).
• For $$$t$$$ test cases, total complexity is $$$O(t)$$$.

Key Takeaways

• Always consider the baseline: $$$n \cdot a$$$.
• Promotion is only useful if $$$b \lt 2a$$$.

• Compact implementation:

  • $$$ \text{pairs} = \left\lfloor \frac{n}{2} \right\rfloor,\quad \text{remainder} = n \bmod 2$$$
  • $$$\text{Answer} = \min(n\cdot a,\ \text{pairs}\cdot b + \text{remainder}\cdot a) $$$

def solve(yogurt, nor_price, pro_price):
    # Using Normal Price
    normal_cost  = yogurt * nor_price
    # Using Promo Price
    pro_price = (yogurt // 2) * pro_price + (yogurt % 2) * nor_price
    #  Take The Min Those Two costs
    return min(pro_price, normal_cost)

test = int(input())
for _ in range(test):
    yogurt, price, pro_price = list(map(int, input().split()))
    print(solve(yogurt, price, pro_price))

We need to determine whether Maxim can compose a letter text $$$s_2$$$ using letters from a newspaper heading $$$s_1$$$. Each letter in $$$s_1$$$ can be used at most once, and uppercase and lowercase letters are distinct. Spaces in the heading can be ignored.

Count Letter Occurrences

For each uppercase or lowercase letter, calculate how many times it appears in both $$$s_1$$$ and $$$s_2$$$.

• Let $$$count_1[c]$$$ be the number of times character $$$c$$$ appears in $$$s_1$$$ (ignoring spaces).
• Let $$$count_2[c]$$$ be the number of times character $$$c$$$ appears in $$$s_2$$$ (ignoring spaces).

Note: Spaces are ignored because Maxim does not cut them out from the heading; he just leaves them blank.

Compare Letter Counts

For every character $$$x$$$ in $$$s_2$$$, check:

• If this is true for all characters, Maxim can cut enough letters to form $$$s_2$$$.
• If this is false for any character, there are not enough letters in $$$s_1$$$ to make $$$s_2$$$, and the answer is NO.

Determine the Result

• All letters satisfy the condition → YES
• Any letter violates the condition → NO

Key Considerations

1. Uppercase and lowercase letters are distinct.
   • A and a are treated separately.
2. Spaces are ignored in both strings.
3. This method ensures accurate accounting of each letter’s availability.

Complexity Analysis

• Counting letters in $$$s_1$$$ → $$$O(|s_1|)$$$
• Counting letters in $$$s_2$$$ → $$$O(|s_2|)$$$
• Comparing counts → $$$O(1)$$$ per letter (since only 52 letters exist)

Overall complexity: $$$O(|s_1| + |s_2|)$$$, which is efficient for $$$|s_1|, |s_2| \leq 200$$$.

from collections import defaultdict

def solve(heading, letter):
    
    # Count Chars from both strings
    heading_memo = defaultdict(int)
    letter_memo  = defaultdict(int)
    
    for char in heading:
        if char != " ":
            heading_memo[char] += 1 
    for char in letter:
        if char != " ":
            letter_memo[char] += 1
    
   
    for char in letter_memo:
        if letter_memo[char] > heading_memo[char]:
            return "NO"
    return "YES"



heading = input().strip()   
letter = input().strip()   
print(solve(heading, letter))

We are asked to find the minimum number of operations required to make the substring $$$a[l..r]$$$ identical to $$$b[l..r]$$$ after sorting.

Each operation allows you to change one character in $$$a$$$ to any character. Operations in one query do not affect other queries.

Key Insight

For two strings to be identical after sorting, they must have the same number of occurrences for every lowercase letter.

• Let $$$cnt_a[c]$$$ = number of occurrences of character $$$c$$$ in $$$a[l..r]$$$
• Let $$$cnt_b[c]$$$ = number of occurrences of character $$$c$$$ in $$$b[l..r]$$$

We must ensure:

• $$$cnt_a[c] = cnt_b[c] \quad \text{for all } c \in {\text{a..z}}$$$

Using Prefix Sums

• Since there are only 26 lowercase letters, we can precompute prefix sums for each character.

• Let $$$prefix_a[c][i]$$$ = number of occurrences of character $$$c$$$ in $$$a[1..i]$$$.

• Similarly, $$$prefix_b[c][i]$$$ for string $$$b$$$.

Then, for a query $$$[l,r]$$$, we can compute:

This allows constant-time calculation for each character per query.

Computing Minimum Operations

• In one operation, we can change one occurrence of a character $$$c$$$ to another character $$$c_2$$$.

• To minimize operations:

  • Focus on characters where $$$cnt_a[c] \gt cnt_b[c]$$$
  • Each excess occurrence of $$$c$$$ can be changed to a character that is lacking ($$$cnt_a[c_2] \lt cnt_b[c_2]$$$)

• Therefore, the minimum number of operations is simply:

This works because reducing an excess character automatically increases the count of a missing character, achieving the desired multiset equality.

Summary of Approach

1. Precompute prefix sums for each character in both strings.
2. For each query $$$[l,r]$$$, compute $$$cnt_a[c]$$$ and $$$cnt_b[c]$$$ for all lowercase letters.
3. Compute the total excess characters in $$$a$$$ compared to $$$b$$$:
   • $$$\text{answer} = \sum_{c \in {\text{a..z}}} \max(0, cnt_a[c] - cnt_b[c])$$$
4. Output the answer for each query.

Complexity Analysis

• Preprocessing prefix sums: $$$O(26 \cdot n)$$$
• Per query: $$$O(26)$$$ → compute counts and sum over letters
• Total across all queries and test cases: $$$O(26 \cdot (n + q))$$$ → efficient for $$$n,q \le 2 \cdot 10^5$$$

def helper(s):
    """
    This Function Help Us To calculate the prefix of chars frequency
    for both string by calling it twice
    
    """
    n = len(s)
    memo = [[0] * (n + 1) for _ in range(26)]
    for i, ch in enumerate(s, 1):
        for c in range(26):
            memo[c][i] = memo[c][i - 1]
        memo[ord(ch) - ord('a')][i] += 1
    return memo


def solve(a, b, n, q):
    freq_a = helper(a)
    freq_b = helper(b)
    
    for _ in range(q):
        left, right = map(int, input().split())
        left -= 1
        right -= 1
        ans = 0
        for c in range(26):
            count_a = freq_a[c][right + 1] - freq_a[c][left]
            count_b = freq_b[c][right + 1] - freq_b[c][left]
            if count_a > count_b:
                ans += count_a - count_b
        print(ans)

test = int(input())

for _ in range(test):
    n, q = map(int, input().split())
    a = input()
    b = input()
    solve(a, b, n, q)
    

Maxim wants to convert a given string $$$s$$$ into an alternating string, where:

• All characters at odd positions are the same.
• All characters at even positions are the same.
• The length of the string must be even.

We are allowed two types of operations:

1. Delete one character (at most once).
2. Replace any character with another character.

We aim to minimize the number of operations.

Observations

• If the string already has even length, we do not need to delete.
• If the string has odd length, deleting one character is mandatory to achieve an even-length string.

After ensuring an even-length string, the problem reduces to making all odd and even positions uniform.

Even-Length String Case

Let:

• $$$n$$$ = length of the string (even)
• $$$s_{\text{odd}}$$$ = characters at odd positions
• $$$s_{\text{even}}$$$ = characters at even positions

Strategy:

1. Count occurrences of each character in odd and even positions.
2. For odd positions, choose the character $$$c_{\text{odd}}$$$ that occurs most frequently.
3. For even positions, choose the character $$$c_{\text{even}}$$$ that occurs most frequently.
4. Number of replacements needed:

This guarantees the minimum replacements since we are only changing characters that differ from the most frequent ones.

Odd-Length String Case

When $$$n$$$ is odd, we must delete one character. The key complication is:

• After deleting character at index $$$i$$$, all indices greater than $$$i$$$ shift left by 1, changing the parity of their positions.
• This affects which characters are now in odd and even positions.

Using Prefix and Suffix Counts

Define prefix and suffix arrays for counting characters:

1. Prefix counts for even positions:
   • $$$\text{pref1}[i][c] = \text{number of occurrences of character } c \text{ at even positions } j \le i$$$
2. Prefix counts for odd positions:
   • $$$\text{pref2}[i][c] = \text{number of occurrences of character } c \text{ at odd positions } j \le i$$$
3. Suffix counts for even positions:
   • $$$\text{suff1}[i][c] = \text{number of occurrences of character } c \text{ at even positions } j \gt i$$$
4. Suffix counts for odd positions:
   • $$$\text{suff2}[i][c] = \text{number of occurrences of character } c \text{ at odd positions } j \gt i$$$

Calculating Counts After Deletion

If we delete character at index $$$i$$$, all indices $$$j \gt i$$$ shift left by 1, flipping parity:

• Even positions after deletion:
  • $$$\text{even count of character } c = \text{pref1}[i][c] + \text{suff2}[i][c]$$$
• Odd positions after deletion:
  • $$$\text{odd count of character } c = \text{pref2}[i][c] + \text{suff1}[i][c]$$$

This allows us to compute the number of replacements needed after deleting any specific character.

Final Strategy

If $$$n$$$ is even:

• Compute replacements directly using counts of odd and even positions.

If $$$n$$$ is odd:

• Try deleting each character from the string:

  • Compute updated counts of characters in odd/even positions using prefix and suffix arrays.
  • Compute replacements for each deletion.
  • Total operations = 1 (deletion) + replacements.

Take the minimum total operations among all deletion choices.

This ensures we find the optimal number of operations to convert $$$s$$$ into an alternating string.

Complexity

• Building prefix and suffix arrays → $$$O(26 \cdot n)$$$
• Checking deletion of each character → $$$O(26 \cdot n)$$$
• Total complexity → $$$O(26 \cdot n) \sim O(n)$$$ for practical purposes.

def solve(n, text):

    if n % 2 == 0:
        even = [0 for _ in range(26)]

        odd = [0 for _ in range(26)]
        
        for i  in range(n):
            if i % 2 == 0:
                odd[ord(text[i]) - ord("a")] += 1
            else:
                even[ord(text[i]) - ord("a")] += 1
        
        # print(f"text = '{text} 'Even_max = {max(even)} Odd_max = {max(odd)}")
        return n - (max(even) + max(odd))
    else:
        suffix_even = [0 for _ in range(26)]
        suffix_odd =  [0 for _ in range(26)]
        for i  in range(n):
            if i % 2 == 0:
                suffix_odd[ord(text[i]) - ord("a")] += 1
            else:
                suffix_even[ord(text[i]) - ord("a")] += 1
        
        prefix_even = [0 for _ in range(26)]
    
        prefix_odd = [0 for _ in range(26)]
        total_max = 0
        for i in range(n):
            if i % 2 == 0:
                suffix_odd[ord(text[i]) - ord("a")] -= 1
            else:
                suffix_even[ord(text[i]) - ord("a")] -= 1
                
            max_even = 0
            
            max_odd = 0
                
            for char in range(26):
                
                max_even = max(max_even, prefix_even[char] + suffix_odd[char])
                
                max_odd = max(max_odd, prefix_odd[char] + suffix_even[char])
                
                total_max = max(total_max, max_even + max_odd)
                
            
            
            if i % 2 == 0:
                prefix_odd[ord(text[i]) - ord("a")] += 1
            else:
                prefix_even[ord(text[i]) - ord("a")] += 1
        return n - total_max
test = int(input())

for _ in range(test):
    n = int(input())
    
    text = input()
    print(solve(n, text))

            

        
        

We are given:

• n robots with distinct skill levels.
• m rap battles, each u_i beats v_i.
• Battles are deterministic, transitive, and non-contradictory.
• Goal: Find the minimum number of battles needed to uniquely determine the skill ordering of all robots.

Key Observations

1. Graph Representation:

• Construct a directed graph (DAG) where:
  • Nodes = robots.
  • Edge u -> v means u beat v.

1. Uniqueness Condition:

• The ordering is uniquely defined if and only if the DAG contains a path covering all n nodes (i.e., a Hamiltonian path).
• Reason: — If a DAG has a path of length n, the vertices on this path must appear in exactly this order in any topological sort. — Otherwise, multiple topological orders are possible.

1. Guaranteed Acyclicity:

• The problem guarantees results are not contradictory, so the graph is a DAG.

Approach Using Longest Path in DAG

Step 1: Compute Longest Path in DAG

• Longest path definition: For a DAG, the longest path is the path that maximizes the number of vertices visited consecutively following the edges.
• Use dynamic programming (DP) along a topological sort:
  • Let dp[v] = length of the longest path ending at node v.
  • Recurrence:

- Initialize `dp[v] = 1` for all nodes with no incoming edges.

Step 2: Check for Full Sorting

• Let L = length of the longest path in the DAG.
• Case 1: L = n
  • There is a Hamiltonian path.
  • The path uniquely determines the ordering.
  • The answer is the time (index of the last edge added) when this path became complete.
• Case 2: L < n
  • No Hamiltonian path exists.
  • Multiple orderings satisfy the battles.
  • Output -1.

Step 3: Implementation Details

1. Traverse edges in order of battles.
2. Maintain longest path ending at each node incrementally as edges are added.
3. Once a path of length n is formed:

• Record the battle index corresponding to the last edge added in this path.

1. Complexity:

• Longest path in DAG using DP on topological sort → O(n + m).

Alternative Approach: Binary Search

• Let k be the number of first battles considered.
• Check if a unique ordering is possible after the first k battles:
  1. Build a DAG with the first k edges.
  2. Compute longest path length using DP or topological sort.
  3. If longest path = n, ordering is unique.
• Use binary search on k to find the minimum number of battles.
• Complexity: O((n + m) log m)
• Log factor comes from the binary search over m edges.

Summary

• Model battles as a DAG.
• The robots are fully sorted if and only if the DAG contains a Hamiltonian path.
• Compute longest path length in DAG:
  • If length = n → answer = last edge forming this path.
  • If length < n → answer = -1.
• Alternative: binary search on the battle index to determine the first point at which a Hamiltonian path exists.

This method guarantees O(n + m) time complexity and efficiently determines the minimum number of battles for a unique skill ordering.

from collections import  deque

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

graph = [[] for _ in range(n + 1)]
indegree = [0 for _ in range(n + 1)] 

for edge_num in range(1, m + 1):
    u, v = map(int, input().split())
    graph[u].append((v, edge_num))
    indegree[v] += 1

queue = deque()

for node in range(1, n + 1):
    if indegree[node] == 0:
        queue.append(node)
        

last_edge = 0  
ordered_nodes = 0 
# print(graph)

while queue:
    #  This mean we have multiple nodes at this point which leads to more than 1
    #  Topological ordering
    if len(queue) > 1:
        break

    u = queue.popleft()
    ordered_nodes += 1

    for v, edge_num in graph[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            queue.append(v)
            last_edge = max(last_edge, edge_num)
            

if  ordered_nodes!= n:
    print(-1)
else:
    print(last_edge)

from collections import deque

def check(n, edges, k):
    graph = [[] for _ in range(n)]
    indegree = [0 for _ in range(n)] 
    for i in range(k):
        u, v = edges[i]
        graph[u].append(v)
        indegree[v] += 1

    queue = deque()
    dp = [0 for _ in range(n)]
    
    for node in range(n):
        if indegree[node] == 0:
            queue.append(node)
            dp[node] = 1
    
    battles = 0
    while queue:
        u = queue.popleft()
        battles += 1
        for v in graph[u]:
            if dp[v] < dp[u] + 1:
                dp[v] = dp[u] + 1
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    if battles < n:
        return False
    return max(dp) == n

def solve():
    n, m = list(map(int, input().split()))
    edges = []
    
    for _ in range(m):
        u, v = list(map(int, input().split()))
        edges.append((u -1, v - 1))
    
    #  Binary search on the value of k
    low = 0
    high = m
    ans = -1
    while low <= high:
        mid = (low + high) // 2
        if check(n, edges, mid):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    return ans

print(solve())

To determine whether a melody is perfect, we check each pair of consecutive notes in the sequence. For each pair $$$a_i, a_{i+1}$$$, we calculate the interval as $$$|a_i - a_{i+1}|$$$. We then verify whether this interval is one of the allowed values, 5 or 7. If all consecutive intervals satisfy this condition, the melody is perfect and the answer is "YES". Otherwise, if any interval is not 5 or 7, the melody is not perfect and the answer is "NO".

This method ensures that every adjacent pair is validated exactly once, giving a time complexity of $$$O(n)$$$ and a space complexity of $$$O(1)$$$.

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

perfect = True
for i in range(n - 1):
    interval = abs(notes[i] - notes[i + 1])
    if interval not in (5, 7):
        perfect = False
        break

print("YES" if perfect else "NO")

Operation:
- Pick $$$\min(a)$$$ and $$$\max(b)$$$.
- Swap if $$$\min(a) \lt \max(b)$$$.

Repeat:
- Perform up to $$$k$$$ times or until no improvement is possible.

Idea:
- Each swap increases the sum of $$$a$$$ (or decreases $$$b$$$) toward the objective.
- Always choose the best candidates (greedy strategy).

Complexity:
- Naive: $$$O(n \cdot k)$$$ → can be $$$O(n^3)$$$
- Optimized: Sort arrays, use pointers → $$$O(n \log n)$$$

test = int(input())
for _ in range(test):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    a.sort()
    b.sort(reverse=True)

    for i in range(min(k, n)):
        if a[i] < b[i]:
            a[i], b[i] = b[i], a[i]
        else:
            break

    print(sum(a))

We are given:

• An integer $$$n$$$ (divisible by $$$3$$$).

• An array $$$a_1, a_2, \dots, a_n$$$.

• In one move, we can pick an index $$$i$$$ $$$(1 \le i \le n)$$$ and replace $$$a_i$$$ with $$$a_i + 1$$$.

We define:

• $$$c_0$$$ = number of elements where $$$a_i \bmod 3 = 0$$$

• $$$c_1$$$ = number of elements where $$$a_i \bmod 3 = 1$$$

• $$$c_2$$$ = number of elements where $$$a_i \bmod 3 = 2$$$

The array is balanced if: $$$c_0 = c_1 = c_2$$$

Our task: Find the minimum number of moves to make the array balanced.

Key Observations

Target count for each group:
Since $$$n$$$ is divisible by 3, the balanced state means: $$$\text{target} = \frac{n}{3}$$$

Allowed move effect:

• If $$$a_i \bmod 3 = 0$$$, one increment moves it to remainder $$$1$$$.

• If $$$a_i \bmod 3 = 1$$$, one increment moves it to remainder $$$2$$$.

• If $$$a_i \bmod 3 = 2$$$, one increment moves it to remainder $$$0$$$.

This forms a cycle:$$$0 \to 1 \to 2 \to 0$$$

Excess and deficit handling:

• If $$$c_k \gt \text{target}$$$ for some $$$k$$$, we can move the excess elements to the next group $$$(k+1) \bmod 3$$$.

• Each such move costs 1 increment per element shifted.

Balancing Process

• Count $$$c_0$$$, $$$c_1$$$, $$$c_2$$$.

• While not all equal to target:

• For $$$i \in {0,1,2}$$$:

  • If $$$c_i \gt \text{target}$$$:
    1. $$$\text{excess} = c_i - \text{target}$$$
    2. Transfer $$$\text{excess}$$$ elements to group $$$(i+1) \bmod 3$$$
    3. Increase move counter by $$$\text{excess}$$$

• Stop when:$$$c_0 = c_1 = c_2 = \text{target}$$$

Example Walkthrough

Example:
$$$n = 6$$$, $$$a = [0, 2, 5, 5, 4, 8]$$$

• Initial remainders:

• Target: $$$\frac{6}{3} = 2$$$

Step 1: $$$c_2$$$ has excess $$$2$$$. Move them to $$$c_0$$$:

Step 2: $$$c_0$$$ has excess $$$1$$$. Move it to $$$c_1$$$:

Balanced in 3 moves.

test = int(input())
for _ in range(test):
    n = int(input())
    arr = list(map(int, input().split()))
    
    # Count remainders
    cnt = [0, 0, 0]
    for x in arr:
        cnt[x % 3] += 1
    
    target = n // 3
    moves = 0
    
    # Keep balancing
    while cnt[0] != target or cnt[1] != target or cnt[2] != target:
        for i in range(3):
            if cnt[i] > target:
                excess = cnt[i] - target
                cnt[i] -= excess
                cnt[(i + 1) % 3] += excess
                moves += excess
    
    print(moves)

We are given $$$n$$$ days of vacation.

• For each day, Vasya knows:

  1. Whether the gym is open.
  2. Whether there is a contest.

• On each day, Vasya can:

  • Rest
  • Write the contest (if available)
  • Go to the gym (if open)

Constraint:
He cannot do the same activity (contest or gym) on two consecutive days.

Goal:
Minimize the number of rest days.

Observation

This is a Dynamic Programming (DP) problem because:

• The decision for day $$$i$$$ depends on what was done on day $$$i-1$$$.

• There’s a constraint to avoid repeating the same activity consecutively.

State Definition

Let:

• $$$dp[i][0]$$$ → Minimum rest days till day $$$i$$$ if Vasya rests on day $$$i$$$.
• $$$dp[i][1]$$$ → Minimum rest days till day $$$i$$$ if Vasya participates in a contest on day $$$i$$$.
• $$$dp[i][2]$$$ → Minimum rest days till day $$$i$$$ if Vasya goes to the gym on day $$$i$$$.

Transition

1. Rest Case

• If Vasya rests on day $$$i$$$:

  • $$$dp[i][0] = 1 + \min(dp[i-1][0],\ dp[i-1][1],\ dp[i-1][2])$$$
  • Because resting adds 1 rest day to the minimum of all possible previous states.

2. Contest Case

• If there is a contest on day $$$i$$$ and he didn't do a contest yesterday:

  • $$$dp[i][1] = \min(dp[i-1][0],\ dp[i-1][2])$$$
  • We take the minimum rest days from rest yesterday or gym yesterday.
  • If no contest is available, $$$dp[i][1]$$$ is infinite (or invalid).

3. Gym Case

• If the gym is open on day $$$i$$$ and he didn’t go to the gym yesterday:

  • $$$dp[i][2] = \min(dp[i-1][0],\ dp[i-1][1])$$$
  • We take the minimum rest days from rest yesterday or contest yesterday.
  • If the gym is closed, $$$dp[i][2]$$$ is infinite (or invalid).

Initialization

• For day $$$1$$$:

  • If rest: $$$dp[1][0] = 1$$$
  • If contest possible: $$$dp[1][1] = 0$$$
  • If gym possible: $$$dp[1][2] = 0$$$
  • If both possible: choose based on availability.

Answer

The final answer is:$$$\min(dp[n][0],\ dp[n][1],\ dp[n][2])$$$

This gives the minimum number of rest days possible after $$$n$$$ days.

def solve():
    n = int(input().strip())
    days = list(map(int, input().strip().split()))
    
    INF = float('inf')
    # dp[i][0] → rest day
    # dp[i][1] → contest day
    # dp[i][2] → gym day
    dp = [[INF] * 3 for _ in range(n + 1)]
    
    # Base case (day 0 — no days taken yet)
    dp[0][0] = dp[0][1] = dp[0][2] = 0

    for i in range(1, n + 1):
        activity = days[i - 1]

        # rest day
        dp[i][0] = 1 + min(dp[i - 1])

        if activity in (1, 3):
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2])

        # didn't do gym yesterday
        if activity in (2, 3):
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1])

    print(min(dp[n]))


solve()

You are given an array $$$a = [a_1, a_2, \dots, a_n]$$$. In one operation, you can choose two distinct elements $$$a_i$$$ and $$$a_j$$$ ($$$i \neq j$$$) and decrease each of them by 1.

You need to determine whether it is possible to reduce all elements to zero.

Step 1: Understanding the Operation

• Each operation reduces the sum of all elements by 2: $$$\text{new sum} = \text{old sum} - 2$$$

• Therefore, if the sum of all elements is initially odd, we can never reach zero because subtracting 2 repeatedly will always leave an odd number.

Condition 1: $$$\sum_{i=1}^{n} a_i$$$ must be even.

Step 2: Considering the Largest Element

Let $$$M = \max(a_1, a_2, \dots, a_n)$$$ and $$$S_{\text{rest}} = \sum_{i=1}^{n} a_i - M$$$

• To reduce $$$M$$$ to zero, we need to pair it with other elements in each operation.
• If $$$M \gt S_{\text{rest}}$$$, there aren’t enough elements to pair with $$$M$$$ to bring it down to zero.

Condition 2: $$$M \le S_{\text{rest}} = \sum_{i=1}^{n} a_i - M$$$

Step 3: Proof of Sufficiency

If both conditions hold:

1. $$$\sum_{i=1}^{n} a_i$$$ is even.
2. $$$M \le \sum_{i=1}^{n} a_i - M$$$

Then we can always reduce all elements to zero using a greedy pairing strategy:

• Always pair the two largest remaining elements.
• Each operation decreases the sum by 2.
• Because the total sum is even, we can eventually reach a sum of zero.
• The largest element $$$M$$$ can always find a partner (since $$$M \le S_{\text{rest}}$$$).

This proves that both conditions are sufficient.

Step 4: Algorithm

1. Compute the sum of all elements:$$$\text{sum_a} = \sum_{i=1}^{n} a_i$$$

2. Find the maximum element: $$$M = \max(a_1, a_2, \dots, a_n)$$$

3. Check the two conditions: $$$\sum_{i=1}^{n} a_i \equiv 0 \pmod{2} \quad \text{and} \quad M \le \sum_{i=1}^{n} a_i - M$$$

   • If both are true → "YES"
   • Otherwise → "NO"

Step 5: Examples

• Example 1:[0, 0, 2, 2]

  • Sum: $$$\sum a_i = 1+1+2+2 = 6 \quad \text{(even)}$$$
  • Maximum element:$$$M = 2$$$

• Sum of others:$$$S_{\text{rest}} = 6 - 2 = 4 \quad (\text{and } M \le S_{\text{rest}})$$$

• Both conditions satisfied → YES

• Operations:

  1. Decrease $$$a_1$$$ and $$$a_2$$$: [0,0,2,2]
  2. Decrease $$$a_3$$$ and $$$a_4$$$: [0,0,1,1]
  3. Decrease $$$a_3$$$ and $$$a_4$$$: [0,0,0,0]

• Example 2:[1, 2, 3, 4, 5, 6]

  • Sum: $$$\sum a_i = 1+2+3+4+5+6 = 21 \quad \text{(odd)} $$$
  • Sum is odd → NO
  • Even if the sum were even, check $$$M$$$: $$$M = 6, \quad S_{\text{rest}} = 15 \quad (M \le S_{\text{rest}}) $$$

• Condition 1 fails → impossible to reach zero.

def solve(arr):
    total_sum = sum(arr)
    max_elem = max(arr)
    
    # First Condition 
    if total_sum % 2 != 0:
        return "NO"
    
    # Second Condition
    if max_elem > total_sum - max_elem:
        return "NO"
    
    return "YES"


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

print(solve(arr))

If you are not interested in competitive programming, this problem is not interview-friendly. You don’t have to solve or understand it, but if you do, it will be a plus for your problem-solving skills

Even if the approach is optimal, it is not accepted by Codeforces.

• You can either change the code to C++ or Java
• Or just understand it and analyze its time complexity

Note: I will update it as soon as I find a more optimal solution than this one.

The key idea is to flatten the tree into an array so that every subtree becomes a contiguous segment.
We run a DFS from the root 1 and record:

• Entry time tin[v] when a vertex v is first visited
• Exit time tout[v] after all its descendants are processed

If t is a global time incremented on entry, we define an order array ord[t] such that
ord[tin[v]] = v.

It is standard that the subtree of v corresponds exactly to the segment
[tin[v], tout[v]] in this DFS order (Euler tour).
Hence, every query “on the subtree of v” reduces to a range operation on [tin[v], tout[v]].

Color Representation as Bitmask

Each vertex color c ∈ {1, …, 60} is represented as a bitmask in a 64-bit integer:

mask(c) = 1 << (c - 1)

For the flattened array A of length n:

A[i] = mask(c_ord[i])

A segment’s set of colors is then the bitwise OR of its elements.
If a segment covers colors S, its mask is:

mask(S) = OR_{x ∈ S} mask(x)

The number of distinct colors is:

#colors = popcount(mask(S))

Segment Tree with Lazy Propagation

We build a segment tree over A with lazy propagation.

For each node x in the tree:

• M_x = bitwise OR of all A[i] for i in this node's segment
• L_x = lazy tag, initially unset (e.g., -1), meaning “no pending assignment.”
  If set, it holds a uniform mask meaning “paint this entire segment with this mask.”

Operations

1) Range Paint (Type 1)

Painting all vertices in the subtree of v with color c means assigning:

V = mask(c)

to the segment [tin[v], tout[v]].

For a fully covered segment:

• Set M_x = V
• Set L_x = V

For partial overlap:

• Push L_x down to children if needed
• Recurse into children

2) Range Query (Type 2)

Counting distinct colors in the subtree of v means:

Ans(v) = popcount(OR_query([tin[v], tout[v]]))

The segment tree merges results by bitwise OR:

res = M_left | M_right

Correctness

We maintain two invariants:

1. If L_x is unset, then M_x is the OR of the actual values in the segment.
2. If L_x is set, then the entire segment is painted with that mask.

Updates replace segments with a constant mask. Push operations ensure children remain consistent.
Because bitwise OR matches set union on these masks, the query result is correct,
and popcount returns the correct count of distinct colors.

Complexity

• Preprocessing (DFS): O(n)
• Range Paint: O(log n)
• Range Query: O(log n)

Total time: O((n + m) log n)
Space: O(n) for the tree and segment tree.

Summary:

1. Flatten the tree via DFS (tin, tout).
2. Store colors as 64-bit masks.
3. Maintain a segment tree with lazy range assignment and range OR queries.
4. Answer queries with popcount of the returned mask.

import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

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

adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

# Euler Tour Flattening
tin = [0] * (n + 1)
tout = [0] * (n + 1)
order = [0] * (n + 1)
timer = 0

def dfs(u, p):
    global timer
    timer += 1
    tin[u] = timer
    order[timer] = u
    for v in adj[u]:
        if v != p:
            dfs(v, u)
    tout[u] = timer

dfs(1, -1)

size = 1
while size < n:
    size <<= 1

tree = [0] * (2 * size)
lazy = [-1] * (2 * size)

def build():
    for i in range(1, n + 1):
        node = order[i]
        tree[size + i - 1] = 1 << (colors[node - 1] - 1)
    for i in range(size - 1, 0, -1):
        tree[i] = tree[i * 2] | tree[i * 2 + 1]

def apply(node, value):
    tree[node] = value
    lazy[node] = value

def push(node):
    if lazy[node] != -1:
        apply(node * 2, lazy[node])
        apply(node * 2 + 1, lazy[node])
        lazy[node] = -1

def update(l, r, value, node=1, lx=1, rx=size):
    if r < lx or rx < l:
        return
    if l <= lx and rx <= r:
        apply(node, value)
        return
    push(node)
    mid = (lx + rx) // 2
    update(l, r, value, node * 2, lx, mid)
    update(l, r, value, node * 2 + 1, mid + 1, rx)
    tree[node] = tree[node * 2] | tree[node * 2 + 1]

def query(l, r, node=1, lx=1, rx=size):
    if r < lx or rx < l:
        return 0
    if l <= lx and rx <= r:
        return tree[node]
    push(node)
    mid = (lx + rx) // 2
    return query(l, r, node * 2, lx, mid) | query(l, r, node * 2 + 1, mid + 1, rx)

build()

for _ in range(m):
    q = list(map(int, input().split()))
    if q[0] == 1:
        v, c = q[1], q[2]
        update(tin[v], tout[v], 1 << (c - 1))
    else:
        v = q[1]
        res = query(tin[v], tout[v])
        print(res.bit_count())  # Python 3.10+

We are given an array of length $$$n$$$ that represents whether Petya watered his flower each day.
Each element $$$a_i$$$ is either:

• $$$1$$$ → the flower was watered
• $$$0$$$ → the flower was not watered

The flower begins at a height of $$$1$$$ cm on day 0 (before processing any input days).

Simulation Logic

We iterate through the array starting from index $$$1$$$ (the second day), and at each step, we examine the current element $$$a_i$$$ and the previous element $$$a_{i-1}$$$.
There are four possible scenarios:

• Case 1: $$$a_i = 1$$$ and $$$a_{i-1} = 1$$$
  → The flower was watered both yesterday and today
  → It grows by $$$5$$$ cm
  → height += 5

• Case 2: $$$a_i = 1$$$ and $$$a_{i-1} = 0$$$
  → The flower was watered today only
  → It grows by $$$1$$$ cm
  → height += 1

• Case 3: $$$a_i = 0$$$ and $$$a_{i-1} = 1$$$
  → The flower was not watered today, but was yesterday
  → It doesn't grow, but remains alive
  → height remains the same

• Case 4: $$$a_i = 0$$$ and $$$a_{i-1} = 0$$$
  → The flower was not watered for two consecutive days
  → The flower dies
  → return -1

Initialization

• The simulation starts with: height = 1

We loop through the array once and apply the above logic. If the flower survives all $$$n$$$ days, we return the final height⁣. If it dies due to two unwatered days in a row, we return -1.

Time Complexity

• This approach has a time complexity of $$$O(n)$$$, since we loop through the array once.

t = int(input())
for _ in range(t):
    n  = int(input())
    arr = list(map(int, input().split()))
    
    height = 1
    if arr[0] == 1:
        height += 1
    for i in range(1, n):
        if arr[i] == 1 and arr[i - 1] == 1:
            height += 5
        elif arr[i] == 1 and arr[i - 1] == 0:
            height += 1
        elif arr[i] == 0 and arr[i - 1] == 0:
            height =  -1  
            break
    print(height)

You're given an array of integers $$$a_1, a_2, \ldots, a_n$$$.
In one move (costing 1 coin), you can increment or decrement any element by 1.
Your goal is to make the product of the entire array equal to 1 using the minimum number of moves.

Key Insight

The product of several integers is 1 if and only if: - Each element is either $$$1$$$ or $$$-1$$$ - The number of $$$-1$$$ elements is even

Step-by-Step Strategy

$$$1$$$. Convert each number to 1, -1, or 0:

• If $$$a_i \gt 1$$$:
  Convert to 1, cost is $$$a_i - 1$$$

• If $$$a_i \lt -1$$$:
  Convert to -1, cost is $$$-1 - a_i = |a_i + 1|$$$

• If $$$a_i = 0$$$:
  Count it separately, will cost 1 later

• If $$$a_i = 1$$$ or $$$-1$$$:
  No cost

$$$2$$$. Track:

• cost: total number of coins used
• neg_count: number of -1s
• zero_count: number of 0s

Final Adjustment

Let $$$k$$$ be the number of zeros.

• If $$$k \gt 0$$$:
  Spend $$$k$$$ coins to convert all zeros
  Use one of the zeros to fix the parity of negative numbers, if needed
  → No extra cost

• If $$$k = 0$$$:
  If neg_count is odd, we must convert one $$$-1$$$ to $$$1$$$
  → Extra cost of 2 coins

Time Complexity

The entire algorithm runs in $$$\mathcal{O}(n)$$$ time.

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

cost = 0
neg_count = 0
zero_count = 0

for num in arr:
    if num > 1:
        cost += num - 1
    elif num < -1:
        cost += abs(num + 1)
        neg_count += 1
    elif num == 0:
        cost += 1
        zero_count += 1
    elif num == -1:
        neg_count += 1

if zero_count == 0 and neg_count % 2 == 1:
    cost += 2

print(cost)

You are given a grid of size $$$n \times m$$$. You start at cell $$$(1,1)$$$ and want to reach cell $$$(n,m)$$$.

Allowed moves:

• Move right from $$$(x, y)$$$ to $$$(x, y+1)$$$, costing $$$x$$$ burles.
• Move down from $$$(x, y)$$$ to $$$(x+1, y)$$$, costing $$$y$$$ burles.

The question: can you reach $$$(n,m)$$$ spending exactly $$$k$$$ burles?

Key Insight: The total cost is constant regardless of the path

No matter which path you take (only moving right or down), the total cost to reach $$$(n,m)$$$ is always the same.

This can be proven by induction on $$$n + m$$$:

• Base case: $$$n = m = 1$$$.
  You are already at the target; no moves are made, so cost is $$$1 \times 1 - 1 = 0$$$.

• Inductive step:
  For fixed $$$(n, m)$$$, the last step to reach $$$(n, m)$$$ must be either:

  • From $$$(n, m-1)$$$, costing $$$n$$$ burles, or
  • From $$$(n-1, m)$$$, costing $$$m$$$ burles.

If the total cost to reach $$$(n, m-1)$$$ is $$$n \times (m-1) - 1$$$, then the total cost reaching $$$(n,m)$$$ from there is: $$$n \times (m-1) - 1 + n = n \times m - 1$$$.

Similarly, if the cost to reach $$$(n-1,m)$$$ is $$$(n-1) \times m - 1$$$, then coming from there costs: $$$(n-1) \times m - 1 + m = n \times m - 1$$$.

Since both paths give the same total cost, by induction the cost to reach $$$(n,m)$$$ is always: $$$n \times m - 1$$$.

What this means

You do not need to consider any particular path. Simply compute: $$$\text{cost} = n \times m - 1$$$

and check if it equals $$$k$$$.

• If $$$k = n \times m - 1$$$, print "YES"
• Otherwise, print "NO"

t = int(input())

for _ in range(t):
    n, m, k = map(int, input().split())
    cost = n * m - 1

    if k == cost:
        print("YES")
    else:
        print("NO")

Track by number, not position.

Let factors talk to each other.

You are given a list of integers $$$a_1, a_2, \dots, a_n$$$ called good integers.
Your goal is to find the maximum length of a good sequence using these integers, satisfying the following conditions:

1. The sequence is strictly increasing.
2. No two adjacent elements are coprime, i.e., for every adjacent pair $$$(x_i, x_{i+1})$$$, $$$\gcd(x_i, x_{i+1}) \gt 1$$$.
3. All elements of the sequence must come from the list of good integers.

Core Idea

The key idea is to use dynamic programming (DP) combined with divisor information to construct and extend valid sequences efficiently.

Since we require adjacent numbers to not be coprime, we want them to share at least one common divisor greater than 1.

A natural way to organize this is by thinking in terms of divisors:
If two numbers are divisible by the same number $$$d \gt 1$$$, then their GCD is at least $$$d$$$, satisfying the condition.

Definitions

We define two key DP structures:

• $$$dp[x]$$$: the maximum length of a valid sequence ending at value $$$x$$$
• $$$d[i]$$$: the maximum length of any sequence that ends with a number divisible by $$$i$$$

Here’s what they mean:

• $$$dp[x]$$$ stores the best (maximum length) sequence that ends at $$$x$$$.
• $$$d[i]$$$ is a helper that tracks the best dp value among all previous values that were divisible by $$$i$$$.

This allows us to efficiently build on previous values that share common divisors.

Step 1: Preprocessing Divisors

To use the divisors efficiently in our transitions, we precompute all the divisors of every number up to the maximum number in the array.

This is done in $$$\mathcal{O}(n \log n)$$$ time using a sieve-like approach:

• For every $$$i$$$ from $$$1$$$ to $$$\max(a)$$$,
• Add $$$i$$$ as a divisor to every multiple of $$$i$$$.

At the end of this step, for any number $$$x$$$, we can instantly access all its divisors via divisors[x].

Step 2: Dynamic Programming Transitions

Now that we have all divisors available, we sort the array $$$a$$$ and remove duplicates to ensure the sequence we build is strictly increasing.

Then for each number $$$x$$$ in the sorted array:

Step 2.1: Compute $$$dp[x]$$$

We want to extend the best sequence that ends with a number sharing a divisor with $$$x$$$.

So we iterate over all divisors $$$i$$$ of $$$x$$$ and do:

This means: “Let’s try to extend a sequence that ends in some previous number divisible by $$$i$$$, and add $$$x$$$ at the end.”

Step 2.2: Update $$$d[i]$$$

Once we compute $$$dp[x]$$$, we update all relevant $$$d[i]$$$ values for the next transitions.

For all $$$i \mid x$$$, we do:

This ensures that any future number $$$y$$$ divisible by $$$i$$$ can use this newly improved path.

Why This Works

Because we're enforcing the GCD condition through shared divisors, this approach naturally guarantees:

• GCD > 1 for all adjacent elements (since they share a common divisor).
• Strictly increasing order, as we process the sorted array from left to right.

Also, since we only process a number's divisors, and the number of divisors of a number is at most $$$\mathcal{O}(\sqrt{x})$$$, and the total over all numbers from $$$1$$$ to $$$n$$$ is bounded by $$$\mathcal{O}(n \log n)$$$, the algorithm remains efficient.

Special Case: Single Element [1]

If the input array is just $$$[1]$$$, there's no possible sequence of length >1, since 1 is coprime with every other number (including itself).
In this case, the only valid sequence is $$$[1]$$$ of length 1.

So we must handle this edge case explicitly.

Time Complexity

This is efficient and works well for $$$n$$$ up to $$$10^5$$$.

Summary Table

Conceptual Takeaway

This approach cleverly transforms a hard GCD-based subsequence constraint into a tractable divisor-based DP problem.
By precomputing and reusing divisor relationships, we efficiently manage transitions and enforce the $$$\gcd \gt 1$$$ rule without needing pairwise comparisons.

n = int(input())
 
arr = list(map(int, input().split()))
 
def get_divisors(x):
    divisors = [[] for _ in range(x + 1)]
    for i in range(2, x + 1):
        for j in range(i, x + 1, i):
            divisors[j].append(i)
    return divisors
div_memo = [0 for _ in range(max(arr) + 1)]
memo = [-1 for _ in range(max(arr) + 1)]
divisors = get_divisors(max(arr))
 
 
def dfs(value):
    if memo[value] != -1:
        return memo[value]
    longest_good_sequence = 0
    for div in divisors[value]:
        longest_good_sequence = max(longest_good_sequence, div_memo[div])
    memo[value] = longest_good_sequence + 1
    for div in divisors[value]:
        div_memo[div] = max(memo[value], div_memo[div])
    return memo[value]
ans  = 0
for a in arr:
    ans = max(dfs(a), ans)
print(ans)
        

Group values, not positions.

Treat it like House Robber on numbers.

We are given a list of integers a of size n. We are allowed to repeatedly choose a number x from the list and:

• Gain x points
• Delete all occurrences of x, x - 1, and x + 1 from the list

Our goal is to maximize the total number of points we can collect through such operations.

This constraint — where selecting a number x forces the removal of its adjacent values — means we cannot pick both x and x+1. So, we must make choices that avoid conflicting selections.

Key Insight

Rather than working directly with the input array, it's helpful to preprocess it to count how many times each value appears.

Let cnt[x] be the number of times value x appears in the array. We now reframe the problem as:

• For every integer value x, we can either
• Take it, earning cnt[x] * x points, but then we must skip x-1
• Skip it, and rely on the optimal value already computed for smaller numbers

This makes the problem well-suited for a Dynamic Programming solution.

Dynamic Programming Approach

We define a dynamic programming array f where:

• f(i) is the maximum score we can get considering values from 1 to i

Base Cases

• f(0) = 0: no values to consider, so the score is 0
• f(1) = cnt[1] * 1: only one value to consider; we can either take it or not

Recurrence Relation

For all values i ≥ 2:

Explanation:

• f(i - 1): if we skip value i, the score is the best score we could get using up to i-1
• f(i - 2) + cnt[i] * i: if we take value i, we must skip i-1, so we add cnt[i] * i to the score we got up to i-2

This transition ensures we never take two adjacent values, which would violate the rule of deleting x-1 and x+1.

Implementation Steps

$$$1$$$. Build the frequency array cnt:

• Iterate through the input array and count the occurrences of each integer
• This helps reduce the problem from position-based to value-based

$$$2$$$. Initialize the DP array f:

• f[0] = 0
• f[1] = cnt[1] * 1

$$$3$$$. Iterate from i = 2 to the maximum value present in the input:

• Use the recurrence relation to fill f[i]

$$$4$$$. Final answer is f[max_val]:

• max_val is the largest number in the array a
• This value represents the best result considering all possible values

Time and Space Complexity

• Time Complexity: O(n + m) where:
• n is the size of the input array
• m is the maximum value in the input
• Counting frequencies takes O(n)
• Filling the DP array takes O(m)

• Space Complexity: O(m) for storing the frequency and DP arrays

Summary

This approach efficiently solves the problem by reducing it to a non-adjacent selection problem over the frequency of values, rather than the positions in the original array. The dynamic programming recurrence ensures optimal choices at each step by balancing between picking or skipping each number based on its contribution and its adjacency constraints.

import sys
import threading
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    max_value = max(arr)
    trr = [0 for i in range(max_value + 1)]
    memo = [-1 for i in range(max_value + 1)]

    for a in arr:
        trr[a] += 1
    def dfs(index):
        if memo[index] != -1:
            return memo[index]
        if index == 0:
            return 0
        if index < 0:
            return 0
        
        not_take = dfs(index - 1)
            
        take = trr[index] * index  + dfs(index - 2)
        memo[index] =  max(take, not_take)
        return memo[index]
    print(dfs(max_value))


def main():
    solve()


if __name__ == '__main__':
    sys.setrecursionlimit(2 * 10**5)
    threading.stack_size(1 << 27)  # ~32 MB stack
    t = threading.Thread(target=main)
    t.start()
    t.join()

    
    

Break big whites smartly.

Subtree sizes are gold.

Cut edges, track splits.

DFS from root, think gain.

You are given a tree with $$$n$$$ nodes.

A tree is an undirected graph that is: - Connected (there is a path between any two nodes) - Acyclic (no cycles)

Each node is initially white.

You play a game on this tree as follows:

• On your first move, you choose any node and paint it black.
• On subsequent moves, you can only paint a white node adjacent to any black node.
• Each time you paint a node, you earn points equal to the size of the white connected component it belonged to just before it was painted.

The game ends when all nodes are painted black.

Objective

Your goal is to choose:

1. The first node to paint.

2. The order in which you paint the rest of the nodes.

such that the total number of points is maximized.

Strategy Overview

Let’s denote: - The first black node as the root. - The tree rooted at this node allows us to define a parent-child relationship between nodes.

This problem becomes one of selecting the best root (i.e., first node) and modeling the painting process as a traversal through the tree.

The idea is to:

1. Fix a node (say, node $$$1$$$) as the root.
2. Use dynamic programming to compute the score for that root.
3. Use a technique called rerooting to efficiently compute the score for every other possible root.

Finally, select the root that gives the maximum score.

Step 1: Fix a Root and Compute Initial DP

Let’s fix node $$$1$$$ as the root of the tree.

We define two arrays:

• $$$\text{siz}_v$$$: the size of the subtree rooted at node $$$v$$$. This includes $$$v$$$ itself and all its descendants.
• $$$\text{dp}_v$$$: the total score of the tree if we start the painting process with $$$v$$$ as the root.

Let $$$\text{ch}(v)$$$ be the set of children of $$$v$$$ in the tree.

We compute:

Why this formula works:

Let’s break it down: - $$$\text{dp}_{\text{to}}$$$: total score from each child subtree. - $$$\text{siz}_v$$$: added because when we select $$$v$$$, we paint it and gain points equal to the number of white nodes connected to it — i.e., its entire subtree before it’s painted.

Using DFS (Depth-First Search), we traverse the tree and compute $$$\text{siz}_v$$$ and $$$\text{dp}_v$$$ for each node.

At this point, we know the score if the root is node $$$1$$$.

Step 2: Rerooting the Tree

Now we want to find the score $$$\text{dp}_v$$$ for every possible root $$$v$$$, not just node $$$1$$$.

A naive way would be to recompute everything from scratch for each root, costing $$$O(n^2)$$$ time.

Instead, we use rerooting to compute the new score in constant time per move, and thus $$$O(n)$$$ total time.

Rerooting Logic

Let’s say the current root is node $$$v$$$, and we want to move the root to its child $$$\text{to}$$$.

We do this in two main steps:

Step 1: Cut the edge $$$(v, \text{to})$$$

• We remove $$$\text{to}$$$ from $$$v$$$'s subtree.
• This means:
  • Subtract $$$\text{dp}_{\text{to}}$$$ from $$$\text{dp}_v$$$
  • Subtract $$$\text{siz}_{\text{to}}$$$ from $$$\text{siz}_v$$$

Step 2: Connect $$$v$$$ as a child of $$$\text{to}$$$

• Now $$$\text{to}$$$ becomes the root.
• We attach $$$v$$$ as a child of $$$\text{to}$$$.
• So we:
  • Add updated $$$\text{dp}_v$$$ to $$$\text{dp}_{\text{to}}$$$
  • Add updated $$$\text{siz}_v$$$ to $$$\text{siz}_{\text{to}}$$$

In math terms:

Now, $$$\text{dp}_{\text{to}}$$$ holds the score with $$$\text{to}$$$ as root.

We update our global answer.

Step 3: Backtrack (Rollback)

After processing $$$\text{to}$$$, we undo all changes and restore the original state. This allows the next sibling to be processed correctly.

Final Steps

$$$1$$$. Run a first DFS from any node (say, node $$$0$$$) to compute:

• $$$\text{siz}_v$$$ for all $$$v$$$
• $$$\text{dp}_v$$$ for all $$$v$$$

$$$2$$$. Run a second DFS that reroots the tree at every node:

• At each step, compute the new $$$\text{dp}_v$$$ in constant time
• Track the maximum score seen

Time Complexity

• First DFS (computing subtree sizes and initial DP): $$$O(n)$$$
• Second DFS (rerooting): $$$O(n)$$$

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

Why This Works for Tree Painting

The painting process and the scoring rules align perfectly with subtree structure:

• When a node is selected, its score equals the size of the connected white component — which is exactly the subtree size.
• By modeling the process as rooting the tree, we reduce the problem to a root-based score maximization.
• Using rerooting, we try all possible starting points efficiently and choose the best one.

This guarantees that we find the maximum possible score achievable in the Tree Painting game.

import sys
import threading

n = int(input())
graph = [[] for _ in range(n)]

for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)

subtree_size = [0] * n
dp = [0] * n
max_score = 0

def dfs(v, parent):
    subtree_size[v] = 1
    for neighbor in graph[v]:
        if neighbor == parent:
            continue
        dfs(neighbor, v)
        subtree_size[v] += subtree_size[neighbor]
        dp[v] += dp[neighbor]
    dp[v] += subtree_size[v]

def solve(v, parent):
    global max_score
    max_score = max(max_score, dp[v])
    
    for neighbor in graph[v]:
        if neighbor == parent:
            continue

        dp[v] -= dp[neighbor] + subtree_size[neighbor]
        subtree_size[v] -= subtree_size[neighbor]
        
        dp[neighbor] += dp[v] + subtree_size[v]
        subtree_size[neighbor] += subtree_size[v]

        solve(neighbor, v)

        subtree_size[neighbor] -= subtree_size[v]
        dp[neighbor] -= dp[v] + subtree_size[v]

        subtree_size[v] += subtree_size[neighbor]
        dp[v] += dp[neighbor] + subtree_size[neighbor]

def main():
    dfs(0, -1)
    solve(0, -1)
    print(max_score)

if __name__ == '__main__':
    sys.setrecursionlimit(2 * 10**5)
    threading.stack_size(1 << 27)  
    t = threading.Thread(target=main)
    t.start()
    t.join()

To determine if each access key is secure, we need to validate it against three specific rules.

1. Digits appear before letters:
   All digits (if present) must appear before any letters. This means the transition from digits to letters can happen only once, and once it does, no digit should appear afterward.

• For example, "123abc" is valid, but "a1b2" is not.

1. Digits are non-decreasing:
   The digits must be in non-decreasing order. As we read through the digits from left to right, each digit must be greater than or equal to the previous one.

• For example, "1125" is valid, but "132" is not, because 3 comes before 2, which violates the order.

1. Letters are non-decreasing:
   The letters must also be in non-decreasing alphabetical order or remain the same.

• For example, "abc" and "aabbcc" are valid, but "acb" is not.

Implementation Approach:

• Iterate over the string character by character.
• Maintain two variables:
• One to track the last digit seen.
• One to track the last letter seen.
• If the current character is a digit:
• Check that it is not less than the last digit.
• If we have already seen a letter and then encounter a digit afterward, mark the key invalid immediately.
• If the current character is a letter:
• Check that it is not less than the last letter.

By applying these checks for each test case, we can determine whether a given access key is secure. If all conditions are satisfied, output "YES"; otherwise, output "NO". This approach is efficient and works well within the given constraints.

t = int(input())

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

    last_digit = '0'
    last_letter = 'a'
    seen_letter = False
    is_secure = True

    for ch in key:
        if ch.isdigit():
            if seen_letter:
                is_secure = False
                break
            if ch < last_digit:
                is_secure = False
                break
            last_digit = ch
        else:
            if ch < last_letter:
                is_secure = False
                break
            last_letter = ch
            seen_letter = True

    print("YES" if is_secure else "NO")

Jean wants to make as many hikes as possible. Each hike requires exactly $$$k$$$ consecutive days of good weather, meaning the weather values must be all zeros during those $$$k$$$ days.

Suppose we identify a continuous block of days where the weather is good (all zeros), and the block length is $$$len$$$. This means Jean has $$$len$$$ consecutive days suitable for hiking.

Each hike takes $$$k$$$ days, and after each hike, Jean must take a rest day before starting another hike. This means every hike plus its mandatory rest day consumes $$$k + 1$$$ days, except for the last hike in the block, which does not require a rest day afterward.

To handle this last hike exception neatly, we imagine adding an imaginary rest day at the end of the block, making the effective block length $$$len + 1$$$.

With this imaginary day included, the entire block can be divided into chunks of length $$$k + 1$$$, where each chunk represents one hike plus its rest day.

Therefore, the maximum number of hikes that fit in the block is calculated by:

where the keyword floor means rounding down to the nearest integer.

If the weather array contains multiple such blocks separated by rainy days (days with 1), we apply this formula to each block independently.

Finally, the sum of hikes from all blocks will be the maximum number of hikes Jean can make.

This approach efficiently accounts for both the length of consecutive good weather days and the mandatory rest days, allowing us to quickly compute the maximum hikes possible in the entire period.

t = int(input())

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

    hikes = 0
    length = 0

    for day in a:
        if day == 0:
            length += 1
        else:
            hikes += (length + 1) // (k + 1)
            length = 0

    hikes += (length + 1) // (k + 1)

    print(hikes)

To solve the problem efficiently, we need to understand the true cost of using a teleporter at position $$$i$$$. In order to use it, we must first walk from point 0 to point $$$i$$$, which costs $$$i$$$ coins since each step costs 1 coin. Then, we must pay an additional $$$a_i$$$ coins to activate the teleporter. Therefore, the total cost to use the teleporter at position $$$i$$$ is

Once we use a teleporter, we are immediately teleported back to point 0, and that specific teleporter becomes unusable.

This reset behavior means that each teleportation brings us back to the same starting point, making the decision to use a teleporter independent of previous choices. In other words, no matter what teleporters we used before, we are always at point 0 again with some coins remaining and a new subset of teleporters to choose from. This observation is key because it allows us to analyze and handle each teleportation individually, based solely on how much it costs.

With this in mind, the optimal strategy is to compute the total cost $$$i + a_i$$$ for each teleporter, then sort all teleporters by their total cost in ascending order. After sorting, we greedily select teleporters starting from the cheapest one, and for each, we subtract its cost from our total coins $$$c$$$. We continue this process until we can no longer afford the next cheapest teleporter. This greedy method guarantees the maximum number of teleporters we can use, as there is no benefit to delaying a cheaper one in favor of a more expensive option later.

In terms of time complexity, this approach is efficient and well within the problem's constraints. Calculating total costs takes $$$O(n)$$$, sorting the teleporters requires $$$O(n \log n)$$$, and the greedy selection phase runs in $$$O(n)$$$. Therefore, the overall complexity per test case is

Since the sum of $$$n$$$ over all test cases is constrained to $$$2 \times 10^5$$$, this solution performs well for all valid inputs.

t = int(input())
for _ in range(t):
    n, coin = map(int, input().split())
    costs = list(map(int, input().split()))
    total_costs = [i + costs[i - 1] for i in range(1, n + 1)]
    total_costs.sort()
    count = 0
    for cost in total_costs:
        if cost <= coin:
            coin -= cost
            count += 1
        else:
            break
    print(count)

Run DFS on $$$G$$$ to label components.

Cut edges in $$$F$$$ crossing $$$G$$$ groups, then count $$$F$$$ components via DFS.

To solve the problem, start by understanding the concept of connected components in a graph. A connected component is a set of vertices where each vertex can be reached from any other vertex in the same set by traversing edges.

• First, consider the original graph $$$G$$$.
• Using DFS (Depth-First Search) on $$$G$$$, assign a component index to each vertex.
• Vertices in the same component share the same index, while vertices in different components have different indices.

Next, examine the graph $$$F$$$ and its edges. For each edge in $$$F$$$:

• Check the component indices of the two vertices it connects according to $$$G$$$.
• If these vertices belong to different components in $$$G$$$ (i.e., their component indices differ), then this edge does not respect the connectivity of $$$G$$$ and should be removed from $$$F$$$.
• Each such removal counts as one operation.
• This step ensures that $$$F$$$ does not create connections that are not present in $$$G$$$.

After removing these invalid edges:

• Run DFS again on the updated graph $$$F$$$ to find its connected components.
• Count how many connected components $$$F$$$ has now.
• Since $$$F$$$ started as a subgraph of $$$G$$$ but had edges removed, it might have more connected components than $$$G$$$.
• To preserve $$$G$$$’s connectivity, the number of connected components in $$$F$$$ should be equal to that in $$$G$$$.
• If $$$F$$$ has more connected components, you need to perform operations to fix the connectivity — essentially, connecting these components back together.

The number of operations needed is:

Thus, the total operations to transform $$$F$$$ to have the same connectivity as $$$G$$$ is:

• The sum of edges removed plus
• The number of connectivity fixes described above.

Summary:

• Use DFS to find connected components in both graphs.
• Remove edges in $$$F$$$ that violate $G$’s connectivity.
• Calculate how many connectivity fixes are needed to make $$$F$$$ and $$$G$$$ equivalent in terms of connected vertices.
• This DFS-based approach efficiently solves the problem without requiring more advanced data structures like DSU.

from collections import defaultdict
 
 
def dfs(node, adj, visited, component_id, comp_id):
    stack = [node]
    while stack:
        curr = stack.pop()
        if visited[curr]:
            continue
        visited[curr] = True
        component_id[curr] = comp_id
        for neighbor in adj[curr]:
            if not visited[neighbor]:
                stack.append(neighbor)
 
t = int(input())
for _ in range(t):
    n, m1, m2 = map(int, input().split())
    
    F_adj = [[] for _ in range(n + 1)]
    G_adj = [[] for _ in range(n + 1)]
    F_edges = []
 
    for _ in range(m1):
        u, v = map(int, input().split())
        F_adj[u].append(v)
        F_adj[v].append(u)
        F_edges.append((u, v))
 
    for _ in range(m2):
        u, v = map(int, input().split())
        G_adj[u].append(v)
        G_adj[v].append(u)
 
    # Build G components
    g_component = [0] * (n + 1)
    visited = [False] * (n + 1)
    g_id = 1
    for i in range(1, n + 1):
        if not visited[i]:
            dfs(i, G_adj, visited, g_component, g_id)
            g_id += 1
 
    # rmove edges in F that violate G connectivi
    remove_count = 0
    new_F_adj = [[] for _ in range(n + 1)]
    for u, v in F_edges:
        if g_component[u] != g_component[v]:
            remove_count += 1
        else:
            new_F_adj[u].append(v)
            new_F_adj[v].append(u)
 
    # build F components on filtered F graph
    f_component = [0] * (n + 1)
    visited = [False] * (n + 1)
    f_id = 1
    for i in range(1, n + 1):
        if not visited[i]:
            dfs(i, new_F_adj, visited, f_component, f_id)
            f_id += 1
 
    g_to_f = defaultdict(set)
    for i in range(1, n + 1):
        g_to_f[g_component[i]].add(f_component[i])
 
    add_count = sum(len(s) - 1 for s in g_to_f.values())
    print(remove_count + add_count)

There is a powerful technique called Disjoint Set Union (DSU) or Union-Find that can solve this problem more efficiently. DSU helps quickly find and merge connected components without needing repeated DFS traversals. Although you haven't learned DSU yet, you will study it in the future, and mastering it will make solving connectivity problems like this much easier and faster..

Look at pairs of names and notice where they first differ.

Think about how letter orders can be arranged to satisfy these differences.

Let’s start by understanding what it means when we say one string $$$S$$$ is less than another string $$$T$$$ in lexicographical order. Suppose $$$S = \text{abcxyz}$$$ and $$$T = \text{abcuv}$$$. According to the definition of lex order, $$$S \lt T$$$ if and only if the first position where they differ determines the order. In this example, the first differing characters are $$$x$$$ in $$$S$$$ and $$$u$$$ in $$$T$$$. So, $$$S \lt T$$$ holds if and only if $$$x \lt u$$$ in the alphabet order we are trying to find.

From this observation, we can transform the problem of comparing whole strings into constraints about the order of individual letters. For every pair of consecutive names $$$\text{name}_1 \lt \text{name}_2$$$, $$$\text{name}_2 \lt \text{name}_3$$$, and so on, we extract the relationship between letters where they first differ. These relationships give us inequalities like $$$x \lt u$$$.

The core question then becomes: Is there a permutation of the alphabet that satisfies all these letter-order conditions? This is a classic problem of finding a topological order in a directed graph. Each letter represents a node, and the inequalities correspond to directed edges between nodes. If a valid topological order exists, it represents a letter ordering that satisfies all constraints.

However, there is a tricky case to consider. Suppose we have a condition like $$$xy \lt x$$$, meaning a longer string starting with $$$xy$$$ is less than its prefix $$$x$$$. According to lexicographical rules, this cannot happen since a prefix is always less than a longer string that starts with it. If such a case appears, then no valid letter ordering exists, and the answer is no solution.

This careful check is essential because such cases might not appear in pretests but can occur in some inputs, so it’s important to handle them explicitly.

Time Complexity:

Let $$$n$$$ be the number of names and $$$L$$$ be the maximum length of a name. Comparing consecutive names takes $$$O(L)$$$ time per pair, so extracting all constraints requires $$$O(n \times L)$$$. Building the graph for letters involves at most 26 nodes (for each Latin letter), so topological sorting runs in $$$O(26 + E)$$$, where $$$E$$$ is the number of edges (constraints), which is at most $$$O(n)$$$. Overall, the solution runs efficiently within $$$O(n \times L)$$$ time, suitable for the given problem constraints.

from collections import deque
 
n = int(input())
words = [input().strip() for _ in range(n)]
 
def helper():
    graph = [[] for _ in range(26)]
    in_degree = [0 for _ in range(26)]
    
    for i in range(n - 1):
        word1 = words[i]
        word2 = words[i + 1]
        pointer = 0
        
        while pointer < len(word1) and pointer < len(word2):
            if word1[pointer] != word2[pointer]:
                index1 = ord(word1[pointer]) - ord("a")
                index2 = ord(word2[pointer]) - ord("a")
                graph[index1].append(index2)
                in_degree[index2] += 1
                break
            pointer += 1
        
        if pointer == len(word2) and len(word1) > len(word2):
            return "Impossible"
    
    queue = deque()
    for i in range(26):
        if in_degree[i] == 0:
            queue.append(i)
    
    order = []
    while queue:
        curr = queue.popleft()
        order.append(curr)
        for neighbor in graph[curr]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(order) < 26:
        return "Impossible"
    
    return ''.join(chr(i + ord('a')) for i in order)
 
print(helper())

Explore the graph using DFS and pay attention to the edges that point back to ancestors.

Separate edges into two groups based on their role in DFS to avoid cycles within a color.

The problem involves coloring the edges of a directed graph to avoid cycles formed by edges of the same color. One effective approach is to run a DFS (Depth-First Search) on the graph and classify edges into two types based on the DFS traversal:

• Back edges: These are edges $$$(u,v)$$$ where $$$v$$$ is an ancestor of $$$u$$$ in the DFS tree. In other words, there is a path from $$$v$$$ to $$$u$$$ using tree edges, and $$$(u,v)$$$ points back up the DFS tree.

• Non-back edges (white edges): These include tree edges, forward edges, and cross edges, which do not point back to ancestors in the DFS tree.

The coloring strategy is to color all back edges with one color (say, black) and all other edges with another color (say, white). This is guaranteed to produce a good 2-coloring, meaning that there will be no monochromatic cycles.

Why does this work?

It can be proven that any cycle in the graph must contain at least one back edge and at least one non-back (white) edge. This is because cycles “wrap around” in the graph, and the presence of back edges reflects these backward connections. Each back edge directly participates in forming at least one cycle by connecting a descendant node back to an ancestor.

To understand this further, consider how vertices can be renumbered based on DFS traversal. We assign an ID to each vertex such that the ID of a parent vertex $$$id(p)$$$ is greater than the IDs of all its children $$$id(c)$$$. This is done by processing children first and then assigning the minimal free number to the parent after processing all its descendants.

With this numbering, we can observe the following:

• For white edges $$$(u,v)$$$ (including tree, forward, and cross edges), the condition $$$id(u) \gt id(v)$$$ always holds. This is because:
• Forward edges go from ancestors to descendants, so $$$id(u) \gt id(v)$$$.
• Cross edges go between already visited nodes where $$$v$$$ was processed before $$$u$$$, so $$$id(v) \lt id(u)$$$.

• For back edges $$$(u,v)$$$, the opposite condition holds: $$$id(u) \lt id(v)$$$, since the edge points from a descendant back to an ancestor.

Since any cycle contains edges where $$$id(u) \gt id(v)$$$ and edges where $$$id(u) \lt id(v)$$$, it must contain both white and black edges. This ensures that no cycle can be formed entirely from edges of the same color, which is exactly what a good coloring requires.

In summary, by using DFS to separate edges into back and non-back edges and coloring them differently, we guarantee a minimal 2-coloring where no monochromatic cycles exist. This approach efficiently solves the problem of minimum good coloring.

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
edges = []
 
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append((v, i))
    edges.append((u, v))
 
color = [0] * m
visited = [0] * n
need_two_colors = False
 
def dfs(u):
    global need_two_colors
    visited[u] = 1
    for v, idx in graph[u]:
        if visited[v] == 0:
            color[idx] = 1
            dfs(v)
        elif visited[v] == 1:
            color[idx] = 2
            need_two_colors = True
        else:
            color[idx] = 1
    visited[u] = 2
 
for i in range(n):
    if visited[i] == 0:
        dfs(i)
 
if need_two_colors:
    print(2)
else:
    print(1)
print(*color)

To check if an amount $$$n$$$ can be formed using coins of denominations $$$2$$$ and $$$k$$$ (with $$$k \ne 2$$$), we can simplify the problem using a key observation: two $$$k$$$-coins can be replaced by $$$k$$$ coins of $$$2$$$, since $$$2k = k \cdot 2$$$.

This means any solution using two or more $$$k$$$-coins can be transformed into one with at most one $$$k$$$-coin. So, we only need to check two cases:

Use only $$$2$$$-coins: possible if $$$n$$$ is even.

Use one $$$k$$$-coin and the rest $$$2$$$-coins: possible if $$$n \ge k$$$ and $$$n - k$$$ is even.

If either condition holds, the answer is "YES"; otherwise, it's "NO". This allows each test case to be solved in constant time.

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    if n % 2 == 0 or (n >= k and (n - k) % 2 == 0):
        print("YES")
    else:
        print("NO")

In this problem, we are given a sequence of cells arranged in a line (from $$$1$$$ to $$$n$$$) with portals between some of them. The portals are one-way and described using an array $$$a$$$, where each element $$$a_i$$$ tells us that from cell $$$i$$$, we can move forward to cell $$$i + a_i$$$. We begin at cell $$$1$$$ and are asked to determine whether we can reach cell $$$t$$$ using only the available portals.

This structure can be interpreted as a directed graph, where each node (cell) has exactly one outgoing edge (as described by the portals). Since we only move forward and there is no branching (each node goes to exactly one next node), we can simulate this as a simple linear traversal—essentially a simplified depth-first search (DFS) or a loop—starting from cell $$$1$$$ and following the portals until we either reach cell $$$t$$$ or go past it.

We continue moving from the current cell to the next one given by the portal, i.e., from $$$i$$$ to $$$i + a_i$$$, and check at each step whether we've landed at cell $$$t$$$. If we do, we output "YES". If we go beyond it or reach a point from which we can no longer progress toward $$$t$$$, we conclude it's unreachable and output "NO."

This logic runs in linear time and is highly efficient due to the constraint that each cell leads to only one next cell.

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

pos = 1
while pos < t:
    pos += a[pos - 1]

if pos == t:
    print("YES")
else:
    print("NO")

We are given a grid where each cell contains a non-negative integer representing the depth of water. A lake is defined as a group of connected cells (connected up, down, left, or right) that all have positive depth (greater than zero). Our goal is to find the lake with the largest total volume, where volume is the sum of depths of all cells in that lake.

To solve this, we can use either Depth-First Search (DFS) or Breadth-First Search (BFS). The idea is to explore the grid cell by cell. Whenever we find a cell with depth greater than zero that we haven’t visited before, we start a DFS/BFS from that cell to find all connected cells belonging to the same lake. During this traversal, we accumulate the total depth (volume) of the lake.

After completing the search for a lake, we compare its volume with the maximum volume found so far and update if needed. We repeat this process until all cells have been checked.

This approach ensures that each cell is visited at most once, resulting in an overall time complexity of $$$O(nm)$$$ where $$$n$$$ and $$$m$$$ are the grid dimensions. This is efficient enough given the problem constraints.

Implementing the search iteratively (using a stack for DFS or a queue for BFS) instead of recursively often gives better performance in practice, avoiding the overhead and limitations of recursion and reducing the risk of stack overflow on large inputs.

import sys
input = sys.stdin.readline

t = int(input())
directions = [(1,0), (-1,0), (0,1), (0,-1)]

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
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] > 0 and not visited[i][j]:
                stack = [(i,j)]
                volume = 0
                visited[i][j] = True
                
                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 grid[nx][ny] > 0 and not visited[nx][ny]:
                                visited[nx][ny] = True
                                stack.append((nx, ny))
                
                if volume > max_volume:
                    max_volume = volume
    
    print(max_volume)

The problem models a 3D plate composed of $$$k$$$ layers, each layer being a 2D grid of size $$$n \times m$$$. Some cells are empty '.', where water can fill, and some contain obstacles '#' that block water flow. Water starts pouring from a specific cell in the top layer and flows to adjacent cells in all 6 directions — up, down, left, right, forward, and backward — but only through empty cells.

To determine how many units of water the plate can hold before overflowing, the key is to find how many empty cells are reachable from the starting tap position. Each reachable empty cell can hold exactly one unit of water. Therefore, the answer is the count of all connected empty cells accessible from the tap.

The solution treats the plate as a 3D grid and performs a Depth-First Search (DFS) starting from the tap’s cell in the top layer. DFS explores all neighboring cells in the six possible directions — vertically between layers, horizontally between rows, and laterally between columns — as long as those cells are within bounds, empty, and not yet visited. This exploration simulates the spread of water filling every reachable empty cell.

The code first reads the 3D grid input carefully, handling blank lines between layers, and converts the coordinates of the tap to zero-based indexing. Then, it initializes a 3D visited array to keep track of cells already counted. The DFS uses an explicit stack to avoid recursion limits and traverses all accessible cells, counting each as water volume.

Finally, the total count of reachable cells represents how many minutes until the plate is completely filled (since one unit of water falls each minute). If the water falls beyond this count, it would overflow, so the answer is this count.

This approach efficiently solves the problem in time complexity $$$O(kmn)$$$ since each cell is visited at most once, which is practical given the problem constraints.

def read_3d_grid():
    d, r, c = map(int, input().split())
    grid = []
    layers_read = 0

    while layers_read < d:
        line = input().strip()
        if line == "":
            continue
        layer = [list(line)]
        for _ in range(r - 1):
            layer.append(list(input().strip()))
        grid.append(layer)
        layers_read += 1

    while True:
        start_line = input().strip()
        if start_line:
            break

    start_x, start_y = map(int, start_line.split())
    start_x -= 1
    start_y -= 1

    return d, r, c, grid, start_x, start_y


def in_bounds(z, x, y, d, r, c):
    return 0 <= z < d and 0 <= x < r and 0 <= y < c


def dfs(z, x, y, grid, visited, d, r, c):
    stack = [(z, x, y)]
    visited[z][x][y] = True
    minutes = 0

    directions = [
        (1, 0, 0), (-1, 0, 0),
        (0, 1, 0), (0, -1, 0),
        (0, 0, 1), (0, 0, -1)
    ]

    while stack:
        cz, cx, cy = stack.pop()
        minutes += 1

        for dz, dx, dy in directions:
            nz, nx, ny = cz + dz, cx + dx, cy + dy
            if in_bounds(nz, nx, ny, d, r, c):
                if not visited[nz][nx][ny] and grid[nz][nx][ny] == '.':
                    visited[nz][nx][ny] = True
                    stack.append((nz, nx, ny))

    return minutes


d, r, c, grid, start_x, start_y = read_3d_grid()
visited = [[[False for _ in range(c)] for _ in range(r)] for _ in range(d)]

start_layer = 0

if grid[start_layer][start_x][start_y] == '.':
    minutes_until_overflow = dfs(start_layer, start_x, start_y, grid, visited, d, r, c)
else:
    minutes_until_overflow = 0

print(minutes_until_overflow)

We are given a graph with $$$n$$$ nodes and $$$m$$$ edges. Among these nodes, $$$k$$$ are designated as government nodes. The graph is stable, which means each connected component contains at most one government node, and there are no paths between different government nodes. Our task is to add as many new edges as possible while keeping the graph stable.

The first step is to analyze each connected component of the graph. In any single component, as long as it contains at most one government node, we are free to add edges. The optimal way to do this is to turn each component into a complete graph (clique), where every pair of nodes is connected. For a component of size $$$s$$$, the maximum number of edges it can contain is $$$s \cdot (s - 1) / 2$$$. If the component currently has $$$e$$$ edges, then we can add $$$s \cdot (s - 1) / 2 - e$$$ new edges.

Some components may not contain any government node. These components can be safely merged with a government component without violating stability, because the resulting component will still have at most one government node. To maximize the number of new edges, we should merge all non-government components into the largest government component. This is because merging a component of size $$$a$$$ with one of size $$$b$$$ allows us to add $$$a \cdot b$$$ new edges. So, the more nodes the government component has, the more beneficial the merge becomes.

To implement the solution, we use depth-first search (DFS) or union-find to identify all connected components and determine which ones have government nodes. We then calculate the number of edges we can add to make each component a clique. After identifying the non-government components, we calculate their total size and merge them into the largest government component, adding $$$x \cdot L$$$ additional edges, where $$$x$$$ is the number of non-government nodes and $$$L$$$ is the size of the largest government component.

The final answer is the sum of all possible new edges minus the $$$m$$$ edges that already exist.

This approach runs in linear time relative to the number of nodes and edges, with an overall time complexity of $$$O(n + m)$$$.

def solve():
    import sys
    input = sys.stdin.readline

    n, m, k = map(int, input().split())
    special = set(map(int, input().split()))

    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * (n + 1)

    def dfs(start):
        stack = [start]
        visited[start] = True
        size = 0
        has_special = False
        while stack:
            node = stack.pop()
            size += 1
            if node in special:
                has_special = True
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    stack.append(neighbor)
        return size, has_special

    def combination(x):
        return x * (x - 1) // 2

    total_non_special = 0
    largest_special_size = 0
    special_sum = 0

    for i in range(1, n + 1):
        if not visited[i]:
            size, has_special = dfs(i)
            if has_special:
                special_sum += combination(size)
                largest_special_size = max(largest_special_size, size)
            else:
                total_non_special += size

    # Recalculate contribution of largest special component
    special_sum -= combination(largest_special_size)
    special_sum += combination(largest_special_size + total_non_special)

    result = special_sum - m
    print(result)

solve()

We are given a connected undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The task is to remove exactly one edge so that the number of vertex pairs $$$(u, v)$$$ with $$$1 \le u \lt v \le n$$$ that are still connected by some path becomes as small as possible.

Initially, since the graph is connected, every pair of vertices is reachable. This means there are $$$\frac{n \cdot (n - 1)}{2}$$$ reachable pairs. If we remove any edge that is not a bridge, the graph remains connected, and the number of reachable pairs stays exactly the same. So, in order to reduce the number of reachable pairs, we must remove a bridge.

A bridge is an edge whose removal increases the number of connected components in the graph. In other words, if we remove a bridge, the graph splits into two disconnected components. Let the sizes of these two components be $$$x$$$ and $$$y$$$, where $$$x + y = n$$$. After the split, only pairs within the same component remain reachable. So the new number of reachable pairs becomes $$$\frac{x \cdot (x - 1)}{2} + \frac{y \cdot (y - 1)}{2}$$$.

Our goal is to find the bridge whose removal results in the smallest possible total of reachable pairs. To do that, we can perform a DFS traversal to find all bridges in the graph. While doing so, we also compute the subtree size for each node. Suppose we are processing a bridge edge $$$(u, v)$$$ where $$$v$$$ is in the subtree of $$$u$$$. Then, one of the resulting components will have size equal to the subtree size of $$$v$$$, and the other will have size $$$n - \text{subtree}[v]$$$.

For every bridge, we calculate the number of reachable pairs after its removal using the formula above, and we keep track of the minimum among them. If no bridges exist, then removing any edge won't disconnect the graph, and the answer remains $$$\frac{n \cdot (n - 1)}{2}$$$.

This solution is efficient. Finding bridges and computing subtree sizes via DFS both take linear time, so each test case runs in $$$O(n + m)$$$ time. Since the total sum of $$$n$$$ and $$$m$$$ over all test cases is limited to $$$2 \cdot 10^5$$$, the solution fits comfortably within the time limits.

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        graph = [[] for _ in range(n + 1)]
        for _ in range(m):
            u, v = map(int, input().split())
            graph[u].append(v)
            graph[v].append(u)

        tin = [0] * (n + 1)
        low = [0] * (n + 1)
        visited = [False] * (n + 1)
        size = [1] * (n + 1)
        bridges = []

        timer = 1
        stack = []
        parent = [-1] * (n + 1)
        neighbors_idx = [0] * (n + 1)

        stack.append(1)
        visited[1] = True
        tin[1] = low[1] = timer
        timer += 1

        while stack:
            u = stack[-1]
            if neighbors_idx[u] < len(graph[u]):
                v = graph[u][neighbors_idx[u]]
                neighbors_idx[u] += 1

                if v == parent[u]:
                    continue

                if not visited[v]:
                    visited[v] = True
                    tin[v] = low[v] = timer
                    timer += 1
                    parent[v] = u
                    stack.append(v)
                else:
                    low[u] = min(low[u], tin[v])
            else:
                stack.pop()
                p = parent[u]
                if p != -1:
                    low[p] = min(low[p], low[u])
                    size[p] += size[u]
                    if low[u] > tin[p]:
                        # Found a bridge between p and u
                        bridges.append((p, u))

        total_pairs = n * (n - 1) // 2

        if not bridges:
            print(total_pairs)
            continue

        max_cut = 0
        for u, v in bridges:
            x = min(size[u], size[v])

            part1_after_cut = (n - x) * (n - x - 1) // 2
            part2_after_cut = x * (x - 1) // 2

            cut_value = total_pairs - (part1_after_cut + part2_after_cut)

            max_cut = max(max_cut, cut_value)

        print(total_pairs - max_cut)

solve()

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

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

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

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

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

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

max_non_square = -10**6 - 1

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

print(max_non_square)

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

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

To solve this problem: Sort the array a.

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

We can use upper_bound logic for that.

Time Complexity:

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

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

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

import sys 
input = sys.stdin.readline 

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

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

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

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

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

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

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

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

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

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

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

print(n - ans)

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

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

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

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

import bisect

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

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

solve()

We can solve this problem greedily. Let's choose the first element to be $$$l$$$. The second element will be $$$l + 1$$$, the third will be $$$l + 3$$$, and so on. In general, the $$$i$$$-th element is given by $$$l + \frac{i \cdot (i + 1)}{2}$$$.

Why does this work? Assume the array $$$a$$$ is the one built by our greedy algorithm, and suppose there's a better array $$$b$$$ such that $$$\text{len}(b) \gt \text{len}(a)$$$. Because of how we construct $$$a$$$, there must exist some index $$$i$$$ such that for all $$$j \lt i$$$, we have $$$a_j = b_j$$$, and at index $$$i$$$, $$$a_i \lt b_i$$$ (since we always pick the smallest valid number possible).

Without loss of generality, assume $$$\text{len}(b) = \text{len}(a) + 1 = n$$$. Then, observe that the gap between the last two elements of $$$b$$$ must grow: $$$b_n - b_{n-1} \gt b_{n-1} - b_{n-2} \ge a_{n-1} - a_{n-2}$$$. But this means we could have added $$$b_n$$$ to the array $$$a$$$, which contradicts our assumption that $$$a$$$ was the longest valid array. So, the greedy approach gives us the optimal sequence.

Now the goal is to find the largest $$$x$$$ such that $$$l + \frac{x \cdot (x + 1)}{2} \le r$$$. We can do this efficiently using binary search, by solving the inequality directly using the discriminant of the corresponding quadratic equation, or even by brute force if the bounds allow.

t = int(input())
for _ in range(t):
    l, r = map(int, input().split())
    low, high = 1, int(2e5)
    ans = 1
    while low <= high:
        mid = (low + high) // 2
        total = mid * (mid - 1) // 2
        if l + total <= r:
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    print(ans)

To solve the problem of finding the $$$k$$$-th positive integer that is not divisible by $$$n$$$, we need to understand how the count of such numbers behaves. If we simply count up to $$$k$$$, we might mistakenly include numbers that are divisible by $$$n$$$, which we must skip. For example, if $$$n = 3$$$ and $$$k = 7$$$, then just taking the first 7 numbers gives us: $$$1, 2, 3, 4, 5, 6, 7$$$, but 3 and 6 are divisible by 3, so we actually have only 5 valid numbers among them. So, we need to find a number $$$x$$$ such that there are exactly $$$k$$$ numbers from $$$1$$$ to $$$x$$$ that are not divisible by $$$n$$$.

The number of integers from $$$1$$$ to $$$x$$$ that are divisible by $$$n$$$ is given by $$$\left\lfloor \frac{x}{n} \right\rfloor$$$. Hence, the number of integers in that range not divisible by $$$n$$$ is $$$x - \left\lfloor \frac{x}{n} \right\rfloor$$$. Our goal is to find the smallest $$$x$$$ for which this expression equals $$$k$$$. Since the function $$$x - \left\lfloor \frac{x}{n} \right\rfloor$$$ increases as $$$x$$$ increases, we can use binary search to efficiently find the minimum such $$$x$$$.

We start the binary search with a reasonable upper limit like $$$2k$$$, since in the worst case every $$$n$$$-th number is divisible and we're skipping one number every $$$n$$$ steps. In each step of the binary search, we compute how many non-divisible numbers exist up to the mid-point using the formula $$$mid - \left\lfloor \frac{mid}{n} \right\rfloor$$$. If this number is less than $$$k$$$, we need to search in the right half (i.e., higher values of $$$x$$$). Otherwise, we search in the left half, trying to find a smaller valid $$$x$$$. Once we find the smallest $$$x$$$ that satisfies the condition, it will be the $$$k$$$-th number that is not divisible by $$$n$$$.

This approach ensures that we solve each test case in logarithmic time, making it efficient even for large values of $$$k$$$ and $$$n$$$ up to $$$10^9$$$.

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    low, high = 1, 2 * k
    ans = -1
    while low <= high:
        mid = (low + high) // 2
        count = mid - (mid // n)
        if count >= k:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    print(ans)

To solve the "Place of the Olympiad" problem efficiently, we aim to minimize the length of the longest bench while seating all the participants in the available rows and columns. The key observation is that the number of desks that can be placed in one row increases as the length of the longest bench increases. This means we can use a binary search over possible bench lengths to find the minimum possible value of the longest bench that still allows seating all the participants.

In each test case, we are given n rows, m columns, and k participants. The objective is to find the minimum value of x, the maximum bench length, such that we can fit all k participants within the constraints. The number of desks we can fit in one row depends on how many benches of length x can be formed in a row, and the total number of desks across all rows is the sum of the desks in each row. Using binary search, we determine the smallest x where the total number of desks fits k.

The binary search approach works by checking the number of desks that can be placed in n rows with a given maximum bench length x. If the total number of desks is sufficient, we attempt to reduce x; otherwise, we increase x. This process continues until we find the smallest x that satisfies the condition.

def is_valid(n, m, k, x):
    row_capacity = x * (m // (x + 1)) + (m % (x + 1))
    total_capacity = n * row_capacity
    return total_capacity >= k

def solve(n, m, k):
    low, high = 1, m
    answer = m
    
    while low <= high:
        mid = (low + high) // 2
        if is_valid(n, m, k, mid):
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    
    return answer

t = int(input())
for _ in range(t):
    n, m, k = map(int, input().split())
    print(solve(n, m, k))

Problem Explanation:

We need to find a sequence of ( n ) distinct integers ( a_1, a_2, \dots, a_n ) such that the difference between the maximum and minimum of the sequence equals the sum of all integers in the sequence. Specifically, we need to satisfy the following condition:

This means the largest number in the sequence minus the smallest number should equal the sum of all the elements in the sequence.

Approach:

Case 1: Odd ( n )

For odd values of ( n ), we begin by constructing a sequence of ( n ) consecutive integers centered around ( n ). This means that we take the range from ( \frac{n}{2} ) to ( \frac{3n}{2} ), creating a symmetric sequence. For example, if ( n = 5 ), the sequence would be:

This sequence is symmetric around the middle value and has a maximum difference of ( n — 1 ) between the smallest and largest numbers.

Next, we increase each of the integers by 2, ensuring that the difference between the smallest and largest element remains the same. So, the sequence ( [3, 4, 5, 6, 7] ) becomes:

This change increases the sum, and now the sum becomes ( n^2 + 2n ).

At this stage, we need to ensure the sum matches the target value of ( (n + 1)^2 ). The equation for this is:

To adjust the sequence to match the target sum, we make a slight modification. We increase the second-to-last element by 1. This gives us the final sequence that satisfies the condition:

For ( n = 5 ), after this adjustment, the sequence becomes:

This sequence now satisfies the condition because:

• The difference between the maximum (10) and minimum (4) is ( 10 — 4 = 6 ).
• The sum of the elements is ( 4 + 6 + 7 + 9 + 10 = 36 ), and ( 36 = 6 ).

Case 2: Even ( n )

For even values of ( n ), we can use a similar approach. The sequence is split into two parts. The first part is from ( \frac{n}{2} ) to ( n — 1 ), and the second part is from ( n + 1 ) to ( \frac{3n}{2} ). This ensures that the difference between the largest and smallest element is exactly ( n ), and the sum of the elements is ( n^2 ), making it a valid solution.

Conclusion:

The approach involves constructing a sequence of consecutive integers, adjusting the values slightly to match the required sum, and ensuring that the difference between the maximum and minimum elements equals the sum of all elements in the sequence. By carefully adjusting the sequence for both odd and even values of ( n ), we can generate a sequence that satisfies the given condition.

for _ in range(int(input())):
    n = int(input())
    if n % 2 == 0:
        arr = []
        for i in range(n // 2, n // 2 + n + 1):
            if i != n:
                arr.append(i)
        print(*arr)
    else:
        arr = []
        for i in range(n // 2 + 3, n // 2 + 3 + n):
            arr.append(i)
        arr[0] -= 1
        arr[-1] += 1
        arr[-2] += 1
        print(*arr)

Split the input into three strings, take the first character of each, and join them.

for _ in range(int(input())):
  print(''.join(x[0] for x in input().split()))

We use a stack to keep track of characters. For each character, if it matches the top of the stack, we remove the top (both letters cancel out). Otherwise, we push the current character onto the stack. At the end, the stack contains the corrected string without consecutive duplicates.

python s=input() st=[] for c in s: if st and st[-1]==c: st.pop() else: st.append(c) print(''.join(st))

To solve this problem, we simulate the bombing process using a stack. We process each character of the string from left to right. If the current character is 'B' and the top of the stack is either 'A' or 'B', it means we have found a bombable substring ("AB" or "BB"), so we remove the top character from the stack (this simulates bombing and removing the substring). If not, we simply push the current character onto the stack. After processing the entire string, the stack will contain the characters that could not be bombed. Therefore, the length of the stack gives the length of the shortest string that BoomBoom can make. This approach is efficient, working in linear time relative to the size of the string.

t = int(input())
for _ in range(t):
    s = input()
    st = []
    for c in s:
        if c == 'B' and st and st[-1] in 'AB':
            st.pop()
        else:
            st.append(c)
    print(len(st))

The problem involves determining whether two wires ("plus" and "minus") can be untangled based on a sequence of their relative positions. The sequence consists of + and -, where + means the "plus" wire is above the "minus" wire, and — means the "minus" wire is above the "plus" wire. The goal is to check if the sequence of these crossings can be resolved by simple operations such as moving the wires over each other. The approach simulates this by using a stack-like structure to keep track of the wire crossings. Every time the wires cross in an alternating manner (e.g., a + followed by a -), we add it to the stack. If the same crossing repeats (like two +s or two -s consecutively), we pop the last element from the stack, essentially removing the crossed wires and simulating the untangling.

The key idea behind this solution is that each crossing that needs to be removed forms a pair (either ++ or --). Thus, we can think of this as matching pairs of crossings. As we traverse the sequence, if we encounter a character that matches the last one in the stack, we remove the last one. This operation models the untangling process, where crossing wires cancel each other. After processing the entire sequence, if the stack is empty, it indicates that all crossings have been untangled, and the answer is "Yes." Otherwise, if there are remaining elements in the stack, it means the wires are still tangled, and the answer is "No."

wire = input()
result = []

for val in wire:
    if not result:
        result.append(val)
        continue
    if result[-1] != val:
        result.append(val)
    else:
        while result and val == result[-1]:
            result.pop()

if result:
    print('No')
else:
    print('Yes')

The problem requires constructing a lexicographically minimal string from a given input string s by using a stack-based approach. The strategy is to use a stack to store characters while ensuring that the result string remains in the smallest possible lexicographical order. The core idea is to push characters from s into the stack, and at each step, we check if the current character at the top of the stack should be popped to form the smallest possible result.

To achieve this, we first preprocess the string s to count the occurrences of each character. Then, for each character in s, we append it to the stack and decrease its count. After that, we check if the character at the top of the stack can be removed by checking whether any smaller character still exists in the remainder of the string. If a smaller character exists, we stop popping and move to the next character.

The algorithm ensures that the string u formed by popping characters from the stack is lexicographically minimal. The key condition is that we always push a character to the stack but only pop it if no smaller character is remaining further down the string.

The time complexity of this approach is O(n), where n is the length of the string s. Each character is pushed and popped from the stack at most once. The inner loop for checking smaller characters runs in constant time because we only check the count array, which has a fixed size of 26. Therefore, the overall time complexity is linear with respect to the length of the input string.

s = input()
count = [0] * 26
for c in s:
    count[ord(c) - ord('a')] += 1

stack = []
answer = []

for c in s:
    idx = ord(c) - ord('a')
    stack.append(c)
    count[idx] -= 1

    while stack:
        top = stack[-1]
        top_idx = ord(top) - ord('a')

        if any(count[i] > 0 for i in range(top_idx)):
            break
        answer.append(stack.pop())

print(''.join(answer))

Think of the operations in reverse order instead of forward.

Track a balance at each step. balance = push count − pop count

We solve the problem by reversing the way we think about stack operations. Instead of applying operations in their original order, we reverse them. In this reversed sequence, the top of the stack after any number of operations will correspond to the first push(x) operation whose contribution has not been canceled out by earlier pop() operations. To track this efficiently, we define a quantity called balance at each operation position. Formally, balance[i] = (number of push operations up to i) − (number of pop operations up to i). When a push(x) occurs, the balance increases by +1; when a pop() occurs, the balance decreases by -1. Therefore, at any moment, the element at the top of the stack corresponds to the first operation where the balance becomes positive.

To manage this efficiently, we use a structured approach to track balances quickly. Instead of calling it a complicated "segment tree," we think of it as a balance tracking tree. In this tree, we maintain two things: max_balances[i], which keeps the maximum balance in the subtree rooted at node i, and total_balances[i], which keeps the total balance sum in that subtree. When a new operation at position p is remembered, if it is a push(x), we set the balance at that position to +1; if it is a pop(), we set the balance to -1. Then, we propagate this change upwards through the tree to keep all balances and maximum values correct.

Once balances are updated, to find the current top of the stack, we start from the root of the tree and always prioritize moving toward the right child if it has a positive maximum balance. If not, we adjust our offset (running sum) by adding the total balance of the right child and move to the left child. This way, once we reach a leaf node, we directly find the operation that corresponds to the top value on the stack. This traversal guarantees that we always find the first push(x) that has not been canceled by enough pop() operations.

The efficiency of this method comes from the fact that each update or query takes only O(log m) time, where m is the number of operations. Since Malak remembers each of the m operations one by one, the total time complexity is O(m log m), which is perfectly acceptable even for large m (up to 10⁵). Thus, the approach is both intuitive when thought of as balancing pushes and pops and highly efficient thanks to the structure used for tracking.

m = int(input())
N = 1
while N < m:
    N *= 2

max_balances = [0] * (2 * N)
total_balances = [0] * (2 * N)
values = [0] * m

for _ in range(m):
    parts = input().split()
    p = int(parts[0])
    t = int(parts[1])

    if t == 0:
        max_balances[N + p - 1] = 0
        total_balances[N + p - 1] = -1
    else:
        x = int(parts[2])
        values[p - 1] = x
        max_balances[N + p - 1] = 1
        total_balances[N + p - 1] = 1

    j = (N + p - 1) // 2
    while j >= 1:
        total_balances[j] = total_balances[2 * j] + total_balances[2 * j + 1]
        max_balances[j] = max(
            max_balances[2 * j + 1],
            max_balances[2 * j] + total_balances[2 * j + 1],
            0
        )
        j //= 2

    if max_balances[1] == 0:
        print(-1)
        continue

    j = 1
    offset = 0
    while j < N:
        if max_balances[2 * j + 1] + offset > 0:
            j = 2 * j + 1
        else:
            offset += total_balances[2 * j + 1]
            j = 2 * j

    print(values[j - N])

There is four possible outcomes to this problem, if there has been both a '>' and '<' in your string , then you cant determine the winner so you return '?'. with that case out of the way you just need to keep track of if theres been a '<' or '>' since we know both couldnt have been there, so which ever one you find, you print, if its neither , you can return '='.

for _ in range(int(input())):
	s = input()
	if '<' in s and '>' in s:
		print('?')
	elif '<' in s:
		print('<')
	elif '>' in s:
		print('>')
	else:
		print('=')

The problem requires selecting k computers with the highest possible equal internet speed, given that we can only decrease speeds but not increase them. A simple and efficient approach is to sort the array in descending order and directly pick the k-th largest speed, as this ensures we select the highest possible speed that at least k computers can have. Alternatively, a brute-force approach involves iterating through potential speeds and counting how many computers can support them, keeping track of the maximum valid speed. Due to the weak constraints (n ≤ 100), both approaches work efficiently, with sorting providing an O(n log n) solution.

n, k = map(int, input().split())
print(sorted(map(int, input().split()))[n - k])

The problem involves ensuring that at least B liters of water flow out of the first hole by blocking the minimum number of holes. The flow from each hole is proportional to its size, and the goal is to maximize the flow from the first hole. We calculate the total sum of hole sizes and sort the remaining holes. By iteratively blocking the smallest holes, we reduce the total size until the flow from the first hole meets or exceeds B. The solution involves sorting and a greedy approach to block the smallest contributors first.

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

s = sum(arr)
res = sorted(arr[1:])
count = 0

while arr[0] * a / s < b:
    s -= res.pop()
    count += 1

print(count)

You’re given an NXM grid where each cell has an initial color. A stranger set is a group of cells that:

1. All share the same color.
2. No two cells in the set share a side (cells can touch diagonally but not edge-to-edge).

In a single step, you can choose any such stranger set and repaint all its cells in any other color. The objective is to make all cells the same color using the fewest steps.

Key Insight

For each color(c):

• If no pair of adjacent cells has color(c), you can repaint all of those cells in 1 step. (They’re already pairwise strangers.)
• If at least one pair of adjacent cells has color color(c), you need 2 steps to repaint all cells of that color. (Because you can split the connected component into two “stranger” groups.)

Hence, define for each color(c):

• color(c) = 0 if (c) does not appear in the grid.
• color(c) = 1 if (c) appears, but never in two adjacent cells.
• color(c) = 2 if (c) appears and there is at least one pair of adjacent cells color(c).

Choosing the Final Color

• Let S be the sum of color(c) over every color c that appears.
  • In code, this is computed as sum(has_color ) + sum(adj_found), where has_color [c] is 1 if c appears, and adj_found[c] is 1 if c has adjacent cells.
• If you select some color C* as the final color, you do not need to repaint cells already in C*.
• The minimum steps required to unify the grid into a single color is:

result = S - max(cost(c))

In the code, max(cost(c)) = 1 + max(adj_found[c]). Hence, the final result is:

result = (sum(has_color ) + sum(adj_found)) - 1 - max(adj_found)

Complexity Analysis:

• Time Complexity: O(n*m):

  • O(n*m) to read the grid and determine adjacent cells.
  • O(n*m) to compute costs and find the maximum cost.

• Space Complexity: O(n*m):

  • We store the entire grid n*m elements.
  • We also maintain two arrays of size (n*m) + 1 to track which colors appear and whether they have adjacent cells.

import sys 
input = sys.stdin.readline 

def solve():
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for i in range(n)]
    has_color = [0] * (n * m + 1)
    adj_found= [0] * (n * m + 1)

    for i in range(n):
        for j in range(m):
            has_color[grid[i][j]] = 1

            if i + 1 < n and grid[i][j] == grid[i + 1][j]:
                adj_found[grid[i][j]] = 1
            if j + 1 < m and grid[i][j] == grid[i][j + 1]:
                adj_found[grid[i][j]] = 1

    print(sum(has_color) + sum(adj_found) - 1 - max(adj_found))

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

To determine whether a valid permutation can be formed using numbers initially marked as either blue or red, we can strategically adjust their values. The key observation is that red numbers should ideally occupy the higher positions in the permutation, while blue numbers should be placed in the lower positions. If at any point a blue number is larger than a red number in the permutation, we can swap their positions by incrementing the red number and decrementing the blue number accordingly. This ensures that if a solution exists, there is always an equivalent arrangement where the smallest blue numbers take the lowest available positions and the largest red numbers take the highest ones. To implement this approach, we first sort all elements based on their color, prioritizing blue numbers first, and then by their value. After sorting, we verify that each element can be adjusted to its expected position—blue numbers should be at least as large as their index so they can be reduced to fit, while red numbers should not exceed their index so they can be increased if necessary. If these conditions hold for all elements, a valid permutation can be constructed.

t = int(input())

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

    blue_chests = []
    red_chests = []

    for i in range(n):
        if chest_colors[i] == "B":
            blue_chests.append(chest_values[i])
        else:
            red_chests.append(chest_values[i])

    blue_chests.sort()
    red_chests.sort()

    is_permutation_possible = True

    for i in range(len(blue_chests)):
        if blue_chests[i] < i + 1:
            is_permutation_possible = False

    for i in range(len(red_chests)):
        if red_chests[i] > (n - len(red_chests) + i + 1):
            is_permutation_possible = False

    print("YES" if is_permutation_possible else "NO")

The problem involves rearranging an array b to match the order of another array a using adjacent swaps. The key insight is that both arrays are guaranteed to be permutations of the same set of elements (i.e., they are multisets), meaning that we can always reorder b to match a. We start by creating a mapping of each value in a to its corresponding index, allowing us to track where each value from b should be placed in a. For each element in b, we replace it with the index from a, resulting in a list of target positions.Once we have this list of target positions, we simulate sorting it into the correct order using adjacent swaps (similar to bubble sort). At each step, we compare adjacent elements, and if they are in the wrong order, we swap them. We continue this process until the list is sorted, recording each swap. Finally, we output the number of swaps and the swap operations themselves. This approach guarantees the desired configuration while ensuring the solution is efficient enough given the problem constraints.

n = int(input())
a = list(map(int,input().split()))
b = list(map(int, input().split()))
def next_index(start,target):
    for i in range(start,n):
        if b[i] == target:
            return i
swaps = []
for i in range(n):
    target = a[i]
    right = next_index(i,target)
 
    while right>i:
        swaps.append([right,right+1])
        b[right],b[right-1] = b[right-1],b[right]
        right-=1
count = 0
print(len(swaps))
for swap in swaps:
    print(*swap)