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

billy_don said:
Không, vì G liên thông nên trường hợp chỉ có (1,2) hoặc (3) thì kệ nó nhé. Đối với vertex có chứa cả 3 loại dù số lượng tụi nó có bao nhiêu đi nữa thì cũng chỉ pick ra một cặp (1,2) hoặc một (3) để E0 nối với V. Nên dùng (1,2,3) là đủ để đại diện cho toàn bộ case rồi còn gì nữa.
Click to expand...
vầy thì phải nói rõ ra trong chứng minh chứ nhỉ 🤔
 
billy_don said:
Đang chứng minh mỗi vertex ưu tiên type 3 mà, mà nếu ưu tiên nghĩa là tồn tại ít nhất một cặp (1,2) và một (3) nối với vertex chứ.
Click to expand...
có vẻ mấy cái nói nãy giờ như không xuyên qua được bên kia: chứng minh chia case mà logic nhiều case khác nhau thì không thể dùng "không mất tính tổng quát" và áp cách chứng minh một case cho các case còn lại được
:burn_joss_stick:

giờ thêm cái nữa nè, cho là chứng minh như đã nói đúng đi thì nó chỉ mới chỉ ra được là thuật toán bắt buộc phải lấy edge type 3 thôi chứ chưa chứng minh được là cái thứ tự lấy edge type 3 trước rồi mới dùng edge type khác trong algo là đúng, tại sao không thể lấy type 1, 2 trước mà phải lấy type 3 trước? thuật toán nó giữ gìn invariant gì mà kết quả sau khi duyệt qua hết edge là đúng?
 
small-lambda said:
có vẻ mấy cái nói nãy giờ như không xuyên qua được bên kia: chứng minh chia case mà logic nhiều case khác nhau thì không thể dùng "không mất tính tổng quát" và áp cách chứng minh một case cho các case còn lại được
:burn_joss_stick:

giờ thêm cái nữa nè, cho là chứng minh như đã nói đúng đi thì nó chỉ mới chỉ ra được là thuật toán bắt buộc phải lấy edge type 3 thôi chứ chưa chứng minh được là cái thứ tự lấy edge type 3 trước rồi mới dùng edge type khác trong algo là đúng, tại sao không thể lấy type 1, 2 trước mà phải lấy type 3 trước? thuật toán nó giữ gìn invariant gì mà kết quả sau khi duyệt qua hết edge là đúng?
Click to expand...
Có vẻ mấy cái nói nãy giờ như không xuyên qua được bên kia.

Chứng minh là ưu tiên pick (3) thì đã chứng minh rồi. Và trường hợp (1,2,3) cũng là tổng quát cho mệnh đề t chứng minh. Các case còn lại dù có từ một trở lên cặp (1,2) hoặc chỉ có từ một trở lên (3) thì chả có duy nhất một lựa chọn à? Nếu nó chỉ có một lựa chọn thì còn gì để nói đâu, hoặc nó chỉ có (1) hoặc chỉ có (2) thì bài toán vô nghiệm.

Thêm nữa nè, để nó đúng cho toàn bộ graph là ở mỗi vertex đã pick thì không xử lí lại lần 2, nên nếu nó có (3) thì pick (3) sau đó xong, không đụng đến nó nữa, nếu nó có thêm cạnh khác thuộc E nối với nó thì đó là vấn đề của vertex khác. Vậy nên nó vẫn đúng cho cả toàn bộ graph.
 
small-lambda said:
giờ lấy trường hợp chỉ có vertex nối edge type 1, 2 thì chứng minh vầy đâu còn đúng nhỉ 🤔
Click to expand...
Thì tôi chứng minh nó ưu tiên (3) mà, còn chỉ nối edge 1, 2 thì pick một cặp (1, 2) cho mỗi vertex thôi. Nên chỉ có 1,2 thì chả có gì phải chứng minh hay bàn luận nữa.
 
Last edited:
billy_don said:
Có vẻ mấy cái nói nãy giờ như không xuyên qua được bên kia.

Chứng minh là ưu tiên pick (3) thì đã chứng minh rồi. Và trường hợp (1,2,3) cũng là tổng quát cho mệnh đề t chứng minh. Các case còn lại dù có từ một trở lên cặp (1,2) hoặc chỉ có từ một trở lên (3) thì chả có duy nhất một lựa chọn à? Nếu nó chỉ có một lựa chọn thì còn gì để nói đâu, hoặc nó chỉ có (1) hoặc chỉ có (2) thì bài toán vô nghiệm.

