thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
lilleboybk
Senior Member
Lần đầu em giải được Q4 
. Tuy k<= 10^9, nhưng may phát hiện ra tập trạng thái để quy hoạch động lại khá nhỏ.
. Tuy k<= 10^9, nhưng may phát hiện ra tập trạng thái để quy hoạch động lại khá nhỏ.
NguyenQUy1801
Senior Member
E cũng hao hao bác , q2 ăn 3 bug
freedom.9
Senior Member
Ừ đú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.Xem tệp đính kèm 2500185
Lần đầu em giải được Q4
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
câu 2 em cũng bị 3 bug.
Lúc đầu em dùng chia để trị + cache nhưng vẫn bị TLE.
Sau đó em thấy tính monotonic, nếu A[l..r] không phải special thì => A[l..r+1] cũng không phải special => nên chọn binary search + cache
lovelyly
Senior Member
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)
hieunm3538
Senior Member
Mình tìm số lần nhảy có thể dẫn đến bậc thang k, công thức là k = 2 **(jump) - back với 0 < back < jump + 1. Sau đấy duyệt từng số lượt jump, tính comb(jump + 1, back) là xong
honda stone
Junior Member
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
bao giờ lên guardian em quay lại voz 13p xong 3q nhưng TLE ở q4 đần vc
NguyenQUy1801
Senior Member
Bác làm hay thật, để e nghiên cứu code theo cách này
freedom.9
Senior Member
Q4 làm DP nhiều là thấy state fence ơithấy thiên hạ hơn 2k người giải được q4, thôi em lặn 1 thời gian để tu đây
13p xong 3q nhưng TLE ở q4 đần vc
freedom.9
Senior Member
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.
lilleboybk
Senior Member
Em cũng dính hai bọ bài 2, tạo 1 mảng cộng dồn: count = số cặp liền nhau "lỗi" từ 0 ->i. Rồi đem so sánh count[l] === count[r-1].Ừ đú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
hieunm3538
Senior Member
Không cần xử lý trùng ý anh, result += m*n là được đó. Counter bác đếm cũng là m*n mà
seastar
Member
Nó trùng là do cặp (i,j) (j,i) được đếm là 2 cặp riêng biệt. Trong khi bài này thì chỉ là 1 cặp. Nên sau khi đếm hết, result trả về chia 2 là xong. Code bài 3 của t đây
Python:
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//2freedom.9
Senior Member
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
via theNEXTvoz for iPhone
LmaoSuVuong
Senior Member
luyện 100 bài hard tự giải ko xem sol chắc là tàng tàng mỗi contest lên 50pTụ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
GD-Cuong
Member
thì nó là math mà
dp chỉ để tìm combination thôi
- Trạng thái
Chủ đề tương tự
