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

freedom.9 · 29/9/24

thangkc89 đã nói:
Biweekly contest buổi sáng: +82 ratingXem tệp đính kèm 2707274
Weekly contest buổi tối: +100 ratingXem tệp đính kèm 2707277
To the moon

Ghê vãi

via theNEXTvoz for iPhone

freedom.9 · 29/9/24

Má buổi sáng ko viết code q4 ngu là ăn 100 rating cmnr :ah:

cay thế nhỉ
Lần nào cũng TLE 1 2 cases éo biết làm sao :ah:

mấy contests rồi đó
via theNEXTvoz for iPhone

clonemasteruwu · 29/9/24

freedom.9 đã nói:

Q3 đọc đề thấy khó tiếp cận quá nên bỏ
Q4 xài Rabin Karp như thế này thì pass còn 1 test case, đm đời đúng đen

Python:

class Solution:
    def minStartingIndex(self, s: str, pattern: str) -> int:
        base = 60
        MOD = 10**18 + 7
        n = len(pattern)
        lastBase = pow(base, n - 1, MOD)
        basePowers = [pow(base, i, MOD) for i in range(n)]

        if len(s) < n:
            return -1

        def calculateHash(target):
            currentHash = 0
            for i in range(n):
                currentHash = (currentHash * base + (ord(target[i]) - ord('a'))) % MOD
            return currentHash

        def getHashList(pattern):
            hashResult = set()
            currentHash = calculateHash(pattern)
           
            for i in range(n):
                order = ord(pattern[i]) - ord('a')
                originalContribution = (order * basePowers[n - i - 1]) % MOD

                newHash = (currentHash - originalContribution + MOD) % MOD
                if newHash < 0:
                    newHash += MOD

                for j in range(26):
                    modifiedHash = (newHash + (j * basePowers[n - i - 1]) % MOD) % MOD
                    hashResult.add(modifiedHash)

            return hashResult

        patternHashes = getHashList(pattern)

        h2 = calculateHash(s[:n])

        if h2 in patternHashes:
            return 0

        left = 0
        for i in range(n, len(s)):
            h2 = (h2 - (ord(s[left]) - ord('a')) * lastBase) % MOD
            h2 = (h2 * base + (ord(s[i]) - ord('a'))) % MOD
            left += 1

            if h2 < 0:
                h2 += MOD

            if h2 in patternHashes:
                return left

        return -1

code yếu tay xin đừng chê ngôn ngữ. anh để mod thế kia thì nhân 2 con mod với nhau hoàn toàn có thể tràn 64 bit -> python convert sang bignum -> %*/+- chậm. expect chậm từ 10x->100x tuỳ python compiler.

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

clonemasteruwu đã nói:
code yếu tay xin đừng chê ngôn ngữ. anh để mod thế kia thì nhân 2 con mod với nhau hoàn toàn có thể tràn 64 bit -> python convert sang bignum -> %*/+- chậm. expect chậm từ 10x->100x tuỳ python compiler.

Ủa phải Hiệp không

Người quan sát cô đơn · 29/9/24

ủa cái contest này tính tham gia như nào vậy ae, làm cả cái sáng với cái tối qua mà ko thấy + coin, + rating gì cả. Hay tại làm ít câu quá :amazed:

LmaoSuVuong · 29/9/24

Người quan sát cô đơn đã nói:
ủa cái contest này tính tham gia như nào vậy ae, làm cả cái sáng với cái tối qua mà ko thấy + coin, + rating gì cả. Hay tại làm ít câu quá

thứ 5 mới có kqua

clonemasteruwu · 29/9/24

Cố Trường Ca đã nói:
Ủa phải Hiệp không

không b ơi nhầm người rồi. nick đi mua mà

LmaoSuVuong · 29/9/24

clonemasteruwu đã nói:
không b ơi nhầm người rồi. nick đi mua mà

