thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

JakovichTimViec · 25/10/25

H mới biết đang trong contest vẫn ăn ban đc :waaaht:

. Tưởng sau contest mới ban dần dần.
Đang 2k9 nhảy lên 1k1

Husqvarna701SM · 25/10/25

freedom.9 đã nói:
Ờ nhỉ, trong contest sao nghĩ phức tạp quá. Loop n thằng đầu tiên là ra cmnr
Vl mình đi làm merge interval các thứ
via theNEXTvoz for iPhone

loop n thằng, check dis thằng hiện tại (2 mảng) với thằng cuối và xem thằng cuối có bị bánh mỳ kẹp thịt phát nào không là đủ r, nói chung nhảm, 2 bài brute force cmnr

LmaoSuVuong · 25/10/25

JakovichTimViec đã nói:
Xem tệp đính kèm 3303377
H mới biết đang trong contest vẫn ăn ban đc . Tưởng sau contest mới ban dần dần.
Đang 2k9 nhảy lên 1k1

nó update chậm thôi chứ chưa lọc đâu. tầm 10p trước chư vào xem mới ghi nhận 307 AK

LmaoSuVuong · 25/10/25

tí virtual thử xem trình độ so các vozlit ở đâu

tiếck9 mới leo lại nên ko đám join

aNotHeRNo0b · 25/10/25

:v đọc không kĩ đề Q3, độ dài hơn nhau 1 mà cứ nghĩ là độ dài khác nhau :v ngồi giải ngáo ngơ luôn

freedom.9 · 25/10/25

LmaoSuVuong đã nói:
k9 mới leo lại nên k

k9 là vozliz rồi thì trình độ tất nhiên là bằng Vozliz chứ trư :shame:

LmaoSuVuong · 26/10/25

3 q đầu làm 20 phút củm oke, xài tí toán học greedy. q4 dp ko biết giải

JakovichTimViec · 26/10/25

LmaoSuVuong đã nói:
3 q đầu làm 20 phút củm oke, xài tí toán học greedy. q4 dp ko biết giải

Mấy bác đỉnh quá, 3q đầu em toàn 40p với dạng giải r

LmaoSuVuong · 26/10/25

JakovichTimViec đã nói:
Mấy bác đỉnh quá, 3q đầu em toàn 40p.

tại mấy bác bảo dễ, nên mình biết là câu 5point chắc chắn là tricky chứ làm live thì ko nhanh v đâu, overthinking phát là ngắm cả tiếng ngay

freedom.9 · 26/10/25

Vl tự dưng húp đc cái contest dễ rating lên 2k2 luôn rồi, rank 1xx

via theNEXTvoz for iPhone

Windows 2001 · 26/10/25

Xong 4Q, 1 bug Q4, gỡ được điểm tối qua rồi :big_smile:

freedom.9 · 26/10/25

Hôm nay thấy mệt mệt có điềm dùng clone thi, đọc đề bài 3 cứ tưởng là strictly smaller mất cả tiếng ko làm ra, nhìn lại thì thấy là strictly cay vl :ah:

Husqvarna701SM · 26/10/25

Má ngồi làm rolling hash mãi éo ra. Cuối cùng bisect thì ăn luôn. Lại feed r. Thôi tối làm cf. 2k5 chắc peak của mình r. Lên 3k xem chừng hard :ah:

analogy.2 · 26/10/25

đề tối nay không khó lắm mà vẫn hay. rếpct :beauty:

JakovichTimViec · 26/10/25

2Q gang, TLE 2Q còn lại

talavuavoz113 · 26/10/25

Nay em mới chơi cái này lần đầu, submit sai nhiều có bị sao không mấy bác :sweat:

analogy.2 · 26/10/25

Bài 4 em có cách này hay hay share cho các bác, tại em làm bài subarray equals k hồi mấy tuần trước nên nảy ra ý làm bài này luôn :ah:

Python:

