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

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

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

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

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

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

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

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

Think of damage as a prefix sum

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

Precompute the total damage for moving forward:

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

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

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

Precompute the total damage for moving backward:

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

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

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

Answer queries efficiently:

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

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

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

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

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

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

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

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

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

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

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

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

Complexity is O(n).

import sys

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


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

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

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

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

Approach

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

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

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

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

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

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

    suml += point
    sumr -= point

print(answer)

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

Let’s assume we pick some $$$x$$$ as our answer and check if moving it left or right changes the total distance.

case 1: Suppose $$$x$$$ is currently at some position, and we move it leftward (decreasing $$$x$$$). This reduces the distance to all points on the left but increases the distance to all points on the right. Since there are generally more points on one side than the other, this movement results in a net increase in the total sum of distances.

case 2: If we move $$$x$$$ rightward (increasing $$$x$$$), the distances to all right-side points decrease, but the distances to all left-side points increase. Again, due to the imbalance in the number of points on each side, the total sum of distances increases.

Thus, the best choice is where moving left or right does not improve the total sum of distances—this happens at the middle point (by index) in the sorted list of the given points..

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

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

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

mid_index = (n - 1) // 2
print(points[mid_index])

How can you maintain monsters in a circle while allowing quick insertion and removal?

You can use a linked list to handle the monsters insertion and removal. But, how can you quickly find a monster’s position without searching the entire list?

The problem requires us to keep track of a group of monsters sitting in a circle, each with an ugliness score. Whenever two adjacent monsters have the same ugliness score, they merge into one, keeping the smaller index and doubling the ugliness score. Each newly added monster gets a unique increasing index, and after every insertion and all possible merges, we need to determine how many monsters remain in the table.

To handle this efficiently, we use a circular doubly linked list. Since each monster has a left and right neighbor, a doubly linked list allows easy movement in both directions. The circular part means that the last node's next pointer points to the first node, and the first node's previous pointer points to the last node. This makes it easier to manage the circle without needing extra checks. In addition to this, a dictionary is used to quickly find any monster's node by its index, so we don't have to search through the list every time.

When a new monster is added, it always appears to the right of the monster with the given index. Using the dictionary, we can find that monster's position immediately and insert the new one by updating a few pointers. After insertion, we check if the new monster can merge with the one on its left. If their ugliness scores are the same, they combine into one, with the remaining monster keeping the smaller index and doubling its ugliness score. This process repeats with the new left neighbor until no more merges are possible. After that, we check the right neighbor and continue merging in the same way. The merging keeps happening as long as there are adjacent monsters with the same ugliness score.

For time complexity, at the beginning, there is just one monster, and then we have $$$n$$$ insertions. Each insertion involves finding the right place in the list, which takes $$$O(1)$$$ time using the dictionary. Inserting a new monster also takes $$$O(1)$$$ time since it only involves pointer updates. After an insertion, we need to check for possible merges. In the worst case, each insertion may trigger up to $$$O(n)$$$ merges. However, since each adjacent monster pair can merge at most once, the total number of merges across all $$$n$$$ insertions will not exceed $$$n$$$. This means the overall time complexity for processing all insertions and merges is $$$O(n)$$$.

For space complexity, we need to store each monster as a node in the linked list, which takes $$$O(n)$$$ space. The dictionary also holds a reference to each monster, adding another $$$O(n)$$$ space. Since both structures grow at the same rate as the number of monsters, the overall space complexity is $$$O(n)$$$.

class ListNode:
    def __init__(self, index, ugliness):
        # Initialize a new monster node with an index and ugliness score.
        self.index = index
        self.ugliness = ugliness
        self.next = None
        self.prev = None


def merge_monsters(node, monster_map, count):
    # Try to merge the node with its adjacent neighbors (left and right) as long as they have the same ugliness score.
    while True:
        merged = False

        # Merge with the left neighbor if they have the same ugliness
        if node.prev != node and node.ugliness == node.prev.ugliness:
            left = node.prev
            if node.index > left.index:
                # Adjust the pointers to remove 'node' and merge with the left neighbor
                left.next = node.next
                node.next.prev = left
                left.ugliness *= 2
                count[0] -= 1  # Decrease the count of monsters after merging
                node = left  # Move 'node' to 'left' as it is now the active node
            else:
                # Adjust the pointers to remove 'left' and merge with 'node'
                node.prev = left.prev
                left.prev.next = node
                node.ugliness *= 2
                count[0] -= 1  # Decrease the count of monsters after merging
            merged = True

        # Merge with the right neighbor if they have the same ugliness
        elif node.next != node and node.ugliness == node.next.ugliness:
            right = node.next
            if node.index > right.index:
                # Adjust the pointers to remove 'node' and merge with the right neighbor
                node.prev.next = right
                right.prev = node.prev
                right.ugliness *= 2
                count[0] -= 1  # Decrease the count of monsters after merging
                node = right  # Move 'node' to 'right' as it is now the active node
            else:
                # Adjust the pointers to remove 'right' and merge with 'node'
                right.next.prev = node
                node.next = right.next
                node.ugliness *= 2
                count[0] -= 1  # Decrease the count of monsters after merging
            merged = True

        # Exit the loop if no merges happened
        if not merged:
            break


def solve():
    # Solve the problem for a single test case
    num_insertions, initial_ugliness = map(int, input().split())

    # Count is an array of 1 value because it is passed to the merge
    # function and we need to modify the value in that function
    count = [1]  # Initialize count to 1 since we have 1 monster initially

    head = ListNode(1, initial_ugliness)
    head.next = head  # Make the list circular by linking the head to itself
    head.prev = head
    monster_map = {1: head}  # Map to track the monsters by their index

    indices = list(map(int, input().split()))
    ugliness_values = list(map(int, input().split()))
    next_index = 2  # Start from the next available index for the new monsters
    results = []

    for i in range(num_insertions):
        monster_index, ugliness_score = indices[i], ugliness_values[i]
        monster = monster_map[monster_index]

        # Create and insert the new monster into the linked list
        new_monster = ListNode(next_index, ugliness_score)
        next_index += 1

        # Adjust the pointers to add the new monster
        new_monster.next = monster.next
        new_monster.prev = monster
        monster.next.prev = new_monster
        monster.next = new_monster

        monster_map[new_monster.index] = new_monster  # Add the new monster to the map
        count[0] += 1  # Increase the count after adding a new monster

        # Perform merges after insertion
        merge_monsters(new_monster, monster_map, count)

        # Store the current number of monsters after the insertion and merges
        results.append(count[0])

    print(*results)


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