[Here](https://mirror.codeforces.com/contests/537575) is the link to the contest. Provide your feedback on each problem so that we can improve upon them the next time.↵
↵
↵
[A. Valid Parentheses](https://mirror.codeforces.com/gym/537575/problem/A)↵
-------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
The most optimal length is achieved if no parentheses need to be removed, but sometimes parentheses must be removed to maintain the balanced property. This happens when encountering a <b>)</b> before a matching <b>(</b>. To solve this, traverse the string from left to right. Every time you encounter a <b>(</b>, increment the open parentheses count by one. If you encounter a <b>)</b>, the count of open parentheses must be at least one. If it is, decrement the count by one and increment your result by two (one for the <b>(</b> and one for the <b>)</b> because both are part of the remaining valid string). If not, it means you have to remove this closing parenthesis.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
def solve():↵
s = input()↵
result = opened = 0↵
↵
for ch in s:↵
if ch == '(':↵
opened += 1↵
elif opened:↵
result += 2↵
opened -= 1↵
↵
print(result)↵
↵
↵
if __name__ == "__main__":↵
solve()↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:1,Good_problem]↵
- Ok problem: [likes:1,Ok_problem]↵
- Bad problem: [likes:1,Bad_problem]↵
- Did not attempt: [likes:1,Did_not_attempt]↵
</spoiler>↵
↵
[B. Chef Jamie](https://mirror.codeforces.com/gym/537575/problem/B)↵
------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
Given a list where removing one element can result in a sorted array:↵
↵
- The out-of-order elements form a nearly sorted sequence.↵
- It takes \( K — 1 \) swaps to sort \( K \) out-of-order elements, as each swap fixes one element's position, and the last swap finalizes the sorting.↵
↵
### Example↵
↵
Consider the list: `[1, 2, 3, 7, 4, 5, 6, 9, 10]`.↵
↵
- The out-of-order elements are `[7, 4, 5, 6]` because they are not in the correct positions.↵
- To correct this, we need 3 swaps.↵
↵
Here's how we can sort it with swaps:↵
↵
1. **Initial Array**: `[1, 2, 3, 7, 4, 5, 6, 9, 10]`↵
2. **Swap `7` and `4`**: `[1, 2, 3, 4, 7, 5, 6, 9, 10]`↵
3. **Swap `7` and `5`**: `[1, 2, 3, 4, 5, 7, 6, 9, 10]`↵
4. **Swap `7` and `6`**: `[1, 2, 3, 4, 5, 6, 7, 9, 10]`↵
↵
We needed 3 swaps to sort the array, which is \( K — 1 \) where \( K = 4 \) (the number of out-of-order elements).↵
↵
Generally, by comparing this list with the sorted version, we can identify the out-of-order sequence by counting the mismatches.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
def solve():↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
ordered = sorted(arr)↵
swaps = 0↵
↵
for i in range(n):↵
swaps += arr[i] != ordered[i]↵
↵
print(max(0, swaps - 1))↵
↵
↵
if __name__ == "__main__":↵
solve()↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:2,Good_problem]↵
- Ok problem: [likes:2,Ok_problem]↵
- Bad problem: [likes:2,Bad_problem]↵
- Did not attempt: [likes:2,Did_not_attempt]↵
</spoiler>↵
↵
↵
[C. Experiment](https://mirror.codeforces.com/gym/537575/problem/C)↵
------------------------------------------------------------↵
↵
<spoiler summary="Hint 1">↵
What will be the brute force solution?↵
The brute force solution is to determine the maximum number of rooms required at any given moment, from the earliest start time to the time when all experiments are completed. ↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try to use prefix sum (sweep line) to optimize the brute force solution. ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
def solve():↵
n = int(input())↵
max_size = int(1e4 + 10)↵
ps = [0] * max_size↵
↵
↵
for _ in range(n):↵
s, t, b = map(int, input().split())↵
ps[s] += b↵
ps[t + 1] -= b↵
↵
result = 0↵
for i in range(1, max_size):↵
ps[i] += ps[i - 1]↵
result = max(result, ps[i])↵
↵
print(result)↵
↵
↵
if __name__ == "__main__":↵
solve()↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:3,Good_problem]↵
- Ok problem: [likes:3,Ok_problem]↵
- Bad problem: [likes:3,Bad_problem]↵
- Did not attempt: [likes:3,Did_not_attempt]↵
</spoiler>↵
↵
[D. Minimum Park Lighting Cost](https://mirror.codeforces.com/gym/537575/problem/D)↵
----------------------------------------------------------------------------↵
↵
↵
<spoiler summary="Solution">↵
Notice that the number of available lights is relatively small, which encourages us to consider a brute force approach.↵
↵
Let's determine how many different combinations of lights Mayor Jane can use to ensure all parks are well-lit. For each light, there are $2$ options: either use it or don't use it. Thus, for $m$ lights, there are $2^m$ combinations of lights Mayor Jane can choose from, which is manageable at around 1024 combinations.↵
↵
Therefore, we can generate all possible combinations of lights and check each one to see if it provides sufficient lighting for all parks. If it does, and the total cost is lower than our current best solution, we update our best solution.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
def backtrack(positions, lights, index):↵
# Base case: If we've considered all lights↵
if len(lights) == index:↵
# Check if all positions are sufficiently lit↵
for pos in positions:↵
if pos > 0:↵
return float("inf") # Not all positions are lit; return infinity↵
return 0 # All positions are lit; return zero cost↵
↵
# Recursive case: Try not using the current light↵
result = backtrack(positions, lights, index + 1)↵
↵
s, t, p, cost = lights[index]↵
↵
# Consider using the current light↵
for i in range(s, t + 1):↵
positions[i] -= p # Reduce light requirement at each position↵
↵
# Calculate the cost if using the current light and take the minimum↵
result = min(result, cost + backtrack(positions, lights, index + 1))↵
↵
# Backtrack: Restore the light requirements for the next iteration↵
for i in range(s, t + 1):↵
positions[i] += p↵
↵
return result↵
↵
↵
def solve():↵
n, m = map(int, input().split())↵
max_len = 124↵
↵
positions = [0] * max_len↵
↵
for _ in range(n):↵
s, t, c = map(int, input().split())↵
positions[s] += c↵
positions[t + 1] -= c↵
↵
for i in range(1, len(positions)):↵
positions[i] += positions[i - 1]↵
↵
lights = [0] * m↵
↵
for i in range(m):↵
lights[i] = list(map(int, input().split()))↵
↵
↵
print(backtrack(positions, lights, 0))↵
↵
↵
if __name__ == "__main__":↵
solve()↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:4,Good_problem]↵
- Ok problem: [likes:4,Ok_problem]↵
- Bad problem: [likes:4,Bad_problem]↵
- Did not attempt: [likes:4,Did_not_attempt]↵
</spoiler>↵
↵
[E. Secure The Castle](https://mirror.codeforces.com/gym/537575/problem/E)↵
-------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
We can block all empty neighboring cells of enemies and then check if all the knights can escape while ensuring no enemies can escape.↵
↵
Consider all the neighboring cells of enemies ('B'). There shouldn't be any path from these cells to the exit cell (n,m). If there is a path from any such cell, the enemy adjacent to that cell can also reach the exit cell (n,m). ↵
↵
Based on this idea, we can block any empty cell neighboring an enemy. Suppose there is another solution in which a cell (i,j) neighboring an enemy does not need to be blocked. In that case, there still won't be any path from (i,j) to (n,m) in that solution. Thus, we can block (i,j) without affecting the solution.↵
↵
It is sufficient to block only the empty neighboring cells of enemies and check the required conditions, which can be done using a BFS or DFS on the grid.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
directions = [[0, -1], [-1, 0], [0, 1], [1, 0]]↵
↵
↵
def block_bad(grid, row, col, visited):↵
stack = [(row, col)]↵
visited[row][col] = True↵
↵
while stack:↵
x, y = stack.pop()↵
↵
for dx, dy in directions:↵
new_row, new_col = x + dx, y + dy↵
if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and not visited[new_row][new_col]:↵
if grid[new_row][new_col] == '.':↵
grid[new_row][new_col] = '#'↵
elif grid[new_row][new_col] != '#':↵
stack.append((new_row, new_col))↵
visited[new_row][new_col] = True↵
↵
↵
def can_exit(grid, row, col, visited):↵
stack = [(row, col)]↵
visited[row][col] = True↵
flag = False↵
↵
while stack:↵
x, y = stack.pop()↵
↵
if (x == len(grid) - 1) and (y == len(grid[0]) - 1):↵
flag = True↵
↵
for dx, dy in directions:↵
new_row, new_col = x + dx, y + dy↵
if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and not visited[new_row][new_col] and grid[new_row][new_col] != '#':↵
stack.append((new_row, new_col))↵
visited[new_row][new_col] = True↵
↵
return flag↵
↵
↵
def solve():↵
n, m = map(int, input().split())↵
↵
grid = [0] * n↵
↵
for i in range(n):↵
grid[i] = list(input().strip())↵
↵
↵
visited = [[False] * m for _ in range(n)]↵
↵
for i in range(n):↵
for j in range(m):↵
if grid[i][j] == 'B' and not visited[i][j]:↵
block_bad(grid, i, j, visited)↵
↵
visited = [[False] * m for _ in range(n)]↵
for i in range(n):↵
for j in range(m):↵
if grid[i][j] == 'G' and not visited[i][j] and not can_exit(grid, i, j, visited):↵
print("No")↵
return↵
↵
print("Yes")↵
↵
if __name__ == "__main__":↵
for _ in range(int(input())):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:5,Good_problem]↵
- Ok problem: [likes:5,Ok_problem]↵
- Bad problem: [likes:5,Bad_problem]↵
- Did not attempt: [likes:5,Did_not_attempt]↵
</spoiler>↵
↵
↵
↵
[A. Valid Parentheses](https://mirror.codeforces.com/gym/537575/problem/A)↵
-------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
The most optimal length is achieved if no parentheses need to be removed, but sometimes parentheses must be removed to maintain the balanced property. This happens when encountering a <b>)</b> before a matching <b>(</b>. To solve this, traverse the string from left to right. Every time you encounter a <b>(</b>, increment the open parentheses count by one. If you encounter a <b>)</b>, the count of open parentheses must be at least one. If it is, decrement the count by one and increment your result by two (one for the <b>(</b> and one for the <b>)</b> because both are part of the remaining valid string). If not, it means you have to remove this closing parenthesis.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
def solve():↵
s = input()↵
result = opened = 0↵
↵
for ch in s:↵
if ch == '(':↵
opened += 1↵
elif opened:↵
result += 2↵
opened -= 1↵
↵
print(result)↵
↵
↵
if __name__ == "__main__":↵
solve()↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:1,Good_problem]↵
- Ok problem: [likes:1,Ok_problem]↵
- Bad problem: [likes:1,Bad_problem]↵
- Did not attempt: [likes:1,Did_not_attempt]↵
</spoiler>↵
↵
[B. Chef Jamie](https://mirror.codeforces.com/gym/537575/problem/B)↵
------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
Given a list where removing one element can result in a sorted array:↵
↵
- The out-of-order elements form a nearly sorted sequence.↵
- It takes \( K — 1 \) swaps to sort \( K \) out-of-order elements, as each swap fixes one element's position, and the last swap finalizes the sorting.↵
↵
### Example↵
↵
Consider the list: `[1, 2, 3, 7, 4, 5, 6, 9, 10]`.↵
↵
- The out-of-order elements are `[7, 4, 5, 6]` because they are not in the correct positions.↵
- To correct this, we need 3 swaps.↵
↵
Here's how we can sort it with swaps:↵
↵
1. **Initial Array**: `[1, 2, 3, 7, 4, 5, 6, 9, 10]`↵
2. **Swap `7` and `4`**: `[1, 2, 3, 4, 7, 5, 6, 9, 10]`↵
3. **Swap `7` and `5`**: `[1, 2, 3, 4, 5, 7, 6, 9, 10]`↵
4. **Swap `7` and `6`**: `[1, 2, 3, 4, 5, 6, 7, 9, 10]`↵
↵
We needed 3 swaps to sort the array, which is \( K — 1 \) where \( K = 4 \) (the number of out-of-order elements).↵
↵
Generally, by comparing this list with the sorted version, we can identify the out-of-order sequence by counting the mismatches.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
def solve():↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
ordered = sorted(arr)↵
swaps = 0↵
↵
for i in range(n):↵
swaps += arr[i] != ordered[i]↵
↵
print(max(0, swaps - 1))↵
↵
↵
if __name__ == "__main__":↵
solve()↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:2,Good_problem]↵
- Ok problem: [likes:2,Ok_problem]↵
- Bad problem: [likes:2,Bad_problem]↵
- Did not attempt: [likes:2,Did_not_attempt]↵
</spoiler>↵
↵
↵
[C. Experiment](https://mirror.codeforces.com/gym/537575/problem/C)↵
------------------------------------------------------------↵
↵
<spoiler summary="Hint 1">↵
What will be the brute force solution?↵
The brute force solution is to determine the maximum number of rooms required at any given moment, from the earliest start time to the time when all experiments are completed. ↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try to use prefix sum (sweep line) to optimize the brute force solution. ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
def solve():↵
n = int(input())↵
max_size = int(1e4 + 10)↵
ps = [0] * max_size↵
↵
↵
for _ in range(n):↵
s, t, b = map(int, input().split())↵
ps[s] += b↵
ps[t + 1] -= b↵
↵
result = 0↵
for i in range(1, max_size):↵
ps[i] += ps[i - 1]↵
result = max(result, ps[i])↵
↵
print(result)↵
↵
↵
if __name__ == "__main__":↵
solve()↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:3,Good_problem]↵
- Ok problem: [likes:3,Ok_problem]↵
- Bad problem: [likes:3,Bad_problem]↵
- Did not attempt: [likes:3,Did_not_attempt]↵
</spoiler>↵
↵
[D. Minimum Park Lighting Cost](https://mirror.codeforces.com/gym/537575/problem/D)↵
----------------------------------------------------------------------------↵
↵
↵
<spoiler summary="Solution">↵
Notice that the number of available lights is relatively small, which encourages us to consider a brute force approach.↵
↵
Let's determine how many different combinations of lights Mayor Jane can use to ensure all parks are well-lit. For each light, there are $2$ options: either use it or don't use it. Thus, for $m$ lights, there are $2^m$ combinations of lights Mayor Jane can choose from, which is manageable at around 1024 combinations.↵
↵
Therefore, we can generate all possible combinations of lights and check each one to see if it provides sufficient lighting for all parks. If it does, and the total cost is lower than our current best solution, we update our best solution.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
def backtrack(positions, lights, index):↵
# Base case: If we've considered all lights↵
if len(lights) == index:↵
# Check if all positions are sufficiently lit↵
for pos in positions:↵
if pos > 0:↵
return float("inf") # Not all positions are lit; return infinity↵
return 0 # All positions are lit; return zero cost↵
↵
# Recursive case: Try not using the current light↵
result = backtrack(positions, lights, index + 1)↵
↵
s, t, p, cost = lights[index]↵
↵
# Consider using the current light↵
for i in range(s, t + 1):↵
positions[i] -= p # Reduce light requirement at each position↵
↵
# Calculate the cost if using the current light and take the minimum↵
result = min(result, cost + backtrack(positions, lights, index + 1))↵
↵
# Backtrack: Restore the light requirements for the next iteration↵
for i in range(s, t + 1):↵
positions[i] += p↵
↵
return result↵
↵
↵
def solve():↵
n, m = map(int, input().split())↵
max_len = 124↵
↵
positions = [0] * max_len↵
↵
for _ in range(n):↵
s, t, c = map(int, input().split())↵
positions[s] += c↵
positions[t + 1] -= c↵
↵
for i in range(1, len(positions)):↵
positions[i] += positions[i - 1]↵
↵
lights = [0] * m↵
↵
for i in range(m):↵
lights[i] = list(map(int, input().split()))↵
↵
↵
print(backtrack(positions, lights, 0))↵
↵
↵
if __name__ == "__main__":↵
solve()↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:4,Good_problem]↵
- Ok problem: [likes:4,Ok_problem]↵
- Bad problem: [likes:4,Bad_problem]↵
- Did not attempt: [likes:4,Did_not_attempt]↵
</spoiler>↵
↵
[E. Secure The Castle](https://mirror.codeforces.com/gym/537575/problem/E)↵
-------------------------------------------------------------------↵
↵
<spoiler summary="Solution">↵
We can block all empty neighboring cells of enemies and then check if all the knights can escape while ensuring no enemies can escape.↵
↵
Consider all the neighboring cells of enemies ('B'). There shouldn't be any path from these cells to the exit cell (n,m). If there is a path from any such cell, the enemy adjacent to that cell can also reach the exit cell (n,m). ↵
↵
Based on this idea, we can block any empty cell neighboring an enemy. Suppose there is another solution in which a cell (i,j) neighboring an enemy does not need to be blocked. In that case, there still won't be any path from (i,j) to (n,m) in that solution. Thus, we can block (i,j) without affecting the solution.↵
↵
It is sufficient to block only the empty neighboring cells of enemies and check the required conditions, which can be done using a BFS or DFS on the grid.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
directions = [[0, -1], [-1, 0], [0, 1], [1, 0]]↵
↵
↵
def block_bad(grid, row, col, visited):↵
stack = [(row, col)]↵
visited[row][col] = True↵
↵
while stack:↵
x, y = stack.pop()↵
↵
for dx, dy in directions:↵
new_row, new_col = x + dx, y + dy↵
if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and not visited[new_row][new_col]:↵
if grid[new_row][new_col] == '.':↵
grid[new_row][new_col] = '#'↵
elif grid[new_row][new_col] != '#':↵
stack.append((new_row, new_col))↵
visited[new_row][new_col] = True↵
↵
↵
def can_exit(grid, row, col, visited):↵
stack = [(row, col)]↵
visited[row][col] = True↵
flag = False↵
↵
while stack:↵
x, y = stack.pop()↵
↵
if (x == len(grid) - 1) and (y == len(grid[0]) - 1):↵
flag = True↵
↵
for dx, dy in directions:↵
new_row, new_col = x + dx, y + dy↵
if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and not visited[new_row][new_col] and grid[new_row][new_col] != '#':↵
stack.append((new_row, new_col))↵
visited[new_row][new_col] = True↵
↵
return flag↵
↵
↵
def solve():↵
n, m = map(int, input().split())↵
↵
grid = [0] * n↵
↵
for i in range(n):↵
grid[i] = list(input().strip())↵
↵
↵
visited = [[False] * m for _ in range(n)]↵
↵
for i in range(n):↵
for j in range(m):↵
if grid[i][j] == 'B' and not visited[i][j]:↵
block_bad(grid, i, j, visited)↵
↵
visited = [[False] * m for _ in range(n)]↵
for i in range(n):↵
for j in range(m):↵
if grid[i][j] == 'G' and not visited[i][j] and not can_exit(grid, i, j, visited):↵
print("No")↵
return↵
↵
print("Yes")↵
↵
if __name__ == "__main__":↵
for _ in range(int(input())):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Feedback">↵
- Good problem: [likes:5,Good_problem]↵
- Ok problem: [likes:5,Ok_problem]↵
- Bad problem: [likes:5,Bad_problem]↵
- Did not attempt: [likes:5,Did_not_attempt]↵
</spoiler>↵
↵
