A. Matrix Rotation
Where should be the minimum and the maximum element of the array in order for the matrix to be beautiful.
If a matrix is beautiful, then its minimum is in the upper left corner, and its maximum is in the lower right corner (and vice versa). If you rotate it, the element from the upper left corner goes to the upper right corner, and the element from the lower right corner goes to the lower left corner — so these elements are still in the opposite corners. No matter how many times we rotate a beautiful matrix, its minimum and maximum elements will be in the opposite corners — and the opposite is true as well; if you have a 2×2 matrix with minimum and maximum elements in opposite corners, it can be rotated in such a way that it becomes beautiful.
So, all we need to check is that the minimum and the maximum elements are in the opposite corners.
def solve():
ROWS, COLS = 2, 2
matrix = []
for i in range(ROWS):
matrix.append(list(map(int,input().split())))
x1, y1 = 0, 0
x2, y2 = 0, 0
for i in range(ROWS):
for j in range(COLS):
if matrix[i][j] < matrix[x1][y1]:
x1, y1 = i, j
if matrix[i][j] > matrix[x2][y2]:
x2, y2 = i, j
dx = abs(x1 - x2)
dy = abs(y1 - y2)
if dx + dy > 1:
print("YES")
else:
print("NO")
def main():
num_tests = int(input())
for test in range(num_tests):
solve()
main()
B. Kefa and First Steps
Note, that if the array has two intersecting continuous non-decreasing subsequence, they can be combined into one. Therefore, you can just pass the array from left to right. If the current subsequence can be continued using the i-th element, then we do it, otherwise we start a new one. The answer is the maximum subsequence of all the found ones.
def main():
size = int(input())
nums = list(map(int, input().split()))
max_subsegment = 0
cur_segment = 1
for i in range(1, size):
if nums[i] >= nums[i-1]:
cur_segment += 1
else:
max_subsegment = max(max_subsegment, cur_segment)
cur_segment = 1
max_subsegment = max(max_subsegment, cur_segment)
print(max_subsegment)
main()
C. Double Strings
Try brute force.
For each string s, brute force all strings x and y such that s=x+y. There are at most 7 such strings, because s has length at most 8. Then check if both x and y appear in the array using some data structure.
def solve():
num_strings = int(input())
strings = []
for i in range(num_strings):
string = input()
strings.append(string)
indices = set(strings)
ans = ['0' for i in range(num_strings)]
for i in range(num_strings):
for j in range(1, len(strings[i])):
prefix = strings[i][: j]
suffix = strings[i][j :]
if prefix in indices and suffix in indices:
ans[i] = '1'
return ''.join(ans)
def main():
num_tests = int(input())
for test in range(num_tests):
print(solve())
main()
D. Balanced Team
May be sorting might help.
In order to create a team with the maximum number of students, it is important to ensure that all members of the team have similar levels of programming skill. A way to do this is by taking the list of students and sorting them in increasing order according to their programming skills. After this, a sliding window technique can then be employed to find the maximum size team window that satisfies the given constraint; i.e. that there is no more than 5 unit difference in skill level between each pair of members. The resulting window size will indicate how many students can be placed together in a team without breaking their specified constraint.
length = int(input())
nums = list(map(int, input().split()))
nums.sort()
ans = 0
left = 0
for right in range(length):
while (nums[right] - nums[left]) > 5:
left += 1
ans = max(ans, right - left + 1)
print(ans)
E. Pair of Topics
Let's sort the difference array(ai — bi)
Let's rewrite the inequality
Let's find pair of topics which fulfills the rewritten inequality
The given problem requires finding the number of pairs of elements (i,j) in two arrays a and b, such that the sum of the differences between corresponding elements in the two arrays (Di = ai — bi and Dj = aj — bj) is positive. To simplify this problem, we can create a new array D where Di is the difference between ai and bi, and sort this array.
Rewriting the inequality gives us:
(ai + aj) > (bi + bj) (ai - bi) + (aj - bj) > 0 Di + Dj > 0
Then, we can iterate through the elements of D from left to right and count the number of pairs (i,j) such that Di and Dj sum to positive and i < j.
length = int(input())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
diff = [0] * length
for i in range(length):
diff[i] = arr1[i] - arr2[i]
diff.sort()
total = 0
beg = 0
end = length - 1
# find pairs which gives Di + Dj > 0
while end >= beg:
while beg < end and diff[beg] + diff[end] <= 0:
beg += 1
total += max(end - beg, 0)
end -= 1
print(total)