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

i-am-groot · 21/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

nếu pass rồi có khi nó k rejudge đâu

freedom.9 · 23/10/24

i-am-groot đã nói:
nếu pass rồi có khi nó k rejudge đâu

vl leetcode nó ko rejudge, rank 263 thấy nhục quá :ah:

seastar · 23/10/24

freedom.9 đã nói:
vl leetcode nó ko rejudge, rank 263 thấy nhục quá

Thấy nhục thì tuần này tự feed làm 1 bài thôi để trừ bù nào, :ah:

freedom.9 · 23/10/24

seastar đã nói:
Thấy nhục thì tuần này tự feed làm 1 bài thôi để trừ bù nào,

cũng là 1 ý kiến hay

freedom.9 · 27/10/24

Gỡ rank biweekly nào ae ơi :ah:

mazda6 · 27/10/24

Cảm giác như tụi kia nó thuộc hết giải thuật, vô là gõ ầm ầm thôi
Giờ phải học ntn vậy các fen, cắm đầu giải đề thấy vô vọng quá

kai_tran · 27/10/24

2 câu hard khó quá, không giải được @@

kai_tran · 27/10/24

đọc không có ý tưởng để giải như nào lun, câu GCD tưởng giống với contest mấy tuần trước nhưng thấy cũng không bắt sóng để giải được.
Nên off sớm ăn cơm trưa ^^

thangkc89 · 27/10/24

vl, câu 3 mình ra DP dpt O(n * max(nums)^2) ~ O(n^3)mà nộp code Python chứ TLE cay thật

thanhdonguyen01 · 27/10/24

mazda6 đã nói:
Cảm giác như tụi kia nó thuộc hết giải thuật, vô là gõ ầm ầm thôi
Giờ phải học ntn vậy các fen, cắm đầu giải đề thấy vô vọng quá

Ngày ngày ngồi cày các dạng thôi thím :sad:

Mà học sinh với sinh viên thì mới có thời gian cày trâu đến thế, chứ đi làm rồi hoặc học lên cao (như Master), thì thời gian ngồi cày mấy cái này còn ít lắm :sad:

freedom.9 · 27/10/24

vl câu 4 đọc lộn đề tưởng t < 10^5 :ah:

Câu 2 ăn 2 bọ cay thật, sao Q4 nó giải được nhiều thế nhỉ

freedom.9 · 27/10/24

Câu hard Q3 DP cơ bản mà các fence :ah:

mình ăn 1 bug do quên cái MOD, total 3 bugs cmnr

Python:

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        @lru_cache(None)
        def dp(gcd1, gcd2, index):
            if index == len(nums):
                if gcd1 == -1 or gcd2 == -1:
                    return 0
                    
                return int(gcd1 == gcd2)

            ans = 0

            ans += dp(gcd1, gcd2, index + 1)
            if gcd1 == -1:
                ans += dp(nums[index], gcd2, index + 1)
            else:
                ans += dp(math.gcd(gcd1, nums[index]), gcd2, index + 1)

            if gcd2 == -1:
                ans += dp(gcd1, nums[index], index + 1)
            else:
                ans += dp(gcd1, gcd(gcd2, nums[index]), index + 1)
            return ans%MOD

        return dp(-1, -1, 0)%MOD

freedom.9 · 27/10/24

