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
13p xong 3q nhưng TLE ở q4 đần vc
Bác làm hay thật, để e nghiên cứu code theo cách nàyQ3: đế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)
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 bao giờ lên guardian em quay lại voz
13p xong 3q nhưng TLE ở q4 đần vc
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.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)
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
Không cần xử lý trùng ý anh, result += m*n là được đó. Counter bác đếm cũng là m*n mà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.
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 đâyQ3 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.
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
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
thì nó là math mà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.
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 )câu cuối mình thấy khó mà 2k người giải được ư
có đó fen, lần trước nó huỷ kết quả của hơn nghìn thằng mà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
rating Q4 này chỉ có 2086, trong khi rating Q4 ở mấy contest trước đều tầm 2k5 trở lên.câu cuối mình thấy khó mà 2k người giải được ư
Bài này khó ở chỗ đưa ra được nhận xét mà bạn nêu ra (sử dụng nhị thức Newton). Còn cài đặt thì ko quá phức tạp.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 )
Đúng ạ. Mình cũng đọc solutions rồi. Vì mình cứ đi theo lối mòn, đó là phải tìm hẳn ra công thức để tính ra kết quả, nên không ra.thì nó là math mà
dp chỉ để tìm combination thôi
xem rating mấy câu hỏi đâu v bác :Vrating Q4 này chỉ có 2086, trong khi rating Q4 ở mấy contest trước đều tầm 2k5 trở lên.
mình xem ở clist: Problems - CLIST (https://clist.by/problems/)xem rating mấy câu hỏi đâu v bác :V