#### [A. Kibr and His Musics](https://codeforces.net/gym/589822/problem/A)↵
↵
<spoiler summary = "Solution">↵
###Problem Overview:↵
The problem involves identifying which song is playing at specific moments during a playlist where each song repeats a defined number of times. The playlist plays sequentially, with song `i` playing `ci` times and each play lasting `ti` minutes. Given moments `vi`, we need to determine which song is playing at each of those times.↵
↵
###Approach:↵
Prefix Sum Array:↵
The key idea is to build a prefix sum array where `prefix[i]` represents the cumulative total duration of songs from the start to the end of song `i`. If `ci` is the repetition count and `ti` is the duration of song `i`, then the contribution of song `i` to the prefix sum is `ci * ti`.↵
The prefix sum allows us to efficiently check which song is playing at any given moment by comparing the `vi` values against cumulative durations.↵
↵
Linear Search:↵
For each moment `vi`, iterate through the prefix sum array until you find the first `i` where `prefix[i] >= vi`.↵
###Time Complexity:↵
Prefix Sum Construction: `O(n)`↵
Query Handling: `O(m) using linear search`↵
Overall: `O(n + m)`↵
Space Complexity: `O(n) for storing the prefix sum array.`↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m = map(int, input().split())↵
prefix = []↵
for i in range(n):↵
c, t = map(int, input().split())↵
prefix.append(c * t)↵
if i > 0:↵
prefix[i] += prefix[i - 1]↵
moments = list(map(int, input().split()))↵
i = 0↵
for j in range(m):↵
while prefix[i] < moments[j]:↵
i += 1↵
print(i + 1)↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [B. Kidus Couldn't Sleep](https://codeforces.net/gym/589822/problem/B)↵
↵
<spoiler summary="Hint"> To efficiently calculate the average sleep time, consider how to sum values over sliding windows without recalculating the entire sum for each new window. </spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> <p> The problem requires calculating the average sleep time over all possible weeks in Polycarp's records. A naive approach would involve iterating through each possible starting index and summing up the next <b>k</b> elements. However, this results in an <b>O(n × k)</b> complexity, which is inefficient for large values of <b>n</b>.↵
Instead, we can use the <b>sliding window</b> technique to efficiently compute the sum for each week in <b>O(n)</b> time:↵
<ul> <li>First, compute the sum of the first <b>k</b> days and store it as the current sum.</li> <li>Iterate from day <b>k</b> to day <b>n</b>, updating the sum by adding the new day's sleep time and removing the sleep time of the day that is no longer in the window.</li> <li>Keep a running total of these weekly sums and compute the final average.</li> </ul>↵
Since there are <b>n − k + 1</b> weeks, the final result is the sum of all weekly sleep times divided by this count.↵
</p> </spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python ↵
n, k = map(int, input().split()) ↵
a = list(map(int, input().split()))↵
curr = sum(a[:k])↵
total = curr↵
for i in range(k, n):↵
curr += a[i] - a[i - k]↵
total += curr↵
↵
print(total / (n - k + 1))↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [C. Restoring to the Original](https://codeforces.net/gym/589822/problem/C)↵
↵
<spoiler summary = "Solution">↵
It's easy to see that letter $z$ appears only in "zero" and $n$ appears only in "one", so we should print $1$ $\text{count}(n)$ times and then $0$ $\text{count}(z)$ times.↵
</spoiler>↵
↵
↵
<spoiler summary = "Code">↵
```python ↵
n = int(input()) ↵
s = input() ↵
ones = s.count('n') ↵
zeros = s.count('z') ↵
print('1 ' * ones + '0 ' * zeros)↵
```↵
</spoiler>↵
↵
#### [D. Socialism](https://codeforces.net/gym/589822/problem/D)↵
↵
<spoiler summary="Hint"> ↵
Try to find the maximum number of people who can have at least x burles after redistributing the money among selected subsets of people. The key observation is that the redistribution must be fair among the chosen subset. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> ↵
The problem requires us to maximize the number of people who have at least `x` burles after any number of redistribution reforms. The key observation is that any subset of people chosen for redistribution will end up with an equal amount of money per person. ↵
↵
### Approach: ↵
1. **Sort the savings in descending order**: This ensures that we consider the wealthiest individuals first. ↵
2. **Iterate through the sorted list and track cumulative wealth**: We keep summing the wealth and checking if the average wealth of the first `i` people is at least `x`. ↵
3. **Break when the condition fails**: If at any step the cumulative wealth divided by `i + 1` is less than `x`, the answer is `i`. Otherwise, the answer is `n` if we can include all individuals. ↵
↵
### Example Walkthrough: ↵
1. **Case 1** (`[5,1,2,1]`, `x=3`): ↵
- Sort: `[5,2,1,1]` ↵
- Sum stepwise: `5`, `5+2=7`, `7+1=8`, `8+1=9` ↵
- The condition fails at index `2`, so the answer is `2`. ↵
↵
2. **Case 2** (`[11,9,11,9]`, `x=10`): ↵
- Sort: `[11,11,9,9]` ↵
- Sum stepwise: `11`, `22`, `31`, `40` ↵
- The condition holds for all, so the answer is `4`. ↵
↵
3. **Case 3** (`[4,3]`, `x=5`): ↵
- Sort: `[4,3]` ↵
- The sum never reaches `5`, so the answer is `0`. ↵
↵
4. **Case 4** (`[9,4,9]`, `x=7`): ↵
- Sort: `[9,9,4]` ↵
- Sum stepwise: `9`, `18`, `22` ↵
- The condition holds for `3`, so the answer is `3`. ↵
↵
### Complexity Analysis: ↵
- Sorting takes **O(n log n)**. ↵
- Iterating through the array takes **O(n)**. ↵
- Thus, the total complexity per test case is **O(n log n)**. ↵
- Since the sum of `n` across all test cases is at most `10^5`, this solution efficiently handles the constraints. ↵
</spoiler>↵
↵
<spoiler summary="Code"> ↵
```python ↵
t = int(input()) # Read number of test cases ↵
↵
for _ in range(t): ↵
n, x = map(int, input().split()) # Read n (number of people) and x (wealth threshold) ↵
nums = sorted(map(int, input().split()), reverse=True) # Sort wealth in descending order ↵
↵
total = 0 # Track cumulative wealth ↵
for i in range(n): ↵
total += nums[i] # Add wealth of the i-th person ↵
if total < x * (i + 1): # Check if the average wealth falls below x ↵
print(i) # Maximum number of wealthy people possible ↵
break ↵
else: ↵
print(n) # If we never break, all n people can be wealthy ↵
```↵
</spoiler>↵
↵
↵
↵
#### [E. TV Off](https://codeforces.net/gym/589822/problem/E)↵
↵
<spoiler summary="Solution">↵
↵
To solve this problem, we need to determine if there exists a TV segment that can be removed without reducing the total covered time. Intuitively, a segment is redundant if every moment it covers is still covered by at least one other segment. Our goal is to efficiently check for such a segment. ↵
↵
Since the given time values can be large (`≤ 10^9`), storing them directly is inefficient. Instead, we use **coordinate compression** to map time values into a smaller range (at most `6 × 10^5`). We then use a **difference array** approach: for each segment `[li, ri]`, we increment coverage at `li` and decrement at `ri + 1`. Taking prefix sums over this array gives us the number of active TV sets at each moment. From this, we compute `pref[i]`, which stores how many moments up to `i` are covered by exactly one segment. ↵
↵
Finally, for each segment `[l, r]`, we check if `pref[r] - pref[l - 1]` is `0`. This means that every moment in this range is covered by at least one other segment, making it **redundant**. If we find such a segment, we print its index; otherwise, we print `-1`. This approach runs in **O(n log n)** due to sorting and coordinate compression, making it efficient.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
↵
def solve():↵
n = int(input())↵
segments = []↵
coord_set = set()↵
↵
# Collecting segments and unique coordinates↵
for _ in range(n):↵
l, r = map(int , input().split())↵
segments.append((l, r + 1))↵
coord_set.add(l)↵
coord_set.add(r + 1)↵
↵
# Coordinate compression↵
coord_list = sorted(coord_set)↵
coord_map = {v: i for i, v in enumerate(coord_list)}↵
m = len(coord_list)↵
↵
# Prefix array to track coverage↵
coverage = [0] * (m + 1)↵
for l, r in segments:↵
coverage[coord_map[l]] += 1↵
coverage[coord_map[r]] -= 1↵
↵
# Compute prefix sums for coverage↵
for i in range(1, m):↵
coverage[i] += coverage[i - 1]↵
↵
# Compute `pref` array, which stores the count of moments covered exactly once↵
pref = [0] * m↵
for i in range(1, m):↵
pref[i] = pref[i - 1] + (1 if coverage[i - 1] == 1 else 0)↵
↵
# Find redundant segment↵
for i, (l, r) in enumerate(segments):↵
if pref[coord_map[r]] - pref[coord_map[l]] == 0:↵
print(i + 1)↵
return↵
↵
print(-1)↵
↵
solve()↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
#### [F. Covered Points Count](https://codeforces.net/gym/589822/problem/F)↵
↵
<spoiler summary="Hint1">↵
- What would you do if the constraints for the coordinates were up to \(10^5\)? ↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
- You could use the line sweep algorithm, but the coordinates go up to \(10^9\). So, what shall we do? </spoiler>↵
↵
<spoiler summary="Hint3">↵
- What if you use a dictionary instead of an array to store only the relevant positions? ↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We perform a line sweep using a dictionary to record events at positions where the number of covering segments changes. Sorting the dictionary keys lets us compute the prefix sum between these "critical" points. For each interval \([prev, cur)\), the number of integer points is \((cur — prev)\) and they are all covered by the current number of segments. This way, we aggregate the answer for every \(k\) in \([1, n]\) without iterating over every integer in a huge range.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
from collections import defaultdict↵
↵
n = int(sys.stdin.readline().strip())↵
events = defaultdict(int)↵
↵
# Record events: +1 when a segment starts, -1 when it ends (at r+1)↵
for _ in range(n):↵
l, r = map(int, sys.stdin.readline().split())↵
events[l] += 1↵
events[r + 1] -= 1↵
↵
# Sort the event points↵
keys = sorted(events.keys())↵
coverage = 0↵
prev = keys[0]↵
result = defaultdict(int)↵
↵
# Line sweep: update coverage and count points in intervals↵
for point in keys:↵
result[coverage] += point - prev↵
coverage += events[point]↵
prev = point↵
↵
# Output counts for points covered by exactly 1 to n segments↵
ans = [result[k] for k in range(1, n + 1)]↵
print(*ans)↵
↵
```↵
</spoiler>↵
↵
↵
#### [G. Evenly Spaced Letters](https://codeforces.net/gym/589822/problem/G)↵
↵
<spoiler summary = "Solution">↵
Let's consider a very special case of equal distances. What if all distances were equal to $1$? It implies that if some letter appears exactly twice, both occurrences are placed right next to each other.↵
↵
That construction can be achieved if you sort the string, for example: first right down all letters '$a$', then all letters '$b$' and so on. If a letter appears multiple times, all its occurrences will be next to each other, just as we wanted.↵
↵
Overall complexity: $O(|s|log|s|)$ or $O(|s|)$ per testcase.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
for _ in range(int(input())):↵
print(''.join(sorted(input())))↵
```↵
</spoiler>↵
↵
#### [H. Dominoes](https://codeforces.net/gym/589822/problem/H)↵
↵
<spoiler summary = "Hint-1">↵
This is a 2D prefix sum problem.↵
</spoiler>↵
↵
<spoiler summary = "Hint-2">↵
Do the 2D prefix sum for the horizontal and vertical arrangements separately.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
↵
<spoiler summary = "Definitions">↵
<p>↵
Let’s have two $h$ by $w$ 2D arrays $vertical$ and $horizontal$ to count the number of possible vertical and horizontal arrangements respectively. $vertical[i][j]$ and $horizontal[i][j]$ indicate the following:↵
↵
<ul>↵
<li>↵
$vertical[i][j]$ is the number of ways we can place a domino vertically in the rectangle whose top left corner is located at the $zeroth$ row and $zeroth$ column and whose bottom left corner is located at the $i-th$ row and at the $j-th$ column, $(0 - indexed).$↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
$horizontal[i][j]$ is the number of ways we can place a domino horizontally in the rectangle whose top left corner is located at the $zeroth$ row and $zeroth$ column and whose bottom left corner is located at the $i-th$ row and at the $j-th$ column, $(0 - indexed).$↵
</li>↵
</ul>↵
↵
</p>↵
</spoiler>↵
↵
<spoiler summary = "Constructing the 2D prefix arrays">↵
<ul>↵
<li>↵
The first column of $horizontal$ will be initialized to zero as we need at least two columns to place a domino horizontally. Then we will traverse $horizontal$ fully. For every row-column pair $r$, $c$ (0-indexed), we will set $horizontal[r][c] = 1$ if $c > 0$, $arr[r][c] == ‘.’$, and $arr[r][c - 1] == ‘.’$ are all true indicating we can place our domino from $r, c - 1$ to $r, c$ horizontally. Otherwise we set $horizontal[r][c] = 0.$ Where $arr$ is the given $h$ x $w$ rectangular grid.↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
The first row of $vertical$ will be initialized to zero as we need at least two rows to place a domino vertically. Then we will traverse $vertical$ fully. For every row-column pair $r$, $c$ (0-indexed), we will set $vertical[r][c] = 1$ if $r > 0$, $arr[r][c] == ‘.’$, and $arr[r - 1][c] == ‘.’$ are all true indicating we can place our domino from $r - 1, c$ to $r, c$ vertically. Otherwise we set $vertical[r][c] = 0.$ ↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
Finally we will do row wise prefix sum followed by column wise prefix sum or vice versa, the order doesn’t matter, for both our 2D arrays. Now we have what we indicated in the $’Definition’$ part above.↵
</li>↵
</ul>↵
</spoiler>↵
↵
<spoiler summary = "Answering the queries">↵
<p>↵
For every query $r1, c1, r2, c2$ we calculate our answer as follows: ↵
</p>↵
<p>↵
<ul>↵
↵
<li>↵
$horizontal$_$count = horizontal[r2][c2]-horizontal[r2][c1]-horizontal[r1 - 1][c2]+horizontal[r1 - 1][c1]$↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
$vertical$_$count = vertical[r2][c2]-horizontal[r2][c1 - 1]-vertical[r1][c2]+horizontal[r1][c1 - 1]$↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
Then our final will be $horizontal$_$ count + vertical$_$count.$ Note that the way we calculate the $vertical$_$count$ and the $horizontal$_$count$ are not identical. For the $horizontal$_$count$, we don’t want to count the number of horizontal arrangements before and at $c1$, because the numbers at $c1$ include the arrangements that start at $c1 - 1$ and end at $c1$. In that case such an arrangement should not be counted as the starting position of the domino is outside the given rectangle in the query. Similarly the vertical arrangements starting from $r1 - 1$ and ending ar $r1$ should also be excluded. We have to be careful when we count. And whenever we are using $r1 - 1$ and $c1 - 1$ we have to check if they are greater than or equal to $0.$↵
</li>↵
</ul>↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary = "Time and space complexities">↵
<ul>↵
<li>↵
$\text{Time Complexity: } O(h .w)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(h .w)$↵
</li>↵
</ul>↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
h, w = map(int, input().split())↵
↵
grid = []↵
for i in range(h):↵
grid.append(input())↵
↵
↵
horizontal = [[0] * w for _ in range(h)]↵
vertical = [[0] * w for _ in range(h)]↵
↵
# indicate valid arrangements by 1 and invalid arrangements by 0.↵
# horizontal[r][c] == 1 means we can place a domino horizontally from grid[r][c - 1] to grid[r][c]↵
# vertical[r][c] == 1 means we can place a domino vertically from grid[r - 1][c] to grid[r][c]↵
for r in range(h):↵
for c in range(w):↵
↵
if c > 0 and grid[r][c] == grid[r][c - 1] == '.':↵
horizontal[r][c] = 1↵
↵
if r > 0 and grid[r][c] == grid[r - 1][c] == '.':↵
vertical[r][c] = 1↵
↵
↵
# perform row-wise prefix sums↵
for r in range(h):↵
for c in range(1, w):↵
horizontal[r][c] += horizontal[r][c - 1]↵
vertical[r][c] += vertical[r][c - 1]↵
↵
# perform column-wise prefix sums↵
for c in range(w):↵
for r in range(1, h):↵
horizontal[r][c] += horizontal[r - 1][c]↵
vertical[r][c] += vertical[r - 1][c]↵
↵
↵
q = int(input())↵
↵
for i in range(q):↵
r1, c1, r2, c2 = map(int, input().split())↵
r1, c1, r2, c2 = r1 - 1, c1 - 1, r2 - 1, c2 - 1 # changing 1-indexed input to 0-indexed↵
↵
horizontal_count = horizontal[r2][c2] - horizontal[r2][c1]↵
if r1 - 1 >= 0:↵
horizontal_count += horizontal[r1 - 1][c1] - horizontal[r1 - 1][c2]↵
↵
vertical_count = vertical[r2][c2] - vertical[r1][c2]↵
if c1 - 1 >= 0:↵
vertical_count += vertical[r1][c1 - 1] - vertical[r2][c1 - 1]↵
↵
answer = horizontal_count + vertical_count↵
↵
print(answer)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [I. The Odd Challenge](https://codeforces.net/gym/589822/problem/I)↵
↵
<spoiler summary="Problem">↵
We have an array \( a \) of length \( n \) and must answer \( q \) queries. Each query modifies all elements in a given range \( [l, r] \) by setting them to \( k \) and asks whether the sum of the updated array is odd.↵
↵
Each query is independent, meaning changes do not persist for subsequent queries.↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Observe that changing a subarray to a fixed value (k) affects the total sum in a predictable way. The effect on the total sum can be computed by removing the sum of the existing subarray and adding the contribution of the new values.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How can prefix sum help us here?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
1. Compute the initial sum of the array.↵
2. Compute the prefix sum for quick range sum retrieval.↵
3. For each query:↵
- Compute the sum of the range \( [l, r] \).↵
- Replace it with \( (r — l + 1) \times k \).↵
- Check if the new sum is odd.↵
- Print "YES" if odd, else "NO".↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
t = int(input())↵
↵
for _ in range(t):↵
n, q = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
prefix = [0] * (n + 1)↵
for i in range(n):↵
prefix[i + 1] = prefix[i] + a[i]↵
↵
total_sum = prefix[-1]↵
results = []↵
for _ in range(q):↵
l, r, k = map(int, input().split())↵
replaced_range_old_sum = prefix[r] - prefix[l - 1]↵
replaced_range_new_sum = (r - l + 1) * k↵
new_sum = total_sum - replaced_range_old_sum + replaced_range_new_sum↵
↵
if new_sum % 2 == 1:↵
results.append("YES")↵
else:↵
results.append("NO")↵
↵
print("\n".join(results) + "\n")↵
```↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
- Computing the total sum: \( O(n) \)↵
- Computing the prefix sum: \( O(n) \)↵
- Each query: \( O(1) \) (using prefix sum)↵
- Total complexity: \( O(n + q) \) per test case, which is optimal given constraints.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
###Problem Overview:↵
The problem involves identifying which song is playing at specific moments during a playlist where each song repeats a defined number of times. The playlist plays sequentially, with song `i` playing `ci` times and each play lasting `ti` minutes. Given moments `vi`, we need to determine which song is playing at each of those times.↵
↵
###Approach:↵
Prefix Sum Array:↵
The key idea is to build a prefix sum array where `prefix[i]` represents the cumulative total duration of songs from the start to the end of song `i`. If `ci` is the repetition count and `ti` is the duration of song `i`, then the contribution of song `i` to the prefix sum is `ci * ti`.↵
The prefix sum allows us to efficiently check which song is playing at any given moment by comparing the `vi` values against cumulative durations.↵
↵
Linear Search:↵
For each moment `vi`, iterate through the prefix sum array until you find the first `i` where `prefix[i] >= vi`.↵
###Time Complexity:↵
Prefix Sum Construction: `O(n)`↵
Query Handling: `O(m) using linear search`↵
Overall: `O(n + m)`↵
Space Complexity: `O(n) for storing the prefix sum array.`↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m = map(int, input().split())↵
prefix = []↵
for i in range(n):↵
c, t = map(int, input().split())↵
prefix.append(c * t)↵
if i > 0:↵
prefix[i] += prefix[i - 1]↵
moments = list(map(int, input().split()))↵
i = 0↵
for j in range(m):↵
while prefix[i] < moments[j]:↵
i += 1↵
print(i + 1)↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [B. Kidus Couldn't Sleep](https://codeforces.net/gym/589822/problem/B)↵
↵
<spoiler summary="Hint"> To efficiently calculate the average sleep time, consider how to sum values over sliding windows without recalculating the entire sum for each new window. </spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> <p> The problem requires calculating the average sleep time over all possible weeks in Polycarp's records. A naive approach would involve iterating through each possible starting index and summing up the next <b>k</b> elements. However, this results in an <b>O(n × k)</b> complexity, which is inefficient for large values of <b>n</b>.↵
Instead, we can use the <b>sliding window</b> technique to efficiently compute the sum for each week in <b>O(n)</b> time:↵
<ul> <li>First, compute the sum of the first <b>k</b> days and store it as the current sum.</li> <li>Iterate from day <b>k</b> to day <b>n</b>, updating the sum by adding the new day's sleep time and removing the sleep time of the day that is no longer in the window.</li> <li>Keep a running total of these weekly sums and compute the final average.</li> </ul>↵
Since there are <b>n − k + 1</b> weeks, the final result is the sum of all weekly sleep times divided by this count.↵
</p> </spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python ↵
n, k = map(int, input().split()) ↵
a = list(map(int, input().split()))↵
curr = sum(a[:k])↵
total = curr↵
for i in range(k, n):↵
curr += a[i] - a[i - k]↵
total += curr↵
↵
print(total / (n - k + 1))↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [C. Restoring to the Original](https://codeforces.net/gym/589822/problem/C)↵
↵
<spoiler summary = "Solution">↵
It's easy to see that letter $z$ appears only in "zero" and $n$ appears only in "one", so we should print $1$ $\text{count}(n)$ times and then $0$ $\text{count}(z)$ times.↵
</spoiler>↵
↵
↵
<spoiler summary = "Code">↵
```python ↵
n = int(input()) ↵
s = input() ↵
ones = s.count('n') ↵
zeros = s.count('z') ↵
print('1 ' * ones + '0 ' * zeros)↵
```↵
</spoiler>↵
↵
#### [D. Socialism](https://codeforces.net/gym/589822/problem/D)↵
↵
<spoiler summary="Hint"> ↵
Try to find the maximum number of people who can have at least x burles after redistributing the money among selected subsets of people. The key observation is that the redistribution must be fair among the chosen subset. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> ↵
The problem requires us to maximize the number of people who have at least `x` burles after any number of redistribution reforms. The key observation is that any subset of people chosen for redistribution will end up with an equal amount of money per person. ↵
↵
### Approach: ↵
1. **Sort the savings in descending order**: This ensures that we consider the wealthiest individuals first. ↵
2. **Iterate through the sorted list and track cumulative wealth**: We keep summing the wealth and checking if the average wealth of the first `i` people is at least `x`. ↵
3. **Break when the condition fails**: If at any step the cumulative wealth divided by `i + 1` is less than `x`, the answer is `i`. Otherwise, the answer is `n` if we can include all individuals. ↵
↵
### Example Walkthrough: ↵
1. **Case 1** (`[5,1,2,1]`, `x=3`): ↵
- Sort: `[5,2,1,1]` ↵
- Sum stepwise: `5`, `5+2=7`, `7+1=8`, `8+1=9` ↵
- The condition fails at index `2`, so the answer is `2`. ↵
↵
2. **Case 2** (`[11,9,11,9]`, `x=10`): ↵
- Sort: `[11,11,9,9]` ↵
- Sum stepwise: `11`, `22`, `31`, `40` ↵
- The condition holds for all, so the answer is `4`. ↵
↵
3. **Case 3** (`[4,3]`, `x=5`): ↵
- Sort: `[4,3]` ↵
- The sum never reaches `5`, so the answer is `0`. ↵
↵
4. **Case 4** (`[9,4,9]`, `x=7`): ↵
- Sort: `[9,9,4]` ↵
- Sum stepwise: `9`, `18`, `22` ↵
- The condition holds for `3`, so the answer is `3`. ↵
↵
### Complexity Analysis: ↵
- Sorting takes **O(n log n)**. ↵
- Iterating through the array takes **O(n)**. ↵
- Thus, the total complexity per test case is **O(n log n)**. ↵
- Since the sum of `n` across all test cases is at most `10^5`, this solution efficiently handles the constraints. ↵
</spoiler>↵
↵
<spoiler summary="Code"> ↵
```python ↵
t = int(input()) # Read number of test cases ↵
↵
for _ in range(t): ↵
n, x = map(int, input().split()) # Read n (number of people) and x (wealth threshold) ↵
nums = sorted(map(int, input().split()), reverse=True) # Sort wealth in descending order ↵
↵
total = 0 # Track cumulative wealth ↵
for i in range(n): ↵
total += nums[i] # Add wealth of the i-th person ↵
if total < x * (i + 1): # Check if the average wealth falls below x ↵
print(i) # Maximum number of wealthy people possible ↵
break ↵
else: ↵
print(n) # If we never break, all n people can be wealthy ↵
```↵
</spoiler>↵
↵
↵
↵
#### [E. TV Off](https://codeforces.net/gym/589822/problem/E)↵
↵
<spoiler summary="Solution">↵
↵
To solve this problem, we need to determine if there exists a TV segment that can be removed without reducing the total covered time. Intuitively, a segment is redundant if every moment it covers is still covered by at least one other segment. Our goal is to efficiently check for such a segment. ↵
↵
Since the given time values can be large (`≤ 10^9`), storing them directly is inefficient. Instead, we use **coordinate compression** to map time values into a smaller range (at most `6 × 10^5`). We then use a **difference array** approach: for each segment `[li, ri]`, we increment coverage at `li` and decrement at `ri + 1`. Taking prefix sums over this array gives us the number of active TV sets at each moment. From this, we compute `pref[i]`, which stores how many moments up to `i` are covered by exactly one segment. ↵
↵
Finally, for each segment `[l, r]`, we check if `pref[r] - pref[l - 1]` is `0`. This means that every moment in this range is covered by at least one other segment, making it **redundant**. If we find such a segment, we print its index; otherwise, we print `-1`. This approach runs in **O(n log n)** due to sorting and coordinate compression, making it efficient.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
↵
def solve():↵
n = int(input())↵
segments = []↵
coord_set = set()↵
↵
# Collecting segments and unique coordinates↵
for _ in range(n):↵
l, r = map(int , input().split())↵
segments.append((l, r + 1))↵
coord_set.add(l)↵
coord_set.add(r + 1)↵
↵
# Coordinate compression↵
coord_list = sorted(coord_set)↵
coord_map = {v: i for i, v in enumerate(coord_list)}↵
m = len(coord_list)↵
↵
# Prefix array to track coverage↵
coverage = [0] * (m + 1)↵
for l, r in segments:↵
coverage[coord_map[l]] += 1↵
coverage[coord_map[r]] -= 1↵
↵
# Compute prefix sums for coverage↵
for i in range(1, m):↵
coverage[i] += coverage[i - 1]↵
↵
# Compute `pref` array, which stores the count of moments covered exactly once↵
pref = [0] * m↵
for i in range(1, m):↵
pref[i] = pref[i - 1] + (1 if coverage[i - 1] == 1 else 0)↵
↵
# Find redundant segment↵
for i, (l, r) in enumerate(segments):↵
if pref[coord_map[r]] - pref[coord_map[l]] == 0:↵
print(i + 1)↵
return↵
↵
print(-1)↵
↵
solve()↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
#### [F. Covered Points Count](https://codeforces.net/gym/589822/problem/F)↵
↵
<spoiler summary="Hint1">↵
- What would you do if the constraints for the coordinates were up to \(10^5\)? ↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
- You could use the line sweep algorithm, but the coordinates go up to \(10^9\). So, what shall we do? </spoiler>↵
↵
<spoiler summary="Hint3">↵
- What if you use a dictionary instead of an array to store only the relevant positions? ↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We perform a line sweep using a dictionary to record events at positions where the number of covering segments changes. Sorting the dictionary keys lets us compute the prefix sum between these "critical" points. For each interval \([prev, cur)\), the number of integer points is \((cur — prev)\) and they are all covered by the current number of segments. This way, we aggregate the answer for every \(k\) in \([1, n]\) without iterating over every integer in a huge range.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
from collections import defaultdict↵
↵
n = int(sys.stdin.readline().strip())↵
events = defaultdict(int)↵
↵
# Record events: +1 when a segment starts, -1 when it ends (at r+1)↵
for _ in range(n):↵
l, r = map(int, sys.stdin.readline().split())↵
events[l] += 1↵
events[r + 1] -= 1↵
↵
# Sort the event points↵
keys = sorted(events.keys())↵
coverage = 0↵
prev = keys[0]↵
result = defaultdict(int)↵
↵
# Line sweep: update coverage and count points in intervals↵
for point in keys:↵
result[coverage] += point - prev↵
coverage += events[point]↵
prev = point↵
↵
# Output counts for points covered by exactly 1 to n segments↵
ans = [result[k] for k in range(1, n + 1)]↵
print(*ans)↵
↵
```↵
</spoiler>↵
↵
↵
#### [G. Evenly Spaced Letters](https://codeforces.net/gym/589822/problem/G)↵
↵
<spoiler summary = "Solution">↵
Let's consider a very special case of equal distances. What if all distances were equal to $1$? It implies that if some letter appears exactly twice, both occurrences are placed right next to each other.↵
↵
That construction can be achieved if you sort the string, for example: first right down all letters '$a$', then all letters '$b$' and so on. If a letter appears multiple times, all its occurrences will be next to each other, just as we wanted.↵
↵
Overall complexity: $O(|s|log|s|)$ or $O(|s|)$ per testcase.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
for _ in range(int(input())):↵
print(''.join(sorted(input())))↵
```↵
</spoiler>↵
↵
#### [H. Dominoes](https://codeforces.net/gym/589822/problem/H)↵
↵
<spoiler summary = "Hint-1">↵
This is a 2D prefix sum problem.↵
</spoiler>↵
↵
<spoiler summary = "Hint-2">↵
Do the 2D prefix sum for the horizontal and vertical arrangements separately.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
↵
<spoiler summary = "Definitions">↵
<p>↵
Let’s have two $h$ by $w$ 2D arrays $vertical$ and $horizontal$ to count the number of possible vertical and horizontal arrangements respectively. $vertical[i][j]$ and $horizontal[i][j]$ indicate the following:↵
↵
<ul>↵
<li>↵
$vertical[i][j]$ is the number of ways we can place a domino vertically in the rectangle whose top left corner is located at the $zeroth$ row and $zeroth$ column and whose bottom left corner is located at the $i-th$ row and at the $j-th$ column, $(0 - indexed).$↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
$horizontal[i][j]$ is the number of ways we can place a domino horizontally in the rectangle whose top left corner is located at the $zeroth$ row and $zeroth$ column and whose bottom left corner is located at the $i-th$ row and at the $j-th$ column, $(0 - indexed).$↵
</li>↵
</ul>↵
↵
</p>↵
</spoiler>↵
↵
<spoiler summary = "Constructing the 2D prefix arrays">↵
<ul>↵
<li>↵
The first column of $horizontal$ will be initialized to zero as we need at least two columns to place a domino horizontally. Then we will traverse $horizontal$ fully. For every row-column pair $r$, $c$ (0-indexed), we will set $horizontal[r][c] = 1$ if $c > 0$, $arr[r][c] == ‘.’$, and $arr[r][c - 1] == ‘.’$ are all true indicating we can place our domino from $r, c - 1$ to $r, c$ horizontally. Otherwise we set $horizontal[r][c] = 0.$ Where $arr$ is the given $h$ x $w$ rectangular grid.↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
The first row of $vertical$ will be initialized to zero as we need at least two rows to place a domino vertically. Then we will traverse $vertical$ fully. For every row-column pair $r$, $c$ (0-indexed), we will set $vertical[r][c] = 1$ if $r > 0$, $arr[r][c] == ‘.’$, and $arr[r - 1][c] == ‘.’$ are all true indicating we can place our domino from $r - 1, c$ to $r, c$ vertically. Otherwise we set $vertical[r][c] = 0.$ ↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
Finally we will do row wise prefix sum followed by column wise prefix sum or vice versa, the order doesn’t matter, for both our 2D arrays. Now we have what we indicated in the $’Definition’$ part above.↵
</li>↵
</ul>↵
</spoiler>↵
↵
<spoiler summary = "Answering the queries">↵
<p>↵
For every query $r1, c1, r2, c2$ we calculate our answer as follows: ↵
</p>↵
<p>↵
<ul>↵
↵
<li>↵
$horizontal$_$count = horizontal[r2][c2]-horizontal[r2][c1]-horizontal[r1 - 1][c2]+horizontal[r1 - 1][c1]$↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
$vertical$_$count = vertical[r2][c2]-horizontal[r2][c1 - 1]-vertical[r1][c2]+horizontal[r1][c1 - 1]$↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
Then our final will be $horizontal$_$ count + vertical$_$count.$ Note that the way we calculate the $vertical$_$count$ and the $horizontal$_$count$ are not identical. For the $horizontal$_$count$, we don’t want to count the number of horizontal arrangements before and at $c1$, because the numbers at $c1$ include the arrangements that start at $c1 - 1$ and end at $c1$. In that case such an arrangement should not be counted as the starting position of the domino is outside the given rectangle in the query. Similarly the vertical arrangements starting from $r1 - 1$ and ending ar $r1$ should also be excluded. We have to be careful when we count. And whenever we are using $r1 - 1$ and $c1 - 1$ we have to check if they are greater than or equal to $0.$↵
</li>↵
</ul>↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary = "Time and space complexities">↵
<ul>↵
<li>↵
$\text{Time Complexity: } O(h .w)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(h .w)$↵
</li>↵
</ul>↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
h, w = map(int, input().split())↵
↵
grid = []↵
for i in range(h):↵
grid.append(input())↵
↵
↵
horizontal = [[0] * w for _ in range(h)]↵
vertical = [[0] * w for _ in range(h)]↵
↵
# indicate valid arrangements by 1 and invalid arrangements by 0.↵
# horizontal[r][c] == 1 means we can place a domino horizontally from grid[r][c - 1] to grid[r][c]↵
# vertical[r][c] == 1 means we can place a domino vertically from grid[r - 1][c] to grid[r][c]↵
for r in range(h):↵
for c in range(w):↵
↵
if c > 0 and grid[r][c] == grid[r][c - 1] == '.':↵
horizontal[r][c] = 1↵
↵
if r > 0 and grid[r][c] == grid[r - 1][c] == '.':↵
vertical[r][c] = 1↵
↵
↵
# perform row-wise prefix sums↵
for r in range(h):↵
for c in range(1, w):↵
horizontal[r][c] += horizontal[r][c - 1]↵
vertical[r][c] += vertical[r][c - 1]↵
↵
# perform column-wise prefix sums↵
for c in range(w):↵
for r in range(1, h):↵
horizontal[r][c] += horizontal[r - 1][c]↵
vertical[r][c] += vertical[r - 1][c]↵
↵
↵
q = int(input())↵
↵
for i in range(q):↵
r1, c1, r2, c2 = map(int, input().split())↵
r1, c1, r2, c2 = r1 - 1, c1 - 1, r2 - 1, c2 - 1 # changing 1-indexed input to 0-indexed↵
↵
horizontal_count = horizontal[r2][c2] - horizontal[r2][c1]↵
if r1 - 1 >= 0:↵
horizontal_count += horizontal[r1 - 1][c1] - horizontal[r1 - 1][c2]↵
↵
vertical_count = vertical[r2][c2] - vertical[r1][c2]↵
if c1 - 1 >= 0:↵
vertical_count += vertical[r1][c1 - 1] - vertical[r2][c1 - 1]↵
↵
answer = horizontal_count + vertical_count↵
↵
print(answer)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [I. The Odd Challenge](https://codeforces.net/gym/589822/problem/I)↵
↵
<spoiler summary="Problem">↵
We have an array \( a \) of length \( n \) and must answer \( q \) queries. Each query modifies all elements in a given range \( [l, r] \) by setting them to \( k \) and asks whether the sum of the updated array is odd.↵
↵
Each query is independent, meaning changes do not persist for subsequent queries.↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Observe that changing a subarray to a fixed value (k) affects the total sum in a predictable way. The effect on the total sum can be computed by removing the sum of the existing subarray and adding the contribution of the new values.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How can prefix sum help us here?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
1. Compute the initial sum of the array.↵
2. Compute the prefix sum for quick range sum retrieval.↵
3. For each query:↵
- Compute the sum of the range \( [l, r] \).↵
- Replace it with \( (r — l + 1) \times k \).↵
- Check if the new sum is odd.↵
- Print "YES" if odd, else "NO".↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
t = int(input())↵
↵
for _ in range(t):↵
n, q = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
prefix = [0] * (n + 1)↵
for i in range(n):↵
prefix[i + 1] = prefix[i] + a[i]↵
↵
total_sum = prefix[-1]↵
results = []↵
for _ in range(q):↵
l, r, k = map(int, input().split())↵
replaced_range_old_sum = prefix[r] - prefix[l - 1]↵
replaced_range_new_sum = (r - l + 1) * k↵
new_sum = total_sum - replaced_range_old_sum + replaced_range_new_sum↵
↵
if new_sum % 2 == 1:↵
results.append("YES")↵
else:↵
results.append("NO")↵
↵
print("\n".join(results) + "\n")↵
```↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
- Computing the total sum: \( O(n) \)↵
- Computing the prefix sum: \( O(n) \)↵
- Each query: \( O(1) \) (using prefix sum)↵
- Total complexity: \( O(n + q) \) per test case, which is optimal given constraints.↵
</spoiler>↵
↵
