thảo luận Leetcode mỗi ngày

chiyeuemthoi đã nói:

ngài đấm hard như con contest toàn 4/4 xuống thị phàm chốn này chăng

Nhấp để mở rộng...

freedom.9 đã nói:

Nay cho bài 2k8 rating cơ à có vẻ hay để mai nghiên cứu xem solution

Nhấp để mở rộng...

anoldvozer1710.v2 đã nói:

rating 2873, AC 28.3%, Hard real đấy ae, ko phải giả cầy đâu, cook luôn chứ làm làm gì nữa
kiếm bài medium khác làm bù daily, câu sv này đi pv mà hỏi là nó ko muốn tuyển mình rồi

Nhấp để mở rộng...

LmaoSuVuong đã nói:

cái rating này hình như chấm theo cái AC , vừa đọc dưới phần discuss thì là cop 1 bài bên codeforce rating 2k3, vừa đào mộ thì là bài 6 điểm trong contest 346

, chỉ có 131/20k người giải dc

Nhấp để mở rộng...

freedom.9 đã nói:

Ngon, quá easy để rating gần 2k9 ra doạ người tí thôi

Spoiler: Python

Python:

class Solution:
    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
        graph = defaultdict(list)
        for edge in edges:
            if edge[2] != -1:
                graph[edge[0]].append((edge[1], edge[2]))
                graph[edge[1]].append((edge[0], edge[2]))

        def dijktra(source):
            visitedAt = [inf]*n
            visitedAt[source] = 0
            pq = []
            pq.append((0, source))
            while pq:
                dist, vertex = heapq.heappop(pq)
                if dist > visitedAt[vertex]:
                    continue

                if vertex == destination:
                    return dist

                for neighbor, weight in graph[vertex]:
                    neighborWeight = dist + weight
                    if neighborWeight < visitedAt[neighbor]:
                        visitedAt[neighbor] = neighborWeight
                        heapq.heappush(pq, (neighborWeight, neighbor))

            return inf

        ans = []
        previousDistance = dijktra(source)
        for i in range(len(edges)):
            f,t,w = edges[i]
            if w != -1:
                ans.append([f, t, w])
                continue
           
            graph[f].append((t, 1))
            graph[t].append((f, 1))
            shortedDistance = dijktra(source)
            if shortedDistance <= target and shortedDistance < previousDistance:
                graph[f][-1] = (t, target - shortedDistance + 1)
                graph[t][-1] = (f, target - shortedDistance + 1)
                ans.append([f, t, target - shortedDistance + 1])
                for j in range(i + 1, len(edges)):
                    f,t,w = edges[j]
                    if w != -1:
                        ans.append([f, t, w])
                    else:
                        ans.append([f,t, 2*10**9])

                break

            previousDistance = shortedDistance
            ans.append([f,t, 1])

        shortedDistance = dijktra(source)
        return [] if shortedDistance != target else ans

Nhấp để mở rộng...

freedom.9 đã nói:

Ngon, quá easy để rating gần 2k9 ra doạ người tí thôi

Spoiler: Python

Python:

class Solution:
    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
        graph = defaultdict(list)
        for edge in edges:
            if edge[2] != -1:
                graph[edge[0]].append((edge[1], edge[2]))
                graph[edge[1]].append((edge[0], edge[2]))

        def dijktra(source):
            visitedAt = [inf]*n
            visitedAt[source] = 0
            pq = []
            pq.append((0, source))
            while pq:
                dist, vertex = heapq.heappop(pq)
                if dist > visitedAt[vertex]:
                    continue

                if vertex == destination:
                    return dist

                for neighbor, weight in graph[vertex]:
                    neighborWeight = dist + weight
                    if neighborWeight < visitedAt[neighbor]:
                        visitedAt[neighbor] = neighborWeight
                        heapq.heappush(pq, (neighborWeight, neighbor))

            return inf

        ans = []
        previousDistance = dijktra(source)
        for i in range(len(edges)):
            f,t,w = edges[i]
            if w != -1:
                ans.append([f, t, w])
                continue
           
            graph[f].append((t, 1))
            graph[t].append((f, 1))
            shortedDistance = dijktra(source)
            if shortedDistance <= target and shortedDistance < previousDistance:
                graph[f][-1] = (t, target - shortedDistance + 1)
                graph[t][-1] = (f, target - shortedDistance + 1)
                ans.append([f, t, target - shortedDistance + 1])
                for j in range(i + 1, len(edges)):
                    f,t,w = edges[j]
                    if w != -1:
                        ans.append([f, t, w])
                    else:
                        ans.append([f,t, 2*10**9])

                break

            previousDistance = shortedDistance
            ans.append([f,t, 1])

        shortedDistance = dijktra(source)
        return [] if shortedDistance != target else ans

Nhấp để mở rộng...

Phó GOAT đã nói:

Đúng người bảo vệ có khác mọi thứ đều easy

Nhấp để mở rộng...

