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

lovelyly · 20/10/24

Leetcode contest lần này được 3Q, còn Q4 thì bí rồi, không nghĩ ra được cách nào nhanh hơn O(n^2) hết

Violet_7 · 20/10/24

lovelyly đã nói:
Leetcode contest lần này được 3Q, còn Q4 thì bí rồi, không nghĩ ra được cách nào nhanh hơn O(n^2) hết

có cách đấy :shame:

freedom.9 · 20/10/24

4Q 1 bug do lỡ thêm cái cache ko cần thiết ăn cái MLE :ah:

đã quá pepsi ơi

freedom.9 · 20/10/24

Violet_7 đã nói:
box này trôi lạc thế. Nay đọc sai đề câu 3, mất mẹ 20 phút xàm lờ

Giải 3 câu trôi chảy mà câu 4 mình đọc mãi đề phải print ra mới thấy nhảm thế ko biết :ah:

Violet_7 · 20/10/24

freedom.9 đã nói:
Giải 3 câu trôi chảy mà câu 4 mình đọc mãi đề phải print ra mới thấy nhảm thế ko biết

câu 4 chính ra cx hay phết. còn thuật toán manacher thì chat gpt thôi :big_smile:

callmemark · 20/10/24

câu 3 dính TLE sieve :/

Violet_7 · 20/10/24

callmemark đã nói:
câu 3 dính TLE sieve :/

sieve 1001 thôi, sieve 10^6 là ăn TLE ngay :sweat:

freedom.9 · 20/10/24

Violet_7 đã nói:
sieve 1001 thôi, sieve 10^6 là ăn TLE ngay

Câu 3 phải giải bằng O(nsqrt(n)) là ăn nhỉ

lilleboybk · 20/10/24

callmemark đã nói:
câu 3 dính TLE sieve :/

Em cũng thế, làm Sàng nguyên tố 10^6 mà toàn TLE mấy TC bé tý. Mãi mới nghĩ chắc LC tính TLE dựa vào tổng thời gian chạy các TC, nên đến phần tử nào thì tìm cái proper divisor của nó luôn.

freedom.9 · 20/10/24

lilleboybk đã nói:
Em cũng thế, làm Sàng nguyên tố 10^6 mà toàn TLE mấy TC bé tý. Mãi mới nghĩ chắc LC tính TLE dựa vào tổng thời gian chạy các TC, nên đến phần tử nào thì tìm cái proper divisor của nó luôn.

Ở mỗi số mình tìm max factor luôn, time complexity đoạn này là sqrt(num). Mình ko nghĩ tới xài sieve gì cả vì ko thấy usecases chỗ prime factor

freedom.9 · 20/10/24

Violet_7 đã nói:
câu 4 chính ra cx hay phết. còn thuật toán manacher thì chat gpt thôi

Câu 4 dùng rolling hash cũng được nhỉ

lilleboybk · 20/10/24

freedom.9 đã nói:
Ở mỗi số mình tìm max factor luôn, time complexity đoạn này là sqrt(num). Mình ko nghĩ tới xài sieve gì cả vì ko thấy usecases chỗ prime factor

Đúng rồi bác, tại em làm theo lối mòn cứ có nguyên tố là bê cái sieve ra dùng thôi. Nay bác làm được Q4 thì lại gỡ được contest tuần trước.

h_ngyn · 20/10/24

freedom.9 đã nói:
Xem tệp đính kèm 2743013
4Q 1 bug do lỡ thêm cái cache ko cần thiết ăn cái MLE đã quá pepsi ơi

Sao cái sol Q4 của fen pass được hay vậy. :amazed:

Violet_7 · 20/10/24

freedom.9 đã nói:
Câu 4 dùng rolling hash cũng được nhỉ

đủ time complexity thì chắc đc thôi bác

freedom.9 · 20/10/24

h_ngyn đã nói:
Sao cái sol Q4 của fen pass được hay vậy.
Xem tệp đính kèm 2743043

Chắc nó rejudge cmnr rồi, nó accepted rồi nên mình ko sửa, nãy mình tính lộn time complexity đổi qua rolling hash mà éo kịp :ah:

Violet_7 · 20/10/24

freedom.9 đã nói:
Chắc nó rejudge cmnr rồi, nó accepted rồi nên mình ko sửa, nãy mình tính lộn time complexity đổi qua rolling hash mà éo kịp

mình xin điểm nhé bác :big_smile:

thangkc89 · 20/10/24

Nay code ẩu ăn 2 con bọ không đáng có

Python:

class Solution:
    def findAnswer(self, parent: List[int], s: str) -> List[bool]:
        n = len(parent)
        children = defaultdict(list)

        base = 31
        MOD = 10 ** 9 + 7
        p = [1] * (n + 1)
        children_count = [0] * n

        

        for i in range(1, n+1):
            p[i] = (p[i-1] * base) % MOD
        

        for i, p_node in enumerate(parent):
            if p_node == -1:
                continue
            children[p_node].append(i)
        
        def count_children(node):
            children_count[node] = 1
            for child in children[node]:
                count_children(child)
                children_count[node] += children_count[child]
        count_children(0)
        
        hash_array = [0] * (n + 1)
        reversed_hash_array = [0] * (n + 1)

        def dfs(node):
            for child in children[node]:
                dfs(child)
                hash_array[node] = (hash_array[node] * p[children_count[child]] + hash_array[child]) % MOD
            hash_array[node] = (hash_array[node] * base + ord(s[node]) - ord('a')) % MOD

        def reverse_dfs(node):
            
            reversed_hash_array[node] = (ord(s[node]) - ord('a')) % MOD
            for child in reversed(children[node]):
                reverse_dfs(child)
                reversed_hash_array[node] = (reversed_hash_array[node] * p[children_count[child]] + reversed_hash_array[child]) % MOD
            
        dfs(0)
        reverse_dfs(0)

        # print(hash_array)
        # print(reversed_hash_array)

        return [hash_array[i] == reversed_hash_array[i] for i in range(n)]

Takeitiz · 20/10/24

Nay em được 3Q thôi mà các anh ở đây toàn 4Q, mạnh quá.

freedom.9 · 20/10/24

Violet_7 đã nói:
mình xin điểm nhé bác

Câu 4 hay thật nhỉ, đi cái hash ngược left right top đi về top right left là ngon. Thấy học thêm được 1 cái variant mới ko đến nỗi khó lắm :beauty:

lilleboybk đã nói:
Đúng rồi bác, tại em làm theo lối mòn cứ có nguyên tố là bê cái sieve ra dùng thôi. Nay bác làm được Q4 thì lại gỡ được contest tuần trước.

Chắc mình bị rejudge rồi fence nhưng chắc vẫn cộng được mấy chục điểm, may làm q3 nhanh tay. Bài 4 hôm nay tính sai TC nữa rồi rút kinh nghiệm :too_sad:

via theNEXTvoz for iPhone

freedom.9 · 20/10/24

Giờ mình mới hiểu tại sao tụi nó hay random cái base cho rolling hash, lí do là để tránh gặp các anti testcases tạo ra các hash collision :sweat:

Hèn gì tụi nó xài rolling hash mượt mà ko sợ bị đụng

via theNEXTvoz for iPhone

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

Senior Member

Member

Senior Member

Senior Member

Member

Junior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này