vãi bác rating 2k8 chắc tuần nào 3/4 là bị trừ dữ lắm

small-lambda · 29/9/24

clonemasteruwu đã nói:
python convert sang bignum

chắc mình hiểu nhầm chứ doc python 3 nói int mặc định đã là 'BigInt' arbitrary bit length chứ đâu có kiểu như xài native int rồi khi overflow mới convert sang "BigInt"?

clonemasteruwu · 29/9/24

small-lambda đã nói:
chắc mình hiểu nhầm chứ doc python 3 nói int mặc định đã là 'BigInt' arbitrary bit length chứ đâu có kiểu như xài native int rồi khi overflow mới convert sang "BigInt"?

đúng là internal rep của nó là arbitary length, mà bác nghĩ thử xem từ byte code xuống machine code muốn optimization/call hardware instruction thì nó thao tác như nào

Python effective integer size

For example in C#, C++, Java or JavaScript effective int size is 32 bits. If we want to calculate some large number, for example, 70 bits, we should use some software features (Arbitrary-precision

stackoverflow.com

small-lambda · 29/9/24

clonemasteruwu đã nói:
đúng là internal rep của nó là arbitary length, mà bác nghĩ thử xem từ native code xuống machine code muốn optimization/call hardware instruction thì nó thao tác như nào

Python effective integer size

For example in C#, C++, Java or JavaScript effective int size is 32 bits. If we want to calculate some large number, for example, 70 bits, we should use some software features (Arbitrary-precision

stackoverflow.com

nhưng mà cũng đâu có chuyện convert sang "BigNum" đâu? với cái nữa nè, giờ bạn đẩy quotient xuống sao cho sau các phép tính kết quả hash nằm vừa trong 2 4-byte integers và mấy cái optimization được áp dụng đi, ví dụ như CPython nó chuyển về native integer rồi làm dùng native CPU instruction chứ không đi gọi hàm nữa, thì bạn có chắc là mấy cái optimization đó nó bù được overhead của CPython không? ngay trong cái link của bạn quăng có đoạn cuối ntn:

That said, there's rarely a reason to take this into account; CPython interpreter overhead is pretty high, and it's pretty hard to imagine a scenario where manually breaking down a larger operation into smaller ones (incurring more interpreter overhead to do many small operations at the Python layer) would outweigh the much smaller cost of Python doing the array-based operations (even without special fast paths) at the C layer

giờ không có profile không benchmark gì hết nói khơi khơi như vầy thì không có giá trị lắm, nhưng nếu đoán bừa tại sao code gốc chậm sao bạn không để ý đoạn này:

Mã:

[pow(base, i, MOD) for i in range(n)]

thay vì loop và dùng kết quả của vòng trước thì lại đi gọi pow liên tục?

freedom.9 · 29/9/24

clonemasteruwu đã nói:
code yếu tay xin đừng chê ngôn ngữ. anh để mod thế kia thì nhân 2 con mod với nhau hoàn toàn có thể tràn 64 bit -> python convert sang bignum -> %*/+- chậm. expect chậm từ 10x->100x tuỳ python compiler.

Vấn đề chậm ko phải ở MOD mà do mình viết code ko hiệu quả chỗ tính power, bài này lấy MOD 10**9 + 7 thì dính hash collission.
Còn chê là chê Python nó chậm thôi chứ rất nhiều bài cùng 1 solution thì ở các ngôn ngữ khác như C++ hay Java vẫn pass như thường, còn làm quá nhiều biết cách optimize thế nào cho nhanh thì ko nói.

via theNEXTvoz for iPhone

freedom.9 · 29/9/24

small-lambda đã nói:
nhưng mà cũng đâu có chuyện convert sang "BigNum" đâu? với cái nữa nè, giờ bạn đẩy quotient xuống sao cho sau các phép tính kết quả hash nằm vừa trong 2 4-byte integers và mấy cái optimization được áp dụng đi, ví dụ như CPython nó chuyển về native integer rồi làm dùng native CPU instruction chứ không đi gọi hàm nữa, thì bạn có chắc là mấy cái optimization đó nó bù được overhead của CPython không? ngay trong cái link của bạn quăng có đoạn cuối ntn:

giờ không có profile không benchmark gì hết nói khơi khơi như vầy thì không có giá trị lắm, nhưng nếu đoán bừa tại sao code gốc chậm sao bạn không để ý đoạn này:

Mã:

[pow(base, i, MOD) for i in range(n)]

thay vì loop và dùng kết quả của vòng trước thì lại đi gọi pow liên tục?

Đúng rồi, như post sau mình có nhận ra mới thấy, làm contest nó áp lực nên code bug tới bug lui mấy bị mấy lỗi thế này. Cái này chỉ cần tập luyện rút kinh nghiệm thôi :sweet_kiss:

v mà vẫn cái hàm này sửa lại thành dùng DP để xài lại cái kết quả trước submit 2 lần thì accepted 1 lần, TLE 1 lần. Phải optimize lại bằng cách ko tính power như thế này mà đi cái base ngược lại mới pass
via theNEXTvoz for iPhone

freedom.9 · 29/9/24

Ví dụ cùng 1 solution, submit 2 lần thì 1 lần TLE 1 lần Accepted, cái đầu trong hình và cái cuối trong hình đều cùng 1 solution.
base với MOD này mình lấy từ 1 solution accepted từ C++, chắc ko ảnh hưởng gì tới benchmark.

Python:

class Solution:
    def minStartingIndex(self, s: str, pattern: str) -> int:
        base = 31
        MOD = 24738041398529
        n = len(pattern)
        lastBase = pow(base, n - 1, MOD)
        basePowers = [0]*n
        basePowers[0] = 1
        for i in range(1, n):
            basePowers[i] = (basePowers[i - 1]*base)%MOD

        if len(s) < n:
            return -1

        def calculateHash(target):
            currentHash = 0
            for i in range(n):
                currentHash = (currentHash * base + (ord(target[i]) - ord('a'))) % MOD
            return currentHash

        def getHashList(pattern):
            hashResult = set()
            currentHash = calculateHash(pattern)
           
            for i in range(n):
                order = ord(pattern[i]) - ord('a')
                originalContribution = (order * basePowers[n - i - 1]) % MOD

                newHash = (currentHash - originalContribution + MOD) % MOD
                if newHash < 0:
                    newHash += MOD

                for j in range(26):
                    modifiedHash = (newHash + (j * basePowers[n - i - 1]) % MOD) % MOD
                    hashResult.add(modifiedHash)

            return hashResult

        patternHashes = getHashList(pattern)

        h2 = calculateHash(s[:n])

        if h2 in patternHashes:
            return 0

        left = 0
        for i in range(n, len(s)):
            h2 = (h2 - (ord(s[left]) - ord('a')) * lastBase) % MOD
            h2 = (h2 * base + (ord(s[i]) - ord('a'))) % MOD
            left += 1

            if h2 < 0:
                h2 += MOD

            if h2 in patternHashes:
                return left

        return -1

clonemasteruwu · 29/9/24

small-lambda đã nói:
nhưng mà cũng đâu có chuyện convert sang "BigNum" đâu? với cái nữa nè, giờ bạn đẩy quotient xuống sao cho sau các phép tính kết quả hash nằm vừa trong 2 4-byte integers và mấy cái optimization được áp dụng đi, ví dụ như CPython nó chuyển về native integer rồi làm dùng native CPU instruction chứ không đi gọi hàm nữa, thì bạn có chắc là mấy cái optimization đó nó bù được overhead của CPython không? ngay trong cái link của bạn quăng có đoạn cuối ntn:

giờ không có profile không benchmark gì hết nói khơi khơi như vầy thì không có giá trị lắm, nhưng nếu đoán bừa tại sao code gốc chậm sao bạn không để ý đoạn này:

Mã:

[pow(base, i, MOD) for i in range(n)]

thay vì loop và dùng kết quả của vòng trước thì lại đi gọi pow liên tục?

ngồi tìm lại vụ int promotion này vì đâu có nhẽ tự nghĩ ra được, đúng là python 2.x có vụ này nhá, lên 3.x thì hết rồi, mental model outdate ác :beat_shot:

source
có thử test lại thì performance hit chỉ là 3x (đúng với lý thuyết)
pow modulo của python cũng chỉ là log n nhé, và cái link tôi gửi nó chỉ bảo not worth do it manually thôi, còn anh tự tránh cold path/loop thì baoh chả hơn
còn tôi chê anh kia vì chưa hiểu hết mạnh yếu ngôn ngữ mà cứ cho là dùng C++ là perf hơn python (xài python ở leetcode thường thọt mỗi call stack chứ k thọt compute, và bản thân C++ cũng bị nerf kha khá ở leetcode, có một còm tôi nhắc đến cái này mà không tìm được, đại ý là leetcode chạy sanitizer khi chấm -> chả khác java là bao)

Python:

import random
import time
import numpy as np

random.seed(42)
size = 100_000_000

array1 = [int(x) for x in np.random.randint(1, int(1e8), size=size)]
array2 = [int(x) for x in np.random.randint(1, int(1e8), size=size)]


start_time = time.time()
result = [a * b for a, b in zip(array1, array2)]
end_time = time.time()
execution_time = end_time - start_time
print(f"{execution_time:.4f} seconds")

del array1
del array2
array1 = [int(x) for x in np.random.randint(int(1e15), int(1e18), size=size)]
array2 = [int(x) for x in np.random.randint(int(1e15), int(1e18), size=size)]
start_time = time.time()
result = [a * b for a, b in zip(array1, array2)]
end_time = time.time()
execution_time = end_time - start_time
print(f"{execution_time:.4f} seconds")

freedom.9 đã nói:

Xem tệp đính kèm 2708056
Ví dụ cùng 1 solution, submit 2 lần thì 1 lần TLE 1 lần Accepted, cái đầu trong hình và cái cuối trong hình đều cùng 1 solution.
base với MOD này mình lấy từ 1 solution accepted từ C++, chắc ko ảnh hưởng gì tới benchmark.

Python:

class Solution:
    def minStartingIndex(self, s: str, pattern: str) -> int:
        base = 31
        MOD = 24738041398529
        n = len(pattern)
        lastBase = pow(base, n - 1, MOD)
        basePowers = [0]*n
        basePowers[0] = 1
        for i in range(1, n):
            basePowers[i] = (basePowers[i - 1]*base)%MOD

        if len(s) < n:
            return -1

        def calculateHash(target):
            currentHash = 0
            for i in range(n):
                currentHash = (currentHash * base + (ord(target[i]) - ord('a'))) % MOD
            return currentHash

        def getHashList(pattern):
            hashResult = set()
            currentHash = calculateHash(pattern)
         
            for i in range(n):
                order = ord(pattern[i]) - ord('a')
                originalContribution = (order * basePowers[n - i - 1]) % MOD

                newHash = (currentHash - originalContribution + MOD) % MOD
                if newHash < 0:
                    newHash += MOD

                for j in range(26):
                    modifiedHash = (newHash + (j * basePowers[n - i - 1]) % MOD) % MOD
                    hashResult.add(modifiedHash)

            return hashResult

        patternHashes = getHashList(pattern)

        h2 = calculateHash(s[:n])

        if h2 in patternHashes:
            return 0

        left = 0
        for i in range(n, len(s)):
            h2 = (h2 - (ord(s[left]) - ord('a')) * lastBase) % MOD
            h2 = (h2 * base + (ord(s[i]) - ord('a'))) % MOD
            left += 1

            if h2 < 0:
                h2 += MOD

            if h2 in patternHashes:
                return left

        return -1

