[Here](https://codeforces.me/contestInvitation/150ae2b6091bfb195b32f32e425f9c230a7795d8) is the mashup link (the problems are from Codeforces' problem set).↵
↵
#### [A. Abenezer's String Problem](https://codeforces.me/gym/499363/problem/A)↵
↵
<spoiler summary = "Solution">↵
To solve the problem we need to find the character with the highest alphabetical order in our string, since Abenezer will need at least that alphabet size and won't need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
s = input()↵
ma = 0↵
for ch in s:↵
ma = max(ma, ord(ch))↵
print(ma - 96)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [B. Ruth Wossen The Monster Killer](https://codeforces.me/gym/499363/problem/B)↵
↵
<spoiler summary = "Solution">↵
We are interested in the sum of a interval of a given sequence. This can be done by calculating the prefix sum of the sequence beforehand. That is,$sv_i = \sum_{j=1}^{i} (v_j)$ let . The sum of numbers in the interval $[l, r]$ would then be $sv_r - sv_{l - 1}$. we can sort sequence $v$ to obtain sequence $u$. We can deal with sequence $u$ likewise.↵
↵
Preprocessing takes $O(n)$ time, and answering a query is only $O(1)$. The total complexity would be $O(nlogn + q)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input()) ↵
nums = list(map(int, input().split()))↵
q = int(input()) ↵
↵
def calc_prefix(arr):↵
res = [arr[0]]↵
for i in range(1, len(arr)):↵
res.append(res[-1] + arr[i])↵
return res↵
sorted_nums = sorted(nums)↵
arr1 = calc_prefix(nums)↵
arr2 = calc_prefix(sorted(nums))↵
for _ in range(q):↵
a, l, r = map(int, input().split())↵
if a == 1:↵
print(arr1[r - 1] - arr1[l - 1] + nums[l - 1])↵
else:↵
print(arr2[r - 1] - arr2[l - 1] + sorted_nums[l - 1])↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [C. Nahom Needs Help](https://codeforces.me/gym/499363/problem/C)↵
↵
<spoiler summary = "Solution">↵
↵
<p>↵
↵
<br><br>↵
First, we need to determine how many times each operation will be performed. For instance, if our query is $1, 3$, and $2, 5$ then $2$ and $3$ will be done twice since they fall within two ranges, while the rest will be done once. To calculate this, we can use a prefix sum with range updates.↵
</p>↵
<p>↵
Next, for each operation $l, r, d, and$ $v$ (where $v$ represents the number of times it will be performed), we'll increment all elements from $l$ to $r$ inclusive by $d*v$. This can also be efficiently computed using a prefix sum with range updates.↵
</p>↵
↵
↵
↵
<p><b>prefix sum with range updates: </b>Let's think about a somewhat easier problem first. What if we were asked to add a constant value to the suffix of the array starting at index l, for multiple queries? Instead of updating the whole suffix for each query, we can only increment the first index of the suffix for each query, $i.e a[l]+=k$. Then after all queries, we take the prefix sum of the whole array. This will "propagate" our increments till the end of the array and thus our task of updating the whole suffix is accomplished at the end, after taking prefix sums. Now, what about updating the range $[l…r]$? Can you decompose this range update as $2 suffix updates? It can be decomposed as such: ↵
</p>↵
<p>↵
if you need to increment the range $[l…r]$ by $k$, you can increment the suffix starting at index $l$ by $k$ and decrement the suffix starting at index $r+1$ by $k$, i.e perform the operations $a[l]+=k$ and $a[r+1]−=k$↵
for each query and then take the prefix sum of the array as before. ↵
</p>↵
A visual summary:↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m, k = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
op = []↵
for _ in range(m):↵
op.append(list(map(int, input().split())))↵
↵
q = [0]*(m+1)↵
for _ in range(k):↵
l, r = (map(int, input().split()))↵
q[l-1] += 1↵
q[r] -= 1↵
↵
for i in range(m-1):↵
q[i+1] += q[i]↵
↵
update = [0]*(n+1)↵
for query in range(m):↵
l,r,d = op[query]↵
update[l - 1] += d*q[query]↵
update[r] -= d*q[query]↵
for i in range(n-1):↵
update[i+1] += update[i]↵
for i in range(n):↵
a[i] += update[i]↵
print(*a) ↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [D. The Keeper Game](https://codeforces.me/gym/499363/problem/D)↵
↵
<spoiler summary = "Hint"> ↵
There is always one sheep that shouldn't move.↵
</spoiler>↵
↵
<spoiler summary= "Solution">↵
<p>↵
<br>↵
Let's denote by k the number of sheep in the string, and by $x_1,x_2,…,x_k$ $(1≤x_1<x_2<…<x_k≤n)$ their positions in the string.↵
↵
Note that in the optimal solution the sheep with the number $m=⌈n/2⌉$↵
will not make moves. This can be proved by considering the optimal solution in which the sheep with the number m↵
makes at least one move. if it moves to the right all sheep that are to the left of $x_m$( $x_1,x_2,…,x_{m-1}$) will move by one to the right but not all the sheep that are on the left side of $x_m$( $x_{m+1},x{m+2},…,x_k$) will decrease their movement by one and same thing if the $m-th$ sheep move to the left. So we can conclude that this solution is not optimal. ↵
Consider sheep with numbers from i=1 to n↵
</p>↵
↵
<p>↵
Then the final position of the $i-th$ sheep will be $x_m−m+i$, and the answer will be $\sum\limits_{k = 0}^n |xi−(xm−m+i)|$, since all the sheep have to move from $x_i$ to $x_m-m+i$.↵
↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
testcases = int(input())↵
for _ in range(testcases)↵
n = int(input())↵
s = input().strip()↵
cnt = s.count('*') # total count of sheeps↵
pos = -1 # hold the position of the mth sheep↵
cur = -1 ↵
for i in range(n):↵
if s[i] == '*':↵
cur += 1↵
if cur == cnt // 2:↵
pos = i↵
↵
ans = 0↵
# pos -> xm cnt//2-> and i =-> 0↵
cur = pos - cnt // 2↵
for i in range(n):↵
if s[i] == '*':↵
ans += abs(cur - i)↵
cur += 1↵
↵
print(ans)↵
↵
↵
↵
```↵
</spoiler>↵
↵
#### [E. Is Nardos's Gift for Timket Bad?](https://codeforces.me/gym/499363/problem/E)↵
↵
<spoiler summary = "Hint 1"> ↵
<p>↵
Let the sum of elements from the beginning be $p_i$. $[l,r]$ isgoobad if the sum of all the elements between that range equals $r - l + 1$. so $[l,r]$ is goobad if $pr−pl + 1 = r−l + 1$.↵
</p>↵
</spoiler>↵
↵
<spoiler summary = "Hint 2"> ↵
Rewrite the formula $pr−pl + 1 = r−l + 1$.↵
</spoiler>↵
↵
<spoiler summary= "Solution">↵
<p>↵
Let's precalculate the array $p$, where $pi=\sum\limits_{j = 0}^{i - 1} a_j$(so $p_x$ is the sum of the first $x$ elements of $a$).↵
Then subarray $[l,r]$ isgoobad if $pr−pl + 1 = r−l + 1$, so $pr−r=pl−l$.↵
↵
Thus, we have to group all prefixes by value $pi−i$ for $i$ from $0$ to $n$. And if x indexes have a prefix with the same value of $pi−i$ then we have to add $x(x−1)/2$ to the answer.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import defaultdict↵
testcases = int(input())↵
for _ in range(testcases):↵
n = int(input())↵
a = input()↵
d = defaultdict(int)↵
d[0] = 1↵
res, s = 0, 0↵
↵
for i in range(n):↵
s += int(a[i])↵
x = s - i - 1↵
d[x] += 1↵
↵
res += d[x] - 1↵
↵
print(res)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [A. Abenezer's String Problem](https://codeforces.me/gym/499363/problem/A)↵
↵
<spoiler summary = "Solution">↵
To solve the problem we need to find the character with the highest alphabetical order in our string, since Abenezer will need at least that alphabet size and won't need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
s = input()↵
ma = 0↵
for ch in s:↵
ma = max(ma, ord(ch))↵
print(ma - 96)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [B. Ruth Wossen The Monster Killer](https://codeforces.me/gym/499363/problem/B)↵
↵
<spoiler summary = "Solution">↵
We are interested in the sum of a interval of a given sequence. This can be done by calculating the prefix sum of the sequence beforehand. That is,$sv_i = \sum_{j=1}^{i} (v_j)$ let . The sum of numbers in the interval $[l, r]$ would then be $sv_r - sv_{l - 1}$. we can sort sequence $v$ to obtain sequence $u$. We can deal with sequence $u$ likewise.↵
↵
Preprocessing takes $O(n)$ time, and answering a query is only $O(1)$. The total complexity would be $O(nlogn + q)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input()) ↵
nums = list(map(int, input().split()))↵
q = int(input()) ↵
↵
def calc_prefix(arr):↵
res = [arr[0]]↵
for i in range(1, len(arr)):↵
res.append(res[-1] + arr[i])↵
return res↵
sorted_nums = sorted(nums)↵
arr1 = calc_prefix(nums)↵
arr2 = calc_prefix(sorted(nums))↵
for _ in range(q):↵
a, l, r = map(int, input().split())↵
if a == 1:↵
print(arr1[r - 1] - arr1[l - 1] + nums[l - 1])↵
else:↵
print(arr2[r - 1] - arr2[l - 1] + sorted_nums[l - 1])↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [C. Nahom Needs Help](https://codeforces.me/gym/499363/problem/C)↵
↵
<spoiler summary = "Solution">↵
↵
<p>↵
↵
<br><br>↵
First, we need to determine how many times each operation will be performed. For instance, if our query is $1, 3$, and $2, 5$ then $2$ and $3$ will be done twice since they fall within two ranges, while the rest will be done once. To calculate this, we can use a prefix sum with range updates.↵
</p>↵
<p>↵
Next, for each operation $l, r, d, and$ $v$ (where $v$ represents the number of times it will be performed), we'll increment all elements from $l$ to $r$ inclusive by $d*v$. This can also be efficiently computed using a prefix sum with range updates.↵
</p>↵
↵
↵
↵
<p><b>prefix sum with range updates: </b>Let's think about a somewhat easier problem first. What if we were asked to add a constant value to the suffix of the array starting at index l, for multiple queries? Instead of updating the whole suffix for each query, we can only increment the first index of the suffix for each query, $i.e a[l]+=k$. Then after all queries, we take the prefix sum of the whole array. This will "propagate" our increments till the end of the array and thus our task of updating the whole suffix is accomplished at the end, after taking prefix sums. Now, what about updating the range $[l…r]$? Can you decompose this range update as $2 suffix updates? It can be decomposed as such: ↵
</p>↵
<p>↵
if you need to increment the range $[l…r]$ by $k$, you can increment the suffix starting at index $l$ by $k$ and decrement the suffix starting at index $r+1$ by $k$, i.e perform the operations $a[l]+=k$ and $a[r+1]−=k$↵
for each query and then take the prefix sum of the array as before. ↵
</p>↵
A visual summary:↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m, k = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
op = []↵
for _ in range(m):↵
op.append(list(map(int, input().split())))↵
↵
q = [0]*(m+1)↵
for _ in range(k):↵
l, r = (map(int, input().split()))↵
q[l-1] += 1↵
q[r] -= 1↵
↵
for i in range(m-1):↵
q[i+1] += q[i]↵
↵
update = [0]*(n+1)↵
for query in range(m):↵
l,r,d = op[query]↵
update[l - 1] += d*q[query]↵
update[r] -= d*q[query]↵
for i in range(n-1):↵
update[i+1] += update[i]↵
for i in range(n):↵
a[i] += update[i]↵
print(*a) ↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [D. The Keeper Game](https://codeforces.me/gym/499363/problem/D)↵
↵
<spoiler summary = "Hint"> ↵
There is always one sheep that shouldn't move.↵
</spoiler>↵
↵
<spoiler summary= "Solution">↵
<p>↵
<br>↵
Let's denote by k the number of sheep in the string, and by $x_1,x_2,…,x_k$ $(1≤x_1<x_2<…<x_k≤n)$ their positions in the string.↵
↵
Note that in the optimal solution the sheep with the number $m=⌈n/2⌉$↵
will not make moves. This can be proved by considering the optimal solution in which the sheep with the number m↵
makes at least one move. if it moves to the right all sheep that are to the left of $x_m$( $x_1,x_2,…,x_{m-1}$) will move by one to the right but not all the sheep that are on the left side of $x_m$( $x_{m+1},x{m+2},…,x_k$) will decrease their movement by one and same thing if the $m-th$ sheep move to the left. So we can conclude that this solution is not optimal. ↵
Consider sheep with numbers from i=1 to n↵
</p>↵
↵
<p>↵
Then the final position of the $i-th$ sheep will be $x_m−m+i$, and the answer will be $\sum\limits_{k = 0}^n |xi−(xm−m+i)|$, since all the sheep have to move from $x_i$ to $x_m-m+i$.↵
↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
testcases = int(input())↵
for _ in range(testcases)↵
n = int(input())↵
s = input().strip()↵
cnt = s.count('*') # total count of sheeps↵
pos = -1 # hold the position of the mth sheep↵
cur = -1 ↵
for i in range(n):↵
if s[i] == '*':↵
cur += 1↵
if cur == cnt // 2:↵
pos = i↵
↵
ans = 0↵
# pos -> xm cnt//2-> and i =-> 0↵
cur = pos - cnt // 2↵
for i in range(n):↵
if s[i] == '*':↵
ans += abs(cur - i)↵
cur += 1↵
↵
print(ans)↵
↵
↵
↵
```↵
</spoiler>↵
↵
#### [E. Is Nardos's Gift for Timket Bad?](https://codeforces.me/gym/499363/problem/E)↵
↵
<spoiler summary = "Hint 1"> ↵
<p>↵
Let the sum of elements from the beginning be $p_i$. $[l,r]$ is
</p>↵
</spoiler>↵
↵
<spoiler summary = "Hint 2"> ↵
Rewrite the formula $pr−pl + 1 = r−l + 1$.↵
</spoiler>↵
↵
<spoiler summary= "Solution">↵
<p>↵
Let's precalculate the array $p$, where $pi=\sum\limits_{j = 0}^{i - 1} a_j$(so $p_x$ is the sum of the first $x$ elements of $a$).↵
Then subarray $[l,r]$ is
↵
Thus, we have to group all prefixes by value $pi−i$ for $i$ from $0$ to $n$. And if x indexes have a prefix with the same value of $pi−i$ then we have to add $x(x−1)/2$ to the answer.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import defaultdict↵
testcases = int(input())↵
for _ in range(testcases):↵
n = int(input())↵
a = input()↵
d = defaultdict(int)↵
d[0] = 1↵
res, s = 0, 0↵
↵
for i in range(n):↵
s += int(a[i])↵
x = s - i - 1↵
d[x] += 1↵
↵
res += d[x] - 1↵
↵
print(res)↵
↵
```↵
</spoiler>↵
↵
↵
