git checkout --theirs (path), it's much easier to
resolve merge conflicts now. I'm getting confidence running the
server.My brain is getting engraved with the algorithm.
def find_parent(i: int, parent: list[int]) -> int:
if parent[parent[i]] == parent[i]:
return parent[i]
return find_parent(parent[i], parent)
def union_set(i: int, j: int, parent: list[int], size: list[int]) -> None:
parent_i: int = find_parent(i, parent)
parent_j: int = find_parent(j, parent)
if parent_i == parent_j:
return None
if size[parent_i] > size[parent_j]:
size[parent_i] += size[parent_j]
parent[parent_j] = parent_i
else:
size[parent_j] += size[parent_i]
parent[parent_i] = parent_j
return
n_nodes: int = 10
# (0, 5, 8, 9), (1, 2, 3), (4, 7), (6)
edges: list[tuple[int, int]] = [
(0, 9),
(9, 8),
(5, 8),
(1, 2),
(3, 2),
(4, 7),
]
parent = list(range(n_nodes))
size = [1] * n_nodes
for s, t in edges:
union_set(s, t, parent, size)
count: int = 0
for i in range(n_nodes):
parent[i] = find_parent(i, parent)
if i == parent[i]: # leader
count += 1
print(f"{parent=}") # [9, 2, 2, 2, 7, 9, 6, 7, 9, 9]
print(f"{count=}") # 4With the knowledge about Disjoint Set Union, the problem can be solved in a straightforward way.
def find_parent(i: int, parent: list[int]) -> int:
if parent[parent[i]] == parent[i]:
return parent[i]
return find_parent(parent[i], parent)
def union_set(i: int, j: int, parent: list[int], size: list[int]) -> None:
parent_i = find_parent(i, parent)
parent_j = find_parent(j, parent)
if parent_i == parent_j:
return
if size[parent_i] > size[parent_j]:
size[parent_i] += size[parent_j]
parent[parent_j] = parent_i
else:
size[parent_j] += size[parent_i]
parent[parent_i] = parent_j
return
for _ in range(int(input())):
n: int = int(input())
p: list[int] = list(map(int, input().split()))
c: list[str] = list(input())
size: list[int] = [1 if x == "0" else 0 for x in c]
parent: list[int] = list(range(n))
for i, pi in enumerate(p):
union_set(i, pi - 1, parent, size)
for i in range(n):
parent[i] = find_parent(i, parent)
result: list[int] = []
for i in range(n):
result.append(size[parent[i]])
print(" ".join([str(x) for x in result]))The only difference with the basic Disjoint Set Union algorithm is that I populated a size as the problem requested. Then, BOOM! The problem is solved.
This solution took 671 ms and used 32000 KB memory whereas my first solution took 811 ms and used 43900 KB memory, though the difference might be negligible.
"""
EEE
EEN => X
a1 == a2, a2 == a3, a3 != a1
NEN
a1 != a2, a2 == a3, a3 != a1
NNN
a1 != a2, a2 != a3, a3 != a1
EENN
a1 == a2, a2 == a3, a3 != a4, a4 != a1
ENEN
a1 == a2, a2 != a3, a3 == a4, a4 != a1
ENENEN
a1 == a2, a2 != a3, a3 == a4, a4 != a5, a5 == a6, a6 != a1
a1 = a2 = 1
a3 = a4 = 2
a5 = a6 = 3
Observation: NO if (num of `N`) == 1 ?
When Ns appear in a row
EN..NE => It's possible to make the each size of E equals to each other
When Ns appear in different chunks
ENE..(E)NE.. => It's possible to make a1 == a2, a2 != a3, ..., ai != a(i+1), a(i+1) == a(i+2)
Each section that is surrounded by N can just have a different number from others
"""
for _ in range(int(input())):
s: list[str] = list(input())
n_num: int = sum(1 if x == "N" else 0 for x in s)
if n_num == 1:
print("NO")
else:
print("YES")def find_parent(i: int, parent: list[int]) -> int:
# print(f"{i=}, {parent=}")
if parent[parent[i]] == parent[i]:
return parent[i]
return find_parent(parent[i], parent)
def union_set(i: int, j: int, parent: list[int], size: list[int]) -> None:
parent_i = find_parent(i, parent)
parent_j = find_parent(j, parent)
if parent_i == parent_j:
return
if size[parent_i] > size[parent_j]:
parent[parent_j] = parent_i
else:
parent[parent_i] = parent_j
for _ in range(int(input())):
s: list[str] = list(input())
n = len(s)
parent: list[int] = list(range(n))
size: list[int] = [1] * n
# 1. Grouping equal values
for i in range(n):
if s[i] == "N":
continue
j, k = (i, i + 1) if i != n - 1 else (0, n - 1)
union_set(j, k, parent, size)
# 2. Update parent information
for i in range(n):
parent[i] = find_parent(i, parent)
# 3. Check all `N`; if adjacent numbers that surround N belongs to the same group
# ( <=> the numbers should be the same value), the input array is inconsistent
for i in range(n):
if s[i] != "N":
continue
j, k = (i, i + 1) if i != n - 1 else (0, n - 1)
if parent[j] == parent[k]:
print("NO")
break
else:
print("YES")How convenient Disjoint Set Union is!
I feel that I can apply this algorithm to any problems.
The Psychology of Science - Abraham Harold Maslow
“If the only tool you have is a hammer, it is tempting to treat everything as if it were a nail.”
Wakame salad 200 Berries 200 Protein shake 400 Seafood salad 400 Rice 200 Mashed potatoes 200
Total 1600 kcal
4 mi run, push-ups
MUST:
TODO: