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

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
 

bribnt

Đã tốn tiền
Mình nghĩ là vừa phát hiện được một bí ẩn của hệ thống Leetcode để giải thích cho hiện tượng submit nhiều lần có thời gian khác nhau.

Lúc nãy thử optimize bằng AVX512 bài Que diêm, build bình thường. Nhưng khi bấm Run Code thì lúc bị SIGILL, lúc thì ra được kết quả.
SIGILL là lỗi thường xảy ra khi chương trình chạy một Illegal Instruction (tập lệnh mà CPU không hỗ trợ).

Điều này có nghĩa là: Leetcode có thể sử dụng nhiều server để chạy code. Nhưng các server này lại dùng CPU khác nhau. Ở đây vừa dùng server hỗ trợ AVX512, vừa dùng server không hỗ trợ.

---

Bonus thêm lời giải 0ms faster than 100% của bài Que diêm.
Vẫn là cách backtrack ở trên nhưng dùng SIMD (AVX512 và SSE4.1) để thực hiện các phép so sánh.

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

1657702047591.png
 
Top