Q2 khắm lọ vl đm nhà nó =((

mãi mới nghĩ ra là xử lí mỗi lần transform trên cái counter nó sẽ cho time complexity 26*t tốn tgian vl
Lúc đầu cứ ngồi nghĩ xoay cái string s ra =((

thangkc89 · 27/10/24

Bài 3 e cũng dp nhưng bottom up sao nó lại TLE được nhể :beat_shot:

200^3 quá là nhỏ mà ta

Python:

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        max_num = max(nums)
        n = len(nums)
        f = [[0] * (max_num + 1) for _ in range(max_num + 1)]
        g = [[0] * (max_num + 1) for _ in range(max_num + 1)]


        gcd_cache = dict()
        
        @lru_cache(maxsize=None)
        def find_gcd(i, j):
            return math.gcd(i, j)

        
        f[0][0] = 1
        for k in range(n):
            for i in range(max_num + 1):
                for j in range(max_num + 1):
                    g[i][j] = f[i][j]
                    f[i][j] = 0
            for i in range(max_num + 1):
                for j in range(max_num + 1):
                    f[i][j] = (f[i][j] + g[i][j]) % MOD
                    set_a_gcd = find_gcd(i, nums[k])
                    f[set_a_gcd][j] = (f[set_a_gcd][j] + g[i][j]) % MOD
                    set_b_gcd = find_gcd(j, nums[k])
                    f[i][set_b_gcd] = (f[i][set_b_gcd] + g[i][j]) % MOD

        res = 0
        for gcd_ in range(1, max_num + 1):
            res = (res + f[gcd_][gcd_]) % MOD

        return res

freedom.9 · 27/10/24

thangkc89 đã nói:

Bài 3 e cũng dp nhưng bottom up sao nó lại TLE được nhể :beat_shot:

200^3 quá là nhỏ mà ta

Python:

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        max_num = max(nums)
        n = len(nums)
        f = [[0] * (max_num + 1) for _ in range(max_num + 1)]
        g = [[0] * (max_num + 1) for _ in range(max_num + 1)]


        gcd_cache = dict()
       
        @lru_cache(maxsize=None)
        def find_gcd(i, j):
            return math.gcd(i, j)

       
        f[0][0] = 1
        for k in range(n):
            for i in range(max_num + 1):
                for j in range(max_num + 1):
                    g[i][j] = f[i][j]
                    f[i][j] = 0
            for i in range(max_num + 1):
                for j in range(max_num + 1):
                    f[i][j] = (f[i][j] + g[i][j]) % MOD
                    set_a_gcd = find_gcd(i, nums[k])
                    f[set_a_gcd][j] = (f[set_a_gcd][j] + g[i][j]) % MOD
                    set_b_gcd = find_gcd(j, nums[k])
                    f[i][set_b_gcd] = (f[i][set_b_gcd] + g[i][j]) % MOD

        res = 0
        for gcd_ in range(1, max_num + 1):
            res = (res + f[gcd_][gcd_]) % MOD

        return res

Fence thử tìm cách convert qua c++ thử xem, bọn Leetcode này nó ghét python users lắm

thangkc89 · 27/10/24

thangkc89 đã nói:

Bài 3 e cũng dp nhưng bottom up sao nó lại TLE được nhể :beat_shot:

200^3 quá là nhỏ mà ta

Python:

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        max_num = max(nums)
        n = len(nums)
        f = [[0] * (max_num + 1) for _ in range(max_num + 1)]
        g = [[0] * (max_num + 1) for _ in range(max_num + 1)]


        gcd_cache = dict()
       
        @lru_cache(maxsize=None)
        def find_gcd(i, j):
            return math.gcd(i, j)

       
        f[0][0] = 1
        for k in range(n):
            for i in range(max_num + 1):
                for j in range(max_num + 1):
                    g[i][j] = f[i][j]
                    f[i][j] = 0
            for i in range(max_num + 1):
                for j in range(max_num + 1):
                    f[i][j] = (f[i][j] + g[i][j]) % MOD
                    set_a_gcd = find_gcd(i, nums[k])
                    f[set_a_gcd][j] = (f[set_a_gcd][j] + g[i][j]) % MOD
                    set_b_gcd = find_gcd(j, nums[k])
                    f[i][set_b_gcd] = (f[i][set_b_gcd] + g[i][j]) % MOD

        res = 0
        for gcd_ in range(1, max_num + 1):
            res = (res + f[gcd_][gcd_]) % MOD

        return res

Vãi, thêm

Python:

if g[i][j] == 0:
    continue

thì pass, sao time limit lại strict vậy nhỉ

freedom.9 · 27/10/24

thangkc89 đã nói:
Vãi, thêm

Python:

if g[i][j] == 0: continue

thì pass, sao time limit lại strict vậy nhỉ

Nó để n = 100 thì chắc pass, còn n = 200 thì hên xui lắm =((

Kêu mình viết bottom up mình ko viết nổi, mà fen có làm đc q4 ko sao tụi q4 nó accepted nhiều thế nhỉ :ah:

đọc thì thấy phải transform qua matrix gì lạ vl

thangkc89 · 27/10/24

freedom.9 đã nói:
Nó để n = 100 thì chắc pass, còn n = 200 thì hên xui lắm
Kêu mình viết bottom up mình ko viết nổi, mà fen có làm đc q4 ko sao tụi q4 nó accepted nhiều thế nhỉ đọc thì thấy phải transform qua matrix gì lạ vl

e code ra solution ra Q3 khá nhanh, mà lỗi TLE xàm quá dỗi éo code tiếp nên chưa đọc Q4

Vừa lên guardian nay lại xuống r

P/s: Thêm 1 bài học là ko phải lúc nào cũng nên bottom-up, vì có thể cái dp matrix có thể khá thưa =((

freedom.9 · 27/10/24

thangkc89 đã nói:
e code ra solution ra Q3 khá nhanh, mà lỗi TLE xàm quá dỗi éo code tiếp nên chưa đọc Q4
Vừa lên guardian nay lại xuống r

Sáng mình cũng động kinh q2 dịch lộn ancestor là hậu duệ làm ko làm đc Q2 =((

nay đc cộng ít điểm vừa đủ buổi sáng. Cái q2 contest lúc nào nó cũng trigger mình vl. Lần nào cũng rất vướng cái Q2 :ah:

Q4 tụi nó cheat rầm rầm cmnr

nahnahinin · 27/10/24

các bác lì đấy, e là e bỏ contest cmnr, mấy page đầu giờ cũng toàn cheat chứ ko phải chỉ top giữa bxh nữa, nhìn nản vl.

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này