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

Kân team v3 · 17/9/22

randomA đã nói:
Xác nhận là cái test case này làm TLE tất cả các cách nhé. Trie cũng chết nốt. Trie còn chậm hơn HashMap trừ khi Trie là nhiều ký tự trở lên ở mỗi level thì tui chưa thử.

vậy là thằng ra đề LC dỏm

cái test case 1.4MB có submit nổi cho LC test case đâu

bribnt · 17/9/22

Trie + Manacher chuẩn O(nk) không sợ các loại test case.
https://leetcode.com/submissions/detail/801992042/

Ý tưởng là dùng thuật toán Manacher để tính trước tất cả các palindrome dạng [0, i) với mọi word trong thời gian O(k), để khỏi phải check palindrome mỗi lần O(k^2).

Ở đây có cải biên Manacher một chút là chỉ duyệt đến nửa chuỗi, nếu tính được d tràn chuỗi thì coi như đoạn [0, i) là palindrome.

Nhưng vẫn chậm. Dù đã dùng pool các trie node để để hạn chế cấp phát động.

Kân team v3 đã nói:
thử 4700 words length 300 và 300 words len từ 0-299 của bác bribnt chưa

cũng vậy thoy hack quá

ví dụ toy generate từ test case 135 nè:

Trie + Manacher mất khoảng 544ms với test này. Chắc vẫn suýt soát AC.

crushkydvn · 17/9/22

bribnt đã nói:
Trie + Manacher chuẩn O(nk) không sợ các loại test case.
https://leetcode.com/submissions/detail/801992042/

Ý tưởng là dùng thuật toán Manacher để tính trước tất cả các palindrome dạng [0, i) với mọi word trong thời gian O(k), để khỏi phải check palindrome mỗi lần O(k^2).

Ở đây có cải biên Manacher một chút là chỉ duyệt đến nửa chuỗi, nếu tính được d tràn chuỗi thì coi như đoạn [0, i) là palindrome.

Nhưng vẫn chậm. Dù đã dùng pool các trie node để để hạn chế cấp phát động.

Trie + Manacher mất khoảng 544ms với test này. Chắc vẫn suýt soát AC.

Nhìn code bác khiếp thế @@ Còn cách nào đơn giản hơn không bác :v

bribnt · 17/9/22

Tiện thể thì các kết quả 100 - 200ms bên C++ là từ thời xưa, giờ cập nhất test case rồi chạy lại sẽ chậm hơn rất nhiều.

crushkydvn đã nói:
Nhìn code bác khiếp thế @@ Còn cách nào đơn giản hơn không bác :v

Dùng cách của các bác trên kia nhé.
Cả Trie lẫn thuật toán Manacher chả có cái nào là code đơn giản hết. Phải debug mấy tiếng mới xong.

Aristides · 17/9/22

đây mới đúng là bài hard này

cơ mà trư bó tay

Lại xem đáp án thôi

sau_tim_thiep_hong · 17/9/22

bribnt đã nói:
Trie + Manacher chuẩn O(nk) không sợ các loại test case.
https://leetcode.com/submissions/detail/801992042/

Ý tưởng là dùng thuật toán Manacher để tính trước tất cả các palindrome dạng [0, i) với mọi word trong thời gian O(k), để khỏi phải check palindrome mỗi lần O(k^2).

Ở đây có cải biên Manacher một chút là chỉ duyệt đến nửa chuỗi, nếu tính được d tràn chuỗi thì coi như đoạn [0, i) là palindrome.

Nhưng vẫn chậm. Dù đã dùng pool các trie node để để hạn chế cấp phát động.

Trie + Manacher mất khoảng 544ms với test này. Chắc vẫn suýt soát AC.

thế giới của CP là đây à

nhìn khiếp thật

Kân team v3 · 18/9/22

bribnt đã nói:
Trie + Manacher chuẩn O(nk) không sợ các loại test case.
https://leetcode.com/submissions/detail/801992042/

Ý tưởng là dùng thuật toán Manacher để tính trước tất cả các palindrome dạng [0, i) với mọi word trong thời gian O(k), để khỏi phải check palindrome mỗi lần O(k^2).

Ở đây có cải biên Manacher một chút là chỉ duyệt đến nửa chuỗi, nếu tính được d tràn chuỗi thì coi như đoạn [0, i) là palindrome.

Nhưng vẫn chậm. Dù đã dùng pool các trie node để để hạn chế cấp phát động.

Trie + Manacher mất khoảng 544ms với test này. Chắc vẫn suýt soát AC.

185 dòng thoy xài cách hack kia thoy

Lập Trình Viên Số Khổ · 18/9/22

C4 1000 ^ 2 mà ko pass, cay :ah:

Violet_7 · 18/9/22

Lập Trình Viên Số Khổ đã nói:
C4 1000 ^ 2 mà ko pass, cay

Đề hôm nay dễ 30p là xong, mà cay c3 làm mất chục phút ngu ko là rank cao hơn r

Arik97 · 18/9/22

Cay thế nhở :canny:

C4 ngồi mân mê đủ kiểu vẫn ko qua đc. Toàn bị hidden test case?
https://leetcode.com/contest/weekly-contest-311/submissions/detail/802578571/

bribnt · 18/9/22