cái này do bác tính hết 1 lượt hash từ đầu nên dễ ăn birthday paradox hơn, chạy nhiều test thì kiểu gì cũng có 1 test sai. thay vì tăng base thì bác có thể tham khảo multiple hash func, cũng reduce collision mà perf ổn hơn nhiều

freedom.9 · 29/9/24

clonemasteruwu đã nói:
cái này do bác tính hết 1 lượt hash từ đầu nên dễ ăn birthday paradox hơn, chạy nhiều test thì kiểu gì cũng có 1 test sai. thay vì tăng base thì bác có thể tham khảo multiple hash func, cũng reduce collision mà perf ổn hơn nhiều

Thanks bác để tí mình nghiên cứu :sweet_kiss:

via theNEXTvoz for iPhone

i-am-groot · 30/9/24

freedom.9 đã nói:

Xem tệp đính kèm 2708056
Ví dụ cùng 1 solution, submit 2 lần thì 1 lần TLE 1 lần Accepted, cái đầu trong hình và cái cuối trong hình đều cùng 1 solution.
base với MOD này mình lấy từ 1 solution accepted từ C++, chắc ko ảnh hưởng gì tới benchmark.

Python:

class Solution:
    def minStartingIndex(self, s: str, pattern: str) -> int:
        base = 31
        MOD = 24738041398529
        n = len(pattern)
        lastBase = pow(base, n - 1, MOD)
        basePowers = [0]*n
        basePowers[0] = 1
        for i in range(1, n):
            basePowers[i] = (basePowers[i - 1]*base)%MOD

        if len(s) < n:
            return -1

        def calculateHash(target):
            currentHash = 0
            for i in range(n):
                currentHash = (currentHash * base + (ord(target[i]) - ord('a'))) % MOD
            return currentHash

        def getHashList(pattern):
            hashResult = set()
            currentHash = calculateHash(pattern)
          
            for i in range(n):
                order = ord(pattern[i]) - ord('a')
                originalContribution = (order * basePowers[n - i - 1]) % MOD

                newHash = (currentHash - originalContribution + MOD) % MOD
                if newHash < 0:
                    newHash += MOD

                for j in range(26):
                    modifiedHash = (newHash + (j * basePowers[n - i - 1]) % MOD) % MOD
                    hashResult.add(modifiedHash)

            return hashResult

        patternHashes = getHashList(pattern)

        h2 = calculateHash(s[:n])

        if h2 in patternHashes:
            return 0

        left = 0
        for i in range(n, len(s)):
            h2 = (h2 - (ord(s[left]) - ord('a')) * lastBase) % MOD
            h2 = (h2 * base + (ord(s[i]) - ord('a'))) % MOD
            left += 1

            if h2 < 0:
                h2 += MOD

            if h2 in patternHashes:
                return left

        return -1

tuần trước Q4 mình cũng bị TLE, chuyển qua C++ thì oke, nhưng mà vài ngày sau LeetCode nó re-judge, và cái python của mình pass :LOL:

freedom.9 · 2/10/24

Tuyệt vời, khóc lóc quá cuối cùng cũng được rejudge :ah:

ko biết bao nhiêu điểm được lên bảo vệ

Cố Trường Ca · 3/10/24

freedom.9 đã nói:
Tuyệt vời, khóc lóc quá cuối cùng cũng được rejudge ko biết bao nhiêu điểm được lên bảo vệ
Xem tệp đính kèm 2713502

gato nên cho cục gạch nhé :beat_brick:

humanversion9x · 3/10/24

freedom.9 đã nói:
Tuyệt vời, khóc lóc quá cuối cùng cũng được rejudge ko biết bao nhiêu điểm được lên bảo vệ
Xem tệp đính kèm 2713502

Tầm 2150 thì phải.

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

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

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