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

thangkc89 · 27/10/24

nahnahinin đã nói:
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.

không hiểu tụi nó cheat kiểu gì hay vậy nhỉ, mình cũng thử đưa đề cho chatgpt thử mà nó ra solution ngu lắm

chắc do xài bản free

freedom.9 · 27/10/24

Làm lòi trĩ ko bằng mấy thằng cheater :ah:

sáng trừ 30 điểm giờ đc cộng 11 điểm =((

Thế đếch nào Q4 lại có tới mấy 800 thằng làm được nhỉ

lilleboybk · 27/10/24

Nay em giải được 2Q, may Q3 + Q4 ít ông làm được. Q3 cách DP dị quá, lần đầu em thấy luôn.

freedom.9 · 27/10/24

lilleboybk đã nói:
Nay em giải được 2Q, may Q3 + Q4 ít ông làm được. Q3 cách DP dị quá, lần đầu em thấy luôn.

Q4 tụi nó cheat bay cả bảng xếp hạng, Q3 thì mình ko biết =((

mazda6 · 27/10/24

nahnahinin đã nói:
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.

bon no cheat ntn?

Tinh Hoa Đông Lào · 27/10/24

Python:

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        MOD = 1000_000_007

        matrix = [[1 if i == j else 0 for j in range(26)] for i in range(26)]

        for row in matrix:
            prev = row.copy()
            for j in range(t):
                for i in range(26):
                    if i == 0:
                        row[i] = prev[25]
                    elif i == 1:
                        row[i] = prev[25] + prev[0]
                    else:
                        row[i] = prev[i-1]

                prev = row.copy()

        ans = 0
        for char in s:
            row_index = ord(char) - ord('a')
            ans += sum(matrix[row_index]) % MOD

        return ans % MOD

Q2 mình làm như trên, mình tính độ phức tạp là 26 * 26 * t là 26 * 26 * 10 ^ 5 sao lại bị TLE nhỉ mn

freedom.9 · 27/10/24

Tinh Hoa Đông Lào đã nói:

Python:

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        MOD = 1000_000_007
        alphabet = 'abcdefghijklmnopqrstuvwxyz'

        arr = [[0] * 26 for _ in range(26)]

        for index, row in enumerate(arr):
            row[index] = 1
            prev = row.copy()
            for j in range(t):
                for i in range(26):
                    if i == 0:
                        row[i] = prev[25]
                    elif i == 1:
                        row[i] = prev[25] + prev[0]
                    else:
                        row[i] = prev[i-1]

                prev = row.copy()

        ans = 0
        for char in s:
            row_index = ord(char) - ord('a')
            ans += sum(arr[row_index]) % MOD

        return ans % MOD

Q2 mình làm như trên, mình tính độ phức tạp là 26 * 26 * t là 26 * 26 * 10 ^ 5 sao lại bị TLE nhỉ mn

Của fence là 52*t*52 do cái hàm copy, duyệt thêm cái S ở cuối nữa TLE là đúng.

via theNEXTvoz for iPhone

Tinh Hoa Đông Lào · 27/10/24

freedom.9 đã nói:
Của fence là 52*t*52 do cái hàm copy, duyệt thêm cái S ở cuối nữa TLE là đúng.

via theNEXTvoz for iPhone

tính chính xác là
loop 1: 26* (26 + t * 26)
loop 2: t * 26

tổng = (26 * 26 + 26*26*t) +26*t = 26 * 26 + 26 * 27 * t :too_sad:

freedom.9 · 27/10/24

Tinh Hoa Đông Lào đã nói:
cái cuối cũng là 10^5 * 26 thui, vậy tổng là O(52*52*10^5)

Khi mà fence reach tới linear 10**8 thì thêm vô mấy cái loop nữa nó đều dễ làm fen TLE lắm. Nhất là với Python nữa.
Nên là giải bài hạn chế nhất tới 10**8 có thể fen.
Bài này fen nghĩ đơn giản là ở mỗi lần transform thì chỉ có z chuyển về thành ab còn lại transform số kí tự ở counter i qua i + 1 là xong, đm dễ thế mà mình ko nghĩ ra làm mãi mới xong :sweat:

via theNEXTvoz for iPhone

nahnahinin · 27/10/24

mazda6 đã nói:
bon no cheat ntn?

có con gpt mới ra mạnh lắm, mà ko biết sao để access. chứ 3.5 với 4 ngu như con lợn, trừ khi đề cũ mấy bố duyệt ko cẩn thận bê ra làm contest thì nó mới làm được.

New OpenAI model achieves 1800 rating - Codeforces

Codeforces. Programming competitions and contests, programming community

codeforces.com

rating gần CM như này thì ăn 90% vozer rồi.

freedom.9 · 27/10/24

nahnahinin đã nói:
có con gpt mới ra mạnh lắm, mà ko biết sao để access. chứ 3.5 với 4 ngu như con lợn, trừ khi đề cũ mấy bố duyệt ko cẩn thận bê ra làm contest thì nó mới làm được.

New OpenAI model achieves 1800 rating - Codeforces

Codeforces. Programming competitions and contests, programming community

codeforces.com

rating gần CM như này thì ăn 90% vozer rồi.

Đánh giá vozers hơi cao :shame:

Tụi Leetcode nên chuyển qua cho đề bằng hình ảnh thay vì text + random đề + Opt cho mỗi user nữa. Mà giờ tụi nó cheat thì ko thể tránh khỏi rồi :too_sad:

q4 8 điểm 800 thằng giải được thì nghỉ chơi cmn luôn

via theNEXTvoz for iPhone

LmaoSuVuong · 27/10/24

freedom.9 đã nói:
Đánh giá vozers hơi cao
Tụi Leetcode nên chuyển qua cho đề bằng hình ảnh thay vì text + random để cho mỗi user nữa. Mà giờ tụi nó cheat thì ko thể tránh khỏi rồi q4 8 điểm 800 thằng giải được thì nghỉ chơi cmn luôn

via theNEXTvoz for iPhone

đọc thử code của thằng ấn top 1 q4 nó giải có chục dòng mà 8d mà sao giải ngắn v nhỉ

freedom.9 · 27/10/24

LmaoSuVuong đã nói:
đọc thử code của thằng ấn top 1 q4 nó giải có chục dòng mà 8d mà sao giải ngắn v nhỉ

Chục dòng đó cả một nghệ thuật, nghe bảo là nhân ma trận gì gì đấy :sweat:

trước giờ làm Leetcode chưa từng gặp

via theNEXTvoz for iPhone

lilleboybk · 27/10/24

freedom.9 đã nói:
Chục dòng đó cả một nghệ thuật, nghe bảo là nhân ma trận gì gì đấy trước giờ làm Leetcode chưa từng gặp

via theNEXTvoz for iPhone

Nhân ma trận dùng cho mấy bài toán có công thức quy nạp thì phải. Như tìm số Fibo thứ n, bác dùng nhân ma trận có thể giải trong O(log(n)).

Nth Fibonacci Number - GeeksforGeeks

The Fibonacci numbers are the numbers in the following integer sequence. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,....Program for Fibonacci Numbers:

www.geeksforgeeks.org

noobdev · 31/10/24

chấm hóng

h_ngyn · 31/10/24

Không biết tụi Leetcode nó chấm lại kiểu gì, bữa biweekly rank 3k, nay vào thấy leo lên 1k4 không bị trừ điểm.

thangkc89 · 31/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

Solution đã được accepted sau khi complain với Leetcode

Dạo này cutoff của Guardian xuống sâu quá, tầm 215x là được rồi, các bác tranh thủ

freedom.9 · 31/10/24

h_ngyn đã nói:
Không biết tụi Leetcode nó chấm lại kiểu gì, bữa biweekly rank 3k, nay vào thấy leo lên 1k4 không bị trừ điểm.

Vì bài 2 tụi nó rejude + cheaters đó fen, bữa thấy tụi nó tìm parent bằng cách On**2 vẫn pass, dfs bằng backtrack thì mới pass nổi. Đọc lộn đề Q2 chứ ko làm ngon ăn rồi.

thangkc89 đã nói:
Solution đã được accepted sau khi complain với Leetcode
Xem tệp đính kèm 2758242
Dạo này cutoff của Guardian xuống sâu quá, tầm 215x là được rồi, các bác tranh thủ Xem tệp đính kèm 2758245

Contest tới mà ko động kinh là lên rồi :ah:

Tintin19 · 2/11/24

Mới giải được 2 sums,

. Công nhận từ ngày có gpt học sâu hẳn, bữa lên hỏi nó ứng dụng thực tế vào cuộc sống bài toán này, nghe thấy có hứng thú học dsa hẳn, chứ ko phải giải xong rồi qua bài khác như thời học cấp 3.
Quan trọng vẫn là tư duy, ko cần giải mấy bài hardcore đâu, nếu trình bình thường.

namkt123 · 2/11/24

anh @freedom.9 ơi, em mới stalk profile leetcode của a, khủng vãi. Có cách nào để a kiên trì với mục tiêu của mình thế ạ, anh chia sẻ cho anh em với

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này