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

_Gia_Cat_Luong_

Senior Member

12/07/2022​


#473. (Medium) Matchsticks to Square

Phân tích bài toán:
  • Vì mỗi que diêm có chiều dài là số nguyên, nên dễ thấy cạnh hình vuông cần tạo thành cũng sẽ là số nguyên
  • Đồng thời, cạnh này sẽ có chiều dài là tổng của tất cả que diêm chia 4. Dĩ nhiên nếu tổng này không chia hết cho 4 thì đáp án mặc định là False
  • Vậy, để tạo ra một cạnh hình vuông ta cần lựa ra một tập các que diêm sao cho tổng của chúng bằng chiều dài cạnh đã tìm
  • Sau đó, chúng ta sẽ tìm 3 cạnh còn lại từ các que diêm bằng phương pháp tương tự
  • Nói cách khác, bài toán trở thành phân các que diêm thành 4 tập con sao cho tổng của mỗi tập đúng bằng cạnh cần tìm

  • Giả sử như ta chỉ cần tìm một cạnh, dễ thấy đây là bài toán kinh điển, tìm tập con có tổng bằng k mà ta đã biết cách giải bằng QHĐ.
  • Mỗi khi chọn xong một cạnh, ta lại thực hiện thuật toán tương tự để tìm cho các cạnh còn lại, tuy nhiên ta phải loại trừ các que đã chọn trước đó ra
  • Để lưu trữ và kiểm tra xem một que đã được chọn hay chưa, ta có thể dùng bitmask vì trong bài này số lượng tối đa của các que diêm chỉ có 16.
  • Tối ưu thêm một chút, dễ thấy ta chỉ cần tìm 3 cạnh thay vì cả 4 cạnh, vì cạnh còn lại mặc nhiên sẽ đúng.

Code:
https://leetcode.com/submissions/detail/744754269/

Nhận xét:
  • Solution này có độ phức tạp O(3^n) vì mỗi que diêm có 3 lựa chọn thuộc về 3 cạnh
  • Tuy nhiên, kết hợp với bitmask độ phức tạp suy biến về O(3*2^n) ~ O(2^n) vì mỗi cạnh chỉ còn 2 lựa chọn, không quan tâm nó thuộc về cạnh nào.
 

the_gioi_that_dep

Junior Member
Bài que diêm hôm nay mà độ khó medium thì hơi ảo nhỉ :sweat:. À sẵn tiện bác nào redeem cái Tshirt chưa em hỏi quy trình thủ tục có gì phức tạp không?? Cái acc từ lâu không để ý nay vào thấy còn thiếu mấy trăm nữa là được 6k :feel_good:

via theNEXTvoz for iPhone
 

the_gioi_that_dep

