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

freedom.9 · 22/9/24

C# toang, dễ unrate cmnr :ah:

lovelyly · 22/9/24

freedom.9 đã nói:
Xem tệp đính kèm 2695579
C# toang, dễ unrate cmnr

seastar · 22/9/24

freedom.9 đã nói:
Xem tệp đính kèm 2695579
C# toang, dễ unrate cmnr

trash lang hay do thằng leetcode setup code C# để test gà thế? :ah:

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

freedom.9 đã nói:
Xem tệp đính kèm 2695579
C# toang, dễ unrate cmnr

Ngon

nchhnchh · 22/9/24

seastar đã nói:
Bài 2 dùng binary search đúng k ae? t thì dùng min heap,

min heap cho đỡ đau đầu :shame:

athxzz · 22/9/24

Đề dễ hơn hẳn tuần trước mà sợ choke nên skip mất contest này :rolleyes:

. Rating đang có 1577, các bác cho em bí kíp luyện lên 1900 với

athxzz · 22/9/24

các bác cho em hỏi có nhiều cheat không nhỉ? E đọc sol của mấy acc thì thấy có cả comment hoặc là sol bài 3 với 4 y nhau mà submit lệch cả mấy phút

lilleboybk · 22/9/24

athxzz đã nói:
Xem tệp đính kèm 2696350

Đề dễ hơn hẳn tuần trước mà sợ choke nên skip mất contest này . Rating đang có 1577, các bác cho em bí kíp luyện lên 1900 với

Có contest thì cứ vào thi thôi bác, bác rating 1k5 chắc mới làm quen, chưa thi nhiều.

LmaoSuVuong · 23/9/24

cận cảnh 12p giải xong contest @Cố Trường Ca

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

LmaoSuVuong đã nói:
cận cảnh 12p giải xong contest @Cố Trường Ca

Vl code trên ide

vicejuniordev · 24/9/24

Cố Trường Ca đã nói:
Vl code trên ide

Toàn thế mà, top nó toàn code = IDE + có sẵn template như Bi search, Trie, UF, Segment Tree... nên code nhanh lắm

freedom.9 · 28/9/24

Má nó vẫn ko hiểu sao cứ TLE mãi với cái python. Ý tưởng là xài Rabin Karp tính ra n*26 hash mà mãi nó cứ TLE. Đổi Base đổi MOD các kiểu vẫn TLE. Tức điên thật chứ

lilleboybk · 28/9/24

Q3 medium 5đ tưởng đơn giản mà đề dị thật. May còn 40p thì mới có 200 accepted nên em biết contest này 2Q cũng ko bị trừ nhiều lắm

vicejuniordev · 28/9/24

lilleboybk đã nói:
Q3 medium 5đ tưởng đơn giản mà đề dị thật. May còn 40p thì mới có 200 accepted nên em biết contest này 2Q cũng ko bị trừ nhiều lắm

Q3 nói thật mình còn thấy khó tiếp cận hơn Q4. Q4 làm toàn TLE không optimize nổi.

via theNEXTvoz for iPhone

freedom.9 · 28/9/24

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

seastar · 28/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

Thấy tụi nó dùng zfunction pass ầm ầm mà, :ah:

freedom.9 · 28/9/24

seastar đã nói:
Thấy tụi nó dùng zfunction pass ầm ầm mà,

Con mẹ nó có thằng xài C++ code y chang mình nó pass hết. Đm đời đm Python :ah:

https://leetcode.com/problems/find-the-occurrence-of-first-almost-equal-substring/solutions/5844323/z-function-python3-o-n-m/

seastar · 28/9/24

freedom.9 đã nói:
Con mẹ nó có thằng xài C++ code y chang mình nó pass hết. Đm đời đm Python

https://leetcode.com/problems/find-the-occurrence-of-first-almost-equal-substring/solutions/5844323/z-function-python3-o-n-m/

Tầm sư học code đi, t lấy rate thấp thôi, :beauty:

lilleboybk · 28/9/24

Q4 lúc thi em chưa giải do nghĩ Q3 khó hơn. Giờ đọc Q4 thấy với mỗi xâu con của word1, mình chặt nhị phân để tìm tiền tố chung dài nhất + hậu tố chung dài nhất của nó với word2, nếu tổng độ dài 2 cái này >= word2.length - 1 thì là thoả mãn.

freedom.9 · 28/9/24

seastar đã nói:
Tầm sư học code đi, t lấy rate thấp thôi,

Thôi lần này t quyết tâm đi học C++ rồi, ko thể nào cay hơn được. Mấy contest rồi =((

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

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

Member

Senior Member

Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này