seastar
Member
Trình còi nên t thấy khó,
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
freedom.9
Senior Member
Chết mẹ rank 3k rồi bị trừ điểm rồi mai fenceTrình còi nên t thấy khó,
seastar
Member
T rank 4k,Chết mẹ rank 3k rồi bị trừ điểm rồi mai fence
vicejuniordev
Senior Member
Q3 khắm quá, ae có tí hint nào không 
lilleboybk
Senior Member
Tưởng contest này hẹo vì làm 45p vẫn TLE Q2. Ai dè Q3 làm 15p vẫn rank 1k. May vl
vicejuniordev
Senior Member
Cố Trường Ca
Senior Member
Q2 thím làm 2 heaps hả, sao tránh được TLE hay thế
lilleboybk
Senior Member
Q3 em tối ưu là mỗi hàng chỉ lưu lại các số khác nhau và có thêm 1 mảng sumMax để tính tổng các ô lớn nhất từ hàng i -> hàng cuối (kể cả các ô lớn nhất này bằng nhau). Xong lúc đệ quy, tại hàng i, nếu tổng đang có + tổng lớn nhất sumMax từ hàng i -> n-1 vẫn nhỏ hơn output thì dừng luôn. Thêm cả trường hợp tại hàng i ko xét các ô của nó mà nhảy đến hàng tiếp theo luôn nữa.
vicejuniordev
Senior Member
Q3 làm sao để lưu lại đống selected value mà ko bị Memory Limit vậy a/e. Mình dùng cả bitmask rồi mà vẫn không pass nổi. Hết TLE lại đến Memory Limit
via theNEXTvoz for iPhone
via theNEXTvoz for iPhone
vicejuniordev
Senior Member
Không thím, dùng 1 max heap là được. Check length nếu bằng k thì lấy giá trị peak còn > k thì pop rồi lấy peak
via theNEXTvoz for iPhone
Cố Trường Ca
Senior Member
lilleboybk
Senior Member
Bác có 1 cái Set để lưu các giá trị đã lấy ấy. Lúc chọn 1 ô, kiểm tra xem có trong Set chưa, nếu chưa thì đẩy vào Set và cộng vào tổng đang có. Bỏ ô đấy ra thì bỏ khỏi Set và trừ đi tổng đang có.
vicejuniordev
Senior Member
Đúng rồi, moé thế mà không nghĩ ra là check thêm cái Sum rồi early exit được
via theNEXTvoz for iPhone
freedom.9
Senior Member
Xài 1 cái sorted list là xong my fence
thanhdonguyen01
Senior Member
Mấy thím cho hỏi bài hôm qua của Biweekly:
Q3. Find the Count of Good Integers
Em làm theo hướng này:
Gen hết palindrome chia hết cho k trước
Sau đó thì đếm số hoán vị của đống palindrome đấy mà không có chữ số 0 nào đứng đầu
Lúc đầu em chạy dùng cái gen permutation của Python thì bị TLE, sau đấy đếm bằng công thức toán thì bị sai ở n = 5, k = 6:
Mọi người cho em hỏi không rõ hướng này của em có sai chỗ nào không ạ, em cảm ơn ạ
Q3. Find the Count of Good Integers
Em làm theo hướng này:
Gen hết palindrome chia hết cho k trước
Sau đó thì đếm số hoán vị của đống palindrome đấy mà không có chữ số 0 nào đứng đầu
Lúc đầu em chạy dùng cái gen permutation của Python thì bị TLE, sau đấy đếm bằng công thức toán thì bị sai ở n = 5, k = 6:
Python:
def count_valid_permutations(self, digits):
n = len(digits)
digit_counts = Counter(digits)
total_permutations = factorial(n)
for count in digit_counts.values():
total_permutations //= factorial(count)
if digit_counts[0] > 0:
permutations_with_leading_zero = factorial(n - 1)
for digit, count in digit_counts.items():
if digit == 0:
count -= 1
permutations_with_leading_zero //= factorial(count)
else:
permutations_with_leading_zero = 0
valid_permutations = total_permutations - permutations_with_leading_zero
return valid_permutationsMọi người cho em hỏi không rõ hướng này của em có sai chỗ nào không ạ, em cảm ơn ạ
lilleboybk
Senior Member
Em thấy cách em vẫn là 11^10, vì mỗi hàng đều thử chọn từng ô hoặc ko chọn ô nào, duyệt tất cả các hàng.Hôm nay tính time complexity bị sai sai 2 contests toang quá.
Q3 hồi sáng thì tính 10^10 ra 2^10, Q3 tối nay thì tính nhầm backtracking qua 10^10 nên ko implement, đúng ra phải là 10*2^100 chuyển về 100*2^10 là ra
- Trạng thái
Chủ đề tương tự
