chiyeuemthoi
Senior Member
2 bai dau lam 5p bai 3 chiu cmnl 
thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
hieunm3538
Senior Member
Bài 3 em pass 702/716 test case, quả test cạnh chia hết chạy for n trong dfs tù quá nên TLE 
Toang quá, mai gỡ
Toang quá, mai gỡ
freedom.9
Senior Member
Mình cũng suy nghĩ phức tạp quá ngáo vl.Bài 3 em pass 702/716 test case, quả test cạnh chia hết chạy for n trong dfs tù quá nên TLE
Tính luôn ra kết quả ở dfs là ngon cmnr, cũng ko khó lắm
chiyeuemthoi
Senior Member
bac co code k cho em tham khao voi aMình cũng suy nghĩ phức tạp quá ngáo vl.
Tính luôn ra kết quả ở dfs là ngon cmnr, cũng ko khó lắm
freedom.9
Senior Member
Mã:
class Solution:
def countPairsOfConnectableServers(self, edges: List[List[int]], signalSpeed: int) -> List[int]:
def dfs(node, parent, weight):
res = 1 if weight % signalSpeed == 0 else 0
for neighbor, neighborWeight in graph[node]:
if neighbor != parent:
res += dfs(neighbor, node, weight + neighborWeight)
return res
n = len(edges) + 1
graph = [[] for _ in range(n)]
for edge in edges:
graph[edge[0]].append([edge[1], edge[2]])
graph[edge[1]].append([edge[0], edge[2]])
ans = [0]*n
for i in range(n):
count = 0
for neighbor, weight in graph[i]:
countJ = dfs(neighbor, i, weight)
ans[i] += count*countJ
count += countJ
return ansThì kết quả sẽ là
sum(I1, I, I2) = pairs(I1, I)*pairs(I2,I)
sum(I1, I, I2, I3 ) = sum(I1, I, I2) *pairs(I3, I)
Mở rộng ra với n đỉnh
Brute force tìm mỗi đỉnh là xong. Do cứ ngồi nghĩ cách tính distance từ đỉnh tới lá nên mình ko viết được hàm dfs, chỉ cần tìm số điểm thoả mãn yêu cầu đề bài là ok rồi
cay thật
Sửa lần cuối:
freedom.9
Senior Member
flashmt - LeetCode Profile
View flashmt's profile on LeetCode, the world's largest programming community.
leetcode.com
via theNEXTvoz for iPhone
hungmessi2
Senior Member
Ông này top CP VN rồi :vTop8, cao thủ phương nào đâyflashmt - LeetCode Profile
View flashmt's profile on LeetCode, the world's largest programming community.leetcode.com
via theNEXTvoz for iPhone
Codeforces max 2900
via theNEXTvoz for iPhone
freedom.9
Senior Member
Chắc cũng cày dữ lắm + tố chất nữa nhỉ. Nhìn tụi nó giải mà nản IQ của mình quá
Đang ngó qua các platform khác thi thố để cải thiện thêm
hungmessi2
Senior Member
Cố lên bác, mình và các bạn khác nhìn bác cày cũng nể lắmChắc cũng cày dữ lắm + tố chất nữa nhỉ. Nhìn tụi nó giải mà nản IQ của mình quá
via theNEXTvoz for iPhone
Violet_7
Member
Rút kinh nghiệm lại, Lưu lại luôn template, lần sau gặp thì vác ra dùng luônlại là đọ template mà mất hết template toàn phải gõ lại, cũng may cài FenwickTree không khó
lần đầu giải được 4 bài mừng quá hahahaha
freedom.9
Senior Member
Bài cuối mình dùng sortedlist + với binary search nên ko cần template gì, thấy còn dễ hơn cả bài 3 kaka.Rút kinh nghiệm lại, Lưu lại luôn template, lần sau gặp thì vác ra dùng luôn
TLE_WA
Junior Member
template C++ linh hoạt hơn hẳn python. Được cái viết mấy cái hàm đệ quy có nhớ với python cứ thêm cái @lru_cache tiện thật, lại còn một đống trick quá tiệnRút kinh nghiệm lại, Lưu lại luôn template, lần sau gặp thì vác ra dùng luôn
Violet_7
Member
chắc e bị overthinking quá
. Giờ vẫn chưa nghĩ ra dùng 2 cái kia kiểu gì
freedom.9
Senior Member
Cái hàm GreatCout nó nhận vô một targeted number, tìm số element lớn hơn trong list nữa là hoàn hảo cho việc xài binary search rồi fence. Việc còn lại là maintain 1 cái sorted order bằng sortedList nữa là ngon cơm. Tính ra Time complexity chỉ là Onlogn nên mình biết là ăn được rồi.chắc e bị overthinking quá
Leetcode nó có cái củ đậu gì output limit exceed cay thế nhỉ, mình kẹp cái print vô để debug ăn ngay con bug
TLE_WA
Junior Member
không cần template là tư duy giải bài của anh tốt đó, chứ chưa chi đã nghĩ ngay dùng template như em cũng không tốt lắm
- Trạng thái
Chủ đề tương tự
