For positions whose numbers are the same, they cannot be colored using the same color.
Let us color the $$$i$$$-th occurrence of any number using color $$$i$$$.

We can see that:
• We cannot use fewer colors: if there are $$$k$$$ occurrences of any number, at least $$$k$$$ color is needed.
• The assignment of color is valid: Since the sequence was non-increasing, for any subsequence it is also non-increasing. As there are no duplicates in colored subsequence, the subsequence is strictly increasing as well.

Therefore, we only need to count the number of occurrences of every number and take the maximum of them.

import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

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

    count = Counter(a)
    print(max(count.values()))

To calculate the lane and desk where eulmelk can sit, we can use the remainder theorem in division with a little bit modification. To find the side(either $$$L$$$ or $$$R$$$) where eulmelk can sit, the parity of the input variable $$$k$$$ can easily tell us.

n, m, k = map(int, input().split())
r = (k - 1) // (2 * m) + 1
d = (k - 1) % (2 * m) // 2 + 1
loc = 'R' if k % 2 == 0 else 'L'
print(r, d, loc)

To solve this problem, we can use dynamic programming (DP) to find the minimum number of 1-burle coins required. This problem is a simpler version of the coin change problem with only 3 coin denominations: 1, 3, and 5 burles.

Dynamic Programming Approach:

1. Define the DP State:

• Let dp[i] represent the minimum number of 1-burle coins needed to make the amount i.

1. State Transition:

• To compute dp[i], consider the following transitions:
  • When using a 1-burle coin: markdown dp[i] = min(dp[i], dp[i - 1] + 1)
  • When using a 3-burle coin: markdown dp[i] = min(dp[i], dp[i - 3])
  • When using a 5-burle coin: markdown dp[i] = min(dp[i], dp[i - 5])

The above transitions ensure that for each amount i, dp[i] is updated to reflect the minimum number of 1-burle coins required by considering the use of 1-burle, 3-burle, and 5-burle coins.

1. Initialization:

• Initialize dp[0] to 0 because no 1-burle coins are needed to make an amount of 0.
• Initialize all other entries in dp to a large value (e.g., infinity) to represent that those amounts are initially unreachable.

1. Algorithm:

• Iterate through all amounts from 1 to the desired amount and update dp[i] using the state transitions described.

By following this approach, you can efficiently determine the minimum number of 1-burle coins needed to make any given amount using coins of denominations 1, 3, and 5 burles.

dp = [float('inf')] * 101
dp[0] = 0
for i in range(1, len(dp)):
    if i-1 >= 0:
        dp[i] = min(dp[i], dp[i-1] + 1)
    if i-3 >= 0:
        dp[i] = min(dp[i], dp[i-3])
    if i-5 >= 0:
        dp[i] = min(dp[i], dp[i-5])
 
for _ in range(int(input())):
    print(dp[int(input())])

There are two key observations to this problem

1. after each pair of moves, the directions go back to the original ones;
2. after each move, we can immediately go back (and combining these observations, we can derive that if we go from city $$$i$$$ to some other city $$$j$$$, we can always go back).

So our task is to find the leftmost and the rightmost city reachable from each city. To calculate for the left side, the movement should start with $$$'L'$$$, and to go beyond that, it should alternate. Similarly, for the right side, the first move should be $$$'R'$$$, and to go beyond that, it should alternate. We can calculate the number of reachable cities using prefix and suffix arrays

import sys   
def solve():

    n = int(sys.stdin.readline().strip())
    s =  sys.stdin.readline().strip()

    pref = [1] * n
    for i in range(1, n):
        if s[i] != s[i - 1]:
            pref[i] = pref[i -1] + 1

    suff = [1] * n
    for i in range(n -2, -1, -1):
        if s[i] != s[i + 1]:
            suff[i] = suff[i + 1] + 1

    ans = [1]* (n + 1)
    if s[0] == "R":
        ans[0] += suff[0]

    for i in range(1, n):
        if s[i] == "R":
            ans[i] += suff[i]
        if s[i - 1] == "L":
            ans[i] += pref[i - 1]

    if s[-1] == "L":
        ans[-1] += pref[-1]
        
    print(*ans)

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

Note that the problem basically states the following: you are given a rooted tree; you can pair two vertices $$$x$$$ and $$$y$$$ if neither $$$x$$$ is an ancestor of $$$y$$$ nor $$$y$$$ is an ancestor of $$$x$$$.

. Each vertex can be used in at most one pair. Calculate the maximum possible number of pairs you can make.

Let's look at subtrees of child nodes of the root. If two vertices belong to different subtrees, we can pair them up. So we can slightly rephrase the problem: given m types of objects, with counts $$$sz_1,sz_2,…,sz_m$$$

, find the maximum number of pairs that can be formed using objects of different types.

This is a well-known problem with the following solution. Let tot be the total number of objects and $$$mx$$$ be the type that has the maximum number of objects (maximum value of $$$sz$$$). If the number of objects of type $$$mx$$$ is at most the number of all other objects (i. e. $$$sz_{mx}$$$ ≤ $$$tot − sz_{mx}$$$), then we can pair all objects (except $$$1$$$ if the total number of objects is odd). Otherwise, we can create $$$tot−sz_{mx}$$$ pairs of the form $$$(mx,i)$$$ for all $$$i$$$ except $$$mx$$$.

.

Now we can return to the original problem. If the first aforementioned option is met for the root, then we know the answer to the problem is tot2 . Otherwise, we can create $$$tot − sz_{mx}$$$ pairs, but some nodes from the $$$mx$$$-th child's subtree are left unmatched (there are not enough vertices outside that subtree). So we can recursively look at the mx-th child subtree and solve the same problem. The only difference is that some number of vertices from that subtree are already matched. To solve this issue, we can add the parameter k — how many vertices in the current subtree are already matched (we care only about the number of them). From the second paragraph, we know that the best situation (we can pair all objects) appears when the maximum value is at most the number of all other objects. Using this fact, we can say that k matched vertices belong to the $$$mx$$$-th child's subtree. So we have to modify our check formula from $$$sz_{mx}$$$ ≤ $$$tot−sz_{mx}$$$ to $$$sz_{mx} − k$$$ ≤ $$$tot − sz_{mx}$$$.

. This process goes on until the current vertex (subtree) is a leaf or the condition is met.

This solution works in $$$O(n)$$$. if we precalculate the sizes for all the subtrees with a DFS before running it.

from collections import defaultdict, deque

def solve():
   n = int(input())
   a = list(map(int, input().split()))
   d = defaultdict(list)
  
   for i in range(n - 1):
       d[i + 2].append(a[i])
       d[a[i]].append(i + 2)
  
   queue = deque([(1, 1)])
   level = [0] * (n + 1)
   v = [0] * (n + 1)
  
   while queue:
       x, y = queue.popleft()
       level[y] += 1
       v[x] = 1
       for i in d[x]:
           if v[i] == 0:
               queue.append((i, y + 1))
  
   ans = 0
   unpaired = 0
  
   for i in range(n, 1, -1):
       if level[i] > 1:
           x = min(unpaired, level[i] - 1)
           ans += x
           unpaired -= x
           level[i] -= x
       ans += level[i] // 2
       unpaired += level[i] % 2
  
   print(ans)

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

If we have $$$n$$$ distinct balloons, first we have $$$n$$$ choices to burst, then $$$n - 1$$$ and so on. Hence, totally we have $$$n!$$$ ways to burst the balloons.

from math import factorial


N = int(input())

distinct_balloons = set(map(int, input().split()))

n = len(distinct_balloons)
print(factorial(n))

Since there is frequent removal and insertion, a linked list (a doubly linked one) is a good fit for the solution. To keep track of the first occurrences of the numbers we can utilize a hashmap with queues as values.

For insertion, the hashmap will tell us which node is the first occurrence of $$$y$$$, with a key, $$$y$$$; and a value, the occurrences of $$$y$$$ (nodes with value == $$$y$$$) in a queue. If we get the instance of the first $$$y$$$, it will be as easy as manipulating pointers of the linked list.

For removal, it is the same process, we get the first occurrence from the hashmap and remove it from the linked list as well as the queue.

import sys
from collections import defaultdict, deque

class ListNode:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.next = next
        self.prev = prev

q = int(input())
queries = [input().split() for i in range(q)]

head = ListNode(None) # dummy node
tail = ListNode(None, prev=head) # dummy node
head.next = tail

positions = defaultdict(lambda :deque())

for query in queries:
    operation = query[0]
    if operation == 'insert':
        x, y = map(int, query[1:])
        new_x = ListNode(x)
        if positions[y]:
            first_y = positions[y][0]
            temp = first_y.next
            new_x.prev = first_y
            new_x.next = temp
            first_y.next = new_x
            temp.prev = new_x
            positions[x].append(new_x)
        else:
            temp = tail.prev
            temp.next = new_x
            tail.prev = new_x
            new_x.next = tail
            new_x.prev = temp
            positions[x].append(new_x)
    
    else:
        w = int(query[1])
        if positions[w]:
            target = positions[w].popleft()
            prev = target.prev
            nxt = target.next
            prev.next = nxt
            nxt.prev = prev

ans = []
current = head.next
while current.val != None:
    ans.append(current.val)
    current = current.next

print(*ans)

The problem can be solved using dynamic programming (DP). The key idea is to use a DP table to keep track of the maximum points Sam can achieve after processing each tree. Let dp[i][j] represent the maximum points Sam can achieve after processing the first i trees, with exactly j half picks made so far. The DP table is initialized to zero because starting at tree 0 gives Sam 0 points.

If Sam picks all the fruits from the current tree $$$i$$$, then the points accumulated will be: $$$dp[i][0]=dp[i−1][0]+(produce[i−1]−k)$$$

If Sam chooses to half-pick the fruits at tree i, then the points will be influenced by the number of previous half-picks j. We have two subcases:

Don't Divide: This continues from the previous state without making an additional half-pick.

Divide: This adds one more half-pick at the current tree.

The transition can be defined as: $$$dp[i][j]=max⁡(dp[i−1][j]+floor(produce[i−1]/2j)−k,dp[i−1][j−1]+floor(produce[i−1]/2j))$$$

$$$dp[i][j]=max(dp[i−1][j]+floor(produce[i−1]/2j)−k,dp[i−1][j−1]+floor(produce[i−1]/2j))$$$

The final result is the maximum value from the last row and column of the DP table after processing all the trees, considering all possible numbers of half-picks.

