[problem:421609A]
Try brute force.
We have two orientations for each rectangle, rotated by 90 or 270 degrees or by 0 or 180 degrees. So, we can try each of the four possibilities we can get by matching each orientations of the first rectangle to the two orientations of the second rectangle.
Time Complexity — O(1) Space Complexity — O(1)
testcases = int(input())
for _ in range(testcases):
w_1, l_1 = map(int, input().split())
w_2, l_2 = map(int, input().split())
answer = "No"
for (a, b) in [(w_1, l_1), (l_1, w_1)]:
for (c, d) in [(w_2, l_2), (l_2, w_2)]:
if a + c == b == d:
answer = "Yes"
print(answer)
[problem:421609B]
You can always find an answer.
An odd number of negatives will result in a Negative Number
Positive numbers set or a set with positive numbers and an even number of negative numbers will result in a Positive set
Anything multiplied with a zero will be Zero
There is always at least one zero
Implement the following algorithms: Create three arrays: zero_array, positive_array, and negative_array. Put the numbers from the given array into their respective arrays. If there are even elements in negative_array, move an element to zero_array. If there are more than two elements in the negative_array, move two elements to the positive_array.
Time Complexity — O(N) Space Complexity — O(N)
n = int(input())
array = list(map(int, input().split()))
zero_array = []
positive_array = []
negative_array = []
for num in array:
if num < 0:
negative_array.append(num)
elif num > 0:
positive_array.append(num)
else:
zero_array.append(num)
if len(negative_array) % 2 == 0:
zero_array.append(negative_array.pop())
if len(negative_array) > 2:
positive_array.append(negative_array.pop())
positive_array.append(negative_array.pop())
print(len(negative_array), *negative_array)
print(len(positive_array), *positive_array)
print(len(zero_array), *zero_array)
[problem:421609C]
Try to see a pattern at the intersection of the diagonals.
For each cell with a hash, check if its diagonally adjacent cells have a hash too.
Time Complexity — O(N^2) Space Complexity — O(1)
def solve(grid):
directions = [(-1, -1), (1, 1), (-1, 1), (1, -1)]
n = 8
for row in range(1, n - 1):
for col in range(1, n - 1):
if grid[row][col] != "#":
continue
bishop = True
for di, dj in directions:
row_n, col_n = row + di, col + dj
bishop &= grid[row_n][col_n] == "#"
if bishop:
return (row + 1, col + 1)
test_cases = int(input())
for _ in range(test_cases):
input()
grid = [input() for _ in range(8)]
print(*solve(grid))
[problem:421609D]
Try to see which cells interchange positions upon rotation.
First, we need some way to find cells that interchange positions; we can achieve this by using four pointers or a formula. After that, from the four cells that interchange positions, we figure out the count of the minority element and add it to our answer.
Time Complexity — O(N^2) Space Complexity — O(1)
from math import ceil
test_case = int(input())
for _ in range(test_case):
n = int(input())
grid = []
for _ in range(n):
row = [int(num) for num in input()]
grid.append(row)
cost = 0
for row in range(ceil(n / 2)):
for col in range(n // 2):
count = sum(
[
grid[row][col],
grid[col][-1 - row],
grid[-1 - row][-1 - col],
grid[-1 - col][row],
]
)
cost += min(count, 4 - count)
print(cost)
[problem:421609E]
List down the different types of paths with fewer than three turns.
Since we can only make two turns max, we have a limited kind of paths.
Paths 1 and 2 are just straight lines; paths 3, 4, 5, and 6 are parallel straight lines connected by an orthogonal line.
To check if such a path exists, paint a cross on S and T with "S" and "T", then try to find S+dots+T or T+dots+S row-wise or column-wise.
Time Complexity — O(N * M) Space Complexity — O(1)
from itertools import product
def paint_cross(s_row, s_col, char, grid, n):
# down
for i in range(s_row + 1, n):
if grid[i][s_col] == ".":
grid[i][s_col] = char
else:
break
# up
for i in range(s_row - 1, -1, -1):
if grid[i][s_col] == ".":
grid[i][s_col] = char
else:
break
# right
for j in range(s_col + 1, m):
if grid[s_row][j] == ".":
grid[s_row][j] = char
else:
break
# left
for j in range(s_col - 1, -1, -1):
if grid[s_row][j] == ".":
grid[s_row][j] = char
else:
break
n, m = map(int, input().split())
grid = [list(input()) for _ in range(n)]
h_row, h_col = None, None
r_row, r_col = None, None
for i in range(n):
for j in range(m):
if grid[i][j] == "S":
h_row, h_col = i, j
elif grid[i][j] == "T":
r_row, r_col = i, j
if h_row is not None and r_col is not None:
break
paint_cross(h_row, h_col, "S", grid, n)
paint_cross(r_row, r_col, "T", grid, n)
# try to find S+dots+T or T+dots+S row-wise
for i in range(n):
last = "*"
for j in range(m):
if (grid[i][j], last) == ("T", "S") or (grid[i][j], last) == ("S", "T"):
print("YES")
exit()
if grid[i][j] != ".":
last = grid[i][j]
# try to find S+dots+T or T+dots+S column-wise
for j in range(m):
last = "*"
for i in range(n):
if (grid[i][j], last) == ("T", "S") or (grid[i][j], last) == ("S", "T"):
print("YES")
exit()
if grid[i][j] != ".":
last = grid[i][j]
print("NO")