[Here](https://codeforces.me/contests/599383) is the contest link.↵
↵
↵
#### [A. The Mad King's Calls](https://codeforces.me/gym/599383/problem/A)↵
↵
<spoiler summary="Hint 1">↵
The numbers we consider are "boring" numbers, meaning they consist of the same digit (e.g., \(1, 11, 111, 1111, \dots\)).↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Instead of checking every number, note that numbers are called in order: all 1s first, then all 2s, and so on.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
To find the total keypresses, we count:↵
- **All previous digits' keypresses** (full sequences for numbers before \(x\)).↵
- **The keypresses needed for numbers up to \(x\)** using a simple sum formula.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Each "boring" number is called in a structured order: all numbers made of 1s first, then 2s, then 3s, and so on. Instead of iterating through every number, we can break the total keypresses into two parts:↵
1. **Counting keypresses for previous digits:**↵
— Before reaching \(x\), all numbers made of smaller digits (e.g., \(1, 11, 111, 1111\) if \(x\) is in the 2s) are fully called.↵
— Each digit contributes \(10\) keypresses for its full sequence. Thus, for a digit \(d\), the total keypresses before it is:↵
\[↵
10 *(d-1)↵
\]↵
2. **Counting keypresses for numbers leading up to \(x\):**↵
— If \(x\) has \(n\) digits (e.g., \(x = 222\) has \(n = 3\)), we count keypresses for forming each prefix:↵
\[↵
1 + 2 + ... + n↵
\]↵
— This is directly computed using a simple loop summing \(1\) to \(n\).↵
By combining these two values, we get the total keypress count in \(O(1)\) time.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
t = int(input())↵
for _ in range(t):↵
x = int(input())↵
val = x % 10 # Get the digit (since x consists of the same digit)↵
ans = 10 * (val - 1) # Count keypresses for previous digits↵
sz = len(str(x)) # Get the number of digits in x↵
ans += sum(range(1, sz + 1)) # Add keypresses for the current digit↵
print(ans)↵
```↵
</spoiler>↵
↵
#### [B. The Lord of Medianfell](https://codeforces.me/gym/599383/problem/B)↵
↵
<spoiler summary = "Approach 1">↵
↵
<spoiler summary="Hint"> ↵
Try maximizing the **median** by allocating as much sum as possible to the **right half** of the sorted array. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution">↵
↵
**Observations**↵
<ul>↵
<li>↵
The median is the <code>(⌊n/2⌋ + 1)</code>-th element in a sorted array. To maximize the median, we should minimize the left half (make elements before the median as small as possible, ideally zero).This leaves us with `m = ⌊n/2⌋ + 1` elements to distribute the sum among.↵
</li>↵
</ul>↵
↵
**Optimal Strategy**↵
<ul>↵
<li>↵
Distribute the sum `s` evenly among these `m` elements and any leftover `(s % m)` can be added to the last element, but this does not affect the median, since all m elements remain equal or greater. Thus, the maximum possible value for the median is going to be `⌊s / m⌋`, as this is the highest uniform value we can assign to each of these m elements.↵
</li>↵
</ul>↵
↵
**Time Complexity:**↵
Since we only perform basic arithmetic, the time complexity is `O(1)` per test case.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python ↵
t = int(input()) ↵
for _ in range(t): ↵
n, s = [int(i) for i in input().split()]↵
m = n // 2 + 1 ↵
print(s // m) ↵
``` ↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Approach 2">↵
↵
<spoiler summary="Hint"> ↵
If it's possible to set the median to **M**, can we say it's also possible to set it to **M — 1**?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
**Observations**↵
↵
<ul>↵
<li>↵
The median is the <code>⌊n/2⌋ + 1</code>-th element in a sorted array. To maximize it, we should ensure that this element and all elements to its right are as large as possible. To achieve this, we distribute the sum <code>s</code> among the rightmost <code>m = ⌊n/2⌋ + 1</code> elements. The largest possible median is the highest uniform value we can assign to these <code>m</code> elements.↵
</li>↵
↵
<li>↵
The highest uniform value we can assign to these <code>m</code> elements is <code>M</code>, which must satisfy <code>m * M ≤ s</code>.↵
</li>↵
↵
<li>↵
If we reduce <code>M</code> to <code>M−1</code>, the total required sum decreases <code>(m × (M − 1) ≤ m × M)</code>, which still satisfies the sum constraint. This monotonic property means that if <code>M</code> is possible, all values <code><= M</code> are also possible allowing us to use binary search over the median value.↵
</li>↵
</ul>↵
**Time Complexity:**↵
The binary search runs in `O(log s)`, and each check runs in `O(1)`, leading to an overall complexity of `O(log s)` per test case.↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Code">↵
```python↵
t = int(input()) ↵
for _ in range(t):↵
n, s = [int(i) for i in input().split()]↵
left, right = 0, s + 1↵
while left <= right:↵
M = (left + right) // 2 ↵
m = n // 2 + 1 ↵
↵
if m * M <= s:↵
left = M + 1↵
answer = M↵
↵
else:↵
right = M - 1 ↵
↵
print(answer) ↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
↵
#### [C. Arya Meets the Night King](https://codeforces.me/gym/599383/problem/C)↵
↵
<spoiler summary="Hint"> ↵
Sort the bases by their defensive power and maintain a running sum of gold. For each spaceship, find the maximum number of bases it can attack efficiently. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> ↵
The problem requires us to determine how much gold each spaceship can steal based on its attacking power. ↵
↵
### Approach: ↵
↵
1. **Sort the Bases by Defensive Power** ↵
- This allows us to efficiently find all bases a spaceship can attack using a two-pointer technique. ↵
- Keep track of the cumulative gold collected as we iterate through the bases. ↵
↵
2. **Sort the Spaceships and Process Them in Order** ↵
- Sorting spaceships ensures that we process weaker spaceships first, maintaining efficiency in tracking available bases. ↵
- Maintain the original indices of spaceships so that we can return the results in the correct order. ↵
↵
3. **Use Two-Pointer Technique** ↵
- Iterate through the sorted spaceships, and for each spaceship, move a pointer (`l`) to include all bases it can attack. ↵
- Keep a running sum of gold to quickly determine the total amount available. ↵
↵
4. **Store Results and Print in Original Order** ↵
- Since we modified the order of spaceships during sorting, we store results in an array indexed by their original positions. ↵
↵
### Example Walkthrough: ↵
↵
#### **Input:** ↵
```↵
5 4 ↵
1 3 5 2 4 ↵
0 1 ↵
4 2 ↵
2 8 ↵
9 4 ↵
```↵
↵
#### **Processing:** ↵
- Sort bases: `[(0,1), (2,8), (4,2), (9,4)]`↵
- Sort spaceships with indices: `[(1,0), (2,3), (3,1), (4,4), (5,2)]`↵
- Maintain a cumulative gold sum:↵
- Spaceship (1): Can attack base `(0,1)`, steals `1`.↵
- Spaceship (2): Can attack bases `(0,1), (2,8)`, steals `9`.↵
- Spaceship (3): Can attack bases `(0,1), (2,8)`, steals `9`.↵
- Spaceship (4): Can attack bases `(0,1), (2,8), (4,2)`, steals `11`.↵
- Spaceship (5): Can attack bases `(0,1), (2,8), (4,2)`, steals `11`.↵
↵
#### **Output:** ↵
```↵
1 9 11 9 11 ↵
```↵
↵
### Complexity Analysis: ↵
- Sorting bases: **O(b log b)** ↵
- Sorting spaceships: **O(s log s)** ↵
- Two-pointer traversal: **O(s + b)** ↵
- Overall complexity: **O((s + b) log(s + b))** ↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python↵
def solve():↵
# Read input values: number of spaceships (s) and number of bases (b)↵
s, b = map(int, input().split())↵
↵
# Read the attacking power of each spaceship↵
ships = list(map(int, input().split()))↵
↵
# Read the defensive power and gold of each base↵
bases = [list(map(int, input().split())) for _ in range(b)]↵
↵
# Step 1: Sort bases by defensive power to process them efficiently↵
bases.sort()↵
↵
# Step 2: Sort spaceships by attacking power while keeping track of original indices↵
ships = sorted((ships[i], i) for i in range(s))↵
↵
# Array to store the maximum gold each spaceship can steal↵
ans = [0] * s↵
↵
# Two-pointer approach to efficiently determine how much gold each spaceship can steal↵
l, max_gold = 0, 0↵
↵
# Step 3: Process each spaceship in increasing order of attacking power↵
for i in range(s):↵
# Move the pointer 'l' to include all bases that the spaceship can attack↵
while l < b and bases[l][0] <= ships[i][0]:↵
max_gold += bases[l][1] # Add the gold from the base↵
l += 1 # Move to the next base↵
↵
# Store the total gold that this spaceship can steal↵
ans[ships[i][1]] = max_gold # Store result at original index↵
↵
# Step 4: Print the results in the original order of spaceships↵
print(*ans)↵
↵
if __name__ == "__main__":↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. The Road to King's Landing](https://codeforces.me/gym/599383/problem/D)↵
↵
<spoiler summary="Hint 1">↵
Consider that the player's position after each move must lie within the intersection of the reachable area from the previous position (given \( k \)) and the current segment's bounds.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Use binary search to efficiently determine the minimal \( k \). For each candidate \( k \), simulate the player's movement through all segments to check feasibility.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
1. **Binary Search Setup**: The minimal \( k \) lies between 0 and a sufficiently large upper bound.↵
2. **Feasibility Check**: For each candidate \( k \):↵
- Start at position 0.↵
- For each segment, compute the reachable interval after moving at most \( k \) units from the previous position.↵
- Intersect this interval with the current segment's bounds.↵
- If the intersection is empty, \( k \) is too small.↵
3. **Binary Search Adjustment**: Adjust the search range based on feasibility results to find the minimal \( k \).↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
import sys↵
def can_complete_level(n, segments, k):↵
L, R = 0, 0 # The range of reachable positions↵
for l, r in segments:↵
# Compute the new reachable range↵
L = max(l, L — k)↵
R = min(r, R + k)↵
if L > R: # If no valid landing position exists↵
return False↵
return True↵
def find_min_k(n, segments):↵
left, right = 0, 10**9 # Binary search for k↵
while left <= right:↵
mid = (left + right) // 2↵
if can_complete_level(n, segments, mid):↵
right = mid — 1↵
else:↵
left = mid + 1↵
return left↵
def main():↵
t = int(input())↵
results = []↵
for _ in range(t):↵
n = int(input())↵
segments = []↵
for _ in range(n):↵
l, r = map(int, inpit().split())↵
segments.append((l, r))↵
results.append(str(find_min_k(n, segments)))↵
sys.stdout.write(" ".join(results) + "\n")↵
if __name__ == "__main__":↵
main()↵
</spoiler>↵
↵
↵
<spoiler summary="Complexity Analysis">↵
- **Binary Search**: The search runs in \( O(\log(\text{max\_distance})) \) iterations, where \(\text{max\_distance}\) is the upper bound (\( 10^9 \)).↵
- **Feasibility Check**: Each check processes \( n \) segments in \( O(n) \) time.↵
- **Total Complexity**: \( O(t \cdot n \cdot \log(10^9)) \), which is efficient given the constraints (sum of \( n \) across test cases is \( 2 \cdot 10^5 \)).↵
</spoiler>↵
↵
↵
#### [E. The Long Road to Winterfell](https://codeforces.me/gym/599383/problem/E)↵
↵
<spoiler summary="Hint 1">↵
Consider selecting Farmer John's room first and then placing the cows in the nearest available unoccupied rooms.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If the farthest distance is \( x \), can you calculate the maximum number of cows that can be placed?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try using prefix sum to efficiently calculate how many cows can be placed within a given range.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
This problem might have another solution where we can calculate the answer directly.↵
But for a moment, let's think about whether this can be solved without binary search.↵
↵
The first thing we do when solving output binary search problems is check:↵
Can we easily verify if a given answer is valid or not?↵
If someone told us the answer in advance, could we efficiently check its validity?↵
If so, we can use binary search to guess the answer.↵
For this to work, the function must be monotonic (i.e., if a certain \( x \) is possible, all larger values are also possible).↵
Since this function is monotonic, we can use binary search to efficiently find the minimum \( x \) that satisfies the conditions.↵
↵
The binary search must start with \( l = 0 \) and \( r = n \), as this ensures we explore the full possible range of distances.↵
To check feasibility for a given distance \( d \), we calculate how many available rooms exist↵
in the range \( left, right \), where:↵
- \( left = max(0, i — d) \)↵
- \( right = min(n, i + d + 1) \)↵
↵
We use the prefix sum array to efficiently compute the number of unoccupied rooms within this range.↵
↵
#### Complexity Analysis↵
- **Binary Search**: The search runs in \( O(\log n) \) iterations since we are halving the search space each time.↵
- **Feasibility Check**: Each check processes \( n \) rooms in \( O(n) \) time.↵
- **Prefix Sum Computation**: Constructing the prefix sum array takes \( O(n) \) time.↵
- **Total Complexity**: The overall complexity is \( O(n log n) \), which is efficient given the constraints.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```python↵
import sys↵
↵
def solve():↵
n, k = map(int, sys.stdin.readline().strip().split())↵
s = sys.stdin.readline().strip()↵
prefix = [0]↵
↵
# Compute prefix sum for counting free rooms quickly↵
for val in s:↵
prefix.append(prefix[-1] + (1 if val == '0' else 0))↵
↵
def max_cows_in_range(d):↵
"""Given max distance d, calculate the maximum number of cows that can be placed"""↵
max_cows = 0↵
for i in range(n):↵
if s[i] == '0': # Consider only unoccupied rooms↵
left = max(0, i - d)↵
right = min(n, i + d + 1)↵
max_cows = max(max_cows, prefix[right] - prefix[left])↵
return max_cows↵
↵
# Binary search for the minimum possible maximum distance↵
l, r = 0, n↵
while l < r:↵
mid = (l + r) // 2↵
if max_cows_in_range(mid) >= k + 1:↵
r = mid # Try a smaller maximum distance↵
else:↵
l = mid + 1↵
↵
print(l)↵
↵
if __name__ == "__main__":↵
solve()↵
```↵
</spoiler>↵
↵
↵
#### [F. The Iron Throne's Multiplication](https://codeforces.me/gym/599383/problem/F)↵
↵
↵
<spoiler summary="Hint 1"> ↵
The problem asks for the k-th largest number in the multiplication table. However, listing all numbers and sorting them in descending order is too slow. Instead, think about how to find the k-th smallest number first—since the k-th largest in a sorted list is the same as the (n*m — k + 1)-th smallest. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Hint 2"> ↵
To efficiently find the k-th smallest number without generating all elements, use binary search on possible values (from 1 to n*m). For a given mid-value, count how many numbers in the table are ≤ mid by checking each row. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> ↵
The problem requires finding the k-th smallest number in an n × m multiplication table where each cell (i, j) contains i * j. Since generating and sorting all n * m elements is too slow for large n and m, we use binary search on the possible values (from 1 to n * m). ↵
↵
For a given mid-value during binary search, we count how many numbers in the table are ≤ mid by iterating through each row i and calculating min(mid // i, m). This gives the count of valid numbers in that row. ↵
↵
If the total count is less than k, the k-th smallest number must be larger than mid, so we adjust the search to higher values. ↵
↵
If the count is ≥ k, the k-th smallest number could be mid or smaller, so we search lower values. ↵
↵
The binary search efficiently narrows down the correct value in O(n log(n * m)) time, making it suitable for large constraints. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python↵
def solve():↵
n, m, k = map(int, input().split())↵
↵
def find(mid):↵
count = 0↵
for i in range(1, n + 1):↵
add = min(mid // i, m)↵
if add == 0:↵
break↵
count += add↵
return count < k↵
↵
low, high = 1, n * m↵
answer = 0↵
↵
while low <= high:↵
mid = (low + high) // 2↵
if find(mid):↵
low = mid + 1↵
else:↵
answer = mid↵
high = mid - 1↵
↵
print(answer)↵
↵
t = 1↵
for _ in range(t):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [A. The Mad King's Calls](https://codeforces.me/gym/599383/problem/A)↵
↵
<spoiler summary="Hint 1">↵
The numbers we consider are "boring" numbers, meaning they consist of the same digit (e.g., \(1, 11, 111, 1111, \dots\)).↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Instead of checking every number, note that numbers are called in order: all 1s first, then all 2s, and so on.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
To find the total keypresses, we count:↵
- **All previous digits' keypresses** (full sequences for numbers before \(x\)).↵
- **The keypresses needed for numbers up to \(x\)** using a simple sum formula.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Each "boring" number is called in a structured order: all numbers made of 1s first, then 2s, then 3s, and so on. Instead of iterating through every number, we can break the total keypresses into two parts:↵
1. **Counting keypresses for previous digits:**↵
— Before reaching \(x\), all numbers made of smaller digits (e.g., \(1, 11, 111, 1111\) if \(x\) is in the 2s) are fully called.↵
— Each digit contributes \(10\) keypresses for its full sequence. Thus, for a digit \(d\), the total keypresses before it is:↵
\[↵
10 *(d-1)↵
\]↵
2. **Counting keypresses for numbers leading up to \(x\):**↵
— If \(x\) has \(n\) digits (e.g., \(x = 222\) has \(n = 3\)), we count keypresses for forming each prefix:↵
\[↵
1 + 2 + ... + n↵
\]↵
— This is directly computed using a simple loop summing \(1\) to \(n\).↵
By combining these two values, we get the total keypress count in \(O(1)\) time.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
t = int(input())↵
for _ in range(t):↵
x = int(input())↵
val = x % 10 # Get the digit (since x consists of the same digit)↵
ans = 10 * (val - 1) # Count keypresses for previous digits↵
sz = len(str(x)) # Get the number of digits in x↵
ans += sum(range(1, sz + 1)) # Add keypresses for the current digit↵
print(ans)↵
```↵
</spoiler>↵
↵
#### [B. The Lord of Medianfell](https://codeforces.me/gym/599383/problem/B)↵
↵
<spoiler summary = "Approach 1">↵
↵
<spoiler summary="Hint"> ↵
Try maximizing the **median** by allocating as much sum as possible to the **right half** of the sorted array. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution">↵
↵
**Observations**↵
<ul>↵
<li>↵
The median is the <code>(⌊n/2⌋ + 1)</code>-th element in a sorted array. To maximize the median, we should minimize the left half (make elements before the median as small as possible, ideally zero).This leaves us with `m = ⌊n/2⌋ + 1` elements to distribute the sum among.↵
</li>↵
</ul>↵
↵
**Optimal Strategy**↵
<ul>↵
<li>↵
Distribute the sum `s` evenly among these `m` elements and any leftover `(s % m)` can be added to the last element, but this does not affect the median, since all m elements remain equal or greater. Thus, the maximum possible value for the median is going to be `⌊s / m⌋`, as this is the highest uniform value we can assign to each of these m elements.↵
</li>↵
</ul>↵
↵
**Time Complexity:**↵
Since we only perform basic arithmetic, the time complexity is `O(1)` per test case.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python ↵
t = int(input()) ↵
for _ in range(t): ↵
n, s = [int(i) for i in input().split()]↵
m = n // 2 + 1 ↵
print(s // m) ↵
``` ↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Approach 2">↵
↵
<spoiler summary="Hint"> ↵
If it's possible to set the median to **M**, can we say it's also possible to set it to **M — 1**?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
**Observations**↵
↵
<ul>↵
<li>↵
The median is the <code>⌊n/2⌋ + 1</code>-th element in a sorted array. To maximize it, we should ensure that this element and all elements to its right are as large as possible. To achieve this, we distribute the sum <code>s</code> among the rightmost <code>m = ⌊n/2⌋ + 1</code> elements. The largest possible median is the highest uniform value we can assign to these <code>m</code> elements.↵
</li>↵
↵
<li>↵
The highest uniform value we can assign to these <code>m</code> elements is <code>M</code>, which must satisfy <code>m * M ≤ s</code>.↵
</li>↵
↵
<li>↵
If we reduce <code>M</code> to <code>M−1</code>, the total required sum decreases <code>(m × (M − 1) ≤ m × M)</code>, which still satisfies the sum constraint. This monotonic property means that if <code>M</code> is possible, all values <code><= M</code> are also possible allowing us to use binary search over the median value.↵
</li>↵
</ul>↵
**Time Complexity:**↵
The binary search runs in `O(log s)`, and each check runs in `O(1)`, leading to an overall complexity of `O(log s)` per test case.↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Code">↵
```python↵
t = int(input()) ↵
for _ in range(t):↵
n, s = [int(i) for i in input().split()]↵
left, right = 0, s + 1↵
while left <= right:↵
M = (left + right) // 2 ↵
m = n // 2 + 1 ↵
↵
if m * M <= s:↵
left = M + 1↵
answer = M↵
↵
else:↵
right = M - 1 ↵
↵
print(answer) ↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
↵
#### [C. Arya Meets the Night King](https://codeforces.me/gym/599383/problem/C)↵
↵
<spoiler summary="Hint"> ↵
Sort the bases by their defensive power and maintain a running sum of gold. For each spaceship, find the maximum number of bases it can attack efficiently. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> ↵
The problem requires us to determine how much gold each spaceship can steal based on its attacking power. ↵
↵
### Approach: ↵
↵
1. **Sort the Bases by Defensive Power** ↵
- This allows us to efficiently find all bases a spaceship can attack using a two-pointer technique. ↵
- Keep track of the cumulative gold collected as we iterate through the bases. ↵
↵
2. **Sort the Spaceships and Process Them in Order** ↵
- Sorting spaceships ensures that we process weaker spaceships first, maintaining efficiency in tracking available bases. ↵
- Maintain the original indices of spaceships so that we can return the results in the correct order. ↵
↵
3. **Use Two-Pointer Technique** ↵
- Iterate through the sorted spaceships, and for each spaceship, move a pointer (`l`) to include all bases it can attack. ↵
- Keep a running sum of gold to quickly determine the total amount available. ↵
↵
4. **Store Results and Print in Original Order** ↵
- Since we modified the order of spaceships during sorting, we store results in an array indexed by their original positions. ↵
↵
### Example Walkthrough: ↵
↵
#### **Input:** ↵
```↵
5 4 ↵
1 3 5 2 4 ↵
0 1 ↵
4 2 ↵
2 8 ↵
9 4 ↵
```↵
↵
#### **Processing:** ↵
- Sort bases: `[(0,1), (2,8), (4,2), (9,4)]`↵
- Sort spaceships with indices: `[(1,0), (2,3), (3,1), (4,4), (5,2)]`↵
- Maintain a cumulative gold sum:↵
- Spaceship (1): Can attack base `(0,1)`, steals `1`.↵
- Spaceship (2): Can attack bases `(0,1), (2,8)`, steals `9`.↵
- Spaceship (3): Can attack bases `(0,1), (2,8)`, steals `9`.↵
- Spaceship (4): Can attack bases `(0,1), (2,8), (4,2)`, steals `11`.↵
- Spaceship (5): Can attack bases `(0,1), (2,8), (4,2)`, steals `11`.↵
↵
#### **Output:** ↵
```↵
1 9 11 9 11 ↵
```↵
↵
### Complexity Analysis: ↵
- Sorting bases: **O(b log b)** ↵
- Sorting spaceships: **O(s log s)** ↵
- Two-pointer traversal: **O(s + b)** ↵
- Overall complexity: **O((s + b) log(s + b))** ↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python↵
def solve():↵
# Read input values: number of spaceships (s) and number of bases (b)↵
s, b = map(int, input().split())↵
↵
# Read the attacking power of each spaceship↵
ships = list(map(int, input().split()))↵
↵
# Read the defensive power and gold of each base↵
bases = [list(map(int, input().split())) for _ in range(b)]↵
↵
# Step 1: Sort bases by defensive power to process them efficiently↵
bases.sort()↵
↵
# Step 2: Sort spaceships by attacking power while keeping track of original indices↵
ships = sorted((ships[i], i) for i in range(s))↵
↵
# Array to store the maximum gold each spaceship can steal↵
ans = [0] * s↵
↵
# Two-pointer approach to efficiently determine how much gold each spaceship can steal↵
l, max_gold = 0, 0↵
↵
# Step 3: Process each spaceship in increasing order of attacking power↵
for i in range(s):↵
# Move the pointer 'l' to include all bases that the spaceship can attack↵
while l < b and bases[l][0] <= ships[i][0]:↵
max_gold += bases[l][1] # Add the gold from the base↵
l += 1 # Move to the next base↵
↵
# Store the total gold that this spaceship can steal↵
ans[ships[i][1]] = max_gold # Store result at original index↵
↵
# Step 4: Print the results in the original order of spaceships↵
print(*ans)↵
↵
if __name__ == "__main__":↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. The Road to King's Landing](https://codeforces.me/gym/599383/problem/D)↵
↵
<spoiler summary="Hint 1">↵
Consider that the player's position after each move must lie within the intersection of the reachable area from the previous position (given \( k \)) and the current segment's bounds.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Use binary search to efficiently determine the minimal \( k \). For each candidate \( k \), simulate the player's movement through all segments to check feasibility.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
1. **Binary Search Setup**: The minimal \( k \) lies between 0 and a sufficiently large upper bound.↵
2. **Feasibility Check**: For each candidate \( k \):↵
- Start at position 0.↵
- For each segment, compute the reachable interval after moving at most \( k \) units from the previous position.↵
- Intersect this interval with the current segment's bounds.↵
- If the intersection is empty, \( k \) is too small.↵
3. **Binary Search Adjustment**: Adjust the search range based on feasibility results to find the minimal \( k \).↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
import sys↵
def can_complete_level(n, segments, k):↵
L, R = 0, 0 # The range of reachable positions↵
for l, r in segments:↵
# Compute the new reachable range↵
L = max(l, L — k)↵
R = min(r, R + k)↵
if L > R: # If no valid landing position exists↵
return False↵
return True↵
def find_min_k(n, segments):↵
left, right = 0, 10**9 # Binary search for k↵
while left <= right:↵
mid = (left + right) // 2↵
if can_complete_level(n, segments, mid):↵
right = mid — 1↵
else:↵
left = mid + 1↵
return left↵
def main():↵
t = int(input())↵
results = []↵
for _ in range(t):↵
n = int(input())↵
segments = []↵
for _ in range(n):↵
l, r = map(int, inpit().split())↵
segments.append((l, r))↵
results.append(str(find_min_k(n, segments)))↵
sys.stdout.write(" ".join(results) + "\n")↵
if __name__ == "__main__":↵
main()↵
</spoiler>↵
↵
↵
<spoiler summary="Complexity Analysis">↵
- **Binary Search**: The search runs in \( O(\log(\text{max\_distance})) \) iterations, where \(\text{max\_distance}\) is the upper bound (\( 10^9 \)).↵
- **Feasibility Check**: Each check processes \( n \) segments in \( O(n) \) time.↵
- **Total Complexity**: \( O(t \cdot n \cdot \log(10^9)) \), which is efficient given the constraints (sum of \( n \) across test cases is \( 2 \cdot 10^5 \)).↵
</spoiler>↵
↵
↵
#### [E. The Long Road to Winterfell](https://codeforces.me/gym/599383/problem/E)↵
↵
<spoiler summary="Hint 1">↵
Consider selecting Farmer John's room first and then placing the cows in the nearest available unoccupied rooms.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If the farthest distance is \( x \), can you calculate the maximum number of cows that can be placed?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try using prefix sum to efficiently calculate how many cows can be placed within a given range.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
This problem might have another solution where we can calculate the answer directly.↵
But for a moment, let's think about whether this can be solved without binary search.↵
↵
The first thing we do when solving output binary search problems is check:↵
Can we easily verify if a given answer is valid or not?↵
If someone told us the answer in advance, could we efficiently check its validity?↵
If so, we can use binary search to guess the answer.↵
For this to work, the function must be monotonic (i.e., if a certain \( x \) is possible, all larger values are also possible).↵
Since this function is monotonic, we can use binary search to efficiently find the minimum \( x \) that satisfies the conditions.↵
↵
The binary search must start with \( l = 0 \) and \( r = n \), as this ensures we explore the full possible range of distances.↵
To check feasibility for a given distance \( d \), we calculate how many available rooms exist↵
in the range \( left, right \), where:↵
- \( left = max(0, i — d) \)↵
- \( right = min(n, i + d + 1) \)↵
↵
We use the prefix sum array to efficiently compute the number of unoccupied rooms within this range.↵
↵
#### Complexity Analysis↵
- **Binary Search**: The search runs in \( O(\log n) \) iterations since we are halving the search space each time.↵
- **Feasibility Check**: Each check processes \( n \) rooms in \( O(n) \) time.↵
- **Prefix Sum Computation**: Constructing the prefix sum array takes \( O(n) \) time.↵
- **Total Complexity**: The overall complexity is \( O(n log n) \), which is efficient given the constraints.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```python↵
import sys↵
↵
def solve():↵
n, k = map(int, sys.stdin.readline().strip().split())↵
s = sys.stdin.readline().strip()↵
prefix = [0]↵
↵
# Compute prefix sum for counting free rooms quickly↵
for val in s:↵
prefix.append(prefix[-1] + (1 if val == '0' else 0))↵
↵
def max_cows_in_range(d):↵
"""Given max distance d, calculate the maximum number of cows that can be placed"""↵
max_cows = 0↵
for i in range(n):↵
if s[i] == '0': # Consider only unoccupied rooms↵
left = max(0, i - d)↵
right = min(n, i + d + 1)↵
max_cows = max(max_cows, prefix[right] - prefix[left])↵
return max_cows↵
↵
# Binary search for the minimum possible maximum distance↵
l, r = 0, n↵
while l < r:↵
mid = (l + r) // 2↵
if max_cows_in_range(mid) >= k + 1:↵
r = mid # Try a smaller maximum distance↵
else:↵
l = mid + 1↵
↵
print(l)↵
↵
if __name__ == "__main__":↵
solve()↵
```↵
</spoiler>↵
↵
↵
#### [F. The Iron Throne's Multiplication](https://codeforces.me/gym/599383/problem/F)↵
↵
↵
<spoiler summary="Hint 1"> ↵
The problem asks for the k-th largest number in the multiplication table. However, listing all numbers and sorting them in descending order is too slow. Instead, think about how to find the k-th smallest number first—since the k-th largest in a sorted list is the same as the (n*m — k + 1)-th smallest. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Hint 2"> ↵
To efficiently find the k-th smallest number without generating all elements, use binary search on possible values (from 1 to n*m). For a given mid-value, count how many numbers in the table are ≤ mid by checking each row. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> ↵
The problem requires finding the k-th smallest number in an n × m multiplication table where each cell (i, j) contains i * j. Since generating and sorting all n * m elements is too slow for large n and m, we use binary search on the possible values (from 1 to n * m). ↵
↵
For a given mid-value during binary search, we count how many numbers in the table are ≤ mid by iterating through each row i and calculating min(mid // i, m). This gives the count of valid numbers in that row. ↵
↵
If the total count is less than k, the k-th smallest number must be larger than mid, so we adjust the search to higher values. ↵
↵
If the count is ≥ k, the k-th smallest number could be mid or smaller, so we search lower values. ↵
↵
The binary search efficiently narrows down the correct value in O(n log(n * m)) time, making it suitable for large constraints. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python↵
def solve():↵
n, m, k = map(int, input().split())↵
↵
def find(mid):↵
count = 0↵
for i in range(1, n + 1):↵
add = min(mid // i, m)↵
if add == 0:↵
break↵
count += add↵
return count < k↵
↵
low, high = 1, n * m↵
answer = 0↵
↵
while low <= high:↵
mid = (low + high) // 2↵
if find(mid):↵
low = mid + 1↵
else:↵
answer = mid↵
high = mid - 1↵
↵
print(answer)↵
↵
t = 1↵
for _ in range(t):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