Thêm nữa nè, để nó đúng cho toàn bộ graph là ở mỗi vertex đã pick thì không xử lí lại lần 2, nên nếu nó có (3) thì pick (3) sau đó xong, không đụng đến nó nữa, nếu nó có thêm cạnh khác thuộc E nối với nó thì đó là vấn đề của vertex khác. Vậy nên nó vẫn đúng cho cả toàn bộ graph.
Click to expand...
billy_don said:
Thì tôi chứng minh nó ưu tiên (3) mà, còn chỉ nối edge 1, 2 thì pick một cặp (1, 2) cho mỗi vertex thôi. Nên chỉ có 1,2 thì chả có gì phải chứng minh hay bàn luận nữa.
Click to expand...
chính vì hiểu rõ nên thấy là hai câu comment này cho thấy người viết comment không thấy vấn đề, không tin thì xin mời hỏi về cái cách chứng minh đã dùng trên một diễn đàn nào khác xem họ có đòi hỏi nói rõ ra từng case không, kiểu như computer science exchange,

mỗi lần nghe vặn thì lại chắp vá thêm vào logic, nhưng không nhìn ra được cái lỗ hỗng trong logic ban đầu, không thấy được sai sót, không hiểu người ta bắt bẻ cái gì

chỉ có lời khuyên là nên theo học một khóa proof-based math đi, có người sửa bài đàng hoàng, có nền tảng đó dễ tiếp thu nhiều thứ trong CS hơn
 
small-lambda said:
intuition mình thấy, nhưng giờ muốn chứng minh là nó optimal thì làm ntn?
Click to expand...
Bạn chia ra hai trường hợp:
TH1: Trong những cạnh phải xóa không có bất cứ cạnh chung nào của 2 đồ thị thuộc type 3. Lấy tổng cạnh mỗi đồ thị trừ đi 2 x (số đỉnh - 1).
TH2: Có nhiều hơn hoặc bằng 1 cạnh phải xóa đồng thời trên 2 đồ thị thuộc type 3.
Ta đặt số cạnh loại 3 phải xóa đồng thời trên 2 đồ thị là ec, số cạnh sẽ xóa là Đáp_án_tối_ưu= e1 - (n - 1) + e2 - (n - 1) - ec.
Giả sử số cạnh loại 3 phải xóa đồng thời trên 2 đồ thị là ec - 1, lúc này thì mỗi một đồ thị bạn phải xóa thêm 1 cạnh để đảm bảo là mỗi đồ thị chỉ còn lại n - 1 cạnh.
Số cạnh phải xóa là
e1 - 1 - (n - 1) + e2 - 1 - (n - 1) - ec < Đáp_án_tối_ưu.
 
Last edited:
small-lambda said:
chính vì hiểu rõ nên thấy là hai câu comment này cho thấy người viết comment không thấy vấn đề, không tin thì xin mời hỏi về cái cách chứng minh đã dùng trên một diễn đàn nào khác xem họ có đòi hỏi nói rõ ra từng case không, kiểu như computer science exchange,

mỗi lần nghe vặn thì lại chắp vá thêm vào logic, nhưng không nhìn ra được cái lỗ hỗng trong logic ban đầu, không thấy được sai sót, không hiểu người ta bắt bẻ cái gì

chỉ có lời khuyên là nên theo học một khóa proof-based math đi, có người sửa bài đàng hoàng, có nền tảng đó dễ tiếp thu nhiều thứ trong CS hơn
Click to expand...
Tôi lại thấy anh bắt bẻ không được tôi nên lại bảo tôi không hiểu anh bắt bẻ gì? :D ??

Còn logic chắp vá là vì anh đọc không hiểu nên tôi phải giải thích ra kĩ hơn đấy. Nên vấn đề ở người đọc chứ không phải người viết đâu.

Tôi học toán nhiều hơn anh đấy không cần phải bảo tôi đi học gì đâu nhé 👍
 
billy_don said:
Tôi lại thấy anh bắt bẻ không được tôi nên lại bảo tôi không hiểu anh bắt bẻ gì? :D ??

Còn logic chắp vá là vì anh đọc không hiểu nên tôi phải giải thích ra kĩ hơn đấy. Nên vấn đề ở người đọc chứ không phải người viết đâu.

Tôi học toán nhiều hơn anh đấy không cần phải bảo tôi đi học gì đâu nhé 👍
Click to expand...
cool 👍
 
