thảo luận Leetcode contest, đường tới Guardian

Cố Trường Ca · 14/9/24

nahnahinin đã nói:
em vô danh tiểu tốt chứ clone ai đâu, vô voz nhìn cụ Cố Ca thiên long nhân cũng phải phấn đầu bằng 1 góc thôi, bác là động lực của em mà

freedom.9 · 14/9/24

anoldvozer1710.v2 đã nói:
hoá ra là câu 4 dễ hơn, mình nhìn đề tưởng khó hơn lại ko làm nữa đi xem đá bóng

lướt solution thấy có cha nào bảo đây là Google OA, fency @freedom.9 ko làm đc thì sao đi pv

Q4 tìm LIS thôi fence, Q3 nhìn sai constrain giải sai hướng ngay từ đầu nên bug sml =((

hiếu thứ tha · 15/9/24

có cách gì để giỏi hơn không ạ, em làm được đúng 1 câu contest

freedom.9 · 15/9/24

anoldvozer1710.v2 đã nói:
hoá ra là câu 4 dễ hơn, mình nhìn đề tưởng khó hơn lại ko làm nữa đi xem đá bóng

lướt solution thấy có cha nào bảo đây là Google OA, fency @freedom.9 ko làm đc thì sao đi pv

https://leetcode.com/u/LarryNY/

Rating 2k8 rụng Q3 như thường :ah:

, hay xem youtube thanh niên này chạy DP nên bài này sai y hệt luôn, lúc đầu vô chạy DP top down ăn bugs vl =((

lilleboybk · 15/9/24

hiếu thứ tha đã nói:
có cách gì để giỏi hơn không ạ, em làm được đúng 1 câu contest

Bác dùng cái virtual contest để thi thử mấy contest trước đó ấy, có ranking của mọi người và của mình thời gian thực luôn. Thi xong thì đọc solution rồi thi thử lại.

lovelyly · 15/9/24

Ủa sáng nay không ai làm contest à :eek:

Tuần trước vào muộn giờ contest bì trừ điểm, tuần này có vẻ gỡ lại được

garanphomai · 15/9/24

Làm dc mỗi câu 1

freedom.9 · 15/9/24

Lùm mé cái câu 5*10^3 giải On^2 éo pass phải xài tới trie, súc vật

thanhdonguyen01 · 15/9/24

freedom.9 đã nói:
Lùm mé cái câu 5*10^3 giải On^2 éo pass phải xài tới trie, súc vật
Xem tệp đính kèm 2684310

Chơi hash còn bị WA thím ạ, quay đi quay lại Trie thì pass :beat_brick:

lovelyly · 15/9/24

freedom.9 đã nói:
Lùm mé cái câu 5*10^3 giải On^2 éo pass phải xài tới trie, súc vật
Xem tệp đính kèm 2684310

T chưa thử trie, nãy dùng binary search tìm chuỗi word gần giống chuỗi trong target nhất để qua Q3, còn Q4 thì thôi :bye:

lilleboybk · 15/9/24

freedom.9 đã nói:
Lùm mé cái câu 5*10^3 giải On^2 éo pass phải xài tới trie, súc vật
Xem tệp đính kèm 2684310

Em giống 2 bác, cách của bác là O(n * n * log (sum_word_len ) ấy. Sau em lại dùng Trie mới pass Q3. Q4 trie TLE vì gặp testcase target và 1 xâu trong word toàn ký tự giống nhau ấy.

freedom.9 · 15/9/24

Q4 xài bottom up + trie vẫn tạch 7 test cases =((

ngày gì toàn TLE MLE :ah:

lilleboybk · 15/9/24

freedom.9 đã nói:
Q4 xài bottom up + trie vẫn tạch 7 test cases ngày gì toàn TLE MLE

Bác thử TC này xem: target = 'a' * 50000, words = ['a' * 50000]. Ăn thế nào được bác.

freedom.9 · 15/9/24

lilleboybk đã nói:
Em giống 2 bác, cách của bác là O(n * n * log (sum_word_len ) ấy. Sau em lại dùng Trie mới pass Q3. Q4 trie TLE vì gặp testcase target và 1 xâu trong word toàn ký tự giống nhau ấy.

Nếu build prefix set thì time complexity là O(100*5*10^3) thôi chứ fence nhỉ, còn dp là O(n^2) sao nó vẫn TLE
Mình phải optimize mạnh nó mới ăn, cay thật

lilleboybk · 15/9/24

freedom.9 đã nói:
Nếu build prefix set thì time complexity là O(100*5*10^3) thôi chứ fence nhỉ, còn dp là O(n^2) sao nó vẫn TLE
Mình phải optimize mạnh nó mới ăn, cay thật

Lúc dp, kiểm tra mỗi xâu con có trong prefix Sét không mất thêm log (100000) ấy bác.

thanhdonguyen01 · 15/9/24

Thấy sol bọn nó chơi Z algo mới pass

1 số thì chơi hash được :sad:

Bọn nó hash thì AC, e hash thì WA mấy test cuối :too_sad:

N^2 thì lên 25 * 10^8 rồi thím, sống sao được :beat_brick:

freedom.9 đã nói:
Nếu build prefix set thì time complexity là O(100*5*10^3) thôi chứ fence nhỉ, còn dp là O(n^2) sao nó vẫn TLE
Mình phải optimize mạnh nó mới ăn, cay thật

1 <= target.length <= 5 * 104

freedom.9 · 15/9/24

lilleboybk đã nói:
Lúc dp, kiểm tra mỗi xâu con có trong prefix Sét không mất thêm log (100000) ấy bác.

Cứ nghĩ nó là O(1) ai ngờ nó là Log =((

Panic quá ko nghĩ ra fence, chỉ nghĩ là đi optimize cái vòng loop cho nó early break là ăn. Đổi qua C++ cũng ko ăn.
Nhớ ra có cái Trie rồi trả về cái pointer của mỗi node là ăn ngon lành rồi =((

freedom.9 · 15/9/24

thanhdonguyen01 đã nói:
Thấy sol bọn nó chơi Z algo mới pass

1 số thì chơi hash được
Bọn nó hash thì AC, e hash thì WA mấy test cuối

N^2 thì lên 25 * 10^8 rồi thím, sống sao được

1 <= target.length <= 5 * 104

Mình đang nói Q3 đó fence, Q4 thì ko pass chắc rồi mà ko biết tụi nó xài z function sao. Để đi đọc đã =((

thanhdonguyen01 · 15/9/24

freedom.9 đã nói:
Mình đang nói Q3 đó fence, Q4 thì ko pass chắc rồi mà ko biết tụi nó xài z function sao. Để đi đọc đã

Cái set nó k đến O(log n) như của bọn C++, nhưng k hoàn toàn O(1):

cpython/Objects/setobject.c at main · python/cpython

The Python programming language. Contribute to python/cpython development by creating an account on GitHub.

github.com

Thím check cái đoạn kiểm tra contain ấy, nó look up key như kiểu look up 1 cái dictionary, nên O(1) của nó ít nhất cũng nhân với 1 cái hệ số rồi :shame:

Chơi trie ở đây là an toàn nhất :shame:

freedom.9 · 15/9/24

thanhdonguyen01 đã nói:
Cái set nó k đến O(log n) như của bọn C++, nhưng k hoàn toàn O(1):

cpython/Objects/setobject.c at main · python/cpython

The Python programming language. Contribute to python/cpython development by creating an account on GitHub.

github.com

Thím check cái đoạn kiểm tra contain ấy, nó look up key như kiểu look up 1 cái dictionary, nên O(1) của nó ít nhất cũng nhân với 1 cái hệ số rồi
Chơi trie ở đây là an toàn nhất

Thật, ngu vãi. Ăn 7 cái bugs trừ mẹ 35 phút :ah:

Lần sau cứ prefix là xài Trie đầu tiên éo nói nhiều =((

thảo luận Leetcode contest, đường tới Guardian

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này