[Here](https://codeforces.net/contestInvitation/4c045db28c3aa82cb82ce9e7c0beccdb1d77c0f1) is the mashup link (the problems are from Codeforces' problem set).↵
#### [A. Community Education Division](https://codeforces.net/gym/496610/problem/A)↵
↵
<spoiler summary = "Solution">↵
For this problem you just need to implement what it asks you. To be able to implement it you need to know about the "if" statement.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3 ↵
t = int(input())↵
for _ in range(t):↵
rating = int(input())↵
if rating >= 1900:↵
print("Division 1")↵
elif 1600 <= rating <= 1899:↵
print("Division 2")↵
elif 1400 <= rating <= 1599:↵
print("Division 3")↵
else:↵
print("Division 4")↵
```↵
</spoiler>↵
↵
#### [B. Encrypted Postcards](https://codeforces.net/gym/496610/problem/B)↵
↵
<spoiler summary = "Solution">↵
Note that during encryption, only characters different from $c$ are added after the character $c$. However, when the character $c$ is encrypted with different characters, another $c$ character is added to the string.↵
↵
This means that for decryption, we only need to read the characters of the string after $c$ until we find the first character equal to $c$. It signals the end of the block of characters that will be converted to the character $c$ during decryption.↵
↵
To decrypt the entire string, we decrypt the first character $s1$. Let the next occurrence of the character $s1$ be at position $pos1$. Then the next character of the original string is $s_{pos1+1}$. We apply the same algorithm to find the next paired character and so on.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
T = int(input())↵
for _ in range(T):↵
n = int(input())↵
s = input()↵
new_string = []↵
l = 0↵
r = 0↵
while r < len(s):↵
if s[l] == s[r] and l != r:↵
new_string.append(s[l])↵
r += 1↵
l = r↵
else:↵
r += 1↵
ans = "".join(new_string)↵
print(ans) ↵
```↵
</spoiler>↵
↵
#### [C. Gena](https://codeforces.net/gym/496610/problem/C)↵
↵
<spoiler summary = "Solution">↵
Let's sort AASTUs and AAiTs by skill. If AASTU with lowest skill can be matched, it is good idea to match him. It can't reduce answer size. Use AAiT with lowest skill to match.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
N = int(input())↵
aastu = sorted(map(int, input().split()))↵
↵
M = int(input())↵
aait = sorted(map(int, input().split()))↵
↵
pairs = 0↵
p1 = 0 # pointer of aastu array↵
p2 = 0 # pointer of aait array↵
↵
while p1 < N and p2 < M:↵
if abs(aastu[p1] - aait[p2]) <= 1:↵
pairs += 1↵
p1 += 1↵
p2 += 1↵
elif aastu[p1] < aait[p2]:↵
p1 += 1↵
else:↵
p2 += 1↵
↵
print(pairs)↵
```↵
</spoiler>↵
↵
#### [D. Metsehafe and Enemy Aliens](https://codeforces.net/gym/496610/problem/D)↵
↵
<spoiler summary= "Hint">↵
Note that if the second operation were free, we would need $\lceil \frac{\text{sum}}{2} \rceil$ operations to get rid of all the aliens. Indeed, when we kill one alien, we can kill a second alien for free with a second operation. But the second operation is not free. So we need to use the second operation as little as possible.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
To do this, we need to apply ultimates (second attack) on the current largest horde by number of aliens, when the combo counter reaches the size of the largest horde. And we apply the first attack on the smallest hordes. This is so because the combo counter allows us to defeat $\lceil \frac{\text{sum}}{2} \rceil$ aliens. But since we can't apply this operation on several hordes at once, we need to keep the number of hordes on which we apply these attacks of the second type as small as possible. Then we can use the greedy algorithm described above. Formally, we need to keep a sorted array and store two↵
pointers: pointer $i$ — to the smallest horde, $j$— to the largest horde. Until $i$ is equal to $j$: if after destroying all horde $i$ we can't kill horde $j$ with ultimates, we destroy horde $i$, increase pointer $i$ by $1$ and increase combo counter $x$ by $a[i]$. Otherwise, hit the horde $i$ so many times that the combo counter $x$ becomes $a[j]$. Then apply a second attack on horde $j$, reduce horde $j$'s counter by $1$, reduce $a[i]$, and nullify the combo counter. When $i$ becomes equal to $j$, you just need to apply the first attack the right number of times to finish with ultimates (or not if $a[i] =1$).↵
↵
Total complexity $O(nlogn)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from math import ceil↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
nums = sorted(map(int, input().split()))↵
ans = 0↵
cur = 0↵
left = 0↵
right = n - 1↵
while left < right:↵
cur += nums[left]↵
if cur >= nums[right]:↵
ans += nums[right] + 1↵
cur -= nums[right]↵
right -= 1↵
left += 1↵
if left == right:↵
cur += nums[right]↵
ans += (ceil(cur / 2) + 1) if cur > 1 else cur↵
print(ans)↵
```↵
</spoiler>↵
↵
#### [E. m-Lucky Numbers](https://codeforces.net/gym/496610/problem/E)↵
↵
<spoiler summary = "Hint 1">↵
<p>↵
Calculate the minimum segment size so that a number can be found in all such segments. Do this for every number.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
<p>↵
For two segment sizes $a$ and $b$ where $a < b$. If $u$ is the minimum number found in all segments with size $a$, and $v$ is the minimum number found in all segments with size $b$, then $v <= u$.↵
</p>↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
<p>↵
Let's fix some arbitrary number $x$ and calculate the minimum value of $k$ such that $x$ occurs in all segments of length $k$. Let $p_{1}<p_{2}<⋯<p_{m}$ be the indices of entries of $x$ in the array. Then, for each $1≤i<m$ it is clear that $k$ should be at least the value of $p_{i+1}−p_{i}$. Also, $k≥p_{1}$ and $k≥n−p_{m}+1$. The maximum of these values is the minimum segment size $k$ where $x$ can possibly be the minimum value in. We do this for every number, and then take the minimum of those numbers for a segment size. ↵
<br/>↵
<br/>↵
Finally for a segment size $a > 1$, we take the minimum of the value already there or the minimum value we had for the previous size $a - 1$.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import defaultdict↵
↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
↵
last_indx = defaultdict(lambda :-1) # stores the last occurence of a given number↵
max_dist = defaultdict(int) # stores maximum distance between instances of a given number↵
ans = [float('inf')]*n↵
↵
# calculate the minimum size segment so that a number can be found in all such segments↵
# and take the minimum of those numbers for the segment size↵
for indx, num in enumerate(a):↵
prev = last_indx[num]↵
max_dist[num] = max(max_dist[num], indx - prev)↵
↵
min_segment_covered = max(max_dist[num], n - indx) - 1↵
ans[min_segment_covered] = min(ans[min_segment_covered], num)↵
last_indx[num] = indx↵
↵
# minimum number propagation to larger segment sizes↵
for indx in range(1, n):↵
ans[indx] = min(ans[indx], ans[indx - 1])↵
↵
# replace the inf's by -1↵
for indx in range(n):↵
if ans[indx] == float('inf'):↵
ans[indx] = -1↵
↵
print(*ans)↵
↵
```↵
</spoiler>↵
↵
#### [A. Community Education Division](https://codeforces.net/gym/496610/problem/A)↵
↵
<spoiler summary = "Solution">↵
For this problem you just need to implement what it asks you. To be able to implement it you need to know about the "if" statement.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3 ↵
t = int(input())↵
for _ in range(t):↵
rating = int(input())↵
if rating >= 1900:↵
print("Division 1")↵
elif 1600 <= rating <= 1899:↵
print("Division 2")↵
elif 1400 <= rating <= 1599:↵
print("Division 3")↵
else:↵
print("Division 4")↵
```↵
</spoiler>↵
↵
#### [B. Encrypted Postcards](https://codeforces.net/gym/496610/problem/B)↵
↵
<spoiler summary = "Solution">↵
Note that during encryption, only characters different from $c$ are added after the character $c$. However, when the character $c$ is encrypted with different characters, another $c$ character is added to the string.↵
↵
This means that for decryption, we only need to read the characters of the string after $c$ until we find the first character equal to $c$. It signals the end of the block of characters that will be converted to the character $c$ during decryption.↵
↵
To decrypt the entire string, we decrypt the first character $s1$. Let the next occurrence of the character $s1$ be at position $pos1$. Then the next character of the original string is $s_{pos1+1}$. We apply the same algorithm to find the next paired character and so on.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
T = int(input())↵
for _ in range(T):↵
n = int(input())↵
s = input()↵
new_string = []↵
l = 0↵
r = 0↵
while r < len(s):↵
if s[l] == s[r] and l != r:↵
new_string.append(s[l])↵
r += 1↵
l = r↵
else:↵
r += 1↵
ans = "".join(new_string)↵
print(ans) ↵
```↵
</spoiler>↵
↵
#### [C. Gena](https://codeforces.net/gym/496610/problem/C)↵
↵
<spoiler summary = "Solution">↵
Let's sort AASTUs and AAiTs by skill. If AASTU with lowest skill can be matched, it is good idea to match him. It can't reduce answer size. Use AAiT with lowest skill to match.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
N = int(input())↵
aastu = sorted(map(int, input().split()))↵
↵
M = int(input())↵
aait = sorted(map(int, input().split()))↵
↵
pairs = 0↵
p1 = 0 # pointer of aastu array↵
p2 = 0 # pointer of aait array↵
↵
while p1 < N and p2 < M:↵
if abs(aastu[p1] - aait[p2]) <= 1:↵
pairs += 1↵
p1 += 1↵
p2 += 1↵
elif aastu[p1] < aait[p2]:↵
p1 += 1↵
else:↵
p2 += 1↵
↵
print(pairs)↵
```↵
</spoiler>↵
↵
#### [D. Metsehafe and Enemy Aliens](https://codeforces.net/gym/496610/problem/D)↵
↵
<spoiler summary= "Hint">↵
Note that if the second operation were free, we would need $\lceil \frac{\text{sum}}{2} \rceil$ operations to get rid of all the aliens. Indeed, when we kill one alien, we can kill a second alien for free with a second operation. But the second operation is not free. So we need to use the second operation as little as possible.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
To do this, we need to apply ultimates (second attack) on the current largest horde by number of aliens, when the combo counter reaches the size of the largest horde. And we apply the first attack on the smallest hordes. This is so because the combo counter allows us to defeat $\lceil \frac{\text{sum}}{2} \rceil$ aliens. But since we can't apply this operation on several hordes at once, we need to keep the number of hordes on which we apply these attacks of the second type as small as possible. Then we can use the greedy algorithm described above. Formally, we need to keep a sorted array and store two↵
pointers: pointer $i$ — to the smallest horde, $j$— to the largest horde. Until $i$ is equal to $j$: if after destroying all horde $i$ we can't kill horde $j$ with ultimates, we destroy horde $i$, increase pointer $i$ by $1$ and increase combo counter $x$ by $a[i]$. Otherwise, hit the horde $i$ so many times that the combo counter $x$ becomes $a[j]$. Then apply a second attack on horde $j$, reduce horde $j$'s counter by $1$, reduce $a[i]$, and nullify the combo counter. When $i$ becomes equal to $j$, you just need to apply the first attack the right number of times to finish with ultimates (or not if $a[i] =1$).↵
↵
Total complexity $O(nlogn)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from math import ceil↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
nums = sorted(map(int, input().split()))↵
ans = 0↵
cur = 0↵
left = 0↵
right = n - 1↵
while left < right:↵
cur += nums[left]↵
if cur >= nums[right]:↵
ans += nums[right] + 1↵
cur -= nums[right]↵
right -= 1↵
left += 1↵
if left == right:↵
cur += nums[right]↵
ans += (ceil(cur / 2) + 1) if cur > 1 else cur↵
print(ans)↵
```↵
</spoiler>↵
↵
#### [E. m-Lucky Numbers](https://codeforces.net/gym/496610/problem/E)↵
↵
<spoiler summary = "Hint 1">↵
<p>↵
Calculate the minimum segment size so that a number can be found in all such segments. Do this for every number.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
<p>↵
For two segment sizes $a$ and $b$ where $a < b$. If $u$ is the minimum number found in all segments with size $a$, and $v$ is the minimum number found in all segments with size $b$, then $v <= u$.↵
</p>↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
<p>↵
Let's fix some arbitrary number $x$ and calculate the minimum value of $k$ such that $x$ occurs in all segments of length $k$. Let $p_{1}<p_{2}<⋯<p_{m}$ be the indices of entries of $x$ in the array. Then, for each $1≤i<m$ it is clear that $k$ should be at least the value of $p_{i+1}−p_{i}$. Also, $k≥p_{1}$ and $k≥n−p_{m}+1$. The maximum of these values is the minimum segment size $k$ where $x$ can possibly be the minimum value in. We do this for every number, and then take the minimum of those numbers for a segment size. ↵
<br/>↵
<br/>↵
Finally for a segment size $a > 1$, we take the minimum of the value already there or the minimum value we had for the previous size $a - 1$.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import defaultdict↵
↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
↵
last_indx = defaultdict(lambda :-1) # stores the last occurence of a given number↵
max_dist = defaultdict(int) # stores maximum distance between instances of a given number↵
ans = [float('inf')]*n↵
↵
# calculate the minimum size segment so that a number can be found in all such segments↵
# and take the minimum of those numbers for the segment size↵
for indx, num in enumerate(a):↵
prev = last_indx[num]↵
max_dist[num] = max(max_dist[num], indx - prev)↵
↵
min_segment_covered = max(max_dist[num], n - indx) - 1↵
ans[min_segment_covered] = min(ans[min_segment_covered], num)↵
last_indx[num] = indx↵
↵
# minimum number propagation to larger segment sizes↵
for indx in range(1, n):↵
ans[indx] = min(ans[indx], ans[indx - 1])↵
↵
# replace the inf's by -1↵
for indx in range(n):↵
if ans[indx] == float('inf'):↵
ans[indx] = -1↵
↵
print(*ans)↵
↵
```↵
</spoiler>↵
↵
