A. Zoro’s Bounty Dilemma
SolutionThere is four possible outcomes to this problem, if there has been both a '>' and '<' in your string , then you cant determine the winner so you return '?'. with that case out of the way you just need to keep track of if theres been a '<' or '>' since we know both couldnt have been there, so which ever one you find, you print, if its neither , you can return '='.
Code
for _ in range(int(input())):
s = input()
if '<' in s and '>' in s:
print('?')
elif '<' in s:
print('<')
elif '>' in s:
print('>')
else:
print('=')
B. Thousand Sunny's Network Setup
SolutionThe problem requires selecting k computers with the highest possible equal internet speed, given that we can only decrease speeds but not increase them. A simple and efficient approach is to sort the array in descending order and directly pick the k-th largest speed, as this ensures we select the highest possible speed that at least k computers can have. Alternatively, a brute-force approach involves iterating through potential speeds and counting how many computers can support them, keeping track of the maximum valid speed. Due to the weak constraints (n ≤ 100), both approaches work efficiently, with sorting providing an O(n log n) solution.
Code
n, k = map(int, input().split())
print(sorted(map(int, input().split()))[n - k])
C. Robin’s Water Wisdom: Stop the Leaks!
SolutionThe problem involves ensuring that at least B liters of water flow out of the first hole by blocking the minimum number of holes. The flow from each hole is proportional to its size, and the goal is to maximize the flow from the first hole. We calculate the total sum of hole sizes and sort the remaining holes. By iteratively blocking the smallest holes, we reduce the total size until the flow from the first hole meets or exceeds B. The solution involves sorting and a greedy approach to block the smallest contributors first.
Coden, a, b = list(map(int, input().split()))
arr = list(map(int, input().split()))
s = sum(arr)
res = sorted(arr[1:])
count = 0
while arr[0] * a / s < b:
s -= res.pop()
count += 1
print(count)
D. Pirates Island: Painting the Grand Line
SolutionYou’re given an NXM grid where each cell has an initial color. A stranger set is a group of cells that:
- All share the same color.
- No two cells in the set share a side (cells can touch diagonally but not edge-to-edge).
In a single step, you can choose any such stranger set and repaint all its cells in any other color. The objective is to make all cells the same color using the fewest steps.
Key Insight
For each color(c):
- If no pair of adjacent cells has
color(c), you can repaint all of those cells in 1 step. (They’re already pairwise strangers.) - If at least one pair of adjacent cells has color
color(c), you need 2 steps to repaint all cells of that color. (Because you can split the connected component into two “stranger” groups.)
Hence, define for each color(c):
color(c) = 0 if (c) does not appear in the grid.color(c) = 1 if (c) appears, but never in two adjacent cells.color(c) = 2 if (c) appears and there is at least one pair of adjacent cells color(c).
Choosing the Final Color
- Let
S be the sum of color(c) over every color c that appears. - In code, this is computed as
sum(has_color ) + sum(adj_found), where has_color [c] is 1 if c appears, and adj_found[c] is 1 if c has adjacent cells.
- If you select some color
C* as the final color, you do not need to repaint cells already in C*. - The minimum steps required to unify the grid into a single color is:
result = S - max(cost(c))
In the code, max(cost(c)) = 1 + max(adj_found[c]). Hence, the final result is:
result = (sum(has_color ) + sum(adj_found)) - 1 - max(adj_found)
Complexity Analysis:
Codeimport sys
input = sys.stdin.readline
def solve():
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for i in range(n)]
has_color = [0] * (n * m + 1)
adj_found= [0] * (n * m + 1)
for i in range(n):
for j in range(m):
has_color[grid[i][j]] = 1
if i + 1 < n and grid[i][j] == grid[i + 1][j]:
adj_found[grid[i][j]] = 1
if j + 1 < m and grid[i][j] == grid[i][j + 1]:
adj_found[grid[i][j]] = 1
print(sum(has_color) + sum(adj_found) - 1 - max(adj_found))
if __name__ == '__main__':
for _ in range(int(input())):
solve()
Solution To determine whether a valid permutation can be formed using numbers initially marked as either blue or red, we can strategically adjust their values. The key observation is that red numbers should ideally occupy the higher positions in the permutation, while blue numbers should be placed in the lower positions. If at any point a blue number is larger than a red number in the permutation, we can swap their positions by incrementing the red number and decrementing the blue number accordingly. This ensures that if a solution exists, there is always an equivalent arrangement where the smallest blue numbers take the lowest available positions and the largest red numbers take the highest ones. To implement this approach, we first sort all elements based on their color, prioritizing blue numbers first, and then by their value. After sorting, we verify that each element can be adjusted to its expected position—blue numbers should be at least as large as their index so they can be reduced to fit, while red numbers should not exceed their index so they can be increased if necessary. If these conditions hold for all elements, a valid permutation can be constructed. <\spoiler>
Code ``` t = int(input())
for _ in range(t): n = int(input()) chest_values = list(map(int, input().split())) chest_colors = input()
blue_chests = []
red_chests = []
for i in range(n):
if chest_colors[i] == "B":
blue_chests.append(chest_values[i])
else:
red_chests.append(chest_values[i])
blue_chests.sort()
red_chests.sort()
is_permutation_possible = True
for i in range(len(blue_chests)):
if blue_chests[i] < i + 1:
is_permutation_possible = False
for i in range(len(red_chests)):
if red_chests[i] > (n - len(red_chests) + i + 1):
is_permutation_possible = False
print("YES" if is_permutation_possible else "NO") </spoiler>
[F. Luffy’s Lineup Challenge](https://codeforces.me/gym/594356/problem/F)
<spoiler summary="Solution">
The problem involves rearranging an array b to match the order of another array a using adjacent swaps. The key insight is that both arrays are guaranteed to be permutations of the same set of elements (i.e., they are multisets), meaning that we can always reorder b to match a. We start by creating a mapping of each value in a to its corresponding index, allowing us to track where each value from b should be placed in a. For each element in b, we replace it with the index from a, resulting in a list of target positions.Once we have this list of target positions, we simulate sorting it into the correct order using adjacent swaps (similar to bubble sort). At each step, we compare adjacent elements, and if they are in the wrong order, we swap them. We continue this process until the list is sorted, recording each swap. Finally, we output the number of swaps and the swap operations themselves. This approach guarantees the desired configuration while ensuring the solution is efficient enough given the problem constraints.
</spoiler>
<spoiler summary= "Code">
n = int(input()) a = list(map(int,input().split())) b = list(map(int, input().split())) def next_index(start,target): for i in range(start,n): if b[i] == target: return i swaps = [] for i in range(n): target = a[i] right = next_index(i,target)
while right>i:
swaps.append([right,right+1])
b[right],b[right-1] = b[right-1],b[right]
right-=1count = 0 print(len(swaps)) for swap in swaps: print(*swap) ```