from math import gcd
class Solution:
    def numGoodSubarrays(self, nums: List[int], k: int) -> int:
        d = {0:1}
        cur = 0
        res = 0
        for num in nums:
            cur += num
            cur %=k
            res += d.get(cur, 0)
            d[cur] = d.get(cur, 0) + 1
        ctr = Counter(nums)
        
        for num, freq in ctr.items():
            required = k//gcd(num,k) # number of required nums to be divisible by k
            d = freq // required
            res -= (d*freq - required*d*(d+1)//2)
        return res

Windows 2001 · 26/10/25

talavuavoz113 đã nói:
Nay em mới chơi cái này lần đầu, submit sai nhiều có bị sao không mấy bác

Sai 1 lần bị tính thêm 5 phút vào thời gian hoàn thành. Khi xếp hạng thì sẽ xếp theo số điểm nhiều nhất trước, nếu bằng điểm xếp theo tổng thời gian nhanh nhất => Sai nhiều thì hạng sẽ thấp hơn

freedom.9 · 26/10/25

Bài 4 khá dễ ấy chứ ko khó nhỉ, ko choke Q3 là ăn rồi. Làm xong Q3 hết bà contest. Trick để loại bỏ phần bị dup là tính overCount của các phần tử liên tiếp vì nếu như việc dup nó nằm ở 2 số khác nhau như 111111112 thì nếu sub array end ở 2 thì sẽ ko bao giờ bị đếm trùng.
Thôi nói chung là xài clone nên ko quan trọng lắm, rút kinh nghiệm đọc đề kĩ hơn

Python:

class Solution:
    def numGoodSubarrays(self, nums: List[int], k: int) -> int:
        def countDupplicated(num, tot):
            l = lcm(num, k)
            curr = 1
            overCount = 0
            while l*curr <= num*tot:
                overCount += tot - (l*curr)//num
                curr += 1

            return overCount
        
        
        seen = defaultdict(int)
        seen[0] = 1
        prefixSum = 0
        ans = 0
        for num in nums:
            prefixSum += num
            if prefixSum % k in seen:
                ans += seen[prefixSum%k]
            
            seen[prefixSum%k] += 1

        count = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                count += 1
            else:
                ans -= countMultipler(nums[i - 1], count)
                count = 1

        ans -= countDupplicated(nums[-1], count)
        return ans

Windows 2001 · 26/10/25

analogy.2 đã nói:

Bài 4 em có cách này hay hay share cho các bác, tại em làm bài subarray equals k hồi mấy tuần trước nên nảy ra ý làm bài này luôn :ah:

Python:

from math import gcd
class Solution:
    def numGoodSubarrays(self, nums: List[int], k: int) -> int:
        d = {0:1}
        cur = 0
        res = 0
        for num in nums:
            cur += num
            cur %=k
            res += d.get(cur, 0)
            d[cur] = d.get(cur, 0) + 1
        ctr = Counter(nums)
     
        for num, freq in ctr.items():
            required = k//gcd(num,k) # number of required nums to be divisible by k
            d = freq // required
            res -= (d*freq - required*d*(d+1)//2)
        return res

Cách viết cú pháp của bạn hay đó, ý tưởng của t cũng gần giống vậy mà gõ dài hơn nhiều

Mã:

class Solution:
    def numGoodSubarrays(self, nums: List[int], k: int) -> int:
        # number of good subarrays, including duplicate arrays
        total_arrays = 0

        prefix_sum = 0
        frequencies_of_prefix_sum = {0: 1} # before the first number

        for num in nums:
            prefix_sum = (prefix_sum + num) % k
            if prefix_sum in frequencies_of_prefix_sum:
                frequencies_of_prefix_sum[prefix_sum] += 1
            else:
                frequencies_of_prefix_sum[prefix_sum] = 1

        for f in frequencies_of_prefix_sum.values():
            total_arrays += f * (f - 1) // 2

        # number of duplicate subarrays
        duplicate_arrays = 0
        frequencies_of_numbers = {}

        for num in nums:
            if num in frequencies_of_numbers:
                frequencies_of_numbers[num] += 1
            else:
                frequencies_of_numbers[num] = 1

        for num in frequencies_of_numbers:
            occurrences = frequencies_of_numbers[num]

            for length in range (1, occurrences):
                if (num * length) % k != 0:
                    continue
                duplicate_arrays += occurrences - length

        return total_arrays - duplicate_arrays

thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này