800 difficulty, my
learning zone is 800~1000."""
Time limit exceeded
t = 500, n = 100 => 100 ** 4 * 500 ~= 10 ** 10 => TLE
"""
def greedy(n: int, a: list) -> int:
res = -1
for i in range(n):
for j in range(n):
for k in range(n):
for l in range(n):
if len(set([i, j, k, l])) < 4:
continue
res = max(
res,
abs(a[i] - a[j])
+ abs(a[j] - a[k])
+ abs(a[k] - a[l])
+ abs(a[l] - a[i]),
)
return res
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print(greedy(n, a))for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
ai, aj, ak, al = a[0], a[-1], a[1], a[-2]
# aj - ai + aj - ak + al - ak + al - ai
print(2 * (aj + al - ai - ak))I found the solution with observation/constructive algorithms, but will try to understand the editorial later.
Codeforces Round 931 (Div. 2) Editorial
def solve(n: int, a: list[int]) -> int:
init_sum = sum(a)
if init_sum % 3 == 0:
return 0
if init_sum % 3 == 2:
return 1 # choose any element and increase the sum by 1
if init_sum % 3 == 1:
if [x for x in a if x % 3 == 1]:
return 1 # remove x where x mod 3 = 1
return 2 # choose any elements and increase the sum by 2
return -1
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
res = solve(n, a)
print(res)def solve(n: int, a: list[int]) -> int:
# all negative numbers can be positive after the operations
# 1. sort a
# 2. reverse all the negative elements
return sum([abs(x) for x in a])
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
res = solve(n, a)
print(res)def solve(n: int, s: str) -> int:
# res(n) = {@: 1, _: 0, *: -1 (unreachiable)} + max(res(n - 1), res(n - 2))
# classic dp problem
# we only need two variables, but the conditions would get complicated
def _val(c: str) -> int:
match c:
case ".":
return 0
case "@":
return 1
case _:
return -1
if n == 1:
return 0
res = [-1] * n
res[0] = 0
res[1] = _val(s[1])
for i in range(2, n):
if res[i - 1] == res[i - 2] == -1:
break
res[i] = _val(s[i])
if res[i] == -1:
continue
res[i] += max(
res[i - 1] if res[i - 1] != -1 else 0,
res[i - 2] if res[i - 2] != -1 else 0,
)
return max(res)
for _ in range(int(input())):
n = int(input())
s = input()
res = solve(n, s)
print(res)def solve(n: int, a: list[int]) -> bool:
target = sum(a) // n
for i in range(n - 1):
if a[i] < target:
return False
a[i + 1] += a[i] - target
return True
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
res = solve(n, a)
if res:
print("YES")
else:
print("NO")def solve(n: int) -> int:
ALPHABETS = "abcdefghijklmnopqrstuvwxyz"
res = "zzz"
for i in range(27):
for j in range(27):
for k in range(27):
if i + j + k != n:
continue
res = min(
res,
(ALPHABETS[i - 1] if i > 0 else "")
+ (ALPHABETS[j - 1] if j > 0 else "")
+ (ALPHABETS[k - 1] if k > 0 else ""),
)
return res
for _ in range(int(input())):
n = int(input())
res = solve(n)
print(res)for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
res = 0
for i in range(0, n * 2, 2):
res += a[i]
print(res)Observation: - the number of cells that can color 2 diagonals = 2 * n - 2 - remaining cells only color 1 diagonal
O###O
OOOOO
#####
# => cells that can color 2 diagonalsimport math
def solve(n: int, k: int) -> int:
# num of cells that can remove 2 diagonals
rm2: int = 2 * n - 2
return math.ceil(min(2 * rm2, k) / 2) + max(0, k - 2 * rm2)
for _ in range(int(input())):
n, k = map(int, input().split())
res = solve(n, k)
print(res)My thought process
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
res = 0
for i in range(1, n):
res += a[i] - a[i - 1]
print(res)Codeforces Round #926 (Div. 2) Editorial
a2 - a1 + a3 - a2 + … + an - an-1 = an - n1. So we just need to maximize this value, which means the answer is the maximum number in the array minus the minimum.
It's embarrasing that I didn't notice this… maybe I'm getting tired (it's 3 am), or maybe I'm super stupid.
def is_wasting_time(a: int, b: int) -> int:
a, b = min(a, b), max(a, b)
# horizontal
if b % 2 == 0:
c, d = a * 2, b // 2
c, d = min(c, d), max(c, d)
if (c, d) != (a, b):
return False
# vertical
if a % 2 == 0:
c, d = a // 2, b * 2
c, d = min(c, d), max(c, d)
if (c, d) != (a, b):
return False
return True
for _ in range(int(input())):
a, b = map(int, input().split())
if is_wasting_time(a, b):
print("NO")
else:
print("YES")from typing import Optional
def solve(n: int, s: str) -> int:
bfirst: Optional[int] = None
blast: Optional[int] = None
for i in range(n):
if s[i] == "B":
if bfirst is None:
bfirst = i
blast = i
if bfirst is None:
return 0
return blast - bfirst + 1
for _ in range(int(input())):
n = int(input())
s = input()
res = solve(n, s)
print(res)leveraging the fact that
The grid contains exactly one triangle or exactly one square that contains all the 𝟷s in the grid. It is guaranteed that the size of the triangle or square is greater than 1 (i.e., the shape cannot consist of exactly one 1).
def is_square(n: int, mat: list[list[int]]) -> bool:
for i in range(n - 1):
if 1 in mat[i]:
return mat[i] == mat[i+1]
return False
for _ in range(int(input())):
n = int(input())
mat = []
for i in range(n):
mat.append(list(map(int, list(input()))))
if is_square(n, mat):
print("SQUARE")
else:
print("TRIANGLE")from collections import defaultdict
for _ in range(int(input())):
s = input()
counter = defaultdict(int)
for c in s:
counter[c] += 1
if counter["A"] > counter["B"]:
print("A")
else:
print("B")I noticed that the positions of characters don't matter. We can just choose any indexes.
import string
def solve(n: int, k: int) -> str:
return string.ascii_lowercase[:k] * n
for _ in range(int(input())):
n, k = map(int, input().split())
res = solve(n, k)
print(res)It seems to be a classic problem, but I'm not confident next time I encounter this sort of problem.
oh, it's getting very late … (4 am)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
i = 0
while a[i] == 0:
i += 1
res = 0
tmp = 0
while i < n:
if a[i] == 1:
res += tmp
tmp = 0
else:
tmp += 1
i += 1
print(res)for _ in range(int(input())):
square = []
square.append(list(map(int, input().split())))
square.append(list(map(int, input().split())))
square.append(list(map(int, input().split())))
square.append(list(map(int, input().split())))
square.sort()
width = square[1][1] - square[0][1]
height = square[2][0] - square[0][0]
print(width * height)for _ in range(int(input())):
a, b = map(int, input().split())
if (a + b) % 2 == 1:
print("Alice")
else:
print("Bob")I just found the solution, but the it's impossible for me (for now) to understand the editorial.
for _ in range(int(input())):
n = int(input())
a = input()
plus = len([x for x in a if x == "+"])
minus = len([x for x in a if x == "-"])
print(abs(plus - minus))Protein shake 400 Salad 300 Chicken 400 Bagel 400 Meat stick 100
Total 1600 kcal
TODO: