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

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
 
...Batman... said:
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
Click to expand...
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
 
_Gia_Cat_Luong_ said:
  • 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
Click to expand...

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ả.
 
bribnt said:
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ả.
Click to expand...
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.
 
_Gia_Cat_Luong_ said:
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.
Click to expand...
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
 
_Gia_Cat_Luong_ said:
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.
Click to expand...

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.
 
_Gia_Cat_Luong_ said:
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.
Click to expand...
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_ said:
Hong hiểu lắm fen ơi. Giải thích idea với...
Click to expand...

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.
 
_Gia_Cat_Luong_ said:
Hong hiểu lắm fen ơi. Giải thích idea với...
Click to expand...
ý 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:
 
tdat00 said:
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
Click to expand...
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
 
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
 

Similar threads

buiduchanh1995
thắc mắc Cách thiết kế database cho hệ thống lớn
2
Replies
37
Views
3K
khonganhit19
khonganhit19
meekoo
thắc mắc [Hỏi AI] Cách làm sao để train AI hiểu một task nào đấy?
Replies
9
Views
969
weed_bông
weed_bông
IM LANG
thắc mắc Cần cao nhân giúp đỡ về WordPress (có sử dụng custom theme bằng HTML, CSS)
Replies
3
Views
289
zaizai_vjp
zaizai_vjp
quangpt12345
kiến thức Join Anchor Consortium trading crypto sàn Odyssey kiếm lợi nhuận 2-3% mỗi ngày
Replies
2
Views
121
quangpt12345
quangpt12345
J
kiến thức Mod Mộng Liêu Trai mới nhất
Replies
0
Views
81
jivrus
J

Share this page

Back
Top