# [A. Missing Level](https://mirror.codeforces.com/gym/673679/problem/A)↵
↵
<spoiler summary="Hint 1.1">If you had all numbers from 1 to n, what would their total sum be?</spoiler>↵
↵
<spoiler summary="Hint 1.2">Subtract the numbers Daniel already played from that total. The remaining number is the missing level.</spoiler>↵
↵
<spoiler summary="Solution">Sum of 1..n = n*(n+1)//2. Subtract the sum of given numbers → missing level. Time: O(n)</spoiler>↵
↵
<spoiler summary="Code"><pre>↵
↵
n = int(input())↵
arr = list(map(int, input().split()))↵
total = n * (n + 1) // 2↵
print(total — sum(arr))↵
↵
</pre></spoiler>↵
↵
[B. Robot’s Path](https://mirror.codeforces.com/gym/673679/problem/B)↵
↵
<spoiler summary="Hint 2.1">↵
From a free cell you can jump at most `k` cells ahead. If there is a block of consecutive obstacles, you must be able to jump over it — what is required from `k` relative to the block size?↵
</spoiler>↵
↵
<spoiler summary="Hint 2.2">↵
If a block of `#` is too long and the robot cannot jump that far, he will get stuck.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Count consecutive `#`. If any group has length ≥ k, the robot cannot pass. Otherwise, he can reach the end. ↵
Time Complexity: O(n)↵
</spoiler>↵
↵
↵
<spoiler summary="Code"><pre>↵
↵
n, k = map(int, input().split())↵
s = input().strip()↵
↵
count = 0↵
for ch in s:↵
if ch == '#':↵
count += 1↵
if count >= k:↵
print("NO")↵
break↵
else:↵
count = 0↵
else:↵
print("YES")↵
</pre>↵
</spoiler>↵
↵
---↵
↵
[C. Book Ordering](https://mirror.codeforces.com/gym/673679/problem/C)↵
↵
<spoiler summary="Hint 3.1">↵
Go from left to right. Keep track of the maximum height allowed for the current book.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3.2">↵
For each book, try the larger side if possible. If not, use the smaller side.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
- Set `prev` to a very large number. ↵
- For each book:↵
— Let `big = max(w, h)`, `small = min(w, h)`.↵
— If `big <= prev`, choose `big`. ↵
— Else if `small <= prev`, choose `small`. ↵
— Else answer is NO. ↵
- If all books work, answer is YES. ↵
Time Complexity: O(n)↵
</spoiler>↵
↵
<spoiler summary="Code"><pre>↵
↵
n = int(input())↵
prev = 10**18↵
for _ in range(n):↵
w, h = map(int, input().split())↵
big = max(w, h)↵
small = min(w, h)↵
↵
if big <= prev:↵
prev = big↵
elif small <= prev:↵
prev = small↵
else:↵
print("NO")↵
break↵
else:↵
print("YES")↵
↵
</pre>↵
↵
</spoiler>↵
↵
[D. Reducing File Sizes](https://mirror.codeforces.com/gym/673679/problem/D)↵
↵
<spoiler summary="Hint 4.1">↵
Check the total size without compression first. Then, if needed, compress files that reduce the most size.↵
</spoiler>↵
↵
<spoiler summary="Hint 4.2">↵
Sort files by how much size they reduce. Apply the biggest reductions first.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
- Let `total = sum(all original sizes)`. ↵
- If `total <= m`, answer is 0. ↵
- Else, compute how much each file reduces, sort reductions decreasing, apply them one by one until `total <= m`. ↵
- If even after compressing all files, `total > m`, print -1. ↵
Time Complexity: O(n log n)↵
</spoiler>↵
↵
↵
<spoiler summary="Code"><pre>↵
n, m = map(int, input().split())↵
total = 0↵
saves = []↵
↵
for _ in range(n):↵
a, b = map(int, input().split())↵
total += a↵
saves.append(a — b)↵
↵
if total <= m:↵
print(0)↵
else:↵
saves.sort(reverse=True)↵
count = 0↵
for s in saves:↵
total -= s↵
count += 1↵
if total <= m:↵
print(count)↵
break↵
else:↵
print(-1)↵
</pre>↵
</spoiler>↵
↵
↵
[E. Single Tower](https://mirror.codeforces.com/gym/673679/problem/E)↵
↵
<spoiler summary="Hint 5.1">↵
Sort all blocks from smallest to largest. Some may already be next to each other in a tower.↵
</spoiler>↵
↵
<spoiler summary="Hint 5.2">↵
If two consecutive numbers in sorted order are already next to each other in one tower, we don’t need to split them.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5.3">↵
Count how many consecutive pairs we can keep. The rest may need splits.↵
</spoiler>↵
↵
<spoiler summary="Hint Solution">↵
- Record each block’s tower and position. ↵
- Sort all blocks. ↵
- Count “good adjacencies”: consecutive sorted blocks in the same tower. ↵
- `splits = (total_blocks - good_adj) - number_of_towers` ↵
- `combines = splits + (number_of_towers - 1)` ↵
Time Complexity: O(N log N)↵
</spoiler>↵
↵
↵
<spoiler summary="Code"><pre>↵
↵
n = int(input())↵
↵
pos = {}↵
vals = []↵
for t in range(n):↵
data = list(map(int, input().split()))↵
k = data[0]↵
blocks = data[1:]↵
for i, v in enumerate(blocks):↵
pos[v] = (t, i)↵
vals.append(v)↵
↵
vals.sort()↵
↵
good = 0↵
for i in range(len(vals) — 1):↵
t1, p1 = pos[vals[i]]↵
t2, p2 = pos[vals[i+1]]↵
if t1 == t2 and p2 == p1 + 1:↵
good += 1↵
↵
N = len(vals)↵
segments = N — good↵
splits = segments — n↵
combines = segments — 1↵
↵
print(splits, combines)↵
</pre>↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1.1">If you had all numbers from 1 to n, what would their total sum be?</spoiler>↵
↵
<spoiler summary="Hint 1.2">Subtract the numbers Daniel already played from that total. The remaining number is the missing level.</spoiler>↵
↵
<spoiler summary="Solution">Sum of 1..n = n*(n+1)//2. Subtract the sum of given numbers → missing level. Time: O(n)</spoiler>↵
↵
<spoiler summary="Code"><pre>↵
↵
n = int(input())↵
arr = list(map(int, input().split()))↵
total = n * (n + 1) // 2↵
print(total — sum(arr))↵
↵
</pre></spoiler>↵
↵
[B. Robot’s Path](https://mirror.codeforces.com/gym/673679/problem/B)↵
↵
<spoiler summary="Hint 2.1">↵
From a free cell you can jump at most `k` cells ahead. If there is a block of consecutive obstacles, you must be able to jump over it — what is required from `k` relative to the block size?↵
</spoiler>↵
↵
<spoiler summary="Hint 2.2">↵
If a block of `#` is too long and the robot cannot jump that far, he will get stuck.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Count consecutive `#`. If any group has length ≥ k, the robot cannot pass. Otherwise, he can reach the end. ↵
Time Complexity: O(n)↵
</spoiler>↵
↵
↵
<spoiler summary="Code"><pre>↵
↵
n, k = map(int, input().split())↵
s = input().strip()↵
↵
count = 0↵
for ch in s:↵
if ch == '#':↵
count += 1↵
if count >= k:↵
print("NO")↵
break↵
else:↵
count = 0↵
else:↵
print("YES")↵
</pre>↵
</spoiler>↵
↵
---↵
↵
[C. Book Ordering](https://mirror.codeforces.com/gym/673679/problem/C)↵
↵
<spoiler summary="Hint 3.1">↵
Go from left to right. Keep track of the maximum height allowed for the current book.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3.2">↵
For each book, try the larger side if possible. If not, use the smaller side.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
- Set `prev` to a very large number. ↵
- For each book:↵
— Let `big = max(w, h)`, `small = min(w, h)`.↵
— If `big <= prev`, choose `big`. ↵
— Else if `small <= prev`, choose `small`. ↵
— Else answer is NO. ↵
- If all books work, answer is YES. ↵
Time Complexity: O(n)↵
</spoiler>↵
↵
<spoiler summary="Code"><pre>↵
↵
n = int(input())↵
prev = 10**18↵
for _ in range(n):↵
w, h = map(int, input().split())↵
big = max(w, h)↵
small = min(w, h)↵
↵
if big <= prev:↵
prev = big↵
elif small <= prev:↵
prev = small↵
else:↵
print("NO")↵
break↵
else:↵
print("YES")↵
↵
</pre>↵
↵
</spoiler>↵
↵
[D. Reducing File Sizes](https://mirror.codeforces.com/gym/673679/problem/D)↵
↵
<spoiler summary="Hint 4.1">↵
Check the total size without compression first. Then, if needed, compress files that reduce the most size.↵
</spoiler>↵
↵
<spoiler summary="Hint 4.2">↵
Sort files by how much size they reduce. Apply the biggest reductions first.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
- Let `total = sum(all original sizes)`. ↵
- If `total <= m`, answer is 0. ↵
- Else, compute how much each file reduces, sort reductions decreasing, apply them one by one until `total <= m`. ↵
- If even after compressing all files, `total > m`, print -1. ↵
Time Complexity: O(n log n)↵
</spoiler>↵
↵
↵
<spoiler summary="Code"><pre>↵
n, m = map(int, input().split())↵
total = 0↵
saves = []↵
↵
for _ in range(n):↵
a, b = map(int, input().split())↵
total += a↵
saves.append(a — b)↵
↵
if total <= m:↵
print(0)↵
else:↵
saves.sort(reverse=True)↵
count = 0↵
for s in saves:↵
total -= s↵
count += 1↵
if total <= m:↵
print(count)↵
break↵
else:↵
print(-1)↵
</pre>↵
</spoiler>↵
↵
↵
[E. Single Tower](https://mirror.codeforces.com/gym/673679/problem/E)↵
↵
<spoiler summary="Hint 5.1">↵
Sort all blocks from smallest to largest. Some may already be next to each other in a tower.↵
</spoiler>↵
↵
<spoiler summary="Hint 5.2">↵
If two consecutive numbers in sorted order are already next to each other in one tower, we don’t need to split them.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5.3">↵
Count how many consecutive pairs we can keep. The rest may need splits.↵
</spoiler>↵
↵
<spoiler summary="Hint Solution">↵
- Record each block’s tower and position. ↵
- Sort all blocks. ↵
- Count “good adjacencies”: consecutive sorted blocks in the same tower. ↵
- `splits = (total_blocks - good_adj) - number_of_towers` ↵
- `combines = splits + (number_of_towers - 1)` ↵
Time Complexity: O(N log N)↵
</spoiler>↵
↵
↵
<spoiler summary="Code"><pre>↵
↵
n = int(input())↵
↵
pos = {}↵
vals = []↵
for t in range(n):↵
data = list(map(int, input().split()))↵
k = data[0]↵
blocks = data[1:]↵
for i, v in enumerate(blocks):↵
pos[v] = (t, i)↵
vals.append(v)↵
↵
vals.sort()↵
↵
good = 0↵
for i in range(len(vals) — 1):↵
t1, p1 = pos[vals[i]]↵
t2, p2 = pos[vals[i+1]]↵
if t1 == t2 and p2 == p1 + 1:↵
good += 1↵
↵
N = len(vals)↵
segments = N — good↵
splits = segments — n↵
combines = segments — 1↵
↵
print(splits, combines)↵
</pre>↵
</spoiler>↵
↵