humanversion9x said:
Bạn chia ra hai trường hợp:
TH1: Trong những cạnh phải xóa không có bất cứ cạnh chung nào của 2 đồ thị thuộc type 3. Lấy tổng cạnh mỗi đồ thị trừ đi 2 x (số đỉnh - 1).
TH2: Có nhiều hơn hoặc bằng 1 cạnh phải xóa đồng thời trên 2 đồ thị thuộc type 3.
Ta đặt số cạnh loại 3 phải xóa đồng thời trên 2 đồ thị là ec, số cạnh sẽ xóa là Đáp_án_tối_ưu= e1 - (n - 1) + e2 - (n - 1) - ec.
Giả sử số cạnh loại 3 phải xóa đồng thời trên 2 đồ thị là ec - 1, lúc này thì mỗi một đồ thị bạn phải xóa thêm 1 cạnh để đảm bảo là mỗi đồ thị chỉ còn lại n - 1 cạnh.
Số cạnh phải xóa là
e1 - 1 - (n - 1) + e2 - 1 - (n - 1) - ec < Đáp_án_tối_ưu.
Click to expand...
cái này mình nghĩ vẫn chưa trực tiếp chứng minh được là cái thuật toán như post trên này ra kết quả đúng, khi chứng minh thì phải nhìn vào phần thân của algo và chỉ ra được là sau mỗi lần loop là nó giữ một cái invariant gì đó dẫn đến kết quả đúng, kể cả khi graph A hoặc B disconnected, nhưng cảm ơn bạn đã dành thời gian

mà nghĩ kĩ, tốn thời gian đi chứng minh làm gì, vì luyện leetcode đâu phải để giỏi CS 😔
 
small-lambda said:
cái này mình nghĩ vẫn chưa trực tiếp chứng minh được là cái thuật toán như post trên này ra kết quả đúng, khi chứng minh thì phải nhìn vào phần thân của algo và chỉ ra được là sau mỗi lần loop là nó giữ một cái invariant gì đó dẫn đến kết quả đúng, kể cả khi graph A hoặc B disconnected, nhưng cảm ơn bạn đã dành thời gian

mà nghĩ kĩ, tốn thời gian đi chứng minh làm gì, vì luyện leetcode đâu phải để giỏi CS 😔
Click to expand...
Nếu mà đồ thị không liên thông thì sẽ trả ra kết quả -1 luôn.
Bạn nói đúng đấy. Theo đúng quy trình thì phải chứng minh như thế.
Việc chứng minh tính đúng đắn của thuật toán rất quan trọng đó bạn, làm như thế thì mới nhanh tiến bộ.
 
Konstante said:
mình trình bày một cài đặt sử dụng kỹ thuật continuation rất hay gặp trong functional programming:
Code: 
let oddEventList xs =
    let rec pickcps xs k =
        match xs with
        | x :: x' :: xs'' -> pickcps xs'' (fun (os, es) -> k (x :: os, x' :: es))
        | x :: _ -> pickcps [] (fun (os, es) -> k (x :: os, es))
        | _ -> ([], []) |> k |> (fun (a, b) -> a @ b)

    pickcps xs id
Click to expand...
Cảm ơn bạn. Qua đây, mình biết thêm về CPS, mà đúng như bạn nói, hay gặp trong compiler của các functional language hơn. Và từ đó, cũng hiểu sâu thêm cơ chế hoạt động của computation expression trong F#.

Konstante said:
Bài này thì tư tưởng tail recursion quá rõ ràng nên một cách khác đơn giản hơn như sau:
Code: 
let oddEvenList xs =
    let rec pick (os, es) xs p =
        match xs, p with
        | x :: xs', true -> pick (x :: os, es) xs' false
        | x :: xs', false -> pick (os, x :: es) xs' true
        | _ -> es @ os |> List.rev

    pick ([], []) xs true
Chỉ cần thêm memory space cho đúng một biến bool (là p), nên SC = O(1).
Click to expand...
Bạn nào muốn tìm hiểu thêm về accumulator & tail recursion, dùng ví dụ bằng F#

Tail Recurse

Tips on refactoring recursive functions to tail-recursive functions.
blog.ploeh.dk blog.ploeh.dk
và với sự góp mặt của compiler
learn.microsoft.com

Tail calls in F#

learn.microsoft.com

Konstante said:
Cách cài đặt trên có thể chuyển thành single-line function bằng cách dùng List.fold, như sau:
Code: 
let oddEventList<'t> =
    List.fold (fun (os, es, p) x ->
        if p then (x :: os, es, not p)
        else (os, x :: es, not p)) ([], [], true)
    >> (fun (a, b, _) -> b @ a |> List.rev)
Click to expand...
Mình cho rằng one-liner với List.fold như vậy có phần khiên cưỡng, tuy cho kết quả đúng nhưng giảm đi tính readability. Vầy có lẽ trong sáng hơn

