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