[Here](https://codeforces.me/contestInvitation/a2c03a5976fa02f50b4e11d6f1fda6e29cd7e083) is the contest link.↵
↵
#### [A. A+ Student](https://codeforces.me/gym/590053/problem/A)↵
↵
<spoiler summary="Hint 1"> ↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2"> 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. </spoiler>↵
↵
<spoiler summary="Solution"> <p> 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.</p> ↵
**Approach:**↵
↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
#### [B. Jo's Adventure](https://codeforces.me/gym/590053/problem/B)↵
↵
<spoiler summary = "Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary = "Hint 2">↵
Think of damage as a prefix sum↵
</spoiler>↵
↵
↵
<spoiler summary="Solution"> 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 < 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 > 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)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
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])↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Binary Flip](https://codeforces.me/gym/590053/problem/C)↵
↵
<spoiler summary = "Solution">↵
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).↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
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()↵
```↵
</spoiler>↵
↵
↵
#### [D. Minimize the Distance](https://codeforces.me/gym/590053/problem/D)↵
↵
<spoiler summary = "Hint">↵
Do we really need to check every point in the given range?↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution 1">↵
<p>↵
↵
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.↵
</p>↵
↵
<p>↵
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.↵
</p>↵
↵
<p>↵
Approach↵
<ul>↵
↵
<li>↵
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.↵
</li>↵
↵
<li>↵
Calculate the distance for each point using running sums and update the answer variable.↵
<ul>↵
<li>↵
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.↵
</li>↵
<li>↵
For a point $p$ that is on index $i$, we can find the total distance as:↵
↵
<ul>↵
<li> left side distance = $i$ * $p$ — $suml$ </li>↵
<li> right side distance = $sumr$ — ($n$ — $i$) * $p$ </li>↵
<li> total distance = left side distance + right side distance </li>↵
</ul>↵
↵
where $n$ is the number of points given.↵
</li>↵
</ul>↵
</p>↵
</ul>↵
<p>Time complexity: $O(nlogn)$</p>↵
<p>Space complexity: $O(1)$</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
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)↵
↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
<p>↵
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.↵
</p>↵
↵
<p>↵
Let’s assume we pick some $x$ as our answer and check if moving it left or right changes the total distance.↵
</p>↵
↵
<p>↵
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.↵
</p>↵
↵
<p>↵
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.↵
</p>↵
↵
<p>↵
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..↵
</p>↵
↵
<p>Time complexity: $O(nlogn)$</p>↵
<p>Space complexity: $O(1)$</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
points = [int(i) for i in input().split()]↵
points.sort()↵
↵
mid_index = (n - 1) // 2↵
print(points[mid_index])↵
```↵
</spoiler>↵
↵
#### [E. Weird and Ugly Monsters](https://codeforces.me/gym/590053/problem/E)↵
↵
<spoiler summary="Hint 1">↵
How can you maintain monsters in a circle while allowing quick insertion and removal?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>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.</p>↵
<p>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.</p>↵
<p>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.</p>↵
<p>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)$.</p>↵
<p>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)$.</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
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()↵
```↵
</spoiler>↵
↵
↵
#### [A. A+ Student](https://codeforces.me/gym/590053/problem/A)↵
↵
<spoiler summary="Hint 1"> ↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2"> 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. </spoiler>↵
↵
<spoiler summary="Solution"> <p> 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.</p> ↵
**Approach:**↵
↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
#### [B. Jo's Adventure](https://codeforces.me/gym/590053/problem/B)↵
↵
<spoiler summary = "Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary = "Hint 2">↵
Think of damage as a prefix sum↵
</spoiler>↵
↵
↵
<spoiler summary="Solution"> 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 < 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 > 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)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
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])↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Binary Flip](https://codeforces.me/gym/590053/problem/C)↵
↵
<spoiler summary = "Solution">↵
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).↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
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()↵
```↵
</spoiler>↵
↵
↵
#### [D. Minimize the Distance](https://codeforces.me/gym/590053/problem/D)↵
↵
<spoiler summary = "Hint">↵
Do we really need to check every point in the given range?↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution 1">↵
<p>↵
↵
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.↵
</p>↵
↵
<p>↵
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.↵
</p>↵
↵
<p>↵
Approach↵
<ul>↵
↵
<li>↵
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.↵
</li>↵
↵
<li>↵
Calculate the distance for each point using running sums and update the answer variable.↵
<ul>↵
<li>↵
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.↵
</li>↵
<li>↵
For a point $p$ that is on index $i$, we can find the total distance as:↵
↵
<ul>↵
<li> left side distance = $i$ * $p$ — $suml$ </li>↵
<li> right side distance = $sumr$ — ($n$ — $i$) * $p$ </li>↵
<li> total distance = left side distance + right side distance </li>↵
</ul>↵
↵
where $n$ is the number of points given.↵
</li>↵
</ul>↵
</p>↵
</ul>↵
<p>Time complexity: $O(nlogn)$</p>↵
<p>Space complexity: $O(1)$</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
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)↵
↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
<p>↵
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.↵
</p>↵
↵
<p>↵
Let’s assume we pick some $x$ as our answer and check if moving it left or right changes the total distance.↵
</p>↵
↵
<p>↵
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.↵
</p>↵
↵
<p>↵
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.↵
</p>↵
↵
<p>↵
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..↵
</p>↵
↵
<p>Time complexity: $O(nlogn)$</p>↵
<p>Space complexity: $O(1)$</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
points = [int(i) for i in input().split()]↵
points.sort()↵
↵
mid_index = (n - 1) // 2↵
print(points[mid_index])↵
```↵
</spoiler>↵
↵
#### [E. Weird and Ugly Monsters](https://codeforces.me/gym/590053/problem/E)↵
↵
<spoiler summary="Hint 1">↵
How can you maintain monsters in a circle while allowing quick insertion and removal?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>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.</p>↵
<p>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.</p>↵
<p>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.</p>↵
<p>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)$.</p>↵
<p>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)$.</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
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()↵
```↵
</spoiler>↵
↵
