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

lovelyly said:

Q3: đếm số chữ số theo từng hàng, từ hàng đơn vị lên hàng chục, hàng trăm,...
Ở mỗi hàng, đếm xong nếu thấy có m chữ số i, n chữ số j (với i khác j) thì result += m * n...

Q4: Sau m lần nhảy lên và n lần đi xuống thì sẽ dừng ở bậc thang 1 + 2^0 + 2^1 + ... + 2^(m-1) - n = 2*m - n
=> Với mỗi giá trị m tính n để 2*m - n = k rồi tính xem có bao nhiêu cách để nhảy lên m lần và đi xuống n lần (lưu ý: không được đi xuống 2 lần liên tục)

Click to expand...

honda stone said:

thấy thiên hạ hơn 2k người giải được q4, thôi em lặn 1 thời gian để tu đây bao giờ lên guardian em quay lại voz
13p xong 3q nhưng TLE ở q4 đần vc

Click to expand...

lovelyly said:

Q3: đếm số chữ số theo từng hàng, từ hàng đơn vị lên hàng chục, hàng trăm,...
Ở mỗi hàng, đếm xong nếu thấy có m chữ số i, n chữ số j (với i khác j) thì result += m * n...

Q4: Sau m lần nhảy lên và n lần đi xuống thì sẽ dừng ở bậc thang 1 + 2^0 + 2^1 + ... + 2^(m-1) - n = 2*m - n
=> Với mỗi giá trị m tính n để 2*m - n = k rồi tính xem có bao nhiêu cách để nhảy lên m lần và đi xuống n lần (lưu ý: không được đi xuống 2 lần liên tục)

Click to expand...

freedom.9 said:

Ừ đúng rồi fence, thực ra nhảy lên 2^i thì i chỉ có 9 thôi, thêm cái boolean nữa thì dp 3 chiều là dễ dàng.
Bài 3 dễ mà giải bài 2 tốn tgian quá gang thật, biết là xài prefixSum rồi mà quên mẹ mất cách biến đổi, khuya rồi đầu óc thật sự rất ngáo

Click to expand...

freedom.9 said:

Q3 mà đếm result m*n thì phải xử lí trùng mệt lắm, nên mình xài one pass luôn.
Thường mấy bài mà tìm pair i, j thì chỉ cần duyệt 1 lần rồi lưu vô counter để khỏi phải xử lí trùng thôi.

Click to expand...

freedom.9 said:

Q3 mà đếm result m*n thì phải xử lí trùng mệt lắm, nên mình xài one pass luôn.
Thường mấy bài mà tìm pair i, j thì chỉ cần duyệt 1 lần rồi lưu vô counter để khỏi phải xử lí trùng thôi.

Click to expand...

class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int:
        c = defaultdict(int)
        for num in nums:
            for i, d in enumerate(str(num)):
                c[(i,d)] += 1
        ret = 0
        for v in c.values():
            ret += v * (len(nums) - v)
        return ret//2

freedom.9 said:

Tụi leetcode nó ko xử lí cheaters hay sao ấy ae. Tụi nó cheat nhiều vl mất cả vui. Rank thì khó lên nữa


via theNEXTvoz for iPhone

Click to expand...

devhockem said:

Q4 solution siêu ngắn mà nghĩ hơn 1 tiếng không ra. Mình nghi nghi dùng DP nhưng lại cứ đi theo hướng Math, thế là tạch.

Click to expand...

NudeDuck said:

câu cuối mình thấy khó mà 2k người giải được ư

Click to expand...

freedom.9 said:

Tụi leetcode nó ko xử lí cheaters hay sao ấy ae. Tụi nó cheat nhiều vl mất cả vui. Rank thì khó lên nữa


via theNEXTvoz for iPhone

Click to expand...

NudeDuck said:

câu cuối mình thấy khó mà 2k người giải được ư

Click to expand...

hieunm3538 said:

Câu cuối mình nghĩ lý do có khoảng 2k người giải được vì bài này chỉ cần hiểu được công thức tính vị trí sau một số lần nhảy là ra, không yêu cầu implement bất kỳ thuật toán nào phức tạp )

Click to expand...

GD-Cuong said:

thì nó là math mà
dp chỉ để tìm combination thôi

Click to expand...

maskup said:

rating Q4 này chỉ có 2086, trong khi rating Q4 ở mấy contest trước đều tầm 2k5 trở lên.

Click to expand...

NguyenQUy1801 said:

xem rating mấy câu hỏi đâu v bác :V

Click to expand...