test_case = int(input())
for _ in range(test_case):
   n,k =  list(map(int,input().split()))
   nums = list(map(int,input().split()))
   dp = [[0 for _ in range(15)] for _ in range(n+1)]
  
  
   for i in range(1,n+1):
       dp[i][0] = dp[i-1][0]+ nums[i-1]- k
  
  
       for j in range(1,min(15,i+1)):
  
  
           dont_div = (dp[i-1][j]+ (nums[i-1]//(2**j))-k)
           div = (dp[i-1][j-1] + nums[i-1]//(2**j))
           dp[i][j] = max(dont_div,div)
  
  
   print(max(dp[n] + [i[-1] for i in dp]))

The goal of this solution is to find the maximum possible value using the aforementioned operation by simulating the tree in reverse order (starting from the leaf nodes to the root). Then, we can return the summation of the possible maximum value and the initial value at the root node as the answer.

We will perform a topological sort starting from the leaf nodes and moving towards the root node. During this process, we update the values of the nodes based on their children's values. This means: For each leaf node, we return the initial given value. For any non-leaf node, once we get the minimum value out of the children of the given non-leaf node, called $$$min_val$$$, we update the value of that non-leaf node based on two conditions: If the $$$min_val$$$ is less than the value of the current non-leaf node, the value of the current non-leaf node should be updated to $$$min_val$$$. If the $$$min_val$$$ is greater than or equal to the value of the current non-leaf node, then the value of the current non-leaf node should be updated to the average of the current node's value and $$$min_val$$$ (it should be rounded to the smallest nearest whole number). This will guarantee that we are performing the operations as much as possible without having any negative nodes. Once we reach the root node, we stop further processing as we've obtained the final possible value for the root. Then the final answer is the sum of the initial value of the root node and the final computed value for the root node after processing.

from collections import defaultdict, deque

for _ in range(int(input())):
    n = int(input())
    vals = list(map(int, input().split()))
    min_vals = [float('inf')] * n
    graph = defaultdict(list)
    indegree  = [0] * n
    # assigning the initial value of the root node as initial answer
    initial_ans = vals[0]
    vals[0] = float('inf')
    
    for i, each in enumerate(map(int, input().split())):
        graph[i + 1].append(each - 1)
        indegree[each - 1] += 1

    # including all leaf nodes as a source node
    queue = deque()
    for i in range(n):
        if indegree[i] == 0:
            queue.append((i, vals[i]))

    # calculating the maximum possible value written at the root using the aforementioned operation
    while queue:
        node, val = queue.popleft()
        if node == 0:
            break
        for neib in graph[node]:
            indegree[neib] -= 1 
            min_vals[neib] = min(min_vals[neib], val)
        
            if indegree[neib] == 0:
                if neib == 0:
                    vals[neib] = min(vals[neib], min_vals[neib]) 
                else:
                    if min_vals[neib] < vals[neib]:
                        vals[neib] = min_vals[neib]
                    else:
                        vals[neib] = (vals[neib] + min_vals[neib]) // 2
                queue.append((neib, vals[neib]))

    print(initial_ans + vals[0])

This problem is about the "rerooting" technique. Firstly, let's calculate the answer for some fixed root. How can we do this? Let $$$dp_v$$$ be the maximum possible difference between the number of white and black vertices in some subtree of $$$v$$$ (yes, the subtree of the rooted tree, i.e. $$$v$$$ and all its direct and indirect children) that contains the vertex $$$v$$$. We can calculate this dynamic programming by simple $$$dfs$$$ or $$$bfs$$$, for the vertex $$$v$$$ it will look like this: $$$dp_v=a_v+ \sum_{\text{to} \in \text{children}(v)} \max(0, dp_{to})$$$.

Okay, we can store the answer for the root somewhere. What's next? Let's try to change the root from the vertex $$$v$$$ to some adjacent to it vertex to. Which states of dynamic programming will change? Only $$$dp_v$$$ and $$$dp_{to}$$$. Firstly, we need to "remove" the child to from the subtree of the vertex $$$v$$$: $$$dp_v=dp_v−max(0,dp_{to})$$$. Then we need to "attach" the vertex $$$v$$$ and make it a child of the vertex to: $$$dp_{to}=dp_{to}+max(0,dp_v)$$$. Then we need to run this process recursively from to (store the answer, reroot the tree and so on) and when it ends we need to "rollback" our changes. Now $$$v$$$ is the root again and we can try the next child of $$$v$$$ as the root.

Time complexity: O(n).

import sys
from collections import defaultdict, deque
   
n = int(sys.stdin.readline().strip())
dp = list(map(int, sys.stdin.readline().strip().split()))

for i in range(n):
    if dp[i] == 0:
        dp[i] = -1

graph = defaultdict(list)
for _ in range(n - 1):
    u, v  = map(int, sys.stdin.readline().strip().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)

queue = deque()
queue.append((0, -1))
i = 0

while i < len(queue):
    le =  len(queue)
    for _ in range(i, le):
        cur, par = queue[i]
        i += 1
        for ne in graph[cur]:
            if ne != par:
                queue.append((ne, cur))

for i in range(len(queue) -1,0, -1):
    dp[queue[i][1]] += max(0, dp[queue[i][0]])

queue = [(0, -1)]
while queue:
    le = len(queue)
    for _ in range(le):
        cur, par = queue.pop()
        for ne in graph[cur]:
            if ne != par:
                dp[ne] += max(0, dp[cur]  - max(0, dp[ne]))
                queue.append((ne, cur))
print(*dp)

This problem just needs to simulate everything that was given in the statement.

n, k = map(int, input().split())
nums = input().split()
count = 0 
for num in nums:
    num_count = num.count('4') + num.count('7')
    if num_count <= k:
        count += 1

print(count)

The problem requires finding how many values ofxcan divide the chores into exactlyachores for Petya (with complexity greater thanx) andbchores for Vasya (with complexity less than or equal tox).

Approach:

1. Sort the Chore Complexities: Begin by sorting the array of chore complexities in ascending order. This allows us to easily separate the chores for Petya and Vasya based on their desired counts.
2. Identifying the Chore Split: Since Vasya will take thebleast complex chores, these will be the firstbelements in the sorted array. Petya will then take the remaining a chores, which are the lastaelements in the sorted array.
3. Determinex: The thresholdxthat divides the chores must be greater than the largest complexity of the chores Vasya takes and less than or equal to the smallest complexity of the chores Petya takes. Therefore,xmust satisfy: arr[b - 1] < x ≤ arr[b].
4. Calculate the Number of Valid Values forx: The number of validxvalues is given by arr[b] - arr[b - 1]. This represents the range of values thatxcan take to properly divide the chores between Petya and Vasya. If the values of arr[b] and arr[b - 1] are the same, no suchxexists, and the answer is $$$0$$$.

import sys

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

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

print(arr[b] - arr[b - 1])

We can simulate exactly what's described in the statement: loop over all cells not equal to $$$1$$$ and check if it doesn't break the city property. To check if a cell breaks the property, just loop over an element in the same row, and an element in the same column, and see if they can add to give the cell's number. The complexity is $$$O(n^4)$$$.

n = int(input())

lab = [] 
for _ in range(n):
    lab.append(list(map(int, input().split())))

for i in range(n):
    for j in range(n):
        if lab[i][j] != 1:
            for k in range(n):
                if i != k and lab[i][j] - lab[k][j] in lab[i]:
                    break
            else:
                print('No')
                exit(0)

print('Yes')

Look for patterns in how cards are distributed based on the step number..

Group steps using modulo 4 to see who gets which cards.

To determine how many cards Alice and Bob receive from a deck of n cards dealt in increasing steps, we can use two approaches: a direct simulation and an optimized mathematical method.

Initial Approach (Simulation):

1. Calculate Maximum Complete Steps x: Simulate dealing cards step-by-step until the total dealt cards exceed n.

2. Compute Total Cards Dealt and Remainder: Sum the cards dealt up to the largest complete step x and find the remaining cards.

3. Distribute Cards:
   • Alice receives cards on steps where current_step % 4 is $$$1$$$ or $$$0$$$.
   • Bob receives cards on steps where current_step % 4 is $$$2$$$ or $$$3$$$.
4. Add Remaining Cards: Distribute any leftover cards based on the current step index after the last complete step.

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

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

t = int(input())
for _ in range(t):
    n = int(input())
    total_cards = 0
    step = 1

    # Find the maximum number of complete steps
    while total_cards + step <= n:
        total_cards += step
        step += 1

    x = step - 1
    remainder = n - total_cards

    alice_sum = bob_sum = 0
    current_step = 1

    # Distribute cards up to step x
    for i in range(1, x + 1):
        if current_step % 4 == 1 or current_step % 4 == 0:
            alice_sum += i
        else:
            bob_sum += i
        current_step += 1

    # Add the remainder to the correct person
    if remainder > 0:
        if current_step % 4 == 1 or current_step % 4 == 0:
            alice_sum += remainder
            
        else:
            bob_sum += remainder
            
    print(alice_sum, bob_sum)

The initial approach, while straightforward, may be inefficient for large n. We can optimize it using mathematical formulas.

Solution Approach:

1. Find Maximum Number of Complete Stepsx: Calculatex where the sum of the first x numbers does not exceed n:

   • Solving for x from this equation ($$$n = \frac{x \cdot (x + 1)}{2}$$$ ) which is the sum of the first natural numbers up to $$$x$$$ gives the bound as $$$x = \left\lfloor \frac{-1 + \sqrt{1 + 8 \cdot n}}{2} \right\rfloor$$$.

2. Calculate Total Cards Dealt and Remaining Cards:

   • Total cards dealt total: $$$\frac{x \cdot (x + 1)}{2}$$$
   • Remainder: n - total

3. Distribute Cards Using Arithmetic Series:

   • Alice’s Cards: Sum of series for steps where i % 4 = 1 and i % 4 = 0.
   • Bob’s Cards: Sum of series for steps where i % 4 = 2 and i % 4 = 3.
   • Use the formula for the sum of an arithmetic series:
     • $$$S_m = \frac{m}{2} \left(2a_1 + (m - 1) \cdot d \right)$$$ where $$$a_1$$$ is the first term, $$$d$$$ is the common difference, and $$$m$$$ is the number of terms.
4. Add Remaining Cards: Distribute the remainder based on the step index after x steps.

Time complexity: $$$O(\log n)$$$
Space complexity: $$$O(1)$$$

import sys, math

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

def arithmetic_series_sum(start, diff, last_term):
    """
    Calculate the sum of an arithmetic series where the first term is `start`,
    the common difference is `diff`, and the last term is `last_term`.
    """
    count = (last_term - start) // diff + 1
    return count * (2 * start + (count - 1) * diff) // 2

def find_max_x(n):
    """
    Find the maximum `x` such that the sum of the first `x` natural numbers is <= `n`.
    """
    return math.floor((-1 + math.sqrt(1 + 8 * n)) / 2)

t = int(input())

for _ in range(t):
    n = int(input())
    
    # Determine the maximum `x` for which the sum of the first `x` natural numbers is <= `n`
    x = find_max_x(n)
    
    # Total sum of the first `x` natural numbers
    total_sum_x = x * (x + 1) // 2
    
    # Calculate the remaining cards
    remainder = n - total_sum_x
    
    # Calculate sums for Alice and Bob up to the largest valid `x`
    alice_sum = 1 + arithmetic_series_sum(4, 4, x) + arithmetic_series_sum(5, 4, x)
    bob_sum = arithmetic_series_sum(2, 4, x) + arithmetic_series_sum(3, 4, x)
    
    # Distribute the remaining cards
    if remainder > 0:
        if (x + 1) % 4 in (1, 0):
            alice_sum += remainder
        else:
            bob_sum += remainder
    
    print(alice_sum, bob_sum)

If $$$d_i$$$ is less than $$$l_i$$$, then $$$d_i$$$ itself is the smallest integer that satisfies the condition because it is divisible by $$$d_i$$$ and does not belong to $$$[l_i, r_i]$$$.

Otherwise, if $$$d_i$$$ is within the segment $$$[l_i, r_i]$$$, the smallest integer divisible by $$$d_i$$$ that is not in the segment is $$$(\lfloor r_i / d_i \rfloor + 1) \cdot d_i$$$.

for _ in range(int(input())):
    l, r, d = map(int,input().split())
    if d < l:
        print(d)
    else:
        print((r//d + 1)*d)

In this problem, our goal is to determine the number of indices that can be set to $$$1$$$ after performing m swaps. Each swap operation allows us to swap elements within a given range $$$[l, r]$$$.

Initially, without any swaps, the only index that can be $$$1$$$ is $$$x$$$. However, if we have a range that includes the current index $$$x$$$, we can swap any of the indices within that range with the current index. This means that the possible indices that can be $$$1$$$ expand based on the ranges provided.

To solve this, we need to combine all the ranges. If the final combined range includes the index $$$x$$$, then all indices within that range can be set to $$$1$$$.

t = int(input())
for _ in range(t):
    n,k,m = list(map(int,input().split()))
    start = k
    end = k
    
    for i in range(m):
        l,r = gns()
        if l <= start <= r or  l <= end <= r:
            start  = min(start,l)
            end = max(end,r)
    print(end - start + 1)

Notice that there will be a path that passes through the edge labeled $$$0$$$ and the edge labeled $$$1$$$ no matter how you label the edges, so there's always a path with MEX $$$2$$$ or more. If any node has degree $$$3$$$ or more, you can distribute the labels $$$0$$$, $$$1$$$, and $$$2$$$ to edges incident to this node and distribute the rest of the labels arbitrarily. Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges, since there will be a path with MEX $$$n−1$$$ anyway.

import sys
from collections import defaultdict

graph = defaultdict(list)
ans = {}

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

for i in range(1, n):
    a, b = map(int, sys.stdin.readline().strip().split())
    graph[a].append(i)
    graph[b].append(i)
    ans[i] = -1

# Find the node with the maximum degree
mx = (0, 0)
for i in range(1, n + 1):
    if len(graph[i]) > mx[0]:
        mx = (len(graph[i]), i)

cur = 0
for i in graph[mx[1]]:
    ans[i] = cur
    cur += 1

for i in range(1, n):
    if ans[i] == -1:
        ans[i] = cur
        cur += 1
    print(ans[i])

• Solution 1: Let's use the data structure called a bitwise trie. Fix some $$$a_{i}$$$, where all $$$a_{j}$$$ for $$$j<i$$$ have already been added to the trie. We will iterate over the bits in $$$a_{i}$$$ from the $$$(k−1)^{th}$$$ bit to the $$$0^{th}$$$ bit. Since $$$2^{t}>2^{t−1}+2^{t−2}+…+2+1$$$, if there exists $$$a_{j}$$$ with the same bit at the corresponding position in $$$a_{i}$$$, we will go into that branch of the trie and append $$$1−b$$$ to the corresponding bit $$$x$$$. Otherwise, our path is uniquely determined. When we reach a leaf, the bits on the path will correspond to the optimal number $$$a_{j}$$$ for $$$a_{i}$$$. The time complexity of this solution is $$$O(nk)$$$.
• Solution 2: Sort $$$a_{1},a_{2},…,a_{n}$$$ in non-decreasing order. We will prove that the answer is some pair of adjacent numbers. Let the answer be numbers $$$a_{i},a_{j} (j−i>1)$$$. If $$$a_{i}=a_{j}$$$, then $$$a_{i}=a_{i+1}$$$. Otherwise, they have a common prefix of bits, after which there is a differing bit. That is, at some position $$$t$$$, $$$a_{i}$$$ has a $$$0$$$ and $$$a_{j}$$$ has a $$$1$$$. Since $$$j−i>1$$$, $$$a{i+1}$$$ can have either $$$0$$$ or $$$1$$$ at this position, but in the first case it is more advantageous to choose $$$a_{i},a_{i+1}$$$ as the answer, and in the second case it is more advantageous to choose $$$a_{i+1},a_{j}$$$ as the answer. The complexity of this solution is $$$O(nlogn)$$$.

For the first approach, make sure to use $$$PyPy 3-64$$$.

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

class TrieNode:
    def __init__(self):
        self.children = [None, None]
        self.position = -1 # index of the corresponding number in the given array

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

    ans_i = ans_j = ans_x = 1, 1, 0
    max_val = 0 # maximum value of (a[i] ^ x) & (a[j] ^ x)
    
    root_node = TrieNode()
    for i, num in enumerate(a):
        cur_node = root_node
        # find a pair a[j] for this number
        # first check if there's at least one number in the trie
        if cur_node.children[0] or cur_node.children[1]:
            x = 0
            for bit_i in range(k - 1, -1, -1):
                if num & (1 << bit_i):
                    # match 1 bit with 1 bit
                    if cur_node.children[1]:
                        cur_node = cur_node.children[1]
                    else: # if not possible, match 1 bit with 0 bit
                        cur_node = cur_node.children[0]

                else:
                    # match 0 bit with 0 bit
                    if cur_node.children[0]:
                        cur_node = cur_node.children[0]
                        x = x ^ (1 << bit_i)
                    else: # if not possible, match 0 bit with 1 bit
                        cur_node = cur_node.children[1]

            j = cur_node.position
            new_val = (num ^ x)&(a[j] ^ x)
            if new_val >= max_val:
                max_val = new_val
                ans_i, ans_j, ans_x = i + 1, j + 1, x

        # insert the current number into the trie
        cur_node = root_node
        for bit_i in range(k - 1, -1, -1):
            if num & (1 << bit_i):
                if not cur_node.children[1]:
                    cur_node.children[1] = TrieNode()
                cur_node = cur_node.children[1]

            else:
                if not cur_node.children[0]:
                    cur_node.children[0] = TrieNode()
                cur_node = cur_node.children[0]

        cur_node.position = i

    print(ans_i, ans_j, ans_x)

    

If we connect the graph using $$$0$$$-weighted edges only and we are left with $$$k$$$ components, we need $$$k - 1$$$ $$$1$$$-weighted edges.

Let's keep track of the unconnected nodes in a set and every time we do a BFS starting from an unconnected node to a node that has no edge with it. We have to check if there is a node in unconnected nodes that is not a neighbor (considering $$$1$$$-weighted edge) of it. Every time we check if the node is the neighbor we pass it and if not we add it in the BFS queue. Worst case, the first case will only happen $$$m$$$ (the number of $$$1$$$-weighted edges) times and the second case will only happen $$$n$$$ times. The overall time complexity will be $$$O(n + m)$$$.

from collections import defaultdict, deque
from sys import stdin


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

N, M = map(int, input().split())

adj = defaultdict(set)
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    adj[u].add(v)
    adj[v].add(u)

unconnected = set(range(N))
edges = 0

for i in range(N):
    if i in unconnected:
        q = deque([i])
        unconnected.remove(i)
        while q:
            v = q.popleft()
            remove = []
            for u in unconnected:
                if v not in adj[u]:
                    edges += 1
                    remove.append(u)
                    q.append(u)
            for u in remove:
                unconnected.remove(u)
print(N - 1 - edges)

We can re-write the formula as $$$b_i = a_i + (b_{i + 1} - b_{i + 2} + \dots)$$$. Then, we can reduce $$$(b_{i + 1} - b_{i + 2} + \dots)$$$ to $$$a_{i + 1}$$$. So, $$$b_i = a_i + a_{i + 1}$$$.

n = int(input())
arr = list(map(int, input().split()))
arr.append(0)
ans = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    ans[i] = arr[i] + arr[i + 1]
print(*ans[:n])

If $$$n$$$ is greater than 26 or the length of the word is less than $$$n$$$, it's impossible to reach $$$n$$$ distinct characters. Otherwise, we can count how many characters are left to reach $$$n$$$ distinct characters.

word = input()
n = int(input())

if n > 26 or len(word) < n:
    print("impossible")
else:
    print(max(0, n - len(set(word))))

The solution to preventing "trygub" from being a subsequence involves disrupting the specific order of its characters. Since "trygub" requires the characters 't', 'r', 'y', 'g', 'u', and 'b' to appear in that precise sequence, the approach is to rearrange the string so that this order cannot be maintained. The simplest way to achieve this is by sorting the string, which effectively disturbs the positions and prevents the sequence from forming. However, a more efficient solution is to start the rearranged string with any character that is not 't' from "trygub." By beginning with a different character and appending the others afterward, we ensure that the required sequence is broken, thus preventing "trygub" from appearing as a subsequence.

Time complexity = $$$O(n)$$$. Space complexity = $$$O(1)$$$.

import sys

input = lambda: sys.stdin.readline().rstrip()
t = int(input())

for _ in range(t):
    N = int(input())
    s = input()
    ans = ["b"] * s.count("b")
    
    for char in s:
        if char != "b":
            ans.append(char)
    
    print("".join(ans))

What if the given number $$$n$$$ cannot be represented as $$$2^{cnt2}⋅3^{cnt3}⋅5^{cnt5}$$$? It means that the answer is $$$-1$$$ because all actions we can do are: remove one power of two, remove one power of three and add one power of two, and remove one power of five and add two powers of two. So if the answer is not $$$-1$$$ then it is $$$cnt2+2.cnt3+3.cnt5$$$. If this formula isn't pretty clear for you, you can just simulate the process, performing actions from third to first.

import sys
t = int(sys.stdin.readline().strip())

for _ in range(t):

    n = int(sys.stdin.readline().strip())
    cnt2, cnt3, cnt5 = 0, 0, 0

    while n % 2 == 0:
        n //= 2
        cnt2 += 1

    while n % 3 == 0:
        n //= 3
        cnt3 += 1

    while n % 5 == 0:
        n //= 5
        cnt5 += 1
        
    if n != 1:
        print(-1)
    else:
        print(cnt2 + 2 * cnt3 + 3 * cnt5)

This problem can be solved in a straightforward way. The key observation is that the order in which the letters are called out does not matter in this game. We only need to know how many times each letter is called out in order to go from the initial word $$$s$$$ to the final word $$$t$$$.

So first, let us compute the number of occurrences of each letter from 'A' to 'Z' in both words $$$s$$$ and $$$t$$$. Let’s call them $$$s_a$$$ and $$$t_a$$$ for each letter $$$a$$$. Using these numbers, we can calculate how many times each letter shall be called in order to get a chance of getting to $$$t$$$. That is $$$s_a − t_a$$$ times for each letter $$$a$$$.

If $$$s_a − t_a < 0$$$ for any letter $$$a$$$, then the answer is 'NO'. Otherwise, there is a chance for a positive answer. However, we also need to verify that the order of the letters in $$$t$$$ is correct. The easy way to verify it is to simulate the game, dropping the first $$$s_a − t_a$$$ occurrences of each letter $$$a$$$, and then compare the result with $$$t$$$.

from collections import Counter
from sys import stdin


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

T = int(input())

for _ in range(T):
    s, t = input().split()
    s_cnt = Counter(s)
    t_cnt = Counter(t)

    remove_cnt = {}
    ok = True
    for ch in s_cnt:
        remove_cnt[ch] = s_cnt[ch] - t_cnt[ch]
        if remove_cnt[ch] < 0:
            ok = False
    
    if not ok:
        print("NO")
        continue
    
    new_s = []
    for ch in s:
        if remove_cnt[ch] > 0:
            remove_cnt[ch] -= 1
        else:
            new_s.append(ch)
    
    if "".join(new_s) == t:
        print("YES")
    else:
        print("NO")

Think of each bit independently.

Solution:

Initially, we set all $$$a_i=2^{30}−1$$$ (all bits on).

You can go through every $$$i$$$,$$$j$$$ such that $$$i≠j$$$ and do $$$a_i$$$ &= $$$M_{i,j}$$$ and $$$a_j$$$ &= $$$M_{i,j}$$$.

Then we check if $$$M_{i,j}=a_i|a_j$$$ for all pairs. If this holds you found the array else the answer is $$$NO$$$.

Proof:

Initially, all elements have all their bits set on and we remove only the bits that affect our answer. If $$$M_{i,j}$$$ doesn't have a specific bit then definitely neither $$$a_i$$$ nor $$$a_j$$$ should have it. If $$$M_{i,j}$$$ has a specific bit on then we don't have to remove anything (in the end we want at least one of $$$a_i$$$ and $$$a_j$$$ to have the bit on).

import sys


def solve():
    n = int(sys.stdin.readline().strip())
    matrix = []

    for _ in range(n):
        row = list(map(int, sys.stdin.readline().strip().split()))
        matrix.append(row)

    a = [2**30 - 1] * n
    
    for i in range(n):
        for j in range(n):
            if i != j:
                a[i] &= matrix[i][j]
                a[j] &= matrix[i][j]

    for i in range(n):
        for j in range(n):
            if i != j and a[i] | a[j] != matrix[i][j]:
                print("NO")
                return
            
    print("YES")
    print(*a)
    
t = int(sys.stdin.readline().strip())

for _ in range(t):
    solve()

To solve this problem, we use binary search on the minimum possible maximum waiting time, denoted as x.

A. Binary Search on x: Perform a binary search to find the smallest x such that all customers can be assigned to three or fewer carvers with each having a maximum waiting time of x.

B. Sorting: First, sort the array of customers' pattern requests to facilitate efficient grouping.

C. Assigning Carvers: Start assigning customers to carvers from the beginning of the sorted list. For each carver, choose a range [l, r] of customers and set the optimal pattern as (r + l) // 2 to minimize the maximum waiting time. If the difference between this average pattern and the range limits exceeds x, start a new range for the next carver. Continue until all customers are assigned or more than three carvers are needed.

D. Adjust x: If three or fewer carvers suffice, reduce x to find a smaller maximum waiting time. If more than three carvers are needed, increase x and retry.

Time Complexity

The time complexity is O(n * log(m)), where n is the number of customers, and m is the difference between the maximum and minimum possible waiting times.

def solve():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort()

    def is_valid_waiting_time(waiting_time):
        start = nums[0]
        count = 1

        for i in range(1, n):
            if (nums[i] - start + 1) // 2 > waiting_time:
                count += 1
                start = nums[i]

        return count <= 3

    l = 0
    r = max(nums)

    while l <= r:
        mid = (l + r) // 2
        if is_valid_waiting_time(mid):
            r = mid - 1
        else:
            l = mid + 1

    print(l)

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

First, check the parity of $$$k$$$. If $$$k$$$ is odd, there is no solution because the cycle described in the task must have an even length. Otherwise, proceed as follows: Use the breadth-first search (BFS) algorithm to find the shortest distance from the starting cell to all other free cells. Next, move through the grid. Before each move, determine the next cell to go to. Consider the directions in the order $$$( "D", "L", "R", "U")$$$. The current direction is $$$c$$$. If the cell $$$x$$$ corresponding to a move in direction $$$c$$$ is empty and the distance from it to the starting cell does not exceed the remaining number of steps, then move in direction $$$c$$$, add the corresponding letter to the answer, and proceed to the next step. If at any step it is impossible to move the Robot, a cycle of length $$$k$$$ does not exist. Otherwise, once the Robot has completed $$$k$$$ steps, simply print the answer.

from collections import deque

n, m, k = map(int, input().split())
if k % 2:
    print("IMPOSSIBLE")
    exit(0)

maze = []
direc = {  (1, 0): 'D', (0, -1): 'L', (0, 1): 'R', (-1, 0): 'U' }
src = None 
for i in range(n):
    maze.append(input())
    for j in range(m):
        if maze[i][j] == 'X':
            src = (i, j)
            break
        
#bfs
track = [[float('inf') for _ in range(m)] for _ in range(n)]
track[src[0]][src[1]] = 0
queue = deque([(src, 0)])
visited = set([src])
while queue:
    loc, step = queue.popleft()
    for dx, dy in direc:
        x, y = loc[0] + dx, loc[1] + dy
        if 0 <= x < n and 0 <= y < m and maze[x][y] != '*' and (x, y) not in visited:
            track[x][y] = min(track[x][y], step + 1)
            queue.append(((x, y), step + 1))
            visited.add((x, y))

#dfs
stack = [src]
ans = []
while stack:
    loc = stack.pop()
    if len(ans) == k:
        print("".join(ans))
        exit(0)
    for dx, dy in direc:
        x, y = loc[0] + dx, loc[1] + dy
        if 0 <= x < n and 0 <= y < m and track[x][y] <= k &mdash; len(ans):
            ans.append(direc[(dx, dy)])
            stack.append((x, y))
            break

print("IMPOSSIBLE")

Since it is counting pairs, we can use divide and conquer approach.

Let's assume we have divided the original string in half, getting $$$substring1$$$ and $$$substring2$$$. Let's have a segment $$$(l, r)$$$ to be inverted where $$$l$$$ lies in $$$substring1$$$ and $$$r$$$ lies in $$$substring2$$$. We can now invert some suffix of $$$substring1$$$ and invert some prefix of $$$substring2$$$ and try to balance the brackets.

There is one fact to create a balanced sequence. Because the original string is balanced:

• For $$$substring1$$$: All the closing brackets must have opening pairs. And, there could be zero or more unbalanced opening brackets.
• For $$$substring2$$$: All the opening brackets must have closing pairs. And, there could be zero or more unbalanced closing brackets.

For instance, after some inversion, if we have $$$Y$$$ amount opening brackets that didn't get a closing match in the fist substring, we should find $$$Y$$$ amount of excess closing brackets in the second substring.

Now, with the same logic we can further divide the two substrings, and account for every $$$(l, r)$$$ pair.

Let's divide $$$substring1$$$ into halves, $$$a$$$ and $$$b$$$. After some $$$(l, r)$$$ inversion, where $$$l$$$ lies in $$$a$$$ and $$$r$$$ lies in $$$b$$$, let's say we have $$$X$$$ amount of excess opening brackets in $$$a$$$, the $$$X$$$ closing matches could come from not just $$$b$$$, but the whole suffix starting from and including $$$b$$$. The same applies if we have some subsegment before $$$a$$$. So, to handle that case, we do some preprocessing and count excess prefix openings and excess suffix closings.

Time complexity: $$$nlog(n)$$$
Make sure to use $$$PyPy 3-64$$$.

import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()

def conquer(l1, r1, l2, r2):

    excess_opening = defaultdict(int)
    inverted_open = 0
    unpaired_closing = 0
    # all closing brackets must have an opening pair on the left subarray
    # invert some suffix of substring 1
    for indx in range(r1, l1 - 1, -1):
        if s[indx] == ')':
            inverted_open += 1
            # follow kadan's algorithm to find opening matches for the closings
            # if we have an excess opening, it is no use for a closing that comes before it
            # so we don't make the unpaired_closing negative
            unpaired_closing = max(unpaired_closing - 1, 0) 
            
        else:
            unpaired_closing += 1
            inverted_open -= 1
        
        # uninverted prefix of this index must provide opening pairs for the unpaired closings
        if pref[indx - 1] >= unpaired_closing:
            excess_opening[pref[indx - 1] + inverted_open] += 1


    unpaired_opening = 0
    inverted_close = 0
    count = 0 # (l, r) matches 

    # invert some prefix of substring 2
    for indx in range(l2, r2 + 1):
        if s[indx] == '(':
            inverted_close += 1
            unpaired_opening = max(unpaired_opening - 1, 0)

        else:
            unpaired_opening += 1
            inverted_close -= 1

        # uninverted suffix of this index must provide closing pairs for the unpaired openings
        if suf[indx + 1] >= unpaired_opening:
            # match 'y' amount of excess opening in the first substring
            # with 'y' amount of closing in the second substring
            count += excess_opening[suf[indx + 1] + inverted_close]

    return count

def divide(l, r):
    if l >= r:
        return 0

    mid = (r + l)//2
    left_count = divide(l, mid)
    right_count = divide(mid + 1, r)
    cur_count = conquer(l, mid, mid + 1, r)
    return left_count + right_count + cur_count

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

    pref = [0]*(n + 1)
    suf = [0]*(n + 1)

    openning_pref = 0
    closing_suf = 0
    for i in range(n):
        openning_pref += 1 if s[i] == '(' else -1
        closing_suf += 1 if s[n - i - 1] == ')' else -1

        pref[i] = openning_pref
        suf[n - i - 1] = closing_suf
    
    ans = divide(0, n - 1)
    print(ans)

Since it does not take time to place your hand over the first letter, you need to calculate the sum of the distances between the keyboard keys corresponding to each pair of adjacent letters of the word, that is $$$ \sum_{i=2}^{n} \left| \text{pos}(s_i) - \text{pos}(s_{i-1}) \right|$$$ where $$$pos(c)$$$ is the position of the keyboard key corresponding to the letter $$$c$$$.

In order to calculate this sum, let's just iterate through the word $$$s$$$ with the for loop and find the differences between the positions of $$$s_i$$$ and $$$s_{i−1}$$$ on the keyboard.

import sys
    
def solve():

    s = sys.stdin.readline().strip()
    t = sys.stdin.readline().strip()

    pos = {}
    for i, ch in enumerate(s):
        pos[ch] = i
        
    ans = 0
    for i in range(1, len(t)):
        ans += abs(pos[t[i]] - pos[t[i - 1]])
    return ans

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

We can sort both $$$a$$$ and $$$b$$$ and use counters to track how many consecutive times we've used characters from each string. Then, as we iterate through both strings, we check the smallest available character in each. If the smallest character is in a string we've already used k times consecutively, we skip it; otherwise, we choose that character, remove it, and reset the counter for the other string.

for _ in range(int(input())):
   n, m, k = map(int, input().split())
   a = sorted(input(), reverse=True)
   b = sorted(input(), reverse=True)
   
   k_a = k_b = 0
   ans = []
   
   while a and b:
       if (a[-1] >= b[-1] and k_a < k) or k_b >= k:
           ans.append(b.pop())
           k_a += 1
           k_b = 0
       else:
           ans.append(a.pop())
           k_b += 1
           k_a = 0
   
   print("".join(ans))

Let's look at an analogy for this game.

• If Alice takes an even number $$$x$$$, she adds $$$x$$$ points to the global result, otherwise $$$0$$$;
• If Bob takes an odd number $$$x$$$, he adds $$$−x$$$ points to the global result, otherwise $$$0$$$;
• Alice wants to maximize the global result and Bob wants to minimize it.

Obviously, this game is completely equivalent to the conditional game.

Suppose now it's Alice's move. Let's look at some number $$$x$$$ in the array.

• If this number is even, then taking it will add $$$x$$$ points, and giving it to Bob will add $$$0$$$ points.
• If this number is odd, then taking it will add $$$0$$$ points, and giving it to Bob will add $$$−x$$$ points.

So taking the number $$$x$$$ by $$$x$$$ points is more profitable than not taking it (regardless of the parity). To maximize the result, Alice should always take the maximum number in the array.

Similar reasoning can be done for Bob. In the task, it was necessary to sort the array and simulate the game.

from sys import stdin


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

T = int(input())

for _ in range(T):
    N = int(input())
    a = sorted(map(int, input().split()), reverse=True)

    alice = bob = 0
    alice_turn = 1
    for ai in a:
        if alice_turn:
            if ai%2 == 0:
                alice += ai
        else:
            if ai%2:
                bob += ai
        alice_turn ^= 1
    
    if alice > bob:
        print("Alice")
    elif bob > alice:
        print("Bob")
    else:
        print("Tie")

We can easily employ a Binary Search Algorithm to find a player $$$y$$$ with the minimum token that can win the game by favoring all the random decisions toward this player $$$y$$$. Then any player that has greater tokens than this player $$$y$$$ will win the game. This will reduce the time complexity to $$$O(nlogn)$$$ instead of $$$O(n^2)$$$.

for _ in range(int(input())):
    n = int(input())
    players = list(map(int, input().split()))
    tokens = sorted(players)

    left, right = 0, n - 1
    tot_sum = sum(tokens)
    init_point = right
    while left <= right:
        mid = left + (right - left) // 2
        curr_sum = sum(tokens[:mid + 1])
        for i in range(mid + 1, n):
            if curr_sum < tokens[i]:
                break
            curr_sum += tokens[i]
            
        if curr_sum == tot_sum:
            right = mid - 1
            init_point = mid 
        else:
            left = mid + 1 
            
    print(n - init_point)
    print(*[indx + 1 for indx in range(n) if players[indx] >= tokens[init_point]])

Firstly, let's prove that the size of the answer is not greater than $$$3$$$ . Suppose that the answer equals to $$$4$$$ . Let $$$a,b,c,d$$$ be coordinates of the points in the answer (and $$$a<b<c<d$$$ ). Let $$$dist(a,b)=2^k$$$ and $$$dist(b,c)=2^l$$$ . Then $$$dist(a,c)=dist(a,b)+dist(b,c)=2^k+2^l=2^m$$$ (because of the condition). It means that $$$k=l$$$ . Conditions must hold for a triple $$$b,c,d$$$ too. Now it is easy to see that if $$$dist(a,b)=dist(b,c)=dist(c,d)=2^k$$$ then $$$dist(a,d)=dist(a,b)∗3$$$ that is not a power of two. So the size of the answer is not greater than $$$3$$$ .

Firstly, let's check if the answer is $$$3$$$ . Iterate over all middle elements of the answer and over all powers of two from $$$0$$$ to $$$30$$$ inclusively. Let $$$xi$$$ be the middle element of the answer and $$$j$$$ — the current power of two. Then if there are elements $$$xi−2^j$$$ and $$$xi+2^j$$$ in the array then the answer is $$$3$$$ .

Now check if the answer is $$$2$$$ . Do the same as in the previous solution, but now we have left point $$$xi$$$ and right point $$$xi+2^j$$$ .

If we did not find answer of lengths $$$3$$$ or $$$2$$$ then print any element of the array.

The solution above have time complexity $$$O(n⋅log10**10)$$$ .

from collections import Counter
     
def find_three(nums, dic):
    # Find a sequence of three numbers with differences of powers of two
    for num in nums:
        i = 1
        while i <= 10 ** 10:
            if num + i in dic and num + 2 * i in dic:
                return 3, [num, num + i, num + 2 * i]
            i *= 2
    return None
 
def find_two(nums, dic):
    # Find a sequence of two numbers with a difference of a power of two
    for num in nums:
        i = 1
        while i <= 10 ** 10:
            if num + i in dic:
                return 2, [num, num + i]
            i *= 2
    return None
 
def main():
    n = int(input().strip())
    nums = sorted(map(int, input().strip().split()))
    dic = Counter(nums)
    
    # Check for sequences of 3, then 2, or return a single number
    result = find_three(nums, dic) or find_two(nums, dic) or (1, [nums[0]])
    
    length, sequence = result
    print(length)
    print(*sequence)
 
if __name__ == "__main__":
    main()

Easily, we can sum up the difference between the maximum coins out of the three and the other two remaining coins. Then, we can subtract this value from the total coins Polycrap has. If Polycrap's remaining coins after this subtraction are less than $$$0$$$ or not divisible by $$$3$$$, the answer will be $$$NO$$$; otherwise, the answer will always be $$$YES$$$.

for _ in range(int(input())):
    a, b, c, n = map(int, input().split())
    n -= 3 * max(a, b, c) - a - b - c
    print('YES' if n % 3 == 0 and n >= 0 else 'NO')

If $$$ n$$$ is greater than $$$ k$$$ and $$$ n$$$ is divisible by $$$ k$$$, then the minimum maximum number will be 1, and the sum will be $$$ n$$$, which is divisible by $$$ k$$$. However, if $$$ n$$$ is not divisible by $$$ k$$$, the minimum maximum number will be 2. The sum of the array could be any number between $$$ n$$$ and $$$ 2n$$$, and since $$$ k$$$ is less than $$$ n$$$, we can guarantee that there is at least one number divisible by $$$ k$$$.

In the other case, if $$$ n$$$ is less than $$$ k$$$, to make the array sum divisible by $$$ k$$$, we can prove that we can't have a sum that is divisible by $$$ k$$$ if the maximum number in the array is less than $$$ \frac{k}{n}$$$. Therefore, the minimum maximum number will be $$$ \lceil \frac{k}{n} \rceil$$$.

for _ in range(int(input())):
    n,k = map(int,input().split())
    if n >= k:
        print(1 if n % k == 0 else 2)
    else:
        print((k-1)//n + 1)

The maximum value of $$$k$$$ should be determined in the following way: let's find the maximum number of people already sitting on the same bench (i. e. the maximum value in the array $$$a$$$). Let this number be $$$max(a)$$$. Then if all additional $$$m$$$ people seat on this bench, we will get the maximum possible value of $$$k$$$, so the answer is $$$max(a)+m$$$.

To determine the minimum value of $$$k$$$, let's perform $$$m$$$ operations. During each operation we put a new person on the bench currently having the minimum number of people occupying it. The answer is the maximum number of people on the bench after we perform this operation for each of $$$m$$$ newcomers.

import sys
from heapq import heapify, heappop, heappush
input = lambda: sys.stdin.readline().rstrip()


n = int(input())
m = int(input())
a = [int(input()) for line in range(n)]

_max = max(a) + m

heapify(a)
for i in range(m):
    min_bench = heappop(a)
    heappush(a, min_bench + 1)

_min = max(a)
print(_min, _max)
    

Since neither the graph nor the number of queries is too large, for each query you can simply count the number of the "good" colors (the colors that satisfies the condition) by checking if each color is "good". To do that, you can perform Depth First Search (or Breadth First Search) and verify whether you can reach vi from ui traversing only the edges of that color. If you prefer using Union-Find, it will also do the job.

from sys import stdin
from collections import defaultdict


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

N, M = map(int, input().split())

graph = [defaultdict(list)  for _ in range(M)]

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

dest = -1
def dfs(v, adj, visited):
    visited.add(v)
    if v == dest:
        return True
    for u in adj[v]:
        if u not in visited:
            if dfs(u, adj, visited):
                return True
    return False


Q = int(input())
for _ in range(Q):
    cnt = 0
    u, v = map(int, input().split())
    for adj in graph:
        visited = set()
        dest = v
        if dfs(u, adj, visited):
            cnt += 1
    print(cnt)

Firstly, we can find answers for all points that are adjacent to at least one point not from the set. The distance for such points is obviously $$$1$$$ (and this is the smallest possible answer we can get). On the next iteration, we can set answers for all points that are adjacent to points with found answers (because they don't have neighbors not from the set, the distance for them is at least $$$2$$$). It doesn't matter which point we will take, so if the point $$$i$$$ is adjacent to some point $$$j$$$ that have the answer $$$1$$$, we can set the answer for the point $$$i$$$ as the answer for the point $$$j$$$. We can repeat this process until we find answers for all points. In terms of the code, this can be done by breadth first search ($$$BFS$$$). In other words, we set answers for the points that have the distance $$$1$$$ and then push these answers to all adjacent points from the set in order of the increasing distance until we find all the answers.

import sys
from collections import deque
 
n = int(sys.stdin.readline().strip())
given_points = set()
points = []

for _ in range(n):
    x, y =  map(int, sys.stdin.readline().strip().split())
    points.append((x, y))
    given_points.add((x, y))

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

queue = deque()
visited = {}

for x, y in points:
    for dx, dy in directions:
        nx = x + dx
        ny = y + dy
        if (nx, ny) not in given_points:
            visited[(x, y)] = (nx, ny)
            queue.append((x, y))
            break


while queue:

    for _ in range(len(queue)):

        x, y = queue.popleft()
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if (nx, ny) not in visited and (nx, ny) in given_points:
                visited[(nx, ny)] = visited[(x, y)]
                queue.append((nx, ny))

ans = []
for x, y in points:
    ans.append(visited[(x, y)])
for a, b in ans:
    print(a, b)

Since the sum of numbers in one pair has to be odd; in each pair, there has to be exactly one odd and one even number. Therefore; for the whole array, the count of odd numbers should be equal to the count of even numbers.

And, because the array size is $$$2n$$$, there has to be $$$n$$$ amount of odd numbers and $$$n$$$ amount of even numbers in the array. We can verify the answer by just checking the count of odd numbers too.

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


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

    odd_count = 0
    even_count = 0

    for num in a:
        if num & 1:
            odd_count += 1
        else:
            even_count += 1

    print('Yes' if odd_count == even_count else 'No')
    

For every child the number of turns that they are going to go through is $$$ceil(a_i/m)$$$, so we need to find the child who have to go through the maximum number of turns and if two childs are going to go through the same number of turns the one who is at the last index will finish later.

from math import ceil
import sys

input = sys.stdin.readline

def solve():
    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    max_ceil = ceil(a[0]/m)
    for i in range(1, n):
   	 cur_ceil = ceil(a[i]/m)
   	 if cur_ceil >= max_ceil:
   		 max_ceil = cur_ceil
   		 ans = i
    print(ans + 1)
    
solve()

For every $$$k$$$ such that $$$a_i=k$$$, $$$a_j=k+1$$$ and $$$i$$$>$$$j$$$ we have to choose $$$x$$$=$$$k$$$+$$$1$$$ at least once for these elements to be in the correct order. It is easy to see that if we choose all such $$$x$$$=$$$k$$$+$$$1$$$ for all such $$$k$$$ exactly once in any order, we will get the identity permutation.

import sys
def solve():

    n = int(sys.stdin.readline().strip())
    nums = list(map(int, sys.stdin.readline().strip().split()))
    prev = set()
    ans = 0
    for num in nums:
        if num + 1 in prev:
            ans += 1
        prev.add(num)
        
    return ans

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

Let's consider the number of candies remaining at the evening of each day for some selected $$$(k1)$$$. Let $$$ai$$$ candies remain on day $$$i$$$. If Vasya will use another number $$$(k2 > k1)$$$ we will have less candies on the first day: $$$(b1 < a1)$$$. So Petya will eat no more candies than in the first case (for $$$k1$$$), but in the next day the number of candies will be not greater than in the first case (if $$$(n1 > n2)$$$ then $$$(n1 - n1 / 10 ≥ n2 - n2 / 10)$$$). The same way, including that $$$(k2 > k1$$$) at the evening of the second day we get $$$(b2 < a2)$$$ and so on. In general, for each $$$i$$$ we have $$$(bi < ai)$$$, so Petya will eat no more candies than in the first case in total. It means that Vasya will eat not less candies than in the first case. That means for a given $$$k1$$$ if Vasya could eat at least half of the candies, we should look for another $$$k2$$$ which is less than $$$k1$$$. And we can use binary search for that. Since Vasya eats $$$k$$$ candies and Petya eats $$$10\%$$$ of candies, its amount decreases exponentially, so there will be only a few days before all the candies will be eaten. Formally the time complexity of the solution is $$$O((\log_k n) \cdot (\log_{10} n))$$$ with constant space complexity.

def check_k(n, k):
    eaten = 0 
    curr_candies = n 
    while curr_candies > 0:
        k = min(k, curr_candies)
        eaten += k 
        curr_candies -= k
        curr_candies -= curr_candies // 10 
    
    return eaten * 2 >= n 

n = int(input())
k = n
left, right = 1, n 
while left <= right:
    mid = left + (right - left) // 2
    if check_k(n, mid):
        k = mid 
        right = mid - 1
    else:
        left = mid + 1

print(k)

Since Drake can predict Kendrick's moves, the only way Kendrick can catch Drake is if there is only one option for Drake to move. If Drake has multiple options, Kendrick will never catch him. The city has a tree-like structure with one extra edge, meaning there is one cycle inside the city. If Drake reaches the cycle faster than Kendrick, Kendrick will never catch Drake. Otherwise, Kendrick will catch him. We can implement this by using topological sort to get all the nodes inside the cycle. After identifying all the nodes in the cycle, we can use multi-source BFS to determine who reaches any of the nodes inside the cycle first.

t = int(input())
for _ in range(t):
    n,m,v = list(map(int,input().split()))
    graph = [[] for i in range(n)]
    degree = [0 for i in range(n)]
    for i in range(n):
        a,b = list(map(int,input().split()))
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
        degree[a - 1] += 1
        degree[b - 1] += 1
    
    que = deque()
    for i in range(len(degree)):
        if degree[i] == 1:
            que.append(i)
    order = []
    while  que:
        cur = que.popleft()
        order.append(cur)
        for child in graph[cur]:
            degree[child] -= 1
            if degree[child] == 1:
                que.append(child)
    
    order = set(order)
    color = [0 for i in range(n)]
    pos = 0
    color[m - 1] = 1
    color[v - 1] = 2
    que.append(m - 1)
    que.append(v - 1)
    while que:
        size = len(que)
        for i in range(size):
            cur = que.popleft()
            for neigh in graph[cur]:
                if color[neigh] == 0:
                    que.append(neigh)
                    color[neigh] = color[cur]
    
    pos  = 0
    for i in range(len(graph)):
        if i not in order and color[i] == 2:
            pos = 1
    if pos and v != m:
        print("YES")
    else:
        print("NO")
 

Check if $$$n$$$ is divisible by $$$7$$$. If so, just print $$$n$$$. If not, we can make it divisible by $$$7$$$ by just changing the one digit. We can make the last digit zero and check if the number is divisible by $$$7$$$ by incrementing one.

from sys import stdin


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

T = int(input())
for _ in range(T):
    n = int(input())

    if n%7 == 0:
        print(n)
    else:
        n -= n%10
        while n%7:
            n += 1
        print(n)    

Generally it takes the sum of each dust level except the last one, however when we select two indices $$$i$$$ and $$$j$$$ every element in between should be different strictly greater than zero so we have to consider the number of zeros involved in the operations.

That means the minimum operation that meets the goal is the summation of the number of non-zero dust-levels excluding the last dust-level and the number of zeros starting from the left-most non-zero dust-level to the right most dust-level excluding the last dust-level.

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

    max_ops = 0 
    for dust in dust_levels[:-1]:
        if dust or max_ops > dust:
            max_ops += dust + int(dust == 0)

    print(max_ops)

To solve the problem, we need to consider three cases:

• $$$k >= 3$$$ :  we can be greedy, and put the maximum number in its own segment (containing only itself), making it the minimum in that segment. Therefore, the maximum number becomes the maximum of minimums.
• $$$k = 2$$$ : the array has to be divided into a prefix and a suffix. One way is to run a loop computing the answer for each prefix-suffix pair. But there is another way, the first element $$$a_{1}$$$ will always be in the first subsegment, and the last element $$$a_{n}$$$ will always be in the second subsegment. If these numbers are small numbers, we can't avoid them. But if at least one of them is a large number, we can limit one of the segments to that number, and it will be the maximum of minimums.
  
  *It can be proven that for $$$k = 2$$$ the answer is the maximum of the first and last element. 
  
• $$$k = 1$$$ :  then the only possible partition is one segment equal to the whole array. So the answer is the minimum value on the whole array.

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

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

if k == 1:
    print(min(a))

elif k == 2:
    print(max(a[0], a[-1]))

else:
    print(max(a))
    

Firstly, we can see that for any two different vertices, their children are independent. It means that infection can not spread from children of one vertex to children of another. Also it does not matter how the infection spreads among the children of some vertex, so we only need to know the amount of vertices with the same parent.

Using this knowledge we can reduce the problem to this one: You are given an array of k

positive integers, each integer denotes the amount of healthy vertices with the same parent. Each second you can infect an integer in this array (by injection). Also each second all infected integers decrease by 1 (because of spreading).

Let's now use a greedy algorithm. We will sort this array in decreasing order and infect all integers one by one. These injections are always needed because the integers are independent. After that, each second, all numbers decrease by 1, and we can choose one number to be decreased once more in the same second.

We start from the first integer. Normally, after infecting just one of the children, the amount of time it takes for that child to infect all the others is equal to the total number of children. The total time it takes, in general, is the amount of time it took to infect the first child in the vertices with the same parent plus the number of children with the same parent. We proceed this way, starting from the largest integer.

Finally, if the last number we processed is greater than all the other numbers, our answer is the last time. If not, we need to do some additional work. If the last group we injected finishes faster than at least one of the other groups, it means we have the capacity to inject while the others spread. So, we will inject into the largest group, since we want the total time to be smaller. We use a heap to simulate this: every time, we get the largest time and decrease it by one, since we are injecting and spreading simultaneously.

from heapq import heapify, heappop, heappush
from sys import stdin


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


t = int(input())
for _ in range(t):
    n = int(input())
    parent = list(map(int,input().split()))
    
    graph = [[] for i in range(n)]
    for i in range(n -1):
        graph[parent[i] - 1].append(i + 1)
    
    graph.sort(key = lambda x : len(x),reverse=True)
    

    arr = []

    for i in graph:
        if len(i) != 0:
            arr.append(len(i))
    
    arr.append(1)
    
    for i in range(len(arr)):
        arr[i] += i
        
    if max(arr) == arr[-1]:
        print(arr[-1])
        
    else:
        
        cur_ans = arr[-1]
        for i in range(len(arr)):
            arr[i] = -arr[i]
            
        heapify(arr)
        
        while cur_ans < -arr[0]:
            cur = heappop(arr)
            heappush(arr,cur + 1)
            cur_ans += 1
            
        print(cur_ans) 

Simple greedy observation: if at some point in time there exists an animal $$$i$$$ such that no one fears it (there is no index $$$a_j=i$$$), then it is optimal to sell that animal first.

Let's iteratively sell such animals as long as they exist. After selling animal $$$i$$$, we must additionally check if animal $$$a_i$$$ has become such that no one fears it, and if so, add it to the list for sale.

What will we get when we sell all such animals? Note that when there are no such animals left, $$$a_i$$$ will form a permutation, as each animal must be feared by at least one other animal.

As it is known, a permutation consists of cycles of the form $$$i→a_i→a_{a_i}→…→i$$$.

Obviously, for each cycle we must solve the problem independently, and then combine the answers in any order. Note that if we sell animals in the order of the cycle, we will only receive a single payment for the last animal sold.

At the same time, it is not possible to obtain double payment for all animals in any case: the last animal sold from the cycle will always be sold for a single payment.

Therefore, it is optimal to sell all animals in the order of the cycle so that the animal with the minimum cost ends up being the last in this order.

import sys

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

    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    c = list(map(int, sys.stdin.readline().strip().split()))

    sons = [0] * n
    for i in range(n):
        a[i] -= 1
        sons[a[i]] += 1
        
    q = []
    for i in range(n):
        if sons[i] == 0:
            q.append(i)

    ans = []
    added = [0] * n
    while q:
        v = q.pop()
        ans.append(v)
        added[v] = 1
        sons[a[v]] -= 1
        if sons[a[v]] == 0:
            q.append(a[v])

    for v in range(n):
        if not added[v]:
            v2 = a[v]
            cycle = [v]
            while v2 != v:
                cycle.append(v2)
                v2 = a[v2]
            minc = 10 ** 9
            for u in cycle:
                added[u] = 1
                minc = min(minc, c[u])
            for i in range(len(cycle)):
                if c[cycle[i]] == minc:
                    ans += cycle[i + 1:]
                    ans += cycle[:i + 1]
                    break
    
    print(*map(lambda x: x + 1, ans))

We can compute the points gained by each person using the formula provided and compare their points.

In the formula, for $$$Misha$$$, $$$p = a$$$ and $$$t = c$$$; and for $$$Vasya$$$, $$$p = b$$$ and $$$t = d$$$.

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

a, b, c, d = map(int, input().split())

def find_points(p, t):
    return max((3*p)//10, p - (p*t)//250)


Misha = find_points(a, c)
Vasya = find_points(b, d)

if Misha > Vasya:
    print('Misha')

elif Misha < Vasya:
    print('Vasya')

else:
    print('Tie')
    

We just have to check if $$$k$$$ is equal to at least one $$$l_i$$$ and at least one $$$r_i$$$. If both conditions satisfy, we can take those intervals with $$$l_i = k$$$ and $$$r_i = k$$$ and remove the rest. Then, $$$k$$$ will have a frequency of $$$2$$$ and the rest will have a frequency of $$$1$$$ or $$$k$$$ will have a frequency of $$$1$$$ and the rest will have a frequency of $$$0$$$. If one or two of the conditions fail, we can be sure that $$$k$$$ will always have less or equal frequency with at least one of it's neighbors.

T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    
    l_ok = r_ok = False
    for _ in range(N):
        l, r = map(int, input().split())
        
        if l == K:
            l_ok = True
        if r == K:
            r_ok = True
    
    if l_ok and r_ok:
        print("YES")
    else:
        print("NO")

Since the constraints are small, let's just iterate through all possible numbers $$$b$$$ of boys in the group and count how many ways we can form the group with $$$b$$$ boys.

First, consider only the values where $$$b >= 4$$$. Given $$$b$$$, it's clear that the number of girls in the group must be $$$g = t - b$$$. If $$$g < 1$$$, don't consider this case. Given the values of $$$b$$$ and $$$g$$$, there are $$$comb(n, b)$$$* $$$comb(m, g)$$$ ways to form the group, since we can combine the boys independently of the girls. Just sum $$$comb(n, b)$$$* $$$comb(m, g)$$$ for each pair $$$(b, g)$$$.

import sys

from math import comb

n, m, t = map(int, sys.stdin.readline().strip().split())

ans = 0
for b in range(4, t):
    ans += comb(n, b)  * comb(m, t  - b)

print(ans)

A graph-related problem. The statement makes you sure that the given graph is connected and contains one (and exactly one) cycle. What you have to do is to compute the distance, in number of edges, from all vertices to the cycle (print 0 for the vertex that are in the cycle. We will call these vertices 'in-cycle').

First, let's find the cycle and find the vertices whose answer is 0. The cycle can be found with a regular Depth-First-Search (DFS), storing the fathers of the vertices. Notice that, during the search, there will be exactly one back edge, say $$$(v_i, v_j)$$$. When this edge is found, iterate from $$$v_i$$$ to $$$v_j$$$ (using the father array) and label the vertices as 'in-cycle'.

After that, let's compute the answers for the other vertices. One could "compact" the graph by merging all the 'in-cycle' vertices into a single vertex. Then, just do another search starting with this vertex and compute the distances, knowing that the distance of a vertex vi is the distance of $$$father[vi]$$$ plus one.

Also, it's also possible to do as many searches as the number of 'in-cycle' vertices if you don't consider others 'in-cycle' vertices during the search. The running time would still be $$$O(n + m)$$$, that, in this problem, is $$$O(n + n) = O(n)$$$.

import sys
import math
 
n=int(input())
e=[[] for _ in range(n)]
for _ in range(n):
   x,y=map(int,input().split())
   e[x-1].append(y-1)
   e[y-1].append(x-1)
d=[len(x) for x in e]
q=[i for i in range(n) if d[i]==1]
 
c=[0]*n
for u in q:
   c[u]=n
   for v in e[u]:
   	d[v]-=1
   	if d[v]==1:
       	q.append(v)
q.extend(i for i in range(n) if not c[i])
for u in q[::-1]:
   for v in e[u]:
   	c[v]=min(c[v],c[u]+1)
print(" ".join(map(str,c)))

If the number of candies is less than $$$k$$$, Marmot can only eat red candies, which means the answer is always $$$1$$$. If the number of candies is equal to $$$k$$$, Marmot can eat $$$k$$$ red candies at once or $$$k$$$ white candies at once, making the answer $$$2$$$. We can consider these two cases as the base case. Now, the problem arises when the number of candies is greater than $$$k$$$. The $$$(ith)$$$ candy sequences can be either red or white, so we have two options at each sequence of candies. Let’s look at those options one by one: 1. If the $$$(ith)$$$ sequence of candies is red, the remaining $$$(i - 1)$$$ candies can be red and white. 2. If the $$$(ith)$$$ sequence of candie is white, the remaining $$$(k - 1)$$$ candies should be white and the rest $$$(i - k)$$$ candies can be red and white. Since our target is to find the number different ways of candies sequences in which Marmot can eat, the answer for the $$$(ith$$$) sequence will be the summation of the number of ways at $$$(i - 1)$$$ and the number of ways at $$$(i - k)$$$. We can utilize prefix sum to answer with constant time complexity for each given input query or test case without recalculating again.

MAX = 10 ** 5 + 1
MOD = 10 ** 9 + 7
t, k = map(int, input().split())

# it is obvious that the number of ways to in which Marmont can eat his dinner is 1 if the number of candies is less than k 
prfx = [1] * MAX
prfx[0] = 0

# if the number of candies is equal to k the number of ways to eat his dinner is 2
prfx[k] = 2

# if the number of candies is greater than k the number of ways to eat his dinner is prfx[ith - 1] + prfx[ith - k] 
for i in range(k + 1, MAX):
    prfx[i] = (prfx[i - 1] + prfx[i - k]) % MOD 

# calculating the prefix sum of the number of ways to eat his dinner to minimize the time complexity from O(t * (b - a)) to O(MAX)
for i in range(1, MAX):
    prfx[i] = (prfx[i] + prfx[i - 1]) % MOD

for _ in range(t):
    a, b = map(int, input().split())
    print((prfx[b] - prfx[a - 1]) % (10 ** 9 + 7))

You should count the number of parentheses at the end of the string, suppose there are $$$x$$$ such parentheses. Then if $$$x>n/2$$$, the message is bad. Note that you should divide n by 2 without rounding. Or you can compare $$$2\cdot x$$$ and $$$n$$$ instead. If $$$2 \cdot x>n$$$, the message is bad.

for _ in range(int(input())):
    n = int(input())
    word = input()
    ind = n - 1
    
    while ind >= 0 and word[ind] == ')':
   	 ind -= 1
   	 
    print("NO" if ind >= (n - 1)//2 else "YES")

So, the first idea that is coming into mind is prefix sums. Let's define two values $$$l_i=max(0,a_i−a_i+1)$$$ and $$$r_i=max(0,a_i+1−a_i)$$$. The value $$$l_i$$$ means the amount of fall damage when we are going to the right from the column $$$i$$$ to the column $$$i$$$+$$$1$$$, and $$$r_i$$$ means the amount of fall damage when we are going to the left from the column $$$i$$$+$$$1$$$ to the column $$$i$$$. Then let's build prefix sums on these two arrays. Now let $$$p_{l_i}$$$ be the sum of all li on a prefix [0;i) (i. e. $$$p_{l_0}$$$=0), and $$$p_{r_i}$$$ be the sum of all $$$r_i$$$ on a $$$prefix [0;i)$$$. Then if $$$s<t$$$ in a query, the answer is $$$pl_{t−1}$$$ − $$$pl_{s−1}$$$, otherwise (if $$$s>t$$$) the answer is $$$pr_{s−1}$$$ − $$$pr_{t−1}$$$.

Time complexity: $$$O(n)$$$.

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [0] + [max(0, a[i] - a[i + 1]) for i in range(n - 1)]
r = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)]
for i in range(n - 1):
    l[i + 1] += l[i]
    r[i + 1] += r[i]
for _ in range(m):
    s, t = map(int, input().split())
    if s < t:
        print(l[t - 1] - l[s - 1])
    else:
        print(r[s - 1] - r[t - 1])

From the condition about the fact that each vertex equally respects all its ancestors, we can understand that each vertex is either always a candidate for deletion or it can never be deleted. That is because when we delete some vertex all new vertices which become sons of it's parent are also disrespecting it.

Now we can iterate over all vertices and if it respects it's parent, we will remember that it's parent can not be deleted. And so we will get the answer.

from collections import defaultdict
from sys import stdin


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

N = int(input())

child = defaultdict(list)
respect = [0]*N

root = 0

for ch in range(N):
    p, c = map(int, input().split())
    p -= 1
    respect[ch] = c
    if p == -2:
        root = ch
        continue
    child[p].append(ch)

stack = [root]

ans = []

while stack:
    v = stack.pop()
    ok = respect[v]
    for ch in child[v]:
        stack.append(ch)
        if respect[ch] == 0:
            ok = False
    if ok:
        ans.append(v + 1)
if not ans:
    print(-1)
else:
    print(*sorted(ans))

A unique subarray is created only if its leftmost element is the first occurrence in the input array and its rightmost element is the last occurrence, regardless of the elements in between.

Note that a subarray suits us if $$$al$$$ is the leftmost occurrence of the number $$$al$$$ in the array and $$$ar$$$ is the rightmost occurrence of the number $$$ar$$$ in the array. Let's create an array$br$ filled with zeros and set $$$br=1$$$ if $$$ar$$$ is the rightmost occurrence of the number $$$ar$$$ in the array (this can be done using sets or dictionaries). Now we need to consider all suitable left boundaries and see how many suitable right boundaries we have on the prefix, by precomputing a prefix sum of the right boundaries.

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

    visited = set()
    right_most = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        if arr[i] not in visited:
            visited.add(arr[i])
            right_most[i + 1] = 1
            visited.add(arr[i])
    
    for i in range(1, len(right_most)):
        right_most[i] += right_most[i - 1]

    visited.clear()
    ans = 0
    for i in range(n):
        if arr[i] not in visited:
            ans += right_most[-1] - right_most[i]
            visited.add(arr[i])

    print(ans)

We only need two segments to check if the answer is $$$YES$$$.

The claim is that if the answer exists, we can take the segment with the minimum right boundary and the segment with the maximum left boundary (let's denote these boundaries as $$$r_{1}$$$ and $$$l_{2}$$$). Therefore, if $$$r_{1}<l_{2}$$$, it is obvious that this pair of segments is suitable for us. Otherwise, all pairs of segments intersect because they have common points in the range $$$l_{2}…r_{1}$$$ .

To keep track of the maximum left and minimum right boundaries, we can use max heap and min heap respectively. Since we might lose track of some segments, we can keep the count of a segment using its boundaries.

import sys
from collections import defaultdict
from heapq import heappush, heappop
input = lambda: sys.stdin.readline().rstrip()

q = int(input())

# to keep track of deleted and duplicate segments
sgt_count = defaultdict(int)
mxheap = [] # to store the largest l value
mnheap = [] # to store the smallest r value

for _ in range(q):
    operation, l, r = input().split()
    l, r = int(l), int(r)

    if operation == '+':
        heappush(mxheap, (-l, r))
        heappush(mnheap, (r, l))
        sgt_count[(l, r)] += 1
    else:
        sgt_count[(l, r)] -= 1

    # remove segments from max heap if they no longer exists on sgt_count
    while mxheap:
            neg_left, right = mxheap[0]
            if sgt_count[(-neg_left, right)]:
                break

            else:
                heappop(mxheap)
    
    # remove segments from min heap if they no longer exists on sgt_count
    while mnheap:
        right, left = mnheap[0]
        if sgt_count[(left, right)]:
            break

        else:
            heappop(mnheap)

    # compare the smallest r value with the largest l value
    if mxheap and mnheap and -mxheap[0][0] > mnheap[0][0]:
        print('YES')
    else:
        print('NO')
            
    

First we need to find the frequencies of the first $$$k$$$ alphabets in the string. Let the minimum frequency among these frequencies be $$$m$$$. Then we cannot select $$$m + 1$$$ characters of one kind, and we can definitely select $$$m$$$ characters of each kind, hence the answer is given by min(frequency of first k characters) * $$$k$$$.

import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

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

count = Counter(s)
ans = float("inf")

for i in range(k):
    char = chr(i + ord('A'))
    ans = min(ans, count[char])

ans *= k
print(ans)
    

Think about addition in base two. Consider two binary numbers: $$$a = 10101$$$, $$$b = 1001 $$$

To perform a bitwise operation that modifies the bits in these numbers, observe the following:

1. When the first bit in $$$ a $$$ is $$$1$$$ and the first bit in $$$ b $$$ is $$$1$$$ (as in the example), you can make both $$$0$$$ by setting that bit in $$$ x $$$ to $$$1$$$. This is the only way to decrease the resulting sum in binary addition.

2. The operation to achieve this can be represented as $$$ x = a \& b $$$, where $$$\& $$$ is the bitwise AND operation. This results in a bitmask where only the bits that are $$$1$$$ in both $$$ a $$$ and $$$ b $$$ are set to $$$1$$$.

3. Using this bitmask $$$ x $$$, you can create modified versions of $$$ a $$$ and $$$ b $$$ by XORing them with $$$ x $$$:

• $$$ a' = a \oplus x $$$
• $$$ b' = b \oplus x $$$

1. Adding these modified versions gives the result. The formula $$$(a \oplus x) + (b \oplus x)$$$ can be further simplified using properties of XOR and AND operations.

We deduce that:

$$$ (a \oplus x) + (b \oplus x) = a \oplus b $$$

This can be proved using properties of bitwise operations:

• $$$ a \oplus x $$$ clears the bits that are $$$1$$$ in both $$$ a $$$ and $$$ b $$$, effectively removing the carry bits.

• $$$ b \oplus x $$$ does the same for $$$ b $$$.

The sum of these modified values is the same as $$$ a \oplus b $$$, where $$$\oplus$$$ is the bitwise XOR operation.

import sys

input = sys.stdin.readline

t = int(input())
for _ in range(t):
    a,b  = map(int, input().split())
    print(a^b)

Let's find out the total damage for a fixed value of $$$k$$$. Since the effect of the poison from the $$$i$$$-th attack deals damage $$$min(k,a_{i+1}−a_i)$$$ seconds for $$$i<n$$$ and $$$k$$$ seconds for $$$i=n$$$, then the total damage is $$$k + \sum_{i=1}^{n-1} \min(k, a_{i+1} - a_i)$$$. We can see that the higher the value of $$$k$$$, the greater the total sum. So we can do a binary search on $$$k$$$ and find the minimum value when the sum is greater than or equal to $$$h$$$.

import sys


def solve():

    n, h = map(int, sys.stdin.readline().strip().split())
    a = list(map(int, sys.stdin.readline().strip().split()))

    def checker(k):
        cur = k
        for i in range(n - 1):
            cur += min(k, a[i + 1] - a[i])
        return cur >= h
    
    low = 1
    high = h

    while low <= high:

        mid = (low + high)//2

        if checker(mid):
            high = mid - 1
        else:
            low = mid + 1
            
    return low
    
t = int(sys.stdin.readline().strip())  
for _ in range(t):
    print(solve())
    

Firstly we have to note that the second soldier should choose only prime numbers. If he choose a composite number $$$x$$$ that is equal to $$$p \cdot  q$$$, he can choose first $$$p$$$, then $$$q$$$ and get a better score. So our task is to find a number of prime factors in factorization of $$$n$$$. Now we have to note the factorization of number $$$a! / b!$$$ is this same as factorization of numbers $$$(b + 1)*(b + 2)*...*(a - 1)*a$$$. Let's count the number of prime factors in the factorization of every number from $$$2$$$ to $$$5000000$$$.

First, we use Sieve of Eratosthenes to find a prime divisor of each of these numbers. Then we can calculate a number of prime factors in factorization of a using the formula: $$$primeFactors[a] =  primeFactors[a / primeDivisor[a]]  +  1$$$ When we know all these numbers, we can use a prefix sum, and then answer for sum on interval.

import sys

input = sys.stdin.readline
dp = [0] * 5000005

def solve():
    n, m = map(int, input().split())
    print(dp[n] - dp[m])

def sieve(n):
    primes = [True] * (n + 1)
    for i in range(2, n + 1):
        if not primes[i]:
            continue
        num = i * 2
        while num <= n:
            primes[num] = False
            num += i

    ans = [i for i in range(2, n + 1) if primes[i]]
    return ans

def preCompute():

    
    ans = sieve(5000001)
    for a in ans:
        dp[a] = 1

    q = int(input())

    for i in range(2, 5000001):
        if dp[i]:
            continue
        d = 0
        while ans[d] * ans[d] <= i:
            if i % ans[d] == 0:
                dp[i] = dp[i // ans[d]] + 1
                break
            d += 1

    for i in range(1, 5000001):
        dp[i] += dp[i - 1]

    for i in range(q):
        solve()

if __name__ == "__main__":
    preCompute()

It is a simple problem, but many competitors used some wrong guesses and failed. First of all, we should check if $$$n$$$ is at most $$$3$$$ and then we can simply output $$$1,2,6$$$.

Now there are two cases: When n is odd, the answer is obviously $$$n(n-1)(n-2)$$$. When n is even, we can still get at least $$$(n-1)(n-2)(n-3)$$$, so these three numbers in the optimal answer would not be very small compared to $$$n$$$. So we can just iterate every $$$3$$$ number triple in $$$[n-50,n]$$$ and update the answer.

from math import lcm

N = int(input())

ans = 0
if N >= 3:
    ans = lcm(N, N - 1, N - 2)

if N >= 4:
    ans = lcm(N - 1, N - 2, N - 3)

min_n = max(1, N - 50)
for i in range(min_n, N + 1):
    for j in range(min_n, N + 1):
        for k in range(min_n, N + 1):
            ans = max(ans, lcm(i, j, k))
print(ans)

If the given input $$$n$$$ is $$$1$$$, the answer will always be $$$2$$$. If the given input $$$n$$$ is divisible by $$$3$$$, that is the minimum distance to reach there. However, if it is not, it means the number is either $$$1$$$ or $$$2$$$ less than any number divisible by $$$3$$$. So, if it's less than by $$$2$$$, we can just add $$$1$$$ to our answer since we can take $$$2$$$ steps. If it's less than by $$$1$$$, we can also add $$$1$$$ to our answer because we will take $$$(n//3)−1$$$ steps and additional $$$3+1=4$$$ steps, which is two $$$2$$$ steps. This means the original answer will be $$$(n//3)$$$ and if the number is not divisible by$3$, we can just add $$$1$$$ to our answer.

for _ in range(int(input())):
    n = int(input())
    if n == 1:
        print(2)
        continue

    ans = n // 3 
    # if n is either less by 1 or 2 from any number divisible by 3
    # if it's less by 1 we can take (n // 3) - 1 step and additional 2 * 2 step 
    # if it's less by two we can take (n // 3) step and 2 additional step
    if n % 3:
        ans += 1

    print(ans)

The problem is about considering the least amount of cases possible. I propose the following options.

If $$$x≠1$$$, then you can always print n ones. So the answer is $$$YES$$$.

If $$$k=1$$$, then no integer is available, so the answer is $$$NO$$$.

If $$$k=2$$$, then only $$$2$$$ is available, so you can only collect even $$$n$$$. So if it's odd, the answer is $$$NO$$$.

Otherwise, you can always collect n with the following construction: if $$$n$$$ is even then take $$$2$$$, otherwise take $$$3$$$. Then take $$$\left\lfloor \frac{n}{2} \right\rfloor - 1$$$ twos. You can see that an even $$$n$$$ only uses twos, so it fits the previous check. If it's odd, then $$$k$$$ is at least $$$3$$$, so $$$3$$$ is allowed to take.

Overall complexity: $$$O(n)$$$ per testcase.

import sys
for _ in range(int(input())):
    n, k, x = map(int, sys.stdin.readline().strip().split())
    if x != 1:
	print("YES")
	print(n)
	print(*([1] * n))
    elif k == 1 or (k == 2 and n % 2):
	print("NO")

    else:
	print("YES")
	print(n // 2)
		
	print(*([2] * (n // 2 - 1)) + [3 if n % 2 == 1 else 2])
    

Let's sort the edges by their weight in descending order and merge the vertices in that order. Whenever you get an already merged vertices, it means the new edge will create cycle; we can update our answer to that edge. Finally, to get the cycle, we can do DFS from either end of that edge until we get to the other end.

from collections import defaultdict
from sys import stdin


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

class DSU:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, v):
        while v != self.p[v]:
            self.p[v] = self.p[self.p[v]]
            v = self.p[v]
        return v
    
    def merge(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.size[pu] < self.size[pv]:
            pu, pv = pv, pu
        self.size[pu] += self.size[pv]
        self.p[pv] = pu
        return True

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    edges = []
    adj = defaultdict(list)
    for __ in range(M):
        u, v, w = map(int, input().split())
        u, v = u - 1, v - 1
        edges.append((w, u, v))
        adj[u].append(v)
        adj[v].append(u)

    edges.sort(key=lambda edge: edge[0], reverse=True)
    dsu = DSU(N)
    for w, u, v in edges:
        if not dsu.merge(u, v):
            ans = (w, u, v)

    min_w, st, end = ans
    stk = [st]


    # DFS to get the cycle
    p = [-1]*N
    p[st] = st
    while stk:
        v = stk.pop()
        for ch in adj[v]:
            if v == st and ch == end: continue
            if ch == end:
                p[ch] = v
                stk = []
                break
            if p[ch] == -1:
                p[ch] = v
                stk.append(ch)
    v = end
    path = []
    while p[v] != v:
        path.append(v)
        v = p[v]
    path.append(st)

    print(min_w, len(path))
    for i in range(len(path)):
        path[i] += 1
    print(*path)

Conclusion first:

First, we transform each digit of the original number as follows:

$$$0$$$, $$$1$$$ $$$\Rightarrow$$$ empty

$$$2$$$ $$$\Rightarrow$$$ $$$2$$$

$$$3$$$ $$$\Rightarrow$$$ $$$3$$$

$$$4$$$ $$$\Rightarrow$$$ $$$3,2,2$$$

$$$5$$$ $$$\Rightarrow$$$ $$$5$$$

$$$6$$$ $$$\Rightarrow$$$ $$$5,3$$$

$$$7$$$ $$$\Rightarrow$$$ $$$7$$$

$$$8$$$ $$$\Rightarrow$$$ $$$7,2,2,2$$$

$$$9$$$ $$$\Rightarrow$$$ $$$7,3,3,2$$$

Then, sort all digits in decreasing order as a new number, then it will be the answer.

Proof:

We can observe that our answer won't contain digits $$$4,6,8,9$$$, because we can always transform digits $$$4,6,8,9$$$ to more digits as in the conclusion, and it makes the number larger.

Then, how can we make sure that the result is the largest after this transformation?

We can prove the following lemma:

For any positive integer $$$x$$$, if it can be written as the form $$$(2!)^{c_2}\times (3!)^{c_3}\times (5!)^{c_5}\times (7!)^{c_7}$$$, there will be only one unique way.

Suppose that there exists two ways to write down x in this form, we can assume that the two ways are $$$(2!)^{a_2}\times (3!)^{a_3}\times (5!)^{a_5}\times (7!)^{a_7}$$$ and $$$(2!)^{b_2}\times (3!)^{b_3}\times (5!)^{b_5}\times (7!)^{b_7}$$$.

We find the largest $$$i$$$ such that $$$ai ≠ bi$$$, Then we know there exists at least one prime number whose factor is different in the two ways.

But according to the Fundamental Theorem of Arithmetic, there is only one prime factorization of each integer. So we get a contradiction.

After getting the result, we don't need to worry about other numbers being larger than ours.

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

N = int(input())
num = input()

digits = []
for digit in num:
    if digit == '4':
        digits.extend(['3','2', '2'])
    elif digit == '6':
        digits.extend(['5', '3'])
    elif digit == '8':
        digits.extend(['7', '2', '2', '2'])
    elif digit == '9':
        digits.extend(['7', '3', '3', '2'])
    elif digit in "2357":
        digits.append(digit)

digits.sort(reverse=True)

print("".join(digits))

First of all, always comparing strings takes quite a long time, so let's create a graph using an $$$ n \times n $$$ grid where $$$graph_{i,j} = 1$$$ denotes that the $$$ith$$$ and $$$ jth$$$ song can be consecutive and $$$0$$$ otherwise. Now, we can do a dynamic programming solution over subsets.

We denote mask as our current bit-mask and we say it has the value of all elements we include. For example, if our mask is equal to 7, in binary it looks like ...000111, so we can say that we included elements 0, 1 and 2. Each power of two set in our mask, implies we include that element.

So now, if we iterate over masks and the last included element, we can mark dpmask,i

as a boolean which tells whether it is possible to get to this state. We transition from a state to another by using the current mask and trying to include all non-included elements one-by-one, and checking out if it is possible to include them. If it is, we update our new mask.

After calculating for each state whether we can get to it, using previously calculated states, we update our answer as the maximum number of included elements (bits set) in a mask which is obtainable.

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")


for _ in range(int(input())):
   n = int(input())
   g = [[0] * n for _ in range(n)]
   a = [input().split() for _ in range(n)]


   for i in range(n):
       for j in range(i):
           if a[i][0] == a[j][0] or a[i][1] == a[j][1]:
               g[i][j] = g[j][i] = 1
  
   dp = [[0] * n for _ in range(1 << n)]


   for i in range(n):
       dp[1 << i][i] = 1


   ans = 1


   for i in range(1, 1 << n):
       for j in range(n):
           if dp[i][j]:
               takes = bin(i).count('1')
               ans = max(ans, takes)
               for k in range(n):
                   if i & (1 << k) == 0 and g[j][k] == 1:
                       dp[i | 1 << k][k] = 1
  
   print(n - ans)

We can divide the given string into substrings of length 1, 2, 3, 4, ... and take the first character from each subarray. Since we don't have to actually generate the substrings, we can just take the first character in $$$t$$$, jump one step and take a character, then jump two steps and take a character, then three steps, ...

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

n = int(input())
t = input()

jump = 1
i = 0
s = ""

while i < n:
    s += t[i]
    i += jump
    jump += 1

print(s)

Let's use the greedy solution: we will go through the digits in decreasing order. If the sum of $$$s$$$ we need to dial is greater than the current digit, we add the current digit to the end of the line with the answer.

Note that in this way we will always get an answer consisting of the minimum possible number of digits, because we are going through the digits in descending order.

Suppose that the resulting number is not optimal. Then some digit can be reduced, and some digit that comes after it can be increased, in order to save the sum (we can not increase the digit before it, as then we get a number greater than the current one). Two variants are possible.

We want to increase the digit $$$x$$$ to $$$x+1$$$, but then it becomes equal to the digit following it, or exceeds the value $$$9$$$. Then we can't increment that digit. Otherwise, in the first step, we can get $$$x+1$$$ instead of $$$x$$$, but since we are going through the digits in decreasing order, we cannot get the value of $$$x$$$ in that case. Contradiction.

T = int(input())

for _ in range(T):
    n = int(input())

    ans = []
    for digit in range(9, 0, -1):
        if n >= digit:
            ans.append(digit)
            n -= digit
    ans.reverse()
    print(*ans, sep="")

To begin with, let's note that potions of types $$$p1,p2,…,pk$$$ are essentially free, so we can replace their costs with 0.

Let $$$ans_i$$$ be the answer for the $$$i-th$$$ potion. Each potion can be obtained in one of two ways: by buying it or by mixing it from other potions. For mixing, we obtain all the required potions at the minimum cost. That is, if there is a way to mix a potion of type $$$i$$$, then the answer for it is either $$$c_i$$$ or the sum of answers for all $$$e_i$$$. Since the graph in the problem does not have cycles, this can be done by a simple breadth-first or depth-first search.

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
def solve():
	n, k = map(int, input().split())
	cost = [0] + list(map(int, input().split()))
	nums = set(map(int, input().split()))

	graph = defaultdict(list)
	degree = [0] * (n + 1)
	future = [0] * (n + 1)
	ans = [0] * (n + 1)
    
	for i in range(1, n + 1):
    	line = list(map(int, input().split()))
    	m, edges = line[0], line[1:]
    	if i in nums:
        	continue
    	degree[i] = m
    	for a in edges:
        	graph[a].append(i)

	queue = deque()
	for node in range(1, n + 1):
    	if node in nums:
        	queue.append(node)
    	elif degree[node] == 0:
        	ans[node] = cost[node]
        	queue.append(node)

	while queue:
    	node = queue.popleft()
    	for child in graph[node]:
        	degree[child] -= 1
        	future[child] += ans[node]
        	if degree[child] == 0:
            	queue.append(child)
            	ans[child] = min(cost[child], future[child])

	print(*ans[1:])

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

We will do binary search on the answer. The lower bound can be set to $$$max(a_{1},…,a_{n})$$$, while $$$max(a_{1},…,a_{n}) + min(n, k)$$$ is enough for the upper bound.

Let $$$b$$$ be some resulting array after performing at most $$$k$$$ operations.

Suppose for some $$$x$$$ we want to check if we can get $$$max(b_{1},…,b_{n})≥x$$$ in at most $$$k$$$ operations. That is, there must exist some index $$$i$$$ such that $$$b_{i}≥x$$$. So, let's iterate $$$i$$$ from $$$1$$$ to $$$n$$$ and check if it possible to have $$$b_{i}≥x$$$ in at most $$$k$$$ operations.

Let $$$f(i,y)$$$ be the minimum number of operations needed to make $$$b_{i}≥y$$$. Then:

• $$$f(i,y)=0$$$ for all $$$y≤a_{i}$$$,
• $$$f(i,y)=y−a_{i}+f(i+1,y−1)$$$ for all $$$1≤i<n$$$ and $$$y>a_{i}$$$,
• $$$f(i,y)=+∞$$$ for $$$i=n$$$ and all $$$y>a_{i}$$$.

It is easy to see that calculating $$$f(i,x)$$$ takes $$$O(n)$$$ time for one call in the worst case.

Thus, our check consists of comparing $$$f(i,x)$$$ and $$$k$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$. If at least one of the values is $$$≤k$$$, it is possible to have some $$$b_{i}≥x$$$ in at most $$$k$$$ operations and we increase the lower bound in the binary search after updating the current answer. Otherwise, it is impossible and we decrease the upper bound.

Time Complexity: $$$O(n^2⋅log(A))$$$, where A is the minimum of $$$n$$$ and $$$k$$$.

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


def check(max_val):

    # consider each index if it can be where we can achieve this 'max_val'
    for i in range(n):

        cost = 0
        cur_val = max_val
        for j in range(i, n):
            
            # if it is the last index and in needs to be incremented
            # we are not allowed to increase the last number
            # we can get away by making cost = k + 1, it will not return True
            if a[j] < cur_val and j == n - 1:
                cost = k + 1
                break
            
            if a[j] >= cur_val:
                break

            cost += cur_val - a[j]
            next_val = max(cur_val - 1, 0)
            cur_val = next_val

        if cost <= k:
            return True

    return False



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

    low = max(a)
    high = max(a) + min(k, n)

    while low <= high:

        mid = low + (high - low)//2

        if check(mid):
            low = mid + 1
        
        else:
            high = mid - 1
    
    print(high)

We don't need to ever go over an edge more than once, since going over an edge twice cancels out (since $$$a$$$ $$$XOR$$$ $$$a$$$=0 for all $$$a$$$)

Let's ignore the teleporting, and decide how to find the answer. Note that we don't need to ever go over an edge more than once, since going over an edge twice cancels out (since $$$a$$$ $$$XOR$$$ $$$a$$$=0 for all $$$a$$$). In other words, the only possible value of $$$x$$$ equals the XOR of the edges on the unique path from $$$a$$$ to $$$b$$$. We can find it through a DFS from $$$a$$$, continuing to keep track of XORs as we move to each adjacent node, and XORing it by the weight of the corresponding edge as we travel across it.

Now let's include the teleport. It means that we travel from $$$a→c$$$, then teleport to $$$d$$$, and go from $$$d→b$$$, for some nodes $$$c$$$ and $$$d$$$. Also, we cannot pass $$$b$$$ on the path from $$$a→c$$$.

Again, note that the value of $$$x$$$ is fixed on each of the paths from $$$a→c$$$ and $$$d→b$$$, since there is a unique path between them. Let $$$x_1$$$ be the XOR of the first path and $$$x_2$$$ be the XOR of the second. Then we need $$$x_1 XOR x_2=0⟹x_1=x_2$$$. So we need to find if there are two nodes $$$c$$$, $$$d$$$ such that the XORs from $$$a$$$ and $$$b$$$ to those nodes are the same. To do this, we can do our $$$DFS$$$ from before, but instead run one $$$DFS$$$ from $$$a$$$ and another from $$$b$$$, and check if any two values are the same.

Make sure not to include nodes past $$$b$$$ while we look for $$$c$$$ on our DFS from $$$a$$$. The time complexity is $$$O(nlogn)$$$.

import sys
from collections import defaultdict

def solve():

    n, a, b = map(int, sys.stdin.readline().strip().split())
    graph = defaultdict(list)

    for _ in range(n - 1):
        u, v, w = map(int, sys.stdin.readline().strip().split())
        graph[u].append((v, w))
        graph[v].append((u, w))

    pref1 = [-1] * (n + 1)
    pref1[a] = 0
    stack = [(a, -1)]
    
    while stack:
        node, par = stack.pop()

        for ne, w in graph[node]:
            if ne != par:
                if ne == b:
                    if w ^ pref1[node] == 0:
                        return "YES"
                    continue
                
                pref1[ne] = w ^ pref1[node]
                stack.append((ne, node))
                
    ss = set(pref1)
    pref2 = [-1] * (n + 1)
    pref2[b] = 0
    stack = [(b, -1)]
    
    while stack:

        node, par = stack.pop()

        for ne, w in graph[node]:

            if ne != par:

                pref2[ne] = w ^ pref2[node]

                if pref2[ne] in ss:
                    return "YES"
                
                stack.append((ne, node))
  
    return "NO"

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

At first let's calculate how many portions of stewed fruit (in one portion — $$$1$$$ lemon, $$$2$$$ apples and $$$4$$$ pears) we can cook. This number equals to $$$min(a, b\ div\ 2, c\ div\ 4)$$$, where $$$x\ div\ y$$$ is integer part of $$$x / y$$$. After that we need to multiply this number of $$$7$$$, because there is $$$7$$$ fruits in $$$1$$$ portion, and print the result.

a = int(input())
b = int(input())
c = int(input())

spris = min(a, b//2, c//4)
print(spris*7)

We can easily remove any $$$BAN$$$ sequences in the given input string by bringing all $$$Ns$$$ to the beginning and all $$$Bs$$$ to the end of the input string. To minimize the number of operations needed, we can consider at each step two $$$BAN$$$ sequences: the leftmost one and the rightmost one. Then we can swap the letter $$$B$$$ of the leftmost one with the letter $$$N$$$ of the rightmost one.

def main():
    for _ in range(int(input())):
        n = int(input())
        k = []
        
        start, end = 1, 3 * n 
        while start < end:
            k.append([start, end])
            start += 3
            end -= 3    

        print(len(k))
        for each in k:
            print(*each) 
        
if __name__ == "__main__":
    main()

We process the potions from left to right. At the same time, we maintain the list of potions we have taken so far. When processing potion $$$i$$$, if we can take $$$i$$$ without dying, then we take it. Otherwise, if the most negative potion we've taken is more negative than potion $$$i$$$, then we can swap out potion $$$i$$$ for that potion. To find the most negative potion we've taken, we can maintain the values of all potions in a heap. This runs in $$$O(n \log n)$$$.

To prove that this works, let's consider the best solution where we take exactly $$$k$$$ potions (best as in max total health). The solution involves taking the $$$k$$$ largest values in our heap. Then when considering a new potion, we should see whether swapping out the new potion for the $$$k$$$ th largest potion will improve the answer.

Since the heap is strictly decreasing, there will be a cutoff $$$K$$$, where for $$$k$$$ at most $$$K$$$, the answer is not affected, and for larger than $$$K$$$, we swap out the $$$k$$$th largest potion. It turns out this process is equivalent to inserting the new potion's value into the heap. For those positions at most $$$K$$$, they are not affected. For the positions larger than $$$K$$$, the elements get pushed back one space, meaning that the smallest element is undrinked.

This can also be seen as an efficient way to transition from one layer of the $$$dp$$$ table to the next.

import heapq

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

h = []
total_sum = 0

for potion in a:
	total_sum += potion
	heapq.heappush(h, potion)
	while total_sum < 0:
    	total_sum -= heapq.heappop(h)

print(len(h))

So let's try to understand what the final array looks like in terms of the initial array. The best way to see this is to look at the process backwards. Basically, start with the final array, and keep replacing an element with the $$$2$$$ elements that xor-ed down to it, until you get the initial array. You'll see that the first element turns into a prefix, the second element turns into a subarray that follows this prefix, and so on. Hence, the whole process of moving from the initial to the final array is like we divide the array into pieces, and then replace each piece with its xor, and we want these xors to be equal.

A nice observation is: we need at most $$$3$$$ pieces. That's because if we have $$$4$$$ or more pieces, we can take $$$3$$$ pieces and merge them into one. Its xor will be the same, but the total piece count will decrease by $$$2$$$ .

Now, checking if you can divide it into $$$2$$$ or $$$3$$$ pieces is a simple task that can be done by bruteforce. You can iterate over the positions you'll split the array, and then check the xors are equal using a prefix-xor array.

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


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

    pref_xor = [a[0]]
    for i in range(1, n):
        pref_xor.append(pref_xor[-1] ^ a[i])

    yes = False

    # if we can create two subarrays of equal xor,
    # the total xor should be zero.
    if pref_xor[-1] == 0:
        yes = True

    # check for three subarrays
    for i in range(n):
        if yes:
            break
        
        first_subarray = pref_xor[i]
        for j in range(i + 1, n):
            second_subarray = pref_xor[j] ^ pref_xor[i]
            third_subarray = pref_xor[-1] ^ pref_xor[j]

            if first_subarray == second_subarray == third_subarray:
                yes = True
                break

    print('YES' if yes else 'NO')

import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
 
    pref_xor = [a[0]]
    for i in range(1, n):
        pref_xor.append(pref_xor[-1] ^ a[i])
    
    
    suf_xor = 0
    last_idx = defaultdict(lambda : -1) 

    for i in range(n - 1, -1, -1):
        suf_xor ^= a[i]
        last_idx[suf_xor] = max(last_idx[suf_xor], i)
    
    yes = False
 
    for i in range(n):
        # two subarrays
        first = pref_xor[i]
        second = pref_xor[-1] ^ first
        if first == second:
            yes = True
            break
        
        # three subarrys
        # the prefix xor should occur as a sufix after this index 
        if pref_xor[-1] ^ first == 0 and last_idx[first] > i:
            yes = True
            break

    print('YES' if yes else 'NO')

Note, that if we can reach the destination in $$$x$$$ days, so we can reach it in $$$y≥x$$$ days.

Note, that if we can reach the destination in $$$x$$$ days, so we can reach it in $$$y≥x$$$ days, since we can stay in the destination point by moving to the opposite to the wind direction. So, we can $$$binary search$$$ the answer.

To check the possibility to reach the destination point $$$(x_2,y_2)$$$ in $$$k$$$ days we should at first look at the position $$$(x_3,y_3)$$$ the wind moves ship to. Now we can calculate where we can go: since each day we can move in one of four directions or not move at all, we can reach any point $$$(x,y)$$$ with Manhattan distance $$$|x−x_3|+|y−y_3|≤k$$$. So we need to check that $$$|x_2−x_3|+|y_2−y_3|≤k$$$.

To calculate $$$(x_3,y_3)$$$ we can note, that there were $$$\left\lfloor \frac{k}{n} \right\rfloor$$$ full cycles and $$$k \bmod n$$$ extra days. So it can be calculated using running sum.

Finally, about borders of binary search: to reach the destination point we need to move closer at least by one (it terms of Manhattan distance) from the full cycle of the wind. So, if answer exists then it doesn't exceed $$$(|x_1−x_2|+|y_1−y_2|)⋅n≤2⋅10^{14}$$$.

import sys

x_1, y_1 = map(int, sys.stdin.readline().strip().split())
x_2, y_2 = map(int, sys.stdin.readline().strip().split())
n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()

def find(ch):

    if ch == "U":
        return [0, 1]
    
    if ch == "D":
        return [0, -1]
    
    if ch == "L":
        return [-1, 0]
    
    if ch == "R":
        return [1, 0]
    
def checker(k):
        
    x_3, y_3 = x_1, y_1
    full_cycles = k // n
    extra_days = k % n

    for ch in s:
        x_3 += find(ch)[0] * full_cycles
        y_3 += find(ch)[1] * full_cycles
    
    for i in range(extra_days):
        x_3 += find(s[i])[0]
        y_3 += find(s[i])[1]
        
    return abs(x_2 - x_3) + abs(y_2 - y_3) <= k

low = 1
high = 10**15

while low <= high:

    mid = (low + high) // 2

    if checker(mid):
        high = mid - 1
    else:
        low = mid + 1

if low > 10**15:
    print(-1)
else:
    print(low)

In a palindrome, the first and last characters are equal, the second and second last characters are equal, ...

Since we are going to double every character, the size of the output will be twice of the original. So if we place a copy of the first character at the last index, the copy of the second character at the second last index, and continue like this, the result will be $$$s + reverse(s)$$$.

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

t = int(input())
for _ in range(t):
    s = input()
    
    s_reverse = s[::-1] 
    print(s + s_reverse)

We assume the answer is $$$x$$$. In its binary representation, one bit will be $$$1$$$ only if in all the $$$a_i$$$'s binary representation, this bit is $$$1$$$. Otherwise, we can use one operation to make this bit in $$$x$$$ become $$$0$$$, which is a smaller answer.

So we can set $$$x=a_1$$$ initially. Then we iterate over the sequence and make $$$x$$$=$$$x$$$ & $$$a_i$$$, the $$$x$$$ is the answer finally.

import sys

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

for _ in range(t):

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

    nums = list(map(int, sys.stdin.readline().strip().split()))

    x = nums[0]

    for i in range(1, n):

        x &= nums[i]
        
    print(x)
    

A word $$$s$$$ of length $$$n$$$ being $$$k-complete$$$ occurs if and only if there exists a palindrome $$$t$$$ of length $$$k$$$ such that $$$s$$$ can be generated by several concatenations of $$$t$$$.

By systematically ensuring that all characters at positions $$$i, k-i+1, k+i, 2k-i+1, 2k+i, 3k-i+1, …$$$ for all $$$1≤i≤ k$$$ are equal in the final string, we can solve the problem independently for each $$$i$$$. To minimize the required number of changes, it's advisable to make all the letters equal to the one which appears at these positions the most initially. Calculate the maximum number of appearances and sum up overall $$$i$$$. However, be cautious with an odd $$$k$$$ because the letter in the center of each block has a different formula.

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

from sys import stdin
from collections import defaultdict, Counter

def main():
    for _ in range(int(input())):
        n, k = map(int, input().split())
        s = input()
        
        freq = defaultdict(Counter)
        for i in range(n):
            loc = min(i % k, k - i % k - 1)
            freq[loc][s[i]] += 1
        
        changes_needed = 0
        tot = 2 * (n // k)
        for i in range(k // 2):
            max_freq= max(freq[i].values())
            changes_needed += tot - max_freq
        
        if k % 2:
            max_freq = max(freq[k//2].values())
            changes_needed += n//k - max_freq
        
        print(changes_needed)


if __name__ == '__main__':
    main()

There should be at least one $$$b$$$ between consecutive $$$a$$$'s. Can't we just consider the last $$$b$$$ we have seen while iterating?

We don't need to do anything about characters other than $$$a$$$ and $$$b$$$.
When we encounter $$$b$$$ let's record how many valid sequences we have. So when we now encounter an $$$a$$$, the new $$$a$$$ can be appended to any of the sequences before the last $$$b$$$. Here the number of valid sequences increases by the amount we had before the last $$$b$$$ because we have the option to pick or not pick the current $$$a$$$. This new $$$a$$$ can also be a start of a new sequence, so we add 1 to the number of sequences we have so far.

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

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

mod = 10**9 + 7
s = input()

sequences = 0
before_last_b = 0 # the number of valid sequences before the last b

for idx, char in enumerate(s):
    if char == 'b':
        # all 'a's that come after now can immediately follow this 'b'
        # hence we can use all the valid sequences we have so far as prefixes of the next sequences we form
        before_last_b = sequences
    
    elif char == 'a':
        # this 'a' can be appended to sequences we formed before the last 'b' -> before_last_b
        # this character can also be a start of a new sequence, so we add 1
        sequences += before_last_b + 1
        sequences %= mod

print(sequences)

To solve this problem we need the prefix tree(trie), which will have all the strings from the group. Next we will calculate the two DP: $$$win[v]$$$ — Can player win if he makes a move now (players have word equal to prefix $$$v$$$ in the prefix tree(trie)). $$$lose[v]$$$ — Can player lose if he makes a move now (players have word equal to prefix $$$v$$$ in the prefix tree(trie)).

If $$$v$$$ is leaf of trie, then $$$win[v] = false$$$; $$$lose[v] = true$$$;

Else $$$win[v]$$$ = ($$$win[v]$$$ or (not $$$win[i]$$$)); $$$lose[v]$$$ = ($$$lose[v]$$$ or (not $$$lose[i]$$$)), such $$$i$$$ — children of vertex $$$v$$$.

Let's look at a few cases:

If $$$win[v] = false$$$, then second player win (first player lose all games).

If $$$win[v] = true$$$ and $$$lose[v] = true$$$, then first player win (he can change the state of the game in his favor).

If $$$win[v] = true$$$ and $$$lose[v] = false$$$, then if $$$k\ mod\ 2 = 1$$$, then first player win, else second player win.

Asymptotics — $$$O(\sum|s_i|)$$$.

import sys, threading
from sys import stdin

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

def main():
    N, K = map(int, input().split())

    root = {}

    def add(s):
        cur = root
        for ch in s:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]

    for _ in range(N):
        s = input()
        add(s)

    def get_winner(node): # Returns 1 (always wins), -1 (always loses) or 0 (wins or loses)
        can_win = False
        can_lose = False
        for ch in node:
            result = get_winner(node[ch])
            if result == 1:
                can_win = True
            elif result == -1:
                can_lose = True
            else:
                can_win = can_lose = True

        if can_win == False: # If my children always lose that means I can always win
            return 1
        elif can_lose == False: # If my children always win that means I can always lose
            return -1
        else:
            return 0

    first_can_win = False
    first_can_lose = False
    for ch in root:
        result = get_winner(root[ch])
        if result == 1:
            first_can_win = True
        elif result == -1:
            first_can_lose = True

    if first_can_win and (K%2 or first_can_lose):
        print("First")
    else:
        print("Second")

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

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

Let's iterate through the given array and store the length of the current increasing subarray in the variable $$$curLen$$$. If the current element is more than the previous we need to increase $$$curLen$$$ by one. Otherwise, the current number is a start of a new increasing subarray, so we need to restart $$$curLen$$$ with $$$1$$$. We keep track of the maximum after considering every number.

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

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

max_len = 1
cur_len = 1

for idx in range(1, n):
    if a[idx - 1] >= a[idx]:
        cur_len = 0
    
    cur_len += 1
    max_len = max(max_len, cur_len)

print(max_len)
    

Let's suppose that when we calculate the collapse of two strings $$$a$$$ and $$$b$$$, we reverse the string a first, so that instead of checking and removing the last letters of $$$a$$$, we do this to the first letters of $$$a$$$. Then, $$$|C(a,b)|=|a|+|b|−2|LCP(a′,b)|$$$, where $$$LCP(a′,b)$$$ is the longest common prefix of $$$a′$$$ (the reversed version of $$$a$$$) and $$$b$$$.

Then the answer to the problem becomes $$$ 2n \sum_{i=1}^{n} |s_i| - 2 \sum_{i=1}^{n} \sum_{j=1}^{n} \text{LCP}(s_i, s_j) $$$.

We need some sort of data structure that allows us to store all strings $$$s_i$$$ and for every string $$$s_j$$$, calculate the total $$$LCP$$$ of it with all strings in the structure. There are many ways to implement it (hashing, suffix arrays, etc), but in our opinion, one of the most straightforward is using a trie.

Build a trie on all strings $$$s_i$$$. Then, for every vertex of the trie, calculate the number of strings $$$s_i$$$ that end in the subtree of that vertex (you can maintain it while building the trie: when you add a new string into it, increase this value by 1 on every vertex you go through).

If you want to find the LCP of two strings $$$s$$$ and $$$t$$$ using a trie, you can use the fact that it is equal to the number of vertices that are both on the path to $$$s$$$ and on the path to $$$t$$$ at the same time (except for the root vertex). This method can be expanded to querying the sum of LCP of a given string $$$s$$$ and all strings in the trie as follows: try to find $$$s$$$ in the trie. While searching for it, you will descend in the trie and go through vertices that represent prefixes of $$$s$$$. For every such prefix, you need the number of strings in the trie that have the same prefix — and it is equal to the number of strings ending in the subtree of the corresponding vertex (which we already calculated). Don't forget that you shouldn't consider the root, since the root represents the empty prefix.

class Trienode:
    def __init__(self):
    	self.child= {}
    	self.cnt = 0
    
   	 
class Trie:
    def __init__(self):
        self.root=Trienode()
   	 
    def insert(self, word: str) -> None:
        cur = self.root
        
        for c in word:
            ind=ord(c)-ord("a")

            if ind  not in cur.child:
                cur.child[ind]=Trienode()
            
            cur=cur.child[ind]
            cur.cnt += 1
   	 
   	 
    def search(self, word: str) -> int:
   	 
        cur=self.root
        tot = 0
        for c in word:
            ind=ord(c)-ord("a")
            if ind not in cur.child:
                return tot
            
            cur=cur.child[ind]
            tot += cur.cnt * 2

        return tot

n = int(input())
s = [input() for i in range(n)]
trie = Trie()
for cur in s:
	trie.insert(cur)
total = sum([len(cur)*2*n for cur in s])
for cur in s:
	total -= trie.search(cur[::-1])
print(total)

To solve this problem efficiently, we can sort the given input array of word length in ascending order while keeping track of their original indices.It helps in generating the smallest possible lexicographical strings by starting with the shortest strings. Using a $$$Trie$$$ data structure, we efficiently generate unique binary strings for each length, which are not a prefix of other words. For each length, starting from the smallest, we can build a binary string by traversing the $$$Trie$$$. If a binary string of the required length cannot be uniquely formed (i.e., both possible extensions lead to existing valid prefixs), we will return $$$NO$$$. If successful, we can store the binary string and update the $$$Trie$$$ to reflect the newly added string. After forming a binary string, we have to backtrack to update the $$$is_end$$$ flags appropriately to ensure that we correctly mark nodes as end nodes when there are no further possible paths (all childrens are occupied).

Time Complexity: $$$O(NlogN + N * M)$$$ time. N is input array length and M denotes the maximum word length

Space Complexity: $$$O(N * M)$$$

class TrieNode:
    def __init__(self):
        self.ch = [None, None]
        self.is_end = False 

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, length):
        stack, trie = [], self.root 
        word = []
        # finding a unique word representation with the given length
        for i in range(length):
            stack.append(trie) 
            if trie.ch[0] is None or not trie.ch[0].is_end:
                if trie.ch[0] is None:
                    trie.ch[0] = TrieNode()
                trie = trie.ch[0]
                word.append('0')
            elif trie.ch[1] is None or not trie.ch[1].is_end:
                if trie.ch[1] is None:
                    trie.ch[1] = TrieNode()
                trie = trie.ch[1]
                word.append('1')
            else:
                return False
        trie.is_end = True

        # backtrcking to update the is_end of the nodes if they don't have unoccopied child for the word represetnation
        while stack and stack[-1].ch[1] and stack[-1].ch[1].is_end:
            prev = stack.pop()
            prev.is_end = True

        return ''.join(word)

def main():
    n = int(input())    
    nums = sorted(zip(map(int, input().split()), range(n)))
    trie = Trie()
    words = [''] * n
    for num, indx in nums:
        word = trie.insert(num)
        if not word:
            print('NO')
            return
        words[indx] = word

    print('YES')
    for word in words:
        print(word)

if __name__ == '__main__':
    main()

How can we find the best possible match for the XOR of some number from an array using a Trie?.

Can We use the same concept for prefix and suffix?

For this problem, we will use the Trie data structure. Let's start by calculating the prefix of the array. For $$$(0 \leq i \leq n)$$$, let $$$pref[0] = 0$$$. After calculating $$$prefix[i]$$$, we should add $$$prefix[i]$$$ to the Trie. Then, we can easily calculate the best possible match for the XOR of the new suffix that starts from $$$n$$$ and ends at $$$i + 1$$$. In this case, we are guaranteed that the prefix and suffix do not intersect.

import sys
   
class Node:
    def __init__(self):
        self.children = [None, None]

class Trie:
    def __init__(self, val):
        self.root = Node()
        self.bit_len = val

    def insert(self, num):
        cur = self.root
     
        for  i in range(self.bit_len, -1, -1):
            bit = 1 if num & (1 << i)else 0
            if cur.children[bit] is None:
                cur.children[bit] = Node()
            cur = cur.children[bit]
            
    def findMax(self, num):
        cur = self.root
        max_num = 0
        for  i in range(self.bit_len, -1, -1):
            bit = 1 if num & (1 << i) else 0
            if cur.children[1 - bit] is not None:
                max_num = max_num | (1 << i)
                cur = cur.children[1 - bit]
            else:
                cur = cur.children[bit]
        return max_num

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

nums = list(map(int, sys.stdin.readline().strip().split()))

trie = Trie(len(bin(max(nums))))

tot_pref = 0
nums = [0] + nums

for num in nums:
    tot_pref ^= num

cur_pref = 0
ans = 0

for  num in nums:
    cur_pref ^= num
    trie.insert(cur_pref)
    ans = max(ans, trie.findMax(cur_pref ^ tot_pref))

print(ans)
  

Because of it is guaranteed, that the answer always exists, we need to sort all cards in non-descending order of the numbers, which are written on them. Then we need to give to the first player the first and the last card from the sorted array, give to the second player the second and the penultimate cards and so on.

from sys import stdin

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

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

nums_idx = [(a[i], i) for i in range(N)]

nums_idx.sort()
for i in range(N//2):
    i1 = nums_idx[i][1] + 1
    i2 = nums_idx[N - 1 - i][1] + 1
    print(i1, i2)

By simulating the movements, we can solve the problem using DP. where

• $$$dp[1][1] = 0$$$, and
• $$$dp[row][col] = min(dp[row - 1][col] + col, dp[row][col - 1] + row)$$$

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

t = int(input())
for _ in range(t):
    n, m, k = map(int, input().split())
    dp = [[0]*(m + 1) for row in range(n + 1)]

    dp[1][1] = 0
    for row in range(1, n + 1):
        for col in range(1, m + 1):
            if (row, col) == (1, 1):
                continue

            dp[row][col] = min(dp[row - 1][col] + col, dp[row][col - 1] + row)
    
    print('YES' if dp[n][m] == k else 'NO')

We are doing unnecessary work. Can we avoid that?

Note that whichever path you choose, the total cost will be the same. If you know that the cost is the same, then it's not hard to calculate it. It's equal to $$$n⋅m−1$$$. So the task is to check: is $$$k$$$ equal to $$$n⋅m−1$$$ or not. The constant cost may be proved by induction on $$$n+m$$$:

• For $$$n=m=1$$$ the cost is $$$1⋅1−1=0$$$.
• For a fixed $$$(n,m)$$$, there are only two last steps you can make: either
  • from $$$(n,m−1)$$$ with cost $$$n$$$: the total cost is $$$n⋅(m−1)−1+n = n⋅m−1$$$ or
  • from $$$(n−1,m)$$$ with cost $$$m$$$: the total cost is $$$(n−1)⋅m−1+m = n⋅m−1$$$.

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

t = int(input())
for _ in range(t):
    n, m, k = map(int, input().split())
    
    print('YES' if n*m - 1 == k else 'NO')

Strategy

• Generate Palindromic Numbers: First, identify all palindromic numbers within the range 0 to 40,000. This involves checking each number in this range to see if it reads the same backward as forward.
• Relate to Coin Change Problem: Once we have the palindromic numbers, we can frame our problem similarly to the "coin change" problem. In the coin change problem, you are given a set of coins and you need to find the number of ways to make a certain amount using those coins.

Dynamic Programming Approach

• Initialize: We create an array dp where each index i represents an amount, and the value at each index represents the number of ways to make that amount using the palindromic numbers.
• Base Case: We start with the base case that there is exactly one way to make the amount zero, which is by using no coins at all. Hence, dp[0] = 1.
• Iterate Over Palindromic Numbers: For each palindromic number c, we update our dp array using the recurrence relation.

Recurrence Relation

The recurrence relation used to update the dp array is:

dp[i] += dp[i — c]

This means that for each amount i, the number of ways to form i is incremented by the number of ways to form i — c.

def generate_palindromic_numbers():
    coins = []
    for i in range(1, 4 * 10000 + 4):
        num = str(i)
        if num == num[::-1]:
            coins.append(i)
    
    return coins

coins = generate_palindromic_numbers()
max_num = 4 * 10 ** 4 + 2
mod = 10 ** 9 + 7
dp = [0] * (max_num)
dp[0] = 1

#compute outside because we don’t really have to compute it again and again 
for coin in coins:
    for i in range(max_num):
        if i - coin >= 0:
            dp[i] += dp[i - coin] 
            dp[i] %= mod

#for each test case output dp[n]       
t = int(input())
for _ in range(t):
    n = int(input())
    print(dp[n])

The main idea is $$$DP$$$. Let's define $$$dp[x]$$$ as the maximal value of the length of the good sequence whose last element is $$$x$$$, and define $$$d[i]$$$ as the (maximal value of $$$dp[x]$$$ where $$$x$$$ is divisible by $$$i$$$).

You should calculate $$$dp[x]$$$ in the increasing order of $$$x$$$. The value of $$$dp[x]$$$ is (maximal value of $$$d[i]$$$ where $$$i$$$ is a divisor of $$$x$$$) + $$$1$$$. After you calculate $$$dp[x]$$$, for each divisor $$$i$$$ of $$$x$$$, you should update $$$d[i]$$$ too.

Note that there is a corner case. When the set is $$${1}$$$, you should output $$$1$$$.

import sys

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

nums = list(map(int, sys.stdin.readline().strip().split()))

if n == 1 and nums[0] == 1:
    print(1)
    sys.exit()

def find_divisors(number):
    divisors = []
    for i in range(2, int(number**0.5) + 1):
        if number % i == 0:
            divisors.append(i)
            if i != number // i:
                divisors.append(number // i)

    return divisors  


dp = [0] *(max(nums) + 1)

for num in nums:
    divisors = find_divisors(num)
    dp[num] = 1
    for div in divisors:
        dp[num] = max(dp[num], dp[div] + 1)

    for div in divisors:
        dp[div] = max(dp[div], dp[num])
print(max(dp))

Let's rephrase the problem a bit. Instead of counting the number of arrays, let's count the number of subsequences of elements that can remain at the end.

One of the classic methods for counting subsequences is dynamic programming of the following kind: $$$\text{dp}_i$$$ is the number of subsequences such that the last taken element is at position $$$i$$$. Counting exactly this is that simple. It happens that element $$$i$$$ cannot be the last overall because it is impossible to remove everything after it. Thus, let's say it a little differently: the number of good subsequences on a prefix of length $$$i$$$. Now we are not concerned with what comes after $$$i$$$ — after the prefix.

If we learned to calculate such $$$\text{dp}$$$, we could get the answer from it. We just need to understand when we can remove all elements after a fixed one. It is easy to see that it is enough for all these elements to be smaller than the fixed one. Then they can be removed one by one from left to right. If there is at least one larger element, then the maximum of such elements cannot be removed.

Therefore, the answer is equal to the sum of $$$\text{dp}$$$ for all $$$i$$$ such that $$$a_i$$$ is the largest element on a suffix of length $$$n-i+1$$$.

How to calculate such $$$\text{dp}$$$?

Let's look at the nearest element to the left that is larger than $$$a_i$$$. Let its position be $$$j$$$. Then any subsequence that ended with an element between $$$j$$$ and $$$i$$$ can have the element $$$i$$$ appended to it. It is only necessary to remove the elements standing before $$$i$$$. This can also be done one by one.

Can $$$j$$$ be removed as well? It can, but it's not that simple. Only the element that is the nearest larger one to the left for $$$a_j$$$ or someone else even more to the left can do this. Let $$$f[i]$$$ be the position of the nearest larger element to the left. Then the element $$$i$$$ can also extend subsequences ending in $$$a[f[i]], a[f[f[i]]], a[f[f[f[i]]]], \ldots$$$.

If there are no larger elements to the left of the element — the element is the maximum on the prefix — then $$$1$$$ is added to its $$$\text{dp}$$$ value. This is a subsequence consisting of only this element.

The position of the nearest larger element to the left can be found using a monotonic stack: keep a stack of elements; while the element at the top is smaller, remove it; then add the current one to the stack.

Counting the $$$\text{dp}$$$ currently works in $$$O(n^2)$$$ in the worst case. How to optimize this? The first type of transitions is optimized by prefix sums, as it is simply the sum of $$$\text{dp}$$$ on a segment. For the second type of transitions, you can maintain the sum of $$$\text{dp}$$$ on a chain of jumps to the nearest larger element: $$$\text{dpsum}_i = \text{dpsum}_{f[i]} + \text{dp}_i$$$. Now, both transitions can be done in $$$O(1)$$$.

Overall complexity: $$$O(n)$$$ for each testcase.

MOD = 998244353

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	next_min = [0] * n
	dp_sum = [0] * (n + 2)
	dp_next = [0] * n

	stack_min = []
	next_min[n - 1] = n
	dp_sum[n] = 1

	for pos in range(n - 1, -1, -1):
    	while stack_min and a[stack_min[-1]] > a[pos]:
        	stack_min.pop()
    	next_min[pos] = n if not stack_min else stack_min[-1]
    	stack_min.append(pos)

    	nxt_pos = next_min[pos]
    	dp_pos = (dp_sum[pos + 1] - dp_sum[nxt_pos + 1]) % MOD
    	if nxt_pos != n:
        	dp_pos = (dp_pos + dp_next[nxt_pos]) % MOD
        	dp_next[pos] = (dp_sum[nxt_pos] - dp_sum[nxt_pos + 1] + dp_next[nxt_pos]) % MOD
   	 
    	dp_sum[pos] = (dp_pos + dp_sum[pos + 1]) % MOD

	res = 0
	mn = a[0]
	for i in range(n):
    	mn = min(mn, a[i])
    	if a[i] == mn:
        	res = (res + dp_sum[i] - dp_sum[i + 1]) % MOD
	print(res)

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

There are many possible solutions. One of them is just to print $$$2,3,…,n,1$$$.

import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    ans = []
    for i in range(2, n + 1):
        ans.append(i)
    ans.append(1)
    print(*ans)

Let $$$score(i)$$$ be the result of the game if we chose $$$i$$$ as the starting position. Let's look at some starting position $$$i$$$. After making a move from it, we will get $$$a[i]$$$ points and move to the position $$$i+a[i]$$$. Let $$$j = i+a[i]$$$, if this is still inbounds we will apply the same operation until it gets out of bounds where the score is $$$0$$$. Formally, $$$score(i)=score(i+a[i])+a[i]$$$.

So lets consider every index as a starting position and track the maximum score we can get.

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


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

        memo = [-1]*n

        def dp(idx):
            # base case
            if idx >= n:
                return 0

            if memo[idx] != -1:
                return memo[idx]
            
            memo[idx] = dp(idx + a[idx]) + a[idx]
            return memo[idx]
        
        ans = 0
        for start in range(n):
            ans = max(ans, dp(start))
        
        print(ans)

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

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

What should our state be?

At each state, what are our possible options?

How does our state change after choosing one of the options?

We are going to use dynamic programming to solve this problem. Our state is going to be $$$n$$$. At each step, we have 3 choices: take $$$a$$$, $$$b$$$, or $$$c$$$. Our recurrence relation is going to be:

$$$dp(n)= 1+max⁡(dp(n−a),dp(n−b),dp(n−c))$$$

For our base cases, if $$$n$$$ becomes 0, we return 0. Another base case is if $$$n$$$ is less than 0, we return $$$-inf$$$, which is a very small number because we want the maximum answer. This answer will ensure that we do not consider this path.

from functools import lru_cache
import sys
import threading

def main():
    n,a,b,c = list(map(int,input().split()))

    memo = [-1 for i in range(n + 1)]
    
    def dp(n):
        
        if n < 0:
            return -float('inf')
        if n == 0:
            return 0
        
        if memo[n] != -1:
            return memo[n]
        
        memo[n] = 1 + max(dp(n - a),dp(n - b),dp(n - c))
        
        return memo[n]
    
    print(dp(n))
    
sys.setrecursionlimit( 1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target = main)
main_thread.start()
main_thread.join()

One thing we can notice is that if we choose a number $$$x$$$, it means we can't choose $$$x - 1$$$ and $$$x + 1$$$. In other words, this means we can't choose two consecutive values. Another point is that once we choose $$$x$$$, choosing it multiple times wouldn't have any disadvantage on our score. Therefore, if we decide to choose $$$x$$$, we have to choose all instances of $$$x$$$, and the score if we choose all $$$x$$$ is going to be $$$\text{count}[x] \times x$$$.

For every number between 1 and $$$\max(a)$$$:

$$$f(i) = \max(f(i - 1), f(i - 2) + \text{count}[i] \times i), \quad 2 \leq i \leq n;$$$

$$$f(1) = \text{count}[1];$$$

$$$f(0) = 0;$$$

The answer is $$$f(n)$$$.

import sys, threading
from collections import Counter

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

def main():
    memo = {}
    n = int(input())
    cnt = Counter(map(int,input().split()))
    def dp(n):

        if n <= 1:
            return cnt[n]
        if n not in memo:
            memo[n] = max(dp(n -1), dp(n -2) + cnt[n]*n)
    	return memo[n]
    print(dp(max(cnt.keys())))
    
if __name__ == '__main__':
    
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

Let's define ( S(k) ) as the sum of elements $$$\sum\limits_{i = k}^{n}{a_i}$$$. Additionally, let $$$p_i$$$ denote the starting position of the $$$( ith)$$$ subarray, where $$$( p1 = 1)$$$ and $$$( pi < pi+1)$$$.

Now, consider the transformation:$$$\sum_{i=1}^{n}{a_i \cdot f(i)} = 1 \cdot (S(p_1) - S(p_2)) + 2 \cdot (S(p_2) - S(p_3)) + \dots + k \cdot (S(p_k) - 0) = \ = S(p_1) + (2 - 1) S(p_2) + (3 - 2) S(p_3) + \dots + (k - (k - 1))) S(p_k) = \ = S(p_1) + S(p_2) + S(p_3) + \dots + S(p_k)$$$

So, our objective is to select the sum of the entire array ( S(1) ) and ( k — 1 ) different suffix sums to maximize their total sum. Consequently, we can simply select the (k — 1) maximum suffix sums along with the sum of the entire array.

Time Complexity: $$$O(n)$$$ time. Space Complexity: $$$O(n)$$$

def main():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))

    sfxSum = [nums[-1]]
    for i in range(n - 2, -1, -1):
        sfxSum.append(sfxSum[-1] + nums[i])
    
    ans = sfxSum.pop()
    sfxSum.sort(reverse=True)
    for i in range(k - 1):
        ans += sfxSum[i]
    print(ans)

if __name__ == '__main__':
    main()

For this problem, the constraints allow us to implement it in $$$O(n)^2$$$ time, but let's try to do it in linear time complexity. We can have a variable for the final answer and iterate through the given string s. If the last character in our answer is a vowel and if $$$s_i$$$ is also a vowel, we can skip adding it to our answer; otherwise, we will add $$$s_i$$$ to our answer.

import sys
input = sys.stdin.readline

N = int(input())
word = input()

answer = []
vowels = {'a', 'e', 'i', 'o', 'u', 'y'}
for char in word:
    if answer and answer[-1] in vowels and char in vowels:
        continue
    answer.append(char)
print(*answer, sep="")

Can we get a better value for $$$z$$$?

Note that $$$z$$$ is masking itself. Therefore its value cannot increase larger than the initial value.

We can now conclude that to get a maximum value, we just need to apply the operation to each index once without changing $$$z$$$. Then take the maximum $$$a_i$$$.

This will tell us that we only actually applied the operation to the number that gives us the maximum value (just once).

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

    max_val = 0
    for num in a:
        max_val = max(max_val, num | z)

    print(max_val)

To achieve the maximum $$$AND$$$ result, we set bits from the $$$30th$$$ bit down to the $$$0th$$$ bit for each number in the given array. However, the available operations $$$k$$$ may be less than the number of elements in the array $$$nums$$$. We first count how many operations we need for each bit position from $$$0$$$ to $$$30$$$ and store these counts in an array $$$needs$$$. Starting with the $$$30th$$$ bit (highest bit), we check if the operations required $$$needs[i]$$$ for setting that bit is within the available operations $$$k$$$. If it is less than or equal to $$$k$$$, we set that bit in the result $$$answer$$$ and subtract the required operations from $$$k$$$. This way, we prioritize setting higher bits in $$$answer$$$ first, as they have a greater impact on the value.

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

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

def main():
    for _ in range(int(input())):
        n, k = map(int, input().split())
        nums = list(map(int, input().split()))
        needs = [0] * 31

        for loc in range(31):
            for num in nums:
                if num & (1 << loc) == 0:
                    needs[loc] += 1
        
        max_val = 0

        for i in range(len(needs) - 1, -1, -1):
            if needs[i] <= k:
                max_val |= (1 << i)
                k -= needs[i]
        
        print(max_val)
    
if __name__ == '__main__':
    main()

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

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

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

Try prefix sums.

Try binary search.

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

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

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

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

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

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

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

        if right < l:
            return -1
        return right

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

 
    print(*ans)

First solve a simplified version: suppose that in type $$$1$$$ queries, only a single character of the string s is inverted, i.e., $$$l=r$$$ in all type $$$1$$$ queries.

When we invert $$$s_i$$$, the XOR of all numbers from group $$$0$$$ and group $$$1$$$ change in the same way, regardless of whether this inversion was from $$$0$$$ to $$$1$$$ or from $$$1$$$ to $$$0$$$.

We will store $$$2$$$ variables: $$$X_0,X_1$$$, which represent the XOR of all numbers from group $$$0$$$ and group $$$1$$$, respectively. When answering a query of type $$$2$$$, we will simply output either $$$X_0$$$ or $$$X_1$$$. Now we need to understand how to update $$$X_0$$$ and $$$X_1$$$ after receiving a query of type $$$1$$$.

Let's first solve a simplified version: suppose that in type $$$1$$$ queries, only a single character of the string s is inverted, i.e., $$$l=r$$$ in all type $$$1$$$ queries.

Let's see how $$$X_0$$$ and $$$X_1$$$ change after this query. If $$$s_i$$$ was $$$0$$$ and became $$$1$$$, then the number $$$a_i$$$ will be removed from group $$$0$$$. Since $$$XOR$$$ is its own inverse operation ($$$w⊕w=0$$$), we can do this with $$$X_0=X_0⊕a_i$$$. And in $$$X_1$$$, we need to add the number $$$a_i$$$, since now $$$s_i=1$$$. And we can do this with $$$X_1=X_1⊕a_i$$$.

The same thing happens if $$$s_i$$$ was $$$1$$$.

This is the key observation: when we invert $$$s_i$$$, $$$X_0$$$ and $$$X_1$$$ change in the same way, regardless of whether this inversion was from $$$0$$$ to $$$1$$$ or from $$$1$$$ to $$$0$$$.

Therefore, to update $$$X_0$$$ and $$$X_1$$$ after a query of type $$$1$$$ with parameters $$$l,r,$$$ we need to do this: $$$X_0=X_0⊕(a_l⊕…⊕a_r)$$$, and the same for $$$X_1$$$.

To quickly find the XOR value on a subsegment of the array a, we can use a prefix XOR array. If $$$p_i=a_1⊕…a_i$$$, then: $$$a_l⊕…⊕a_r=p_r⊕p_{l−1}$$$.

import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    s = sys.stdin.readline().strip()
    q = int(sys.stdin.readline().strip())

    pref = [0] * (n + 1)
    for i in range(1, n + 1):
        pref[i] = pref[i - 1] ^ a[i-1]

    x_0 = 0
    x_1 = 0
    for i in range(n):
        if s[i] == "0":
            x_0 ^= a[i]
        else:
            x_1 ^= a[i]

    ans = []
    for i in range(q):
        line = list(map(int, sys.stdin.readline().strip().split()))
        if line[0] == 2:
            if line[1]:
                ans.append(int(str(x_1)))
            else:
                ans.append(int(str(x_0)))
        else:
            l, r = line[1], line[2]
            seg = pref[r] ^ pref[l - 1]   
            x_0 ^= seg
            x_1 ^= seg
    print(*ans)

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

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

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

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

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

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

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

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

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

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

from sys import stdin


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

T = int(input())

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

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

    print(ans)

If the length of the given string $$$s$$$ is odd, then the answer is $$$NO$$$, since it cannot be a concatenation of two equal strings. Otherwise, Let's slice the string into equal halves. If the two halves are equal the answer is $$$YES$$$, otherwise $$$NO$$$.

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

    if len(s)%2:
        print('NO')
    
    else:
        mid = len(s)//2
        print('YES' if s[:mid] == s[mid:] else 'NO')
        

Treat the forest as a union-find data structure.

The key observation is that each baboon and its most distant relative on the same tree belong to the same tree (connected component). We can use this fact to identify the number of trees.

Solution Approach:

We can use a Union-Find data structure to efficiently group relative baboons in a single tree. Initialize a union-find object with $$$n$$$ baboons (one for each baboon) Iterate through the sequences $$$s$$$. For each baboon $$$i$$$, perform a union operation on $$$i$$$ and $$$(s[i] - 1)$$$. This connects baboon $$$i$$$ with its most distant relative. Count the number of unique representatives in the union-find. That will be the answer.

Time & Space Complexity

Time Complexity: $$$O(n)$$$, where $$$n$$$ is the number of baboons. This is due to the single loop for processing the $$$s$$$ sequence and another loop for finding representatives. Space Complexity: $$$O(n)$$$, due to the Union-Find data structure and the set used to store representatives.

from collections import defaultdict
class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.size = [1] * size

    def find(self, x):
        while x != self.root[x]:
            self.root[x] = self.root[self.root[x]]
            x = self.root[x]
        return x
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.size[rootX] > self.size[rootY]:
                self.root[rootY] = rootX
                self.size[rootX] += self.size[rootY]
            else:
                self.root[rootX] = rootY
                self.size[rootY] += self.size[rootX]


def main():
    n = int(input())
    seq = list(map(int, input().split()))
    forest  = UnionFind(n)
    for i in range(n):
        forest.union(i, seq[i] - 1)
    
    tree_numbers = set()
    for i in range(n):
        tree_numbers.add(forest.find(i))
    
    print(len(tree_numbers))

if __name__ == '__main__':
    main()

To track the valid parenthesis strings, we can use a stack. When encountering an opening bracket $$$($$$, we add its index to the stack. If it's a closing bracket $$$)$$$, we remove the last unpaired opening bracket. Whenever we remove the index of an opening bracket $$$i$$$, we can observe that the substring from $$$s_i$$$ to the current index forms a balanced bracket sequence. This is because when we remove an unpaired opening bracket, the substring between the removed index and the current index has matching opening and closing brackets. Thus, we unite the two indices to mark this valid substring as part of the connected components in Athanasius's graph. This process ensures that we account for all balanced bracket sequences in the graph construction. Additionally, if the current bracket is a closing bracket $$$)$$$ and the next bracket (current index plus one) is an opening bracket $$$($$$, we unite them. This is because the current bracket marks the end of a balanced bracket sequence, and the next bracket marks the start of another balanced bracket sequence, and two balanced brackets together form a balanced bracket sequence.

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

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

	def union(self, element_a, element_b):
            root_a, root_b = self.find(element_a), self.find(element_b)
            if root_a != root_b:
                if self.rank[root_a] > self.rank[root_b]:
                    self.parent[root_b] = root_a
                elif self.rank[root_a] < self.rank[root_b]:
                    self.parent[root_a] = root_b
                else:
                    self.parent[root_a] = root_b
                    self.rank[root_b] += 1

def solve():
	num_pairs = int(input())
	brackets = input().strip()
	uf = UnionFind(2 * num_pairs)
	stack = []
	for i, bracket in enumerate(brackets):
            if bracket == "(":
                    stack.append(i)
            else:
                top = stack.pop()
                uf.union(i, top)
                if i + 1 < 2 * num_pairs and brackets[i + 1] == "(":
                    uf.union(i, i + 1)
	num_connected_components = sum(1 for i, parent in enumerate(uf.parent) if i == parent)
	print(num_connected_components)

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

In this problem we are given a disjoint set union process with $$$n−1$$$ steps, merging $$$n$$$ initial $$$1$$$-element sets into one $$$n$$$-element set. We have to put elements into a linear array of cells, so that the cells to be joined at each step of the process were immediate neighbours (i.e. not separated by other cells).

This problem can be solved in $$$O(nlogn)$$$ via standard disjoint-set data structure, additionally storing lists of elements in each set.

The simplest solution is storing mapping from item to id (representative) of its current set, and the inverse mapping from set to the list of its elements when we have to merge two sets A and B, we make the smaller set part of the larger set and update mappings and concatenating the lists can be done in $$$O(min(|A|,|B|)))$$$.

This gives us $$$O(nlogn)$$$: element can not change its set more than $$$logn$$$ times, because the change leads to (at least) doubling of the element's set size.

import sys
n = int(sys.stdin.readline().strip())
parent = {}
elem = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    elem[i].append(i)
    parent[i] = i
size = [1] * (n + 1)

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

def union(x, y):
    par_x = find(x)
    par_y = find(y) 
    if par_x != par_y:
        if size[par_x] >  size[par_y]:
            parent[par_y] = par_x
            elem[par_x].extend(elem[par_y])
            size[par_x] += size[par_y]
        else:
            parent[par_x] = par_y
            elem[par_y].extend(elem[par_x])
            size[par_y] += size[par_x]
for _ in range(n - 1):
    x, y = map(int, sys.stdin.readline().strip().split())
    union(x, y)

print(*elem[find(1)])

Let's sort the edges by their weight in descending order and merge the vertices in that order. Whenever you get an already merged vertices, it means the new edge will create cycle; we can update our answer to that edge. Finally, to get the cycle, we can do DFS from either end of that edge until we get to the other end.

from collections import defaultdict
from sys import stdin


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

class DSU:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, v):
        while v != self.p[v]:
            self.p[v] = self.p[self.p[v]]
            v = self.p[v]
        return v
    
    def merge(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.size[pu] < self.size[pv]:
            pu, pv = pv, pu
        self.size[pu] += self.size[pv]
        self.p[pv] = pu
        return True

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    edges = []
    adj = defaultdict(list)
    for __ in range(M):
        u, v, w = map(int, input().split())
        u, v = u - 1, v - 1
        edges.append((w, u, v))
        adj[u].append(v)
        adj[v].append(u)

    edges.sort(key=lambda edge: edge[0], reverse=True)
    dsu = DSU(N)
    for w, u, v in edges:
        if not dsu.merge(u, v):
            ans = (w, u, v)

    min_w, st, end = ans
    stk = [st]


    # DFS to get the cycle
    p = [-1]*N
    p[st] = st
    while stk:
        v = stk.pop()
        for ch in adj[v]:
            if v == st and ch == end: continue
            if ch == end:
                p[ch] = v
                stk = []
                break
            if p[ch] == -1:
                p[ch] = v
                stk.append(ch)
    v = end
    path = []
    while p[v] != v:
        path.append(v)
        v = p[v]
    path.append(st)

    print(min_w, len(path))
    for i in range(len(path)):
        path[i] += 1
    print(*path)

To maximize the minimum frequency of a character, it's best to equalize the frequencies of each character as much as possible. So, each set of $$$k$$$ characters should have a frequency of at least $$$n$$$ // $$$k$$$. Then, we can distribute the remaining $$$n$$$ % $$$k$$$ characters however we want among those $$$k$$$ characters.

t = int(input())
for _ in range(t):
    n,k = input()
    
    numbers = n // k
    
    remaining = n % k
    
    ans = ""
    
    for i in range(k):
        ans += chr(i + ord("a")) * numbers
    ans += "a" * remaining
    print(ans)

We can easily add a friend to the display system when that friend goes online. When there is a query to check if a friend can be displayed by the system, we need to remove friends with the lowest goodness values until the size of the online friends list is less than or equal to $$$k$$$. The answer will be $$$YES$$$ if the friend exists in the displayed system. If the friend is not currently in the display system, either because they were never added or because they were removed from the list, the answer will be $$$NO$$$.

Time Complexity: $$$(O(q * log(n)))$$$ where $$$q$$$ is number of queries and $$$n$$$ is number of friends Space Complexity: $$$O(n)$$$

from heapq import heappop, heappush
from collections import defaultdict

def main():
    n, k, q = map(int, input().split())
    friendship = list(map(int, input().split()))
    hashMap = defaultdict(int)
    heap = []

    for _ in range(q):
        type, friend = map(int, input().split())
        if type == 1:
            hashMap[friend] = 2
            heappush(heap, (friendship[friend - 1], friend))
        else:
            if hashMap[friend]:
                while len(heap) > k:
                    weight, f = heappop(heap)
                    hashMap[f] = 1 
            if hashMap[friend] == 2:
                print('YES') 
            else:
                print('NO')
    
if __name__ == '__main__':
    main()
 
 

The order in which they will be applied is not important.

To solve it, it should be noted that despite the way the deck with bonuses works, the order in which they will be applied is not important. Then, when we meet the hero card, we just need to add to the answer the maximum of the available bonuses.

Constraints make you use data structures such as $$$heap$$$ to quickly find and extract the maximum.

Total complexity: $$$O(nlogn)$$$

import sys
from heapq import heappush, heappop

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

for _ in range(t):
    
    n =  int(sys.stdin.readline().strip())
    nums = list(map(int, sys.stdin.readline().strip().split()))
    my_heap = []
    ans = 0
    for num in nums:
        if num:
            heappush(my_heap, -1 * num)
        else:
            if my_heap:
                ans +=( heappop(my_heap) * -1)
    print(ans)

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

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

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

import heapq

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

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

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

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

When do we print $$$NO$$$?

If we can't form a valid topological order of the vertices by using only the directed edges, the answer is $$$NO$$$.

If the graph consisting of the vertices and only directed edges contains at least one cycle then the answer is $$$NO$$$. In other words, If we can’t form a valid topological order of the vertices with just the directed edges, we print $$$NO$$$.

Let’s now have the topological sort of the graph without undirected edges. For each pair of vertices $$$X, Y$$$ in the undirected edges, if $$$X$$$ comes before $$$Y$$$ in the topological order, we direct the edge from $$$X$$$ to $$$Y$$$, otherwise we direct it from $$$Y$$$ to $$$X$$$.

from collections import deque, defaultdict


def topSort(graph, indegree):
    queue = deque()

    for node in range(n):
        if not indegree[node]:
            queue.append(node)

    top_order = []

    while queue:
        cur = queue.popleft()
        top_order.append(cur)

        for neigh in graph[cur]:
            indegree[neigh] -= 1

            if not indegree[neigh]:
                queue.append(neigh)
    
    return top_order


t = int(input())

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

    directed = []
    undirected = []
    
    for i in range(m):
        direction, x, y = map(int, input().split())

        x -= 1 # let's make it zero indexed
        y -= 1

        if direction:
            directed.append((x, y))
        
        else:
            undirected.append((x, y))
    

    graph = [[] for node in range(n)]
    indegree = defaultdict(int)

    for x, y in directed:
        graph[x].append(y)
        indegree[y] += 1
    

    order= topSort(graph, indegree)

    if len(order) < n:
        print("NO")
    
    else:
        # compute the index of each node in the topological order
        temp = {node: idx for idx, node in enumerate(order)}


        print('YES')
        for x, y in undirected:
            if temp[x] < temp[y]:
                print(x + 1, y + 1)
                
            else:
                print(y + 1, x + 1)

        for x, y in directed:
            print(x + 1, y + 1)
        

Initialize three variables $$$chest$$$, $$$biceps$$$, and $$$back$$$ to $$$0$$$, representing the total repetitions for each muscle group. Loop through the repetitions of exercises, and for each exercise: If the $$$index$$$ is divisible by $$$3$$$ (chest exercises), add the repetitions to the $$$chest$$$ variable. If the $$$index$$$ modulo $$$3$$$ is $$$1$$$ (biceps exercises), add the repetitions to the $$$biceps$$$ variable. If the $$$index$$$ modulo $$$3$$$ is $$$2$$$ (back exercises), add the repetitions to the $$$back$$$ variable Compare the values of $$$chest$$$, $$$biceps$$$, and $$$back$$$ to determine which muscle group has the highest total repetitions.

Time Complexity: $$$O(n)$$$, $$$n$$$ is input size

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

    def main():
    n = int(input())
    routine = list(map(int, input().split()))

    exercises = [0, 0, 0]
    for turn in range(n):
        exercises[turn % 3] += routine[turn]
    
    if exercises[0] > exercises[1] and exercises[0] > exercises[2]:
        print('chest')
    elif exercises[1] > exercises[2]:
        print('biceps')
    else:
        print('back')
    
if __name__ == '__main__':
    main()

Since we know the start of the path, we can begin our DFS or BFS from 0 while tracking the distance covered so far. Whenever we add a new node to our path, we include the distance between the parent node and the current node, maximizing our answer because we seek the maximum distance. Finally, output the maximum distance that we found.

V = int(input())
adj = [[] for __ in range(V)]

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

stack = [(0, 0)]
visited = set([0])
max_cost = 0

while stack:
    curr, cost = stack.pop()
    max_cost = max(max_cost, cost)

    for ed, nxt_cost in adj[curr]:
        if ed not in visited:
            visited.add(ed)
            stack.append((ed, cost + nxt_cost))

print(max_cost)

Consider the process from the end, we will "delete" any subtree from the tree, whose color of the ancestor of the highest vertex differs from the color of the highest vertex and the colors of all vertices in the subtree are the same. Thus, we can show that the answer is the number of edges whose ends have different colors + 1.

from collections import deque
from sys import stdin


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

N = int(input())

parents = list(map(int, input().split()))
color = list(map(int, input().split()))

adj = [[] for _ in range(N)]
for ch, p in enumerate(parents, 1):
    adj[p - 1].append(ch)

q = deque([(0, color[0])])
ans = 1

while q:
    v, c = q.popleft()
    for ch in adj[v]:
        q.append((ch, color[ch]))
        ans += (color[ch] != c)
print(ans)

Let's label the diagonal that goes from the top-left to the bottom-right as "diagonal 1" and the diagonal that goes from the bottom-left to the top-right as "diagonal 2". Any cell $$$s_{i,j}$$$ can be visited in these two different diagonals. If the cell was visited with diagonal 1 with a cost of $$$d$$$, all the cells it can reach in diagonal 2 will have a cost of $$$d + 1$$$. Similarly, if the cell was visited with diagonal 2, the cells it can reach on diagonal 1 will have a cost of $$$d + 1$$$. Since the cost of the reachable cells differs based on the diagonal that their parent was visited from, we need to calculate the shortest path for each visited cell for both diagonals.

To calculate the shortest path, we can use BFS starting at the current position of the bishop for both diagonals in our queue. For every element in the queue, if it was visited with diagonal 1, since the cell that visited it will visit all the nodes in that diagonal, we only need to calculate for diagonal 2, and vice versa. While we are calculating for one diagonal, we will calculate for all nodes until we encounter an obstacle, reach a cell that was visited with that diagonal, go out of bounds, or reach the target cell. We return the answer when we reach the target or -1 if we can't reach it.

from collections import deque
from sys import stdin

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

N = int(input())
start_x, start_y = map(int, input().split())
target_x, target_y = map(int, input().split())

start_x -= 1
start_y -= 1
target_x -= 1
target_y -= 1

grid = []
for _ in range(N):
	grid.append(input())

visited = [[[False, False] for _ in range(N)] for _ in range(N)]

queue = deque([(start_x, start_y, 1, 1), (start_x, start_y, -1, 1)])

moves = 0
while queue:
	queue_length = len(queue)
	for _ in range(queue_length):
    	x, y, dx, dy = queue.popleft()
    	if x == target_x and y == target_y:
        	print(moves)
        	exit()
    	visited[x][y][0] = visited[x][y][1] = True
    	is_diagonal = (dx == dy)
   	 
    	for direction in [1, -1]:
        	for i in range(1, 2 * N):
            	nx = x + i * dx * direction
            	ny = y + i * dy * direction
            	if nx < 0 or nx >= N or ny < 0 or ny >= N or grid[nx][ny] == '#' or visited[nx][ny][is_diagonal]:
                	break
            	if not visited[nx][ny][0] and not visited[nx][ny][1]:
                	queue.append((nx, ny, -dx, dy))
            	visited[nx][ny][is_diagonal] = True
	moves += 1
print(-1)

Let's try to solve the problem for odd numbers and then just run the same algorithm with even numbers.

In this problem, we have directed graph consisting of $$$n$$$ vertices (indices of the array) and at most $$$2n−2$$$ edges. Our problem is to find for every vertex the nearest vertex having the opposite parity. Let's try to solve the problem for odd numbers and then just run the same algorithm with even numbers.

We have multiple odd vertices and we need to find the nearest even vertex for each of these vertices. This problem can be solved with the standard and simple but pretty idea. Let's inverse our graph and run a multi-source breadth-first search from all even vertices. The only difference between standard bfs and multi-source bfs is that the second one have many vertices at the first step (vertices having zero distance).

Now we can notice that because of bfs every odd vertex of our graph has the distance equal to the minimum distance to some even vertex in the initial graph. This is exactly what we need. Then just run the same algorithm for even numbers and print the answer.

Time complexity: $$$O(n)$$$ .

import sys
from collections import defaultdict, deque

n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().strip().split()))

graph = defaultdict(list)

for i in range(n):
    left, right =  i - arr[i], i + arr[i]
    if left > -1:
        graph[left].append(i)
    if right < n:
        graph[right].append(i)
    
def bfs(start, _end):
    _value = [-1] * n
    queue = deque()
    for num in start:
        queue.append(num)
        _value[num] = 0
    while queue:
        cur = queue.popleft()
        for to in graph[cur]:
            if _value[to] == -1:
                _value[to] = _value[cur] + 1
                queue.append(to)
    for num in _end:
        ans[num] = _value[num]

odd = []
even = []

for i, num in enumerate(arr):
    if num % 2:
        odd.append(i)
    else:
        even.append(i)

ans = [-1] * n

bfs(odd, even)
bfs(even, odd)
print(*ans)
   
    

There are two cases we need to check:

1. If there is more than one color in a row. We can check this in many ways. We can put a row in a set and see if it has a length of one. OR, we can check if consecutive colors in a row are the same.
2. If there are consecutive rows with the same color. For each square in a row we can see if it has the same color as the one above it (i.e. on the previous row).

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

n, m = map(int, input().split()) # n = rows, m = cols

flag = []
for _ in range(n):
    row = input()
    flag.append(row)


yes = True
for row in range(n):
    for col in range(1, m):
        # check if we have different colors in a row
        if flag[row][col] !=  flag[row][col - 1]:
            yes = False
            break
        
        # check if we have similar consecutive rows
        if row > 0 and flag[row][col] == flag[row - 1][col]:
            yes = False
            break
    
    if not yes:
        break

print('YES' if yes else 'NO')

Let's look at the degrees of each node.

To form a ring topology, each node must have a degree of $$$2$$$. For a bus topology, the starting and ending nodes must have a degree of $$$1$$$, while the other $$$n - 2$$$ nodes will have a degree of $$$2$$$. In a star topology, one node must have a degree of $$$n - 1$$$, while the other $$$n - 1$$$ nodes will only have a degree of $$$1$$$. If the graph doesn't satisfy one of the above conditions, it is an unknown topology.

n,k = list(map(int,input().split()))
degree = [0 for i in range(n)]
for i in range(k):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    
    #increase the degrees of both nodes
    degree[x] += 1
    degree[y] += 1

#count the occurrences of the degrees   
count = Counter(degree)

if count[2] == n:
    print('ring topology')
elif count[1] == 2 and count[2] == (n - 2):
    print('bus topology')
elif count[1] == n - 1 and count[n - 1] == 1:
    print('star topology')
else:
    print("unknown topology")

The tree itself is bipartite so we can run a dfs to partition the tree into the $$$2$$$ sets (called bicoloring), We can't add an edge between any $$$2$$$ nodes in the same set and we can add an edge between every $$$2$$$ nodes in different sets, so let the number of nodes in the left set be $$$l$$$ and the number of nodes in the right set be $$$r$$$, The maximum number of edges that can exist is $$$l \cdot r$$$, but $$$n - 1$$$ edges already exist so the maximum number of edges to be added is $$$l \cdot r - (n - 1)$$$.

Time complexity : $$$O(n)$$$.

from sys import stdin


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

N = int(input())
adj = [[] for _ in range(N)]

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

color = [-1]*N
color[0] = 0
stack = [0]

cnt = [0]*2

while stack:
    v = stack.pop()
    parent_color = color[v]
    child_color = 1 - parent_color
    cnt[parent_color] += 1

    for ch in adj[v]:
        if color[ch] == -1:
            color[ch] = child_color
            stack.append(ch)

print(cnt[0]*cnt[1] - (N - 1))

We know that node $$$1$$$ is the root, hence it always won’t have any ancestor. All other nodes might have sometimes not fixed ancestors, but we know for sure, for beginning, node 1 won’t have any unfixed ancestor (because it won’t have any). So, for beginning we can start with node $$$1$$$. More, suppose node $$$1$$$ is unfixed. The only way to fix it is to make an operation on it. Since it’s unfixed and this is the only way to fix it, you’ll be obligated to do this operation. This means, in an optimal sequence of operations, you’ll be obligated to do this operation, too.

Generally, suppose all ancestors of node $$$x$$$ are fixed. We get the current value of node $$$x$$$ after the operations done on ancestors of $$$x$$$. If the current value is not the expected one, we’ll have to do an operation on node $$$x$$$ (this is the only way to fix the node $$$x$$$). Now, after node $$$x$$$ is fixed, we can process sons of it. This strategy guarantees minimal number of operations, because we do an operation only when we’re forced to do it.

How to get $$$O(N)$$$? Suppose we are at node $$$x$$$ and want to know its current value after operations done for its ancestors. Obviously, it is defined by initial value. If we know number of operations done so far by even levels for its ancestors, number of operations done so far by odd levels and current level, we can determine the current value. Suppose these values are (initial_value, odd_times, even_times, level). We observe that $$$2$$$ operations cancel each other, so we can take this number modulo $$$2$$$. If level % 2 = 0, then only even_times will matter, and current_value = (initial_value + even_times) % 2. Otherwise, current_value = (initial_value + odd_times) % 2.

import sys
from collections import defaultdict
n = int(sys.stdin.readline().strip())
graph = defaultdict(list)

for i in range(n - 1):
    u, v = map(int, sys.stdin.readline().strip().split())
    graph[u].append(v)
    graph[v].append(u)
init = list(map(int, sys.stdin.readline().strip().split()))
goal = list(map(int, sys.stdin.readline().strip().split()))
stack = [(1, 1, 0, 0, 0)]
ans = []

while stack:
    node, par, level, even_op, odd_op = stack.pop()
    if level % 2 == 0:
        if even_op % 2:
            if 1 - init[node - 1] != goal[node - 1]:
                ans.append(node)
                even_op = 1 -even_op
        else:
            if init[node - 1] != goal[node - 1]:
                ans.append(node)
                even_op = 1 -even_op
    else:
        if odd_op % 2:
            if 1 - init[node - 1] != goal[node - 1]:
                ans.append(node)
                odd_op = 1 -odd_op
        else:
            if init[node - 1] != goal[node - 1]:
                ans.append(node)
                odd_op = 1 -odd_op
    for el in graph[node]:
        if el != par:
            stack.append((el, node, level + 1, even_op, odd_op))
print(len(ans))
for a in ans:
    print(a)

Replace the empty cells with walls if they are adjacent to bad cells

Take the escape $$$(n,m)$$$ as the source node to perform depth-first-search (DFS) traversal.

Here’s the step-by-step process:

1. Represent the graph in a grid as a graph representation.
2. Identify all the good, bad, and empty cells.
3. Replace the empty cells with walls if they are adjacent to bad cells.
4. Initialize a visited set to track visited nodes.
5. Take the cell $$$(n,m)$$$ as a source node and perform a depth-first search (DFS) traversal.
6. Once the traversal is finished, check if all good cells exist in the visited set and none of the bad cells exist in the visited set.
7. If some (one or more) good cells do not exist in the visited set, it means we can’t traverse to all the good cells, and all of the good people can’t escape.
8. If some (one or more) bad cells exist in the visited set, it means we can’t block all bad cells, and they can escape.

Time Complexity: $$$O(N * M)$$$, where $$$N$$$ is the number of rows and $$$M$$$ is the number of columns in the maze.

Space Complexity: $$$O(N * M)$$$

def inBound(row, col, n, m, visited, graph):
    return 0 <= row < n and 0 <= col < m and (row, col) not in visited and graph[row][col] != '#'

def main():
     for _ in range(int(input())):
        n, m = map(int, input().split())
        graph = []

        for _ in range(n):
            graph.append(list(input()))
        
        direc = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        good, bad, empty = [], [], []

        # Find the good, bad and empty cells
        for row in range(n):
            for col in range(m):
                if graph[row][col] == 'G':
                    good.append((row, col))
                elif graph[row][col] == 'B':
                    bad.append((row, col))
                elif graph[row][col] == '.':
                    empty.append((row, col))

        # Replace the empty cells with walls if they are adjacent to bad cells
        for row, col in empty:
            for i, j in direc:
                _row, _col = row + i, col + j
                if 0 <= _row < n and 0 <= _col < m and graph[_row][_col] == 'B':
                    graph[row][col] = '#'
                    break 

        # Check if the good cells are reachable and the bad cells are not reachable
        stack = [(n - 1, m - 1)]
        visited = set()
        while stack:
            row, col = stack.pop()
            if not inBound(row, col, n, m, visited, graph):
                continue
            visited.add((row, col))
            for i, j in direc:
                _row, _col = row + i, col + j
                stack.append((_row, _col))

        ans = 'Yes'
        for cell in good:
            if cell not in visited:
                ans = 'No'
                break
        
        for cell in bad:
            if cell in visited:
                ans = 'No'
                break

        print(ans)

if __name__ == '__main__':
    main()

Consider representing the permutation as a directed graph, where an edge exists from node $$$i$$$ to node $$$j$$$ if $$$p_i = j$$$.

Note that all connected components in this graph are simple cycles.

To begin with, let's understand why the string will return to its original form. In fact, the graph that the permutation sets consists of simple cycles and it turns out that after a certain number of operations, each character will return to its place.

Consider each cycle as a string that is cyclically shifted every turn. It may seem that the answer is — lcm (the smallest common multiple) of the cycle lengths, but to become equal to the initial string, it is not necessary to go through the entire cycle. We can calculate the length of the minimum suitable shift $$$k_j$$$ in $$$O(len)$$$ using built in function. Note that after $$$k_j$$$ operations, the cycle will return to its original form and this will happen again after $$$k_j$$$.

operations.

The answer will be lcm of all $$$k_j$$$, since each cycle individually comes to its original form after the number of operations is a multiple of its $$$k_j$$$.

import sys
from math import gcd
 
def solve():
	# Read input for the number of elements, string, and array of integers
	n = int(sys.stdin.readline().strip())
	s = sys.stdin.readline().strip()
	a = list(map(int, sys.stdin.readline().split()))
 
	lcm = 1
	vis = [0] * n
	for i in range(n):
    	if vis[i]:
        	continue
    	cur = []
    	ind = i
    	# Traverse the cycle starting from current index
    	while not vis[ind]:
        	cur.append(s[ind])
        	vis[ind] = 1
        		ind = a[ind] - 1
    	# Create a search string by repeating current cycle twice
    	search = "".join(cur + cur)
    	# Remove the first character (repetition), if we dont remove it the answer will always be 0
    	search = search[1:]  
    	# Find the starting index of the cycle
    	index = search.find("".join(cur)) + 1  
    	lcm = (lcm* index) // gcd(lcm, index)
	return lcm
 
if __name__ == "__main__":
 
	t = int(sys.stdin.readline().strip())
	for _ in range(t):
    	# Call solve() for each test case and print the result
    	result = solve()
    	print(result)

Consider the substring of $$$s$$$ from the second character to the last, or $$$s_2s_3⋯s_n$$$. If it's not palindrome, then the answer must be $$$n−1$$$. What if it's palindrome? This implies that $$$s_2=s_n, s_3=s_{n−1}$$$, and so on. Meanwhile, the fact that $$$s$$$ is palindrome implies $$$s_1=s_n, s_2=s_{n−1}$$$, etc. So we get $$$s_1=s_n=s_2=s_{n−1}=⋯$$$ or that all characters in $$$s$$$ is the same. In this situation, every subsequence of $$$s$$$ is palindrome of course, so the answer should be $$$−1$$$.

import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
    s = sys.stdin.readline().strip()
    if len(set(list(s))) == 1:
        print(- 1)
    else:
        print(len(s) - 1)

Every number can be represented as a product of prime numbers.

The only even prime number is 2.

We divide the given number by 2 until we can't. If the number that we get at the end is 1, that means the number doesn't have an odd divisor except 1. Otherwise, the number we found is either a prime number itself or divisible by another prime number other than 2, which is an odd number.

t = int(input())

for _ in range(t):
    n = int(input())
    while n > 1:
        n /= 2
    
    if n  == 1:
        print("NO")
    else:
        print("YES")
   

If you use LCM function on all numbers, you might get TLE (as the number might get big).

Any positive integer number can be factorized and written as $$$2^a·3^b·5^c·7^d·...$$$

We can multiply given numbers by $$$2$$$ and $$$3$$$ so we can increase $$$a$$$ and $$$b$$$ for them. So we can make all $$$a$$$ and $$$b$$$ equal by increasing them to the same big value (e.g. $$$100$$$). But we can't change powers of other prime numbers so they must be equal from the beginning. We can check it by diving all numbers from input by two and by three as many times as possible. Then all of them must be equal.

Alternative solution is to calculate GCD of given numbers. Answer is "YES" if and only if we can get each number by multiplying GCD by $$$2$$$ and $$$3$$$. Otherwise, some number had different power of prime number other than $$$2$$$ and $$$3$$$.

from sys import stdin


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

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

for i in range(N):
    while a[i]%2 == 0:
        a[i] //= 2
    while a[i]%3 == 0:
        a[i] //= 3

for i in range(1, N):
    if a[i] != a[0]:
        print("No")
        exit()
print("Yes")

For each index $$$i∈[1,n]$$$ let's try to find which $$$d$$$ we should use in order to make $$$i-th$$$ element of $$$c$$$ equal to zero. If $$$a_i=0$$$, then $$$c_i=b_i$$$ no matter which $$$d$$$ we choose. So we should just ignore this index and add $$$1$$$ to the answer if $$$b_i=0$$$.

Otherwise, we should choose $$$d=−b_i/a_i$$$. Let's calculate the required fraction for each index, and among all fractions find one that fits most indices (this can be done, for example, by storing all fractions in a dictionary).

The only thing that's left to analyze is how to compare the fractions, because floating-point numbers may be not precise enough. Let's store each fraction as a pair of integers $$$(x,y)$$$, where $$$x$$$ is the numenator and $$$y$$$ is the denominator. We should normalize each fraction as follows: firstly, we reduce it by finding the greatest common divisor of $$$x$$$ and $$$y$$$, and then dividing both numbers by this divisor. Secondly, we should ensure that numenator is non-negative, and if numenator is zero, then denominator should also be non-negative (this can be achieved by multiplying both numbers by −1).

import sys
from collections import Counter
from math import gcd
n = int(sys.stdin.readline().strip())
a =list(map(int, sys.stdin.readline().strip().split()))
b =list(map(int, sys.stdin.readline().strip().split()))
count = Counter()
ans = 0
for i in range(n):
    if a[i] == 0:
        if b[i] == 0:
            ans += 1
    else:
        x = b[i] // (gcd(abs(a[i]), abs(b[i])))
        y = a[i] // (gcd(abs(a[i]), abs(b[i])))
        if b[i] < 0:
            x *=  -1
            y *= -1
        elif b[i] == 0 and a[i] < 0:
            y *=  -1
        count[(x, y)] += 1
if len(count) == 0:
    print(ans)
else:
    print(ans + max(count.values()))
    

When is the answer $$$-1$$$?

What Happens when if we want to change all elements to $$$x$$$ and:

1. If $$$a_i > k$$$ and $$$x \leq k$$$:

2. If $$$a_i < k$$$ and $$$x \geq k$$$:

3. If $$$a_i = k$$$ and $$$x \neq k$$$:

Imagine we want to transform every number on the blackboard into $$$x$$$. For each $$$a_i$$$, until $$$a_i$$$ becomes $$$x$$$, we will split $$$a_i$$$ into two parts: $$$a_i + k = x$$$ and $$$a_i + k - x$$$. In other words, $$$a_i = a_i + k - x$$$, and we add $$$x$$$ at the end of the blackboard. For subsequent operations, we focus only on $$$a_i$$$.

We can observe three cases:

1. If $$$a_i > k$$$ and $$$x \leq k$$$: $$$a_i + k - x > a_i$$$, so $$$a_i$$$ keeps increasing, making it unsolvable.
2. If $$$a_i < k$$$ and $$$x \geq k$$$: $$$a_i + k - x < a_i$$$, so $$$a_i$$$ keeps decreasing and won't reach $$$x$$$, also unsolvable.
3. If $$$a_i = k$$$ and $$$x \neq k$$$: if $$$x < k$$$, $$$a_i$$$ keeps increasing. And if $$$x > k$$$, $$$a_i$$$ keeps decreasing and won’t reach $$$x$$$, so it’s unsolvable.

Therefore, for all $$$i, 1 \leq i \leq n$$$ if $$$a_i = k$$$, $$$x$$$ should be $$$k$$$; if $$$a_i > k$$$, $$$x$$$ should be $$$> k$$$; if $$$a_i < k$$$, $$$x$$$ should be $$$< k$$$; otherwise, we won’t have an answer and print $$$-1$$$.

Now, to make the solution efficient, we aim to minimize the number of operations required.

You have to split each $$$a_i$$$ into $$$p_i$$$ pieces equal to $$$x$$$, and their sum must be equal to $$$a_i + k(p_i - 1) = a_i + k \cdot p_i - k $$$

$$$ a_i + k \cdot p_i - k = (a_i - k) + k \cdot p_i $$$

$$$(a_i - k) + k \cdot p_i = x \cdot p_i$$$.

Then, $$$(a_i - k) = (x - k) \cdot p_i$$$, so $$$x - k$$$ must be a divisor of every $$$ a_i - k$$$.

Since we want to minimize the number of operations (i.e., $$$p_i$$$), and since $$$p_i = (a_i - k) / (x - k)$$$, we want to make $$$x - k$$$ the largest number that divides all $$$a_i - k$$$.

import math, sys


def solve():
    n, k = map(int, sys.stdin.readline().strip().split())
    a = list(map(int, sys.stdin.readline().strip().split()))
    
    if a.count(a[0]) == n:
        return 0

    for x in a:
        if (x >= k and a[0] <= k) or (x <= k and a[0] >= k):
            return -1
    gcd = abs(k - a[0])
    for i in a:
   	gcd = math.gcd(gcd, abs(k - i))
    
    ans = 0
    for i in a:
   	ans += (abs(k - i) // gcd - 1)
    
    return ans

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

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

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

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


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

Output binary search.

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

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

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

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

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

from math import ceil
from sys import stdin


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

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

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

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

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

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

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

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

from sys import stdin


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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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


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

Topic: Greedy

What is the maximum number of points for the $$$(k + 1)$$$-th team?

If $$$k$$$ equals $$$n$$$ (the last position), the answer is $$$0$$$ since $$$0$$$ points are needed to secure the last position.

Let's calculate for other positions:

Firstly, let's determine the maximum number of points the $$$(k + 1)$$$-th team can have. To maximize this, the first $$$(k + 1)$$$ teams will win all matches against the remaining $$$n - (k + 1)$$$ teams, resulting in the first $$$(k + 1)$$$ teams having points equal to $$$(n - (k + 1)) \cdot 3$$$.

Now, our task is to maximize the points of both the $$$k$$$-th and $$$(k + 1)$$$-th teams. To achieve this, we focus on the remaining matches involving the $$$k$$$ teams (excluding the $$$(k + 1)$$$-th team). Since we aim to maximize the minimum points within these $$$k$$$ teams, we need to maximize the minimum points in the remaining matches.

For $$$k = 2$$$, there is only $$$k - 1 = 1$$$ match remaining for a team. If a team wins, the other team will have $$$0$$$ points, resulting in a minimum of $$$0$$$ points. However, to maximize the minimum points, it's better if the match ends in a draw, resulting in a minimum of $$$1$$$ point. For $$$k = 3$$$, there are $$$k - 1 = 2$$$ matches remaining for a team. If a team wins one and loses one, all teams will have $$$3$$$ points, resulting in a minimum of $$$3$$$ points. However, if one team wins both matches, the minimum points will be $$$0$$$ or $$$1$$$.

We observe that if a match ends in a win or a loss, the overall points are $$$3$$$, whereas if it is a draw, it is $$$2$$$ (with $$$1$$$ point for each team). We aim to avoid losing points in a draw. The issue arises when there is only one match remaining and it's either a win or a loss, resulting in a minimum of $$$0$$$ points. However, with a draw, the minimum is $$$1$$$ point. For two matches, we can achieve an overall of $$$6$$$ points with wins, distributing $$$3$$$ points to each team.

Hence, to maximize the minimum points within the $$$k$$$ teams, we have $$$(k - 1)$$$ matches for each team. If $$$(k - 1)$$$ is even, the team wins $$$\frac{k - 1}{2}$$$ matches and loses $$$\frac{k - 1}{2}$$$ matches. If $$$(k - 1)$$$ is odd, the team wins $$$\frac{k - 2}{2}$$$ matches, loses $$$\frac{k - 2}{2}$$$ matches, and draws $$$1$$$ match. Generally (for even or odd), the points it can obtain is $$$\left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2$$$.

Now, both the $$$k$$$-th and $$$(k + 1)$$$-th teams have $$$(n - (k + 1)) \cdot 3 + \left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2$$$ points. The only match remaining is between them. We can secure the $$$k$$$-th team in the $$$k$$$-th position by ensuring it wins the match against the $$$(k + 1)$$$-th team. However, if both teams have the same number of points, they will both secure the $$$k$$$-th position. Therefore, to minimize the points required to guarantee the $$$k$$$-th position, the match should end in a draw. Finally, the $$$k$$$-th team will have $$$(n - (k + 1)) \cdot 3 + \left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2 + 1$$$ point.

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

from sys import stdin


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

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

    if N == K:
        print(0)
        continue

    ans = (N - (K + 1))*3 + ((K - 1)//2)*3 + (K - 1)%2 + 1
    print(ans)