Kân team v3 đã nói:
185 dòng thoy xài cách hack kia thoy

Hơi muộn nhưng vừa nghĩ cách khác ~~cũng O(nk)~~ nhưng đơn giản hơn dùng Hash chứ không phải Trie.
Để ý thấy những lần tính hash toàn là của những substring khác nhau mỗi ký tự cuối. Nên có thể tận dụng để tính lại hash của substring sau dựa vào cái trước trong O(1).

----
Edited: quên mất vẫn còn phải check key equal nên vẫn là O(nk^2), nhưng đỡ được phần tính hash là có cải thiện rồi.

Kân team v3 · 18/9/22

bribnt đã nói:
Hơi muộn nhưng vừa nghĩ cách khác cũng O(nk) nhưng đơn giản hơn dùng Hash chứ không phải Trie.
Để ý thấy những lần tính hash toàn là của những substring khác nhau mỗi ký tự cuối. Nên có thể tận dụng để tính lại hash của substring sau dựa vào cái trước trong O(1).

có chắc là hash ko trùng nhau ko

mà cái implement O(nk) kia có chắc là O(nk) ko 5000 x 300 = 1.5e6 đáng lẽ chạy vài chục tới 100ms thoy chứ

bribnt · 18/9/22

Kân team v3 đã nói:
có chắc là hash ko trùng nhau ko

mà cái implement O(nk) kia có chắc là O(nk) ko 5000 x 300 = 1.5e6 đáng lẽ chạy vài chục tới 100ms thoy chứ

Edit rồi, kể cả hash ko trùng thì vẫn phải có bước compare key nên vẫn mất O(nk^2). Nhưng đỡ được phần tính hash là có cải thiện rồi.

Trie đúng là O(nk) nhưng miss cache nhiều quá nên chậm, nên mới nghĩ cách xài hash.

Kân team v3 · 18/9/22

bribnt đã nói:
Edit rồi, kể cả hash ko trùng thì vẫn phải có bước compare key nên vẫn mất O(nk^2). Nhưng đỡ được phần tính hash là có cải thiện rồi.

Trie đúng là O(nk) nhưng miss cache nhiều quá nên chậm, nên mới nghĩ cách xài hash.

nếu hash ko trùng thì có thể làm cái hash map có key là hash value/uint64_t thoy chứ ko cần key là string. Check string có trong hmap bằng cách check hash của string đó có trong hmap hay ko, so sánh uint64_t thì O(1) ngon lành ròi. Mà làm xao hash ko trùng được

có thể có cách tạo hash ko trùng được bằng cách lấy địa chỉ của chuỗi đó trong trie làm hash, nhưng làm vậy thì phải build trie cũng như ko ròi

~~à có thể tốn bước build thoy còn mấy bước tìm kiếm sau đỡ phải miss cache gì đó~~

à mà để tính hash value của 1 string thì cũng phải duyệt trong trie cũng như ko

nói chung tạo trie là tương đương tạo unique hash cho mấy substring ròi

NudeDuck · 18/9/22

contest nay dễ thế nhỉ, Cơ mà sao câu cuối làm hash bị TLE nhỉ, là O(nm) = O(10^6) mà

JAPAN GLOBAL · 18/9/22

Các bác trình độ cao thế này sao không qua nước ngoài làm ạ. Thiết nghĩ giải được khoảng 50 bài Hard Leetcode thì có thể sang nước ngoài làm rồi chứ nhỉ.

Lập Trình Viên Số Khổ · 18/9/22

NudeDuck đã nói:
contest nay dễ thế nhỉ, Cơ mà sao câu cuối làm hash bị TLE nhỉ, là O(nm) = O(10^6) mà

thế mới khó hiểu

JUchi · 18/9/22

JAPAN GLOBAL đã nói:
Các bác trình độ cao thế này sao không qua nước ngoài làm ạ. Thiết nghĩ giải được khoảng 50 bài Hard Leetcode thì có thể sang nước ngoài làm rồi chứ nhỉ.

Vợ con bỏ lại cho ai?
Bố mẹ bỏ lại cho ai?
Sốc văn hóa?
Ở nước ngoài chắc gì đã ngon hơn ở Việt Nam đâu bạn

Violet_7 · 18/9/22

Arik97 đã nói:
Cay thế nhở
C4 ngồi mân mê đủ kiểu vẫn ko qua đc. Toàn bị hidden test case?
https://leetcode.com/contest/weekly-contest-311/submissions/detail/802578571/

time map cho 1 string là độ dài string đó, mình nghĩ v.

bribnt · 18/9/22

Lập Trình Viên Số Khổ đã nói:
thế mới khó hiểu

NudeDuck đã nói:
contest nay dễ thế nhỉ, Cơ mà sao câu cuối làm hash bị TLE nhỉ, là O(nm) = O(10^6) mà

Tại vì nó bản chất là O(nm^2)
Các fen nên đọc kỹ lại về hàm hash và cách implement hash map.

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

Senior Member

Đã tốn tiền

Senior Member

Đã tốn tiền

Senior Member

Member

Senior Member

Senior Member

Member

Senior Member

Đã tốn tiền

Senior Member

Đã tốn tiền

Senior Member

Junior Member

Junior Member

Senior Member

Senior Member

Member

Đã tốn tiền

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này