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

seastar · 14/1/24

freedom.9 đã nói:
Python:

class Solution: bIndexes = [index for index in range(len(s)) if s.startswith(b, index)] aIndexes = [index for index in range(len(s)) if s.startswith(a, index)]

Bài 4 dùng 2 binary search sao lại TLE nhỉ? O(nlogn) mà

Đoạn độ phức tạp là m*n . Phải dùng KMP để giảm xuống còn n + m.
Bài này mới coi lại thấy sai xàm vkl ra, :ah:

freedom.9 · 14/1/24

seastar đã nói:
Đoạn độ phức tạp là m*n . Phải dùng KMP để giảm xuống còn n + m.
Bài này mới coi lại thấy sai xàm vkl ra,

Cái đệch mẹ nhà nó cay vãi :beat_brick:

ko để ý tưởng là O(m + n) KMP là gì thế các fence :gach:

Mà ngồi viết binary search ngu như lợn huhu, ngồi giải bài 2 bằng binary search mất mẹ cả tiếng đồng hồ =((

contests này lại nát rồi huhu

seastar · 14/1/24

freedom.9 đã nói:
Cái đệch mẹ nhà nó cay vãi ko để ý tưởng là O(m + n) KMP là gì thế các fence
Mà ngồi viết binary search ngu như lợn huhu, ngồi giải bài 2 bằng binary search mất mẹ cả tiếng đồng hồ contests này lại nát rồi huhu

KMP thì đọc ở đây:

KMP Algorithm for Pattern Searching - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

Loay hoay làm bài 3 lâu quá mà k ra. Nhảy qua bài 4 lúc sắp hết giờ, nhìn lướt qua là biết dùng KMP rồi. Sửa lại bài 2, add thêm cái KMP vào mà quên k xóa cái dòng seach m*n ở bài 2 đi, làm nó bị timeout error, lỗi sơ đẳng quá, cay vkl, :ah:

freedom.9 · 14/1/24

Lmao cái bài 2, ngồi loay hoay cái binary search cứ tìm left right mãi sai tùm lum. Brute force phát ra luôn =))

))))
Thi contest đúng kiểu rèn interview, panic quá là éo nghĩ ra cái gì. Chuyển xuống bài 4 tâm lí thoải mái ngồi ngẫm lại viết đúng binary search cứ tưởng O((m + n) log n) hí hửng ăn cmnr thì ai ngờ là O(m*nlogn) như cái cục cức :ah:

seastar · 14/1/24

freedom.9 đã nói:
Xem tệp đính kèm 2287978
Lmao cái bài 2, ngồi loay hoay cái binary search cứ tìm left right mãi sai tùm lum. Brute force phát ra luôn ))))
Thi contest đúng kiểu rèn interview, panic quá là éo nghĩ ra cái gì. Chuyển xuống bài 4 tâm lí thoải mái ngồi ngẫm lại viết đúng binary search cứ tưởng O((m + n) log n) hí hửng ăn cmnr thì ai ngờ là O(m*nlogn) như cái cục cức

Binary search k code quen dễ ăn corner case lắm. Trước có ông nào post cái pattern chuyên trị cho binary search, cứ follow theo, bài nào cũng ăn, :ah:

seastar · 14/1/24

Bài 3 cũng dùng binary search luôn, hướng làm sai thảo nào loay hoay mãi k xong. :ah:

freedom.9 · 14/1/24

seastar đã nói:
Binary search k code quen dễ ăn corner case lắm. Trước có ông nào post cái pattern chuyên trị cho binary search, cứ follow theo, bài nào cũng ăn,

bữa mình cóp nhặt post lên Voz chứ ai, xong rồi code sai tùm lum cay vl :LOL:

)) do panic quá ko nghĩ được gì cả fence :beat_brick:

chỉ cần ngồi tìm thằng left gần nhất và thằng right gần nhất rồi kiểm tra abs là xong cmn nửa nốt nhạc rồi, đi làm 3 thứ tào lao sai lên sai xuống đm. Để ngồi học cái Kmp search đã =((

Violet_7 · 14/1/24

Đc 1, 2, 4. Trình lít cốt mai một quá :pudency:

. Thôi tuần sau làm acc phụ tiếp :cry:

seastar · 14/1/24

freedom.9 đã nói:
Để ngồi học cái Kmp search đã

Cái KMP đau não phết đấy. :ah:

freedom.9 · 14/1/24

seastar đã nói:
Bài 3 cũng dùng binary search luôn, hướng làm sai thảo nào loay hoay mãi k xong.

Mai fence dịch mình bài 3 ra tiếng Việt với, đọc ko hiểu gì cả =((

Đuối quá rồi chắc mai ngồi nghiên cứu.
Nãy làm xong bài 2 thấy bài 4 nhiều thằng giải đc hơn nên skip bài 3

freedom.9 · 14/1/24

Yawn_Sean - LeetCode Profile

View Yawn_Sean's profile on LeetCode, the world's largest programming community.

leetcode.com

Thằng top 1 hôm nay, đ phải người nữa rồi ...
Giải 4 bài trong vòng 11 phút ...

seastar · 14/1/24

freedom.9 đã nói:
Mai fence dịch mình bài 3 ra tiếng Việt với, đọc ko hiểu gì cả Đuối quá rồi chắc mai ngồi nghiên cứu.
Nãy làm xong bài 2 thấy bài 4 nhiều thằng giải đc hơn nên skip bài 3

Dịch bài cho thanh niên đang ở mẽo quốc, có gì đó sai sai thì phải, :beat_brick:

freedom.9 · 14/1/24

seastar đã nói:
Dịch bài cho thanh niên đang ở mẽo quốc, có gì đó sai sai thì phải,

Đọc đề ko hiểu gì thật :too_sad:

thôi ngủ mai cày tiếp giờ ngáo quá rồi
À bài 4 thay vì dùng binary search thì dùng 2 pointers cũng ok nhỉ, binary search làm mẹ gì ko biết cho bug tùm lum :canny:

via theNEXTvoz for iPhone

seastar · 14/1/24

Tính ra hôm nay bài 3 là khó nhất. Loay hoay mãi cũng giải được, nay rảnh nên sẽ cố gắng trình bày chi tiết, hầu bác @freedom.9 , :beauty:

Đề bài:

cho 1 dãy s là biểu diễn dạng binary của 1 số bất kỳ, với index bắt đầu từ 1, đếm từ trái sang phải

Mã:

vd: 4 => 100'b => giá trị tại index số 1 của 4 là 0, giá trị tại index số 3 của 4 là 1

Cho 1 số x, gọi price của 1 số n bất kỳ tại x là tổng sổ bit 1 theo biểu diễn s tại những index chia hết cho x. ký hiệu là price(x, n).

Mã:

=> price(1, 2) = 1 (do 2 = 10'b => có 1 bit 1. Vị trí nào thì cũng chia hết cho 1, k cần quan tâm vị trí)
=> price(1, 5) = 2 (do 5 = 101'b => có 1 bit 1. Vị trí nào thì cũng chia hết cho 1, k cần quan tâm vị trí)
=> price(2, 2) = 1 (do 2 = 10'b => có 1 bit 1 tại index 2 chia hết cho 2)
=> price(2, 5) = 0 (do 5 = 101'b => k có bit 1 nào tạo index chia hết cho 2)

Đề bài là tìm số n lớn nhất sao cho tổng của price từ 1 đến n tại x thì không lớn hơn 1 số k cho trước.

Phân tích bài toán:

Mã:

Gọi hàm số f(x, n) = price(x, 1) + price(x, 2) +  price(x, 3) + ... + price(x, n)  (1)
từ (1) => Bài toán chính là đi tìm n lớn nhất sao cho f(x, n) <= k (2)
từ (1) => f(x, n) = f(x, n - 1) + price(x, n) (3)
từ (3) và price luôn >= 0 suy ra f(x, n) >= f(x, n - 1).  Tức là với cùng x thì khi n tăng thì f(x, n) cũng tăng theo => f đồng biến (4)
từ (4) => có thể dùng binary search để tìm n được.

Khi dùng binary seach thì code sẽ có dạng ntn:

Python:

class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:     
        l, h = 0, int(1e15)
        pivot = l + (h - l + 1)//2
      
        while pivot < h:
            if cal(pivot) <= k:
                l = pivot
            else:
                h = pivot
            pivot = l + (h - l + 1)//2
        return l

l, h tại sao đc gán như vậy thì tự coi đề bài và suy nghĩ nhé, :beauty:

Đến đây mấu chốt nằm ở chỗ function cal, chính là cái hàm f(x, n) phía trên.

Hàm cal có thể viết theo kiểu ngây thơ nhất như dưới đây.

Python:

def cal1(x, n):
    count = 0
    for i in range(1, n+1):
        count += sum(1 for j, c in enumerate("{0:b}".format(i)[::-1]) if (j+1)%x == 0 and c == '1')
        return count

độ phức tạp của cal1 là O(n) mà n có thể lên đến 10^15 => chắc chắn viết ntn sẽ bị timeout.
=> phải tìm được cách tính khác nhanh hơn. Thường mấy bài kiểu này sẽ có cách tính nhanh hơn. thử viết ra biểu diễn của các số từ 0 đến 16 để tìm quy luật.

Mã:

    i4  i3  i2  i1
0   0   0   0   0
1   0   0   0   1
2   0   0   1   0
3   0   0   1   1
4   0   1   0   0
5   0   1   0   1
6   0   1   1   0
7   0   1   1   1
8   1   0   0   0
9   1   0   0   1
10  1   0   1   0
11  1   0   1   1
12  1   1   0   0
13  1   1   0   1
14  1   1   1   0
15  1   1   1   1

Các hàng 0, 1, 2, ...., 16 là biểu diễn binary của số đó. i4, i3, i2, i1 chính là các index có vị trí là 4,3,2,1 tương ứng => f(x, n) = tổng số bit 1 ở hàng 1 đến n và chỉ những cột có trọng số chia hết cho x.

Đến đây chịu khó quan sát quy luật rồi tính thôi. Phần khó nhất của bài này nằm ở đây.

Mã:

vd: f(1, 12) sẽ được tách ra thành b1, b2 như sau:
bảng 1: b1
    i4  i3  i2  i1
0   0   0   0   0
1   0   0   0   1
2   0   0   1   0
3   0   0   1   1
4   0   1   0   0
5   0   1   0   1
6   0   1   1   0
7   0   1   1   1

bảng 2: b2
    i4  i3  i2  i1
8   1   0   0   0
9   1   0   0   1
10  1   0   1   0
11  1   0   1   1
12  1   1   0   0

mỗi cột của bảng b1 đều có 4 bit 1 => f(1, 7) = b1 = 4*3 = 12.

bảng 3: b3
    i4  i3  i2  i1
0   0   0   0   0
1   0   0   0   1
2   0   0   1   0
3   0   0   1   1
4   0   1   0   0
=> bảng 3 và bảng 2 chỉ khác nhau ở cột i4 => b3 = 5 + f(1, 4)
=> f(1, 12) = f(1, 7) + 5 + f(1, 4) = 17 + f(1, 4)
tiếp tục tách f(1, 4) ra f(1, 4) = 1 + f(1,3) = 1 + 2*2 => f(1, 12) = 22
làm tương tự với x = 2 (chỉ tính cột i2, i4, ...), x = 3 (chỉ tính cột i3, i6, ...)

Đến đây thì phải tự ngộ ra quy luật thôi, :beauty:

. Tóm lại cần có phải ngộ tính cao, nếu k thì phải luyện thêm thôi, ép skill sớm dễ xịt, :matrix:

Python:

class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        def cal(num):
            if num < 2**(x-1):
                return 0
            f = math.floor(math.log(num, 2))

            ret = 2**(f-1) * (f//x)
            if (f+1)%x == 0:
                ret += num - 2**f + 1
            ret += cal(num - 2**f)

            return int(ret)
      
        l, h = 0, int(1e15)
        pivot = l + (h - l + 1)//2
      
        while pivot < h:
            if cal(pivot) <= k:
                l = pivot
            else:
                h = pivot
            pivot = l + (h - l + 1)//2
      
        return l

freedom.9 · 14/1/24

seastar đã nói:
Tính ra hôm nay bài 3 là khó nhất. Loay hoay mãi cũng giải được, nay rảnh nên sẽ cố gắng trình bày chi tiết, hầu bác @freedom.9 ,

Đề bài:
cho 1 dãy s là biểu diễn dạng binary của 1 số bất kỳ, với index bắt đầu từ 1, đếm từ trái sang phải

Mã:

vd: 4 => 100'b => giá trị tại index số 1 của 4 là 0, giá trị tại index số 3 của 4 là 1

Cho 1 số x, gọi price của 1 số n bất kỳ tại x là tổng sổ bit 1 theo biểu diễn s tại những index chia hết cho x. ký hiệu là price(x, n).

Mã:

=> price(1, 2) = 1 (do 2 = 10'b => có 1 bit 1. Vị trí nào thì cũng chia hết cho 1, k cần quan tâm vị trí) => price(1, 5) = 2 (do 5 = 101'b => có 1 bit 1. Vị trí nào thì cũng chia hết cho 1, k cần quan tâm vị trí) => price(2, 2) = 1 (do 2 = 10'b => có 1 bit 1 tại index 2 chia hết cho 2) => price(2, 5) = 0 (do 5 = 101'b => k có bit 1 nào tạo index chia hết cho 2)

Đề bài là tìm số n lớn nhất sao cho tổng của price từ 1 đến n tại x thì không lớn hơn 1 số k cho trước.

Phân tích bài toán:

Mã:

Gọi hàm số f(x, n) = price(x, 1) + price(x, 2) + price(x, 3) + ... + price(x, n) (1) từ (1) => Bài toán chính là đi tìm n lớn nhất sao cho f(x, n) <= k (2) từ (1) => f(x, n) = f(x, n - 1) + price(x, n) (3) từ (3) và price luôn >= 0 suy ra f(x, n) >= f(x, n - 1). Tức là với cùng x thì khi n tăng thì f(x, n) cũng tăng theo => f đồng biến (4) từ (4) => có thể dùng binary search để tìm n được.

Khi dùng binary seach thì code sẽ có dạng ntn:

Python:

class Solution: def findMaximumNumber(self, k: int, x: int) -> int: l, h = 0, int(1e15) pivot = l + (h - l + 1)//2 while pivot < h: if cal(pivot) <= k: l = pivot else: h = pivot pivot = l + (h - l + 1)//2 return l

l, h tại sao đc gán như vậy thì tự coi đề bài và suy nghĩ nhé,
Đến đây mấu chốt nằm ở chỗ function cal, chính là cái hàm f(x, n) phía trên.

Hàm cal có thể viết theo kiểu ngây thơ nhất như dưới đây.

Python:

def cal1(x, n): count = 0 for i in range(1, n+1): count += sum(1 for j, c in enumerate("{0:b}".format(i)[::-1]) if (j+1)%x == 0 and c == '1') return count

độ phức tạp của cal1 là O(n) mà n có thể lên đến 10^15 => chắc chắn viết ntn sẽ bị timeout.
=> phải tìm được cách tính khác nhanh hơn. Thường mấy bài kiểu này sẽ có cách tính nhanh hơn. thử viết ra biểu diễn của các số từ 0 đến 16 để tìm quy luật.

Mã:

i4 i3 i2 i1 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1

Các hàng 0, 1, 2, ...., 16 là biểu diễn binary của số đó. i4, i3, i2, i1 chính là các index có vị trí là 4,3,2,1 tương ứng => f(x, n) = tổng số bit 1 ở hàng 1 đến n và chỉ những cột có trọng số chia hết cho x.

Đến đây chịu khó quan sát quy luật rồi tính thôi. Phần khó nhất của bài này nằm ở đây.

Mã:

vd: f(1, 12) sẽ được tách ra thành b1, b2 như sau: bảng 1: b1 i4 i3 i2 i1 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 bảng 2: b2 i4 i3 i2 i1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 mỗi cột của bảng b1 đều có 4 bit 1 => f(1, 7) = b1 = 4*3 = 12. bảng 3: b3 i4 i3 i2 i1 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 => bảng 3 và bảng 2 chỉ khác nhau ở cột i4 => b3 = 5 + f(1, 4) => f(1, 12) = f(1, 7) + 5 + f(1, 4) = 17 + f(1, 4) tiếp tục tách f(1, 4) ra f(1, 4) = 1 + f(1,3) = 1 + 2*2 => f(1, 12) = 22 làm tương tự với x = 2 (chỉ tính cột i2, i4, ...), x = 3 (chỉ tính cột i3, i6, ...)

Đến đây thì phải tự ngộ ra quy luật thôi, . Tóm lại cần có phải ngộ tính cao, nếu k thì phải luyện thêm thôi, ép skill sớm dễ xịt,

Python:

class Solution: def findMaximumNumber(self, k: int, x: int) -> int: def cal(num): if num < 2**(x-1): return 0 f = math.floor(math.log(num, 2)) ret = 2**(f-1) * (f//x) if (f+1)%x == 0: ret += num - 2**f + 1 ret += cal(num - 2**f) return int(ret) l, h = 0, int(1e15) pivot = l + (h - l + 1)//2 while pivot < h: if cal(pivot) <= k: l = pivot else: h = pivot pivot = l + (h - l + 1)//2 return l

Cảm ơn my fence :sweet_kiss:

nhìn phức tạp vl :too_sad:

via theNEXTvoz for iPhone

humanversion9x · 14/1/24

seastar đã nói:
Binary search k code quen dễ ăn corner case lắm. Trước có ông nào post cái pattern chuyên trị cho binary search, cứ follow theo, bài nào cũng ăn,

freedom.9 đã nói:
bữa mình cóp nhặt post lên Voz chứ ai, xong rồi code sai tùm lum cay vl )) do panic quá ko nghĩ được gì cả fence chỉ cần ngồi tìm thằng left gần nhất và thằng right gần nhất rồi kiểm tra abs là xong cmn nửa nốt nhạc rồi, đi làm 3 thứ tào lao sai lên sai xuống đm. Để ngồi học cái Kmp search đã

Hai bạn cho mình xin cái binary search pattern với, cài đặt binary search hay phải để ý corner case.

darklord1611 · 14/1/24

humanversion9x đã nói:
Hai bạn cho mình xin cái binary search pattern với, cài đặt binary search hay phải để ý corner case.

https://leetcode.com/problems/binary-search/solutions/423162/Binary-Search-101-The-Ultimate-Binary-Search-Handbook đây bác

freedom.9 · 17/1/24

Lại tụt hạng cmnr ae ơi :too_sad:

đường lên Knight xa quá, có bi weekly gỡ gạc vậy :too_sad:

via theNEXTvoz for iPhone

pikachu_1 · 17/1/24

freedom.9 đã nói:
Lại tụt hạng cmnr ae ơi đường lên Knight xa quá, có bi weekly gỡ gạc vậy

via theNEXTvoz for iPhone

Cố lên thím, kiên trì là lên thôi.
Mà có chỗ nào quy định chính xác bao nhiêu điểm thì Knight, bao nhiêu thì Guardian không nhỉ?
Hay là tính theo phần trăm?

freedom.9 · 17/1/24

pikachu_1 đã nói:
Cố lên thím, kiên trì là lên thôi.
Mà có chỗ nào quy định chính xác bao nhiêu điểm thì Knight, bao nhiêu thì Guardian không nhỉ?
Hay là tính theo phần trăm?

Ko thím, tụi nó bảo 1k850 là knight, 2k2 là guardian đó

via theNEXTvoz for iPhone

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

Member

Senior Member

Member

Senior Member

Member

Member

Senior Member

Member

Member

Senior Member

Senior Member

Member

Senior Member

Member

Đề bài:​

Phân tích bài toán:​

Senior Member

Đề bài:​

Phân tích bài toán:​

Senior Member

Junior Member

Senior Member

Đã tốn tiền

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này

Đề bài:

Phân tích bài toán:

Đề bài:

Phân tích bài toán: