thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

Husqvarna701SM đã nói:

Xem tệp đính kèm 3280987
mới update, lên 4x hehe

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

LmaoSuVuong đã nói:

q4 nhìn tưởng dễ xơi mà khoai nhỉ,

có khi xuống nữa, đọc dc vài a ấn xài AI giải ko thèm đổi biến r

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

LmaoSuVuong đã nói:

dạng bài design data structure có vẻ hot ở mấy web OA tầm vài tháng trước, h leetcode update vào liên tục

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

freedom.9 đã nói:

Q4 n khá nhỏ nên dùng graph để bipartiate theo distance, đm 4 bugs rank 1k4 cmnr

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

JakovichTimViec đã nói:

share để tham khảo đc ko bác

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

JakovichTimViec đã nói:

share để tham khảo đc ko bác

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

class Solution:
    def isBipartite(self, n: int, adj: dict) -> bool:
        colors = [0] * n
        for startNode in range(n):
            if colors[startNode] == 0:
                stack = [(startNode, 1)]
                colors[startNode] = 1

                while stack:
                    u, uColor = stack.pop()

                    for v in adj.get(u, []):
                        if colors[v] == 0:
                            colors[v] = -uColor
                            stack.append((v, -uColor))
                        elif colors[v] == uColor:
                            return False
        return True


    def maxPartitionFactor(self, points: List[List[int]]) -> int:
        n = len(points)

        if n <= 2:
            return 0

        allDistances = []

        for i in range(n):
            xi, yi = points[i]
            for j in range(i + 1, n):
                xj, yj = points[j]
                distance = abs(xi - xj) + abs(yi - yj)
                allDistances.append((distance, i, j))

        allDistances.sort(key=lambda x: x[0])
 
        uniqueDistances = sorted(list(set(d[0] for d in allDistances)))

        maxFactor = uniqueDistances[0]
 
        for i in range(1, len(uniqueDistances)):
            thresholdD = uniqueDistances[i]
            adj = defaultdict(list)
            for dist, u, v in allDistances:
                if dist < thresholdD:
                    adj[u].append(v)
                    adj[v].append(u)
                else:
                    pass

            if self.isBipartite(n, adj):
                maxFactor = thresholdD
            else:
                break

        return maxFactor

freedom.9 đã nói:

Spoiler: Code

Python:

class Solution:
    def isBipartite(self, n: int, adj: dict) -> bool:
        colors = [0] * n
        for startNode in range(n):
            if colors[startNode] == 0:
                stack = [(startNode, 1)]
                colors[startNode] = 1

                while stack:
                    u, uColor = stack.pop()

                    for v in adj.get(u, []):
                        if colors[v] == 0:
                            colors[v] = -uColor
                            stack.append((v, -uColor))
                        elif colors[v] == uColor:
                            return False
        return True


    def maxPartitionFactor(self, points: List[List[int]]) -> int:
        n = len(points)

        if n <= 2:
            return 0

        allDistances = []

        for i in range(n):
            xi, yi = points[i]
            for j in range(i + 1, n):
                xj, yj = points[j]
                distance = abs(xi - xj) + abs(yi - yj)
                allDistances.append((distance, i, j))

        allDistances.sort(key=lambda x: x[0])
 
        uniqueDistances = sorted(list(set(d[0] for d in allDistances)))

        maxFactor = uniqueDistances[0]
 
        for i in range(1, len(uniqueDistances)):
            thresholdD = uniqueDistances[i]
            adj = defaultdict(list)
            for dist, u, v in allDistances:
                if dist < thresholdD:
                    adj[u].append(v)
                    adj[v].append(u)
                else:
                    pass

            if self.isBipartite(n, adj):
                maxFactor = thresholdD
            else:
                break

        return maxFactor

Lúc đầu ngu quá viết code greedy bằng cách dùng 1 line hoặc 1 point để split thành 2 groups nên ko ăn, sau mới nghĩ ra dùng bipartiate graph kiểm tra từng point, cuối giờ viết code ko kịp chôm code chỗ bipartiate có sẵn. Nhanh hơn thì phải dùng binary search
Ý tưởng là vì min của 2 groups phải > 1 cái threshold nào đấy nên chỉ cần kiểm tra xem với đống distance mà < threshold nó bắt buộc phải bipartiate ở 2 group khác nhau là ok. Nếu nghĩ theo hướng binary search on the answer thì code đơn giản hơn nhiều rồi.

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

Husqvarna701SM đã nói:

Thif e bảo đề nay dễ mà, hai câu array cơ bản 2 câu binarysearch, câu 3 thêm prefixsum còn câu 4 thêm tô màu graph (dfs/bfs) là xong

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

freedom.9 đã nói:

Ừ q cuối phải reverse thinking mà nhìn thấy cái trick này thì dễ là đúng rồi. Khó nhất là cái trick này thôi

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

Husqvarna701SM đã nói:

Chắc do có đợt em spam toàn làm binary search ))) nên dễ xử lý hơn

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