from typing import Optional
def solve(n: int, m: int, mat: list[list[str]]) -> tuple[int, int]:
longest_rowi: int = -1
longest_len: int = 0
for rowi in range(n):
manlen: int = sum(1 if x == "#" else 0 for x in mat[rowi])
if manlen > longest_len:
longest_len = manlen
longest_rowi = rowi
li: Optional[int] = None
ri: Optional[int] = None
for coli in range(m):
if mat[longest_rowi][coli] != "#":
continue
if li is None:
li = coli
ri = coli
# because of the nature of Manhattan circle, `ri + li` is always even
midi = (ri + li) // 2
return longest_rowi + 1, midi + 1
for _ in range(int(input())):
n, m = map(int, input().split())
mat = []
for i in range(n):
mat.append(list(input()))
res: tuple[int, int] = solve(n, m, mat)
print(f"{res[0]} {res[1]}")t <= 10 ^ 4 and n <= 2 * 10 ^ 5, so I
needed to come up with a O(n) solution.
I thought of an approach that checks sum // 2 in prefix
using set or dict, so that the check should be
doen in O(1) and O(n) in total.
However, that approach exceeded the time limit on test 10. My
suspicion is that, the number of elements I needed to hold in a hash
table was too large, facing collisions, and the time complexity of the
lookup became > O(1) (~=O(n)?), making the
total time complexity exceed O(n).
The fact I could not notice is that I only need to track the maximum
number in a prefix because only the maximum number in a prefix can be
sum // 2. Other values cannot be satisfy the condition
because the remaining part already contains a value bigger than the
value, thus the value is always smaller than the sum, including the
maximum element.
from collections import defaultdict
def solve(n: int, a: list[int]) -> int:
su: int = 0
ma: int = 0
ans: int = 0
for x in a:
su += x
ma = max(ma, x)
if ma * 2 == su:
ans += 1
return ans
for _ in range(int(input())):
n: int = int(input())
a: list[int] = list(map(int, input().split()))
ans: int = solve(n, a)
print(ans)The parity of each number changes after an operation. That means that if 2 numbers have the same parity, they will always have the same parity. If they had different parity, their parities stay different.
(2, 2, 2)
->
(3, 1, 1)
->
(2, 0, 2)So, for any digit, the count can be decreased to
x mod 2. Considered the fact that the difference of
parities of any 2 numbers don't change on the operations, the solution
is,
for _ in range(int(input())):
a, b, c = map(int, input().split())
ans: tuple[int] = (
1 if b % 2 == c % 2 else 0,
1 if a % 2 == c % 2 else 0,
1 if a % 2 == b % 2 else 0,
)
print(f"{ans[0]} {ans[1]} {ans[2]}")This is the second time I tackled this problem.
The most important thing (for me) is
There are 𝑛 coins on the table forming a circle, and each coin is either facing up or facing down.
Because it took me a long time to realize that I did not have to consdier edge cases.
Removing a coin only flips the parity (mod 2) by 1
because
(two adjacent coins)
(U, U), (D, D) 0 mod 2 -> (D, D), (U, U) 0 mod 2
(U, D), (D, U) 1 mod 2 -> (D, U), (U, D) 1 mod 2The parity of each player does not change until the operation before the last one.
for _ in range(int(input())):
n: int = int(input())
s: list[str] = list(input())
parity: int = sum(1 if x == "U" else 0 for x in s) % 2
if parity == 0:
print("NO")
else:
print("YES")for _ in range(int(input())):
k, q = map(int, input().split())
a: list[int] = list(map(int, input().split()))
q: list[int] = list(map(int, input().split()))
a.sort()
amin: int = a[0]
ans: list[int] = []
for n in q:
if n < amin:
ans.append(n)
else:
ans.append(amin - 1)
print(" ".join([str(x) for x in ans]))for _ in range(int(input())):
n: int = int(input())
a: list[int] = list(map(int, input().split()))
if 0 in a:
print(0)
continue
negs: int = sum(1 if x < 0 else 0 for x in a)
if negs % 2 == 0:
print(1)
print("1 0")
else:
print(0)Ketone 40 mg/dl // I'm taking Keto suppliments, and I bet the Keto is not something generated by my body.
Bacon Egg 0g Salad 20g Pistachio 10g Protein shake 10g
Total carbohydrate 40g
MUST:
cyclon, updating a
function with Result<> (20240728)TODO: