Here is the mashup link (the problems are from Codeforces' problem set).
A. Community Education Division
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.
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")
B. Encrypted Postcards
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.
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)
C. Gena
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.
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)
D. Metsehafe and Enemy Aliens
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.
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)$$$.
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)
E. m-Lucky Numbers
Calculate the minimum segment size so that a number can be found in all such segments. Do this for every number.
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$$$.
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.
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$$$.
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)
Auto comment: topic has been updated by A2SV_Group5 (previous revision, new revision, compare).
Why showing "You do not have view access to non-public contest"?