Về sếp tự do 9 thì bạn đọc qua thớt này nhé thảo luận - Chia sẻ, Sắp relocate qua Mỹ sau 5.5 năm làm Software. Mình nghĩ mình biết chìa khóa của sự thành công trong nghề :D (https://voz.vn/t/chia-se-sap-relocate-qua-my-sau-5-5-nam-lam-software-minh-nghi-minh-biet-chia-khoa-cua-su-thanh-cong-trong-nghe-d.697783/)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
))
Về skill thì trong topic này anh đếm cũng hơn chục bạn khủng hơn anh mà, còn em muốn kiên trì thì anh nghĩ có vài điểm như thế này em phải luôn manifest vô trong đầu: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
Anh học algorithm chỉ để hiểu hơn những dòng code mình viết ra hàng ngày thôi chứ ko dùng để interview gì đâu, lên voz post bài daily chửi vozliz, thi contests các thứ là vui rồi
Q4 ko biết cách xử lý phần trùng buồn vl
e stuck hơn 30p cho Q4 vì ban đầu nghĩ ra cách dp gọi f[ i ][diff_sum][diff_count] là số cách chọn từ i số đầu tiên sao cho tổng even - tổng odd = diff_sum và even_count - odd_count == diff_count. Thì kq là f[len(nums)-1][0][0] + f[len(nums)-1][0][1]. Nhưng làm cách này ko tính được số hoán vị.
class Solution:
def countBalancedPermutations(self, num: str) -> int:
digits_freq = [0] * 10
for c in num:
digits_freq[ord(c) - ord('0')] += 1
s = 0
for i in range(10):
s += i * digits_freq[i]
if s & 1:
return 0
MOD = 10**9 + 7
@lru_cache(None)
def c(n, k):
if k == 0:
return 1
if n == k:
return 1
else:
return (c(n-1, k-1) + c(n-1, k)) % MOD
@lru_cache(None)
def dp(d, diff, n_even, n_odd):
if n_even < 0 or n_odd < 0:
return 0
if d == -1:
return 1 if diff == 0 else 0
res = 0
for e in range(digits_freq[d] + 1):
remain_even = n_even-e
remain_odd = n_odd-(digits_freq[d]-e)
if remain_even < 0 or remain_odd < 0:
continue
temp = dp(d-1, diff + e*d - (digits_freq[d]-e)*d, remain_even, remain_odd)
temp = (temp * c(n_even, e) * c(n_odd, digits_freq[d]-e)) % MOD
res = (res + temp) % MOD
return res
return dp(9, 0, (len(num) + 1) // 2, len(num) // 2)
hay nhỉ cách này sẽ giảm được 1 chiều (từ [sum_even][sum_odd] -> [diff]), lâu không động vào quên hết trick
Cách bác là xét từng chữ số một, từ 9 về 0 nhỉ, tính số hoán vị thì chỉ nhân thêm số cách đặt một số lượng chữ số đang xét vào 2 mảng chẵn-lẻ thôi. Làm thế này hay thật. Em lại xét từng vị trí i trong xâu gốc, nên ra kết quả vẫn phải nhân/chia một mớ lên.
Sau mới nhận ra là digits chỉ từ 0-9, cũng chả quan tâm thứ tự trong nums như nào, mình chỉ cần số lượng xuất hiện của từng digit thôi.
Thì lúc này e mới ra công thức mới là gọi f[d][diff][n_even][n_odd] là số cách chọn first d digits ([0..d]) sao cho sum_even - sum_odd == diff.
Thì f[d][diff][n_even][n_odd] = sum(f[d-1][diff + d*e - d*(freq[d]-e)][n_even-e][n_odd-freq[d]+e] * n_even_C_e * n_odd_C_(freq[d]-e))
Mã:class Solution: def countBalancedPermutations(self, num: str) -> int: digits_freq = [0] * 10 for c in num: digits_freq[ord(c) - ord('0')] += 1 s = 0 for i in range(10): s += i * digits_freq[i] if s & 1: return 0 MOD = 10**9 + 7 @lru_cache(None) def c(n, k): if k == 0: return 1 if n == k: return 1 else: return (c(n-1, k-1) + c(n-1, k)) % MOD @lru_cache(None) def dp(d, diff, n_even, n_odd): if n_even < 0 or n_odd < 0: return 0 if d == -1: return 1 if diff == 0 else 0 res = 0 for e in range(digits_freq[d] + 1): remain_even = n_even-e remain_odd = n_odd-(digits_freq[d]-e) if remain_even < 0 or remain_odd < 0: continue temp = dp(d-1, diff + e*d - (digits_freq[d]-e)*d, remain_even, remain_odd) temp = (temp * c(n_even, e) * c(n_odd, digits_freq[d]-e)) % MOD res = (res + temp) % MOD return res return dp(9, 0, (len(num) + 1) // 2, len(num) // 2)
Lúc đầu mình cũng đi DP y như fen, sau mới nhận ra là cách đi DP này ko tính được số trùng.
Sau mới nhận ra là digits chỉ từ 0-9, cũng chả quan tâm thứ tự trong nums như nào, mình chỉ cần số lượng xuất hiện của từng digit thôi.
Thì lúc này e mới ra công thức mới là gọi f[d][diff][n_even][n_odd] là số cách chọn first d digits ([0..d]) sao cho sum_even - sum_odd == diff.
Thì f[d][diff][n_even][n_odd] = sum(f[d-1][diff + d*e - d*(freq[d]-e)][n_even-e][n_odd-freq[d]+e] * n_even_C_e * n_odd_C_(freq[d]-e))
Mã:class Solution: def countBalancedPermutations(self, num: str) -> int: digits_freq = [0] * 10 for c in num: digits_freq[ord(c) - ord('0')] += 1 s = 0 for i in range(10): s += i * digits_freq[i] if s & 1: return 0 MOD = 10**9 + 7 @lru_cache(None) def c(n, k): if k == 0: return 1 if n == k: return 1 else: return (c(n-1, k-1) + c(n-1, k)) % MOD @lru_cache(None) def dp(d, diff, n_even, n_odd): if n_even < 0 or n_odd < 0: return 0 if d == -1: return 1 if diff == 0 else 0 res = 0 for e in range(digits_freq[d] + 1): remain_even = n_even-e remain_odd = n_odd-(digits_freq[d]-e) if remain_even < 0 or remain_odd < 0: continue temp = dp(d-1, diff + e*d - (digits_freq[d]-e)*d, remain_even, remain_odd) temp = (temp * c(n_even, e) * c(n_odd, digits_freq[d]-e)) % MOD res = (res + temp) % MOD return res return dp(9, 0, (len(num) + 1) // 2, len(num) // 2)
để mai mình nghiên cứu lại xem.
cay thật sự chứ đọc lộn nên làm lâu quá.class Solution:
def countBalancedPermutations(self, num: str) -> int:
m = len(num)
MOD = 10**9 + 7
count = defaultdict(int)
for i in range(m):
count[int(num[i])] += 1
digits = list(set(list(num)))
n = len(digits)
oddCounts = m//2 + 1
evenConts = m//2
@lru_cache(None)
def dp(i, oddSum, evenSum, diff):
if i == n:
if m%2 == 0 and diff == 0 and oddSum == evenSum:
return 1
if m%2 == 1 and abs(diff) == 1 and oddSum == evenSum:
return 1
return 0
ans = 0
total = count[int(digits[i])]
intDigit = int(digits[i])
for k in range(0, total + 1):
currentDiff = k - (total - k)
odds = k
evens = total - k
if odds <= oddCounts and evens <= evenConts:
ans += dp(i + 1, oddSum + intDigit*k, evenSum + intDigit*(total - k), diff + currentDiff)
return ans%MOD
ans = dp(0, 0, 0, 0)
return ansQ3 chỉ modify 1 tí ở Q2 thôi mà fen, mà tụi nó viết đề khó hiểu quá
Q3 thì em ko nhìn ra cách làm. Q4 em thấy giống Q3 weekly trước nhỉ. Cũng là đếm cách chia 1 tập đã cho thành 2 tập nhỏ (có thể chia hết, hoặc không), để thoả mãn điều kiện nào đó.Q3 chỉ modify 1 tí ở Q2 thôi mà fen, mà tụi nó viết đề khó hiểu quá
Bác lại chung mâm Knight với em rồi.
chuâne rồi em thử đi thử lại queue với heap mãi mới tìm ra cách
Hồi xưa e học còn nhiều trick lỏ lắm mà lâu không đụng cũng quên hết rồi.hay nhỉ cách này sẽ giảm được 1 chiều (từ [sum_even][sum_odd] -> [diff]), lâu không động vào quên hết trick
CP phải cày thường xuyên mới đượcMỗi cách có cái hay riêng bác. E vẫn chưa nghĩ ra cách nào dp trên từng vị trí i trong xâu gốc mà tính được số hoán vị
chăm chỉ report cheating thôi bác, nhiều khi lên đc 3-400 ranks thì cũng vừa đủ lên guardian đó
vãi lọ Faang bây h 2k5 mới tự tin cơ à bác?Hồi xưa e học còn nhiều trick lỏ lắm mà lâu không đụng cũng quên hết rồi.
Mỗi cách có cái hay riêng bác. E vẫn chưa nghĩ ra cách nào dp trên từng vị trí i trong xâu gốc mà tính được số hoán vị
chăm chỉ report cheating thôi bác, nhiều khi lên đc 3-400 ranks thì cũng vừa đủ lên guardian đó
Xem tệp đính kèm 2762063
Contest này bay quá, e đang đặt mục tiêu rating 2500+ để pv FAANG, chắc nhanh nhất thì năm sau mới đạt được, chứ giờ performance hơi phập phùng
Tại bữa giờ e nộp CV faang còn không pass nổi resume screening bác, dù có cả referral. Nên chắc kiếm rating cao cao để gây ấn tượng với recruiters
Mới report cả đống cheaters rồi, lên tầm 50 ranks nữa chắc đủ điểm Guardian.Hồi xưa e học còn nhiều trick lỏ lắm mà lâu không đụng cũng quên hết rồi.
Mỗi cách có cái hay riêng bác. E vẫn chưa nghĩ ra cách nào dp trên từng vị trí i trong xâu gốc mà tính được số hoán vị
chăm chỉ report cheating thôi bác, nhiều khi lên đc 3-400 ranks thì cũng vừa đủ lên guardian đó
Xem tệp đính kèm 2762063
Contest này bay quá, e đang đặt mục tiêu rating 2500+ để pv FAANG, chắc nhanh nhất thì năm sau mới đạt được, chứ giờ performance hơi phập phùng
lại bị cái Q2 củ chuối này