freedom.9 đã nói:

Ngon, quá easy để rating gần 2k9 ra doạ người tí thôi

Spoiler: Python

Python:

class Solution:
    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
        graph = defaultdict(list)
        for edge in edges:
            if edge[2] != -1:
                graph[edge[0]].append((edge[1], edge[2]))
                graph[edge[1]].append((edge[0], edge[2]))

        def dijktra(source):
            visitedAt = [inf]*n
            visitedAt[source] = 0
            pq = []
            pq.append((0, source))
            while pq:
                dist, vertex = heapq.heappop(pq)
                if dist > visitedAt[vertex]:
                    continue

                if vertex == destination:
                    return dist

                for neighbor, weight in graph[vertex]:
                    neighborWeight = dist + weight
                    if neighborWeight < visitedAt[neighbor]:
                        visitedAt[neighbor] = neighborWeight
                        heapq.heappush(pq, (neighborWeight, neighbor))

            return inf

        ans = []
        previousDistance = dijktra(source)
        for i in range(len(edges)):
            f,t,w = edges[i]
            if w != -1:
                ans.append([f, t, w])
                continue
          
            graph[f].append((t, 1))
            graph[t].append((f, 1))
            shortedDistance = dijktra(source)
            if shortedDistance <= target and shortedDistance < previousDistance:
                graph[f][-1] = (t, target - shortedDistance + 1)
                graph[t][-1] = (f, target - shortedDistance + 1)
                ans.append([f, t, target - shortedDistance + 1])
                for j in range(i + 1, len(edges)):
                    f,t,w = edges[j]
                    if w != -1:
                        ans.append([f, t, w])
                    else:
                        ans.append([f,t, 2*10**9])

                break

            previousDistance = shortedDistance
            ans.append([f,t, 1])

        shortedDistance = dijktra(source)
        return [] if shortedDistance != target else ans

Nhấp để mở rộng...

freedom.9 đã nói:

Bài này mình đoán đoán tí thôi rồi thấy có vẻ match với hint nên code thử xem, chứ nhìn thấy rating 2k9 sợ quá.
Vẽ cái graph ra thì thấy nếu source và destination nó bị disconnect bởi các cạnh -1 thì có 2 trường hợp.
1) Nối 1 cạnh -1 vào mà nó giảm distance xuống, nghĩa là cái cạnh -1 nó contribute vô đường đi ngắn nhất.
2) Nối 1 cạnh -1 vào mà distance ko giảm xuống, nghĩa là cạnh -1 đấy nó ko contribute vô đường đi ngắn nhất.
Rồi tới bước chọn value cho các cạnh -1, nếu chọn value là 1 mà distance giảm xuống vẫn lớn hơn target thì tiếp tục tìm cạnh khác, vì 1 là số nhỏ nhất mà vẫn ko ăn thua nên bỏ qua cạnh vừa rồi.
Còn nếu chọn value là 1 mà distance giảm xuống nhỏ hơn target thì việc còn lại chỉ cần tăng cái weight lên cho nó match với target là xong, các cạnh còn lại mark là 2*10^9 để nó khỏi contribute vô kết quả.

Nhấp để mở rộng...

Cố Trường Ca đã nói:

Em nghĩ bây giờ các thím tính xem card bao nhiêu hợp lí là vừa, mất lòng trước được lòng sau vậy, em đề nghị tính như này.
Mỗi lần @freedom.9 gạch ai thì người đó +2$, còn nếu ưng thì +1$

Sinh hoạt trong thread này hơn 2 tháng từ lúc @freedom.9 join thì auto 10$. Các bác thấy ổn không, có ít quá không, em sợ đòi hỏi ít quá bác ấy tưởng mình coi thường

Nhấp để mở rộng...

Cố Trường Ca đã nói:

Em nghĩ bây giờ các thím tính xem card bao nhiêu hợp lí là vừa, mất lòng trước được lòng sau vậy, em đề nghị tính như này.
Mỗi lần @freedom.9 gạch ai thì người đó +2$, còn nếu ưng thì +1$

Sinh hoạt trong thread này hơn 2 tháng từ lúc @freedom.9 join thì auto 10$. Các bác thấy ổn không, có ít quá không, em sợ đòi hỏi ít quá bác ấy tưởng mình coi thường

Nhấp để mở rộng...

• Clone năm hoạt động cao 2013, 2014. Join Date khác nhau khó bị phát hiện.
• Nâng bi có quote đầy đủ, dẫn chứng hiệu quả, không khen hời hợt.
• Cách comment đa dạng, đa nhân cách.
• Có hỗ trợ chửi đổng, tổ lái, công kích cá nhân và tìm lỗi chính tả.
• Hoạt động bền bỉ, sẵn sàng chi viện khi khách hàng comment đuối sức.
• Thích hợp ngược dòng, ngược gió, cân topic.

freedom.9 đã nói:

via theNEXTvoz for iPhone

Nhấp để mở rộng...