Code: 
let oddEventList<'t> =
    List.fold (fun (os, es, p) x ->
        if p then (x :: os, es, not p)
        else (os, x :: es, not p)) ([], [], true)
    >> fun (a, b, _) -> b @ a
    >> List.rev

hoặc

Code: 
let oddEventList<'t> list =
    list
    |> List.fold (fun (os, es, p) x ->
        if p then (x :: os, es, not p)
        else (os, x :: es, not p)) ([], [], true)
    |> fun (a, b, _) -> b @ a
    |> List.rev

Tuy nhiên, trong trường hợp này, dùng pattern matching như ban đầu có vẻ dễ đọc nhất.

Konstante said:
Cách cài đặt này không thỏa mãn ràng buộc O(1) space, ngoài ra còn quá phức tạp (sử dụng fancy functions không cần thiết).
Click to expand...
Đồng ý với nhận xét trên trong context của LeetCode với ràng buộc optimization.
 
Last edited:
Python: 
class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        auf = UF(n)
        buf = UF(n)
        needed_edges = 0
        for t, v1, v2 in edges:
            if t == 3:
                needed_edges +=  auf.union(v1, v2) | buf.union(v1, v2)
        for t, v1, v2 in edges:
            if t == 1:
                needed_edges += auf.union(v1, v2)
            elif t == 2:
                needed_edges += buf.union(v1, v2)
     
        if auf.is_completed() and buf.is_completed():
            return len(edges) - needed_edges
        return -1
class UF:
    def __init__(self, size):
        self.rep = [i for i in range(size + 1)]
        self.rank = [ 1 for _ in range(size + 1)]
        self.total_edges = size - 1
 
    def is_completed(self):
        return self.total_edges == 0
    def find(self, node):
        if node != self.rep[node]:
            self.rep[node] = self.find(self.rep[node])
     
        return self.rep[node]
 
    def union(self, node1, node2):
        rep1 = self.find(node1)
        rep2 = self.find(node2)
        if rep1 != rep2:
            if self.rank[rep1] < self.rank[rep2]:
                self.rep[rep1] = rep2
            elif self.rank[rep1] > self.rank[rep2]:
                self.rep[rep2] = rep1
            else:
                self.rep[rep2] = rep1
                self.rank[rep1] += 1
            self.total_edges -= 1
            return 1
        else:
            return 0
 
PHP: 
class Solution {

    /**
     * @param Integer[] $arr
     * @return Boolean
     */
    function threeConsecutiveOdds($arr) {
        for ($i=0; $i<=count($arr)-3; $i++) {
            if ($arr[$i] % 2 == 0) continue;
            if ($arr[$i+1] % 2 == 0) continue;
            if ($arr[$i+2] % 2 == 0) continue;

            return true;
        }

        return false;
    }
}
 
Python: 
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        for i in range(len(arr) - 2):
            if arr[i] % 2 + arr[i + 1] % 2 + arr[i + 2] %2 ==3 :
                return True
        return False

Note : Bài nay dễ chắc anh em bỏ qua hết rồi :beat_brick:
 
Bài dễ nhưng mấy solution bên trên đều dính lỗi kiểm tra parity của một phần tử nhiều lần.

C-like: 
impl Solution {
    pub fn three_consecutive_odds(arr: Vec<i32>) -> bool {
        let is_odd = |i: usize| { arr[i] & 1 == 1 };
      
        let mut i = 2;
        while i < arr.len() {
            if !is_odd(i) {
                i += 3;
                continue;
            }
            if !is_odd(i - 1) {
                i += 2;
                continue;
            }
            if !is_odd(i - 2) {
                i += 1;
                continue;
            }
            return true;
        }
        return false;
    }
}
 
Last edited:
Bài Weekly Premium hôm nay là phiên bản dễ hơn của bài Daily hôm qua. Nếu anh em không có Premium mà muốn làm thì đây là đề bài.

1719800634583.png
 
Swift: 
class Solution {
    func threeConsecutiveOdds(_ arr: [Int]) -> Bool {
        var countOdds = 0
        for num in arr {
            if num%2==0 {
                countOdds = 0
            } else {
                if countOdds == 2 {
                    return true
                }
                countOdds += 1
            }
        }
        return false
    }
}
 

Similar threads

nhbin
kiến thức Kèo Watch to earn 5p mỗi ngày $EVERY gọi vốn $60M từ A16Z, Coinbase, DragonFly
Replies
0
Views
103
nhbin
nhbin
Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
639
heocon0123
heocon0123
MasterchiefsReborn
Sinh viên than kiến tập mà làm việc không kịp ăn
2 3
Replies
47
Views
3K
OneThing
OneThing
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
164
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
17
Views
445
truonggiang!
T

Share this page

Back
Top