thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

freedom.9 · 29/9/25

LmaoSuVuong đã nói:
e giải toàn kiểu ngồi ngâm, observe data 1 lúc lâu mới giải, làm kiểu đó vào là thấy cho rớt từ vòng gửi xe r nghe mấy lò luyện pvan trên mạng toàn kêu chấm cảđiểm giao tiếp. điểm trình bày suy nghĩ nữa

Chắc do vibe coding nhiều quá hư não rồi đó fen

via theNEXTvoz for iPhone

Husqvarna701SM · 29/9/25

huungphan đã nói:
móc mỉa gì đâu, mấy cty tier 1/faang thì pv mid level hỏi dsa là chính mà, mà đa số là medium thôi, chừng nào senior thì mới đòi hỏi cao về system design. Trong này quất hard ầm ầm làm mình thắc mắc là mấy thím có đi pv ko?

T chưa phỏng vấn faang nhưng pv tier 1 ở VN thì làm 2 câu hard còn oa là medium rồi nhé thím
Với làm contest làm vui vui là chính thôi

Husqvarna701SM · 29/9/25

nói chung là phỏng vấn cũng vô vàn, tôi chơi với 1 thằng cũng tryhard thi icpc (tạch ở vòng chọn đội), tầm 2k cf gì đấy thì đi phỏng vấn k ăn dc bài calculator nhé, bị dí dí tí lăn đùng ra ngay

athxzz · 30/9/25