Junior Member
codeforces thì hơn leetcode nhiều ko nhỉ, em thấy nhiều nơi tuyển ưu tiên rank cao codeforces, topcoder
Codeforces nó cho dân chuyên CP rồi bác, món đấy đau đầu hơn Leet. :ops: 2k6 tương đương Grandmaster Codeforces(nếu em nhớ không nhầm), của ông kia mà sang Leet thì cứ phải gọi là "ao chình" kha khá :((

via theNEXTvoz for iPhone
 

bribnt

Đã tốn tiền
  • Vậy, để tạo ra một cạnh hình vuông ta cần lựa ra một tập các que diêm sao cho tổng của chúng bằng chiều dài cạnh đã tìm
  • Sau đó, chúng ta sẽ tìm 3 cạnh còn lại từ các que diêm bằng phương pháp tương tự
  • Nói cách khác, bài toán trở thành phân các que diêm thành 4 tập con sao cho tổng của mỗi tập đúng bằng cạnh cần tìm

Cũng đã thử hướng này nhưng sai ở case [3 3 3 3 4 4 4 4 5 5 5 5]. Giả sử nếu tìm được một tập có tổng bằng S/4 = 12, ví dụ như {4, 4, 4} thì phần còn lại không có cách nào để chia đều thành 3 tập con cả.
 

_Gia_Cat_Luong_

Senior Member
Cũng đã thử hướng này nhưng sai ở case [3 3 3 3 4 4 4 4 5 5 5 5]. Giả sử nếu tìm được một tập có tổng bằng S/4 = 12, ví dụ như {4, 4, 4} thì phần còn lại không có cách nào để chia đều thành 3 tập con cả.
Chính xác, có nhiều cách để lựa chọn tập đầu tiên có tổng bằng 12, bài toán chính là tìm ra cách sao cho phần còn lại cũng có thể phân thành 3 tập có tổng bằng 12. Btw, bài này mà medium thì hơi ảo :v.
 

the_gioi_that_dep

Junior Member
Chính xác, có nhiều cách để lựa chọn tập đầu tiên có tổng bằng 12, bài toán chính là tìm ra cách sao cho phần còn lại cũng có thể phân thành 3 tập có tổng bằng 12. Btw, bài này mà medium thì hơi ảo :v.
Nãy em mới lướt qua chợ việc làm thấy bác/anh giới thiệu đang làm tech lead. Vậy mà vẫn luyện leetcode mỗi ngày thì quả là siêng thật. Công việc có yêu cẩu thuật toán nhiều không anh/bác?? :misdoubt:

via theNEXTvoz for iPhone
 

bribnt

Đã tốn tiền
Chính xác, có nhiều cách để lựa chọn tập đầu tiên có tổng bằng 12, bài toán chính là tìm ra cách sao cho phần còn lại cũng có thể phân thành 3 tập có tổng bằng 12. Btw, bài này mà medium thì hơi ảo :v.

Backtrack cho đơn giản:

1657643960644.png


https://leetcode.com/submissions/detail/745323602/

Hai trick chính để giảm số nhánh là:
  • Sort từ lớn đến bé. Khi đó tổng tích lũy sẽ tăng nhanh để vượt quá độ dài cần thiết ==> bị ngắt sớm,
  • Ở mỗi lần backtrack với 4 nhóm chỉ test tiếp những nhóm có tổng tích lũy khác nhau.
Đã thử dùng thêm cache nhưng lại càng chậm hơn. Có lẽ vì những cách trên đã giảm số lượt tìm kiếm và số lần lặp quá nhiều rồi nên chi phí search/insert cache lại lớn hơn lợi ích.
 

Zayt__

Senior Member
Chính xác, có nhiều cách để lựa chọn tập đầu tiên có tổng bằng 12, bài toán chính là tìm ra cách sao cho phần còn lại cũng có thể phân thành 3 tập có tổng bằng 12. Btw, bài này mà medium thì hơi ảo :v.
Bài này code non tay quá nên fail nhiều : 1 lần hiểu sai đề như này + 1 lần cache lắm nên MLE + 1 lần ko cache TLE, lần 4 dùng mảng với cắt bớt nhánh mới được
4gmOAMB.png
 

_Gia_Cat_Luong_

Senior Member
Bài này code non tay quá nên fail nhiều : 1 lần hiểu sai đề như này + 1 lần cache lắm nên MLE + 1 lần ko cache TLE, lần 4 dùng mảng với cắt bớt nhánh mới được
4gmOAMB.png
chắc cũng thuộc top bài medium chua nhất cmnr
 

bribnt

Đã tốn tiền
Hong hiểu lắm fen ơi. Giải thích idea với...

Thì cũng giống như những cách backtracking khác. Chỉ là chuyển sang BFS.
  • bfs là mảng lưu tất cả các bộ-4 độ dài các cạnh khi duyệt đến stick hiện tại,
  • Với mỗi stick mới thì thử thêm nó vào một trong số các cạnh của các bộ-4,
  • Tất nhiên cũng có các kỹ thuật để giảm số bộ-4 phải thêm vào. VD như sort rồi so sánh để đảm bảo unique.
 
Hong hiểu lắm fen ơi. Giải thích idea với...
ý tưởng dựa trên bfs đó fen.

Mỗi node sẽ là 1 cái array gồm 4 phần tử, tương ứng với 4 nhóm.
1 matchstick thì sẽ được chia cho 4 nhóm => 1 node cha thì sẽ có 4 node code con.
Tất nhiên phải áp dụng thêm 1 số trick để giảm thiểu số lượng cần visit xuống nhỏ nhất mà k làm sai kq.
VD: node hiện tại là [0,0,0,0] thì chỉ cần visit node tiếp [x,0,0,0] thôi, mấy node con còn lại k cần visit.

Cách này k nó sẽ k tối ưu bằng mấy cách bên trên của mấy fen đâu, chỉ là cung cấp 1 cái nhìn khác thôi, :big_smile:
 

ngoctan_95

Senior Member
Bài sáng nay chắc đua xem ai có code sáng tạo nhất nhỉ :D Tôi chỉ biết mỗi cách DFS hoặc dùng Queue. Có thím nào dùng cách khác không?

https://leetcode.com/submissions/detail/745635662/

Sent from Samsung SM-A528B using vozFApp
Mình dùng đệ quy DFS, mất gần 1 tiếng hơn để test failed cases
  • Loại bỏ case null thì trả về empty (1)
  • Bắt đầu từ empty data, index = 0, chèn lần lượt node (2)
  • Kiểm tra các giá trị node trái và phải theo vị trí index + 1, nếu khác null mới process lặp lại (2)
// Gần hơn tuần chưa vô box, nhưng vẫn giải bài trong challenges hàng ngày : )))
Screen Shot 2022-07-13 at 11.52.30.png
 
Top