ngâm mãi vẫn chưa hiểu Q3 của weekly contest tuần trước =((

freedom.9 · 30/9/25

athxzz đã nói:
ngâm mãi vẫn chưa hiểu Q3 của weekly contest tuần trước

Cái q3 nó là thế này, zigzag nghĩa là 3 phần tử liên tiếp nó form cái shape như này \/ hoặc là /\.
Nếu dpUp[index][val] là số cách chọn ở index i với val mà index tiếp theo là up, thì số cách chọn dpUp[index][val] sẽ là tổng của dpDown[i-1][preVal] ở đây preVal phải > val hiện tại mình muốn chọn. Để có thể form đc cái shape như này \/.
Tương tự với dpDown[index][val] nó sẽ form đc cái shape Zigzag như này
/\, số cách chọn dpDown[index][val] sẽ là tổng của dpUp[i-1][preVal] ở đây preVal phải < val

Python:

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 10**9 + 7
        up = [0] * (r + 2)
        down = [0] * (r + 2)
        for j in range(l, r + 1):
            up[j] = 1
            down[j] = 1

        prefixUp = [0] * (r + 2)
        postfixDown = [0] * (r + 2)

        s = 0
        for j in range(l, r + 1):
            s += up[j]
            prefixUp[j] = s % MOD
        s = 0
        for j in range(r, l - 1, -1):
            s += down[j]
            postfixDown[j] = s % MOD

        for _ in range(1, n):
            cUp = [0] * (r + 2)
            cDown = [0] * (r + 2)
            for j in range(l, r + 1):
                cUp[j] = postfixDown[j + 1]
                cDown[j] = prefixUp[j - 1]

            up, down = cUp, cDown

            s = 0
            for j in range(l, r + 1):
                s += up[j]
                prefixUp[j] = s % MOD
              
            s = 0
            for j in range(r, l - 1, -1):
                s += down[j]
                postfixDown[j] = s % MOD

        return (sum(up[l:r + 1]) + sum(down[l:r + 1])) % MOD

Nếu nghĩ theo hướng index là phần tử middle giữa 3 phần tử để form 1 cái zigzag thì implement khá dễ với prefixSum với bottom up, mình đi dp topdown rồi maintain cái biến streak nên ko làm ra do time complexity cao quá.

athxzz · 30/9/25

freedom.9 đã nói:
Cái q3 nó là thế này, zigzag nghĩa là 3 phần tử liên tiếp nó form cái shape như này \/ hoặc là /\.
Nếu dpUp[index][val] là số cách chọn ở index i với val mà index tiếp theo là up, thì số cách chọn dpUp[index][val] sẽ là tổng của dpDown[i-1][preVal] ở đây preVal phải > val hiện tại mình muốn chọn. Để có thể form đc cái shape như này \/.
Tương tự với dpDown[index][val] nó sẽ form đc cái shape Zigzag như này
/\, số cách chọn dpDown[index][val] sẽ là tổng của dpUp[i-1][preVal] ở đây preVal phải < val

Python:

class Solution: def zigZagArrays(self, n: int, l: int, r: int) -> int: MOD = 10**9 + 7 up = [0] * (r + 2) down = [0] * (r + 2) for j in range(l, r + 1): up[j] = 1 down[j] = 1 prefixUp = [0] * (r + 2) postfixDown = [0] * (r + 2) s = 0 for j in range(l, r + 1): s += up[j] prefixUp[j] = s % MOD s = 0 for j in range(r, l - 1, -1): s += down[j] postfixDown[j] = s % MOD for _ in range(1, n): cUp = [0] * (r + 2) cDown = [0] * (r + 2) for j in range(l, r + 1): cUp[j] = postfixDown[j + 1] cDown[j] = prefixUp[j - 1] up, down = cUp, cDown s = 0 for j in range(l, r + 1): s += up[j] prefixUp[j] = s % MOD s = 0 for j in range(r, l - 1, -1): s += down[j] postfixDown[j] = s % MOD return (sum(up[l:r + 1]) + sum(down[l:r + 1])) % MOD

Nếu nghĩ theo hướng index là phần tử middle giữa 3 phần tử để form 1 cái zigzag thì implement khá dễ với prefixSum với bottom up, mình đi dp topdown rồi maintain cái biến streak nên ko làm ra do time complexity cao quá.

quả não tàn của e chỉ làm được top down nhưng TLE =((

Number of ZigZag Arrays I - LeetCode (https://leetcode.com/problems/number-of-zigzag-arrays-i/submissions/1787387402/)

freedom.9 · 1/10/25

athxzz đã nói:
quả não tàn của e chỉ làm được top down nhưng TLE

Number of ZigZag Arrays I - LeetCode (https://leetcode.com/problems/number-of-zigzag-arrays-i/submissions/1787387402/)

TLE là đúng rồi vì nếu đi theo hướng này nó là On^4 mà, phải có cách chuyển về prefixsum để giải còn On^2 thôi.
Có thể giải được bằng On^3 bằng cách dp(i, streak, lastVal) và bên trong thì loop từ last tới right + 1 hoặc left tới last nhưng mà cũng chết =((

vì với cách này ko tận dụng đc prefixSum để giảm về O(n^2)
Cái key point bài này là phải nghĩ cách để bỏ cái biến streak ra, maintain cái streak này thì ko giải được :ah:

athxzz · 1/10/25

freedom.9 đã nói:
TLE là đúng rồi vì nếu đi theo hướng này nó là On^4 mà, phải có cách chuyển về prefixsum để giải còn On^2 thôi.
Có thể giải được bằng On^3 bằng cách dp(i, streak, lastVal) và bên trong thì loop từ last tới right + 1 hoặc left tới last nhưng mà cũng chết vì với cách này ko tận dụng đc prefixSum để giảm về O(n^2)
Cái key point bài này là phải nghĩ cách để bỏ cái biến streak ra, maintain cái streak này thì ko giải được

sao lại O(N^4) được bác? O(N*M) thôi chứ, N = max n, M = max(r - l + 1) vì dfs cũng chỉ là O(1) thôi mà vì cache lại toàn bộ mảng dp thì cao nhất là 2 * 2000 * 2000. Chẳng qua chạy recursion nên nó bị TLE. Em chạy worst case riêng vẫn ổn mà

freedom.9 · 1/10/25

athxzz đã nói:
sao lại O(N^4) được bác? O(N*M) thôi chứ, N = max n, M = max(r - l + 1) vì dfs cũng chỉ là O(1) thôi mà vì cache lại toàn bộ mảng dp thì cao nhất là 2 * 2000 * 2000. Chẳng qua chạy recursion nên nó bị TLE. Em chạy worst case riêng vẫn ổn mà
Xem tệp đính kèm 3263781

À đúng rồi mình đọc nhầm tưởng bác shrink cái left right qua cái do function do viết &l, &r, &n.
Vậy chỉ là 2*2000*2000 thôi mà sao nó ko pass hết nhỉ

Submit lại lần nữa xem có ok ko, c++ là nhanh nhất rồi mà
via theNEXTvoz for iPhone

freedom.9 · 1/10/25

athxzz đã nói:
sao lại O(N^4) được bác? O(N*M) thôi chứ, N = max n, M = max(r - l + 1) vì dfs cũng chỉ là O(1) thôi mà vì cache lại toàn bộ mảng dp thì cao nhất là 2 * 2000 * 2000. Chẳng qua chạy recursion nên nó bị TLE. Em chạy worst case riêng vẫn ổn mà
Xem tệp đính kèm 3263781

Mình viết Python thế này cũng TLE dù bottom up đây, phải nhờ chat GPT nó optimize dùng variable thay vì xử lí trên mảng prefixSum trực tiếp mới pass, ảo lắm.

Number of ZigZag Arrays I - LeetCode

Can you solve this real interview question? Number of ZigZag Arrays I - You are given three integers n, l, and r. A ZigZag array of length n is defined as follows: * Each element lies in the range [l, r]. * No two adjacent elements are equal. * No three consecutive elements form a strictly...

leetcode.com

Mấy thằng rank cao nó switch solution khiếp vãi, đầu óc nhảy số nhanh, kiên nhẫn ngồi debug rồi chửi Leetcode :sweat:

freedom.9 · 2/10/25

Rank 7xx mà được cộng có 17 điểm =((

Mà cái rank này hơi ảo nhỉ, xưa rank 8 900 tầm rank này là cộng cũng phải 30 điểm

Chắc phải 2 cái contests nữa rank 5xx mới lên nổi, thời đại AI khó leo rank quá :ah:

aNotHeRNo0b · 2/10/25

freedom.9 đã nói:
Rank 7xx mà được cộng có 17 điểm Mà cái rank này hơi ảo nhỉ, xưa rank 8 900 tầm rank này là cộng cũng phải 30 điểm
Xem tệp đính kèm 3265526Chắc phải 2 cái contests nữa rank 5xx mới lên nổi, thời đại AI khó leo rank quá

Bác xem cái này ở đâu vậy, em tìm mãi k thấy

LmaoSuVuong · 2/10/25

aNotHeRNo0b đã nói:
Bác xem cái này ở đâu vậy, em tìm mãi k thấy

cái này trong tab contest/my contest chứ đâu. mà thứ 5 mới cập nhật

Husqvarna701SM · 3/10/25

Husqvarna701SM đã nói:
Xem tệp đính kèm 3234705
Bắt đầu hard core r 4/4 vẫn feed rank

24xx roài

Manmapi · 4/10/25

Mới làm thử virtual weekly tuần trước. Làm được câu 3 nma tạch câu 4. Câu 4 phải nhìn được nó dưới dạng matrix multiplication và đưa về fast exponential để giảm xuống còn log(n)

Manmapi · 4/10/25

freedom.9 đã nói:
Cái q3 nó là thế này, zigzag nghĩa là 3 phần tử liên tiếp nó form cái shape như này \/ hoặc là /\.
Nếu dpUp[index][val] là số cách chọn ở index i với val mà index tiếp theo là up, thì số cách chọn dpUp[index][val] sẽ là tổng của dpDown[i-1][preVal] ở đây preVal phải > val hiện tại mình muốn chọn. Để có thể form đc cái shape như này \/.
Tương tự với dpDown[index][val] nó sẽ form đc cái shape Zigzag như này
/\, số cách chọn dpDown[index][val] sẽ là tổng của dpUp[i-1][preVal] ở đây preVal phải < val

Python:

class Solution: def zigZagArrays(self, n: int, l: int, r: int) -> int: MOD = 10**9 + 7 up = [0] * (r + 2) down = [0] * (r + 2) for j in range(l, r + 1): up[j] = 1 down[j] = 1 prefixUp = [0] * (r + 2) postfixDown = [0] * (r + 2) s = 0 for j in range(l, r + 1): s += up[j] prefixUp[j] = s % MOD s = 0 for j in range(r, l - 1, -1): s += down[j] postfixDown[j] = s % MOD for _ in range(1, n): cUp = [0] * (r + 2) cDown = [0] * (r + 2) for j in range(l, r + 1): cUp[j] = postfixDown[j + 1] cDown[j] = prefixUp[j - 1] up, down = cUp, cDown s = 0 for j in range(l, r + 1): s += up[j] prefixUp[j] = s % MOD s = 0 for j in range(r, l - 1, -1): s += down[j] postfixDown[j] = s % MOD return (sum(up[l:r + 1]) + sum(down[l:r + 1])) % MOD

Nếu nghĩ theo hướng index là phần tử middle giữa 3 phần tử để form 1 cái zigzag thì implement khá dễ với prefixSum với bottom up, mình đi dp topdown rồi maintain cái biến streak nên ko làm ra do time complexity cao quá.

Cái này bác log ra sẽ thấy top == down[::-1]
Nên câu này chỉ cần 1 array dp thôi là đủ.

Qua Q4 thì phải biểu diễn được cái array dp này dưới dạng phép nhân ma trận

Python:

MOD = 1_000_000_007

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        m = r - l + 1
        dp = [i for i in range(m)]
        for _ in range(n - 2):
            new_dp = [0]
            curr = dp[m - 1] % MOD
            i = m - 1
            while i > 0:
                new_dp.append(curr % MOD)
                i -= 1
                curr += dp[i]
                curr %= MOD
            dp = new_dp[:]
        return (sum(dp) * 2) % MOD

Husqvarna701SM · 4/10/25

Manmapi đã nói:
Cái này bác log ra sẽ thấy top == down[::-1]
Nên câu này chỉ cần 1 array dp thôi là đủ.

Qua Q4 thì phải biểu diễn được cái array dp này dưới dạng phép nhân ma trận

Python:

MOD = 1_000_000_007 class Solution: def zigZagArrays(self, n: int, l: int, r: int) -> int: m = r - l + 1 dp = [i for i in range(m)] for _ in range(n - 2): new_dp = [0] curr = dp[m - 1] % MOD i = m - 1 while i > 0: new_dp.append(curr % MOD) i -= 1 curr += dp[i] curr %= MOD dp = new_dp[:] return (sum(dp) * 2) % MOD

Về cơ bản là markov chain :big_smile:

Windows 2001 · 5/10/25

Tuần này được 4Q, hehe :big_smile:

freedom.9 · 5/10/25

Code mãi ko ra cái digit dp, lại 3Q gang rồi cay thật

aNotHeRNo0b · 5/10/25

:> gap câu cuối rồi, câu cuối DP digit làm ít + DNA issue thì chịu

thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

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

Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này