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

freedom.999 đã nói:

Spoiler: q4

Maximum Balanced Subsequence Sum - LeetCode

Can you solve this real interview question? Maximum Balanced Subsequence Sum - You are given a 0-indexed integer array nums. A subsequence of nums having length k and consisting of indices i0 < i1 < ... < ik-1 is balanced if the following holds: * nums[ij] - nums[ij-1] >= ij - ij-1, for every...

leetcode.com

Q4 cũng giống bài này nha ae dùng đc segment tree, mới tuần trước làm virtual thấy

Nhấp để mở rộng...

analogy.2 đã nói:

bài Q4 này chính ra tier medium-hard thôi bác nhỉ, chắc rating bài này cỡ 1k9

Nhấp để mở rộng...

analogy.2 đã nói:

bài Q4 này chính ra tier medium-hard thôi bác nhỉ, chắc rating bài này cỡ 1k9

Nhấp để mở rộng...

freedom.999 đã nói:

Ừ đúng rồi, ko cần nghĩ phức tạp quá thì sẽ ra thôi. Mới sửa lại thì dùng 1 sorted list là ăn luôn

Nhấp để mở rộng...

aNotHeRNo0b đã nói:

Em xin code sorted list với ạ

Nhấp để mở rộng...

freedom.999 đã nói:

Spoiler: q4

Maximum Balanced Subsequence Sum - LeetCode

Can you solve this real interview question? Maximum Balanced Subsequence Sum - You are given a 0-indexed integer array nums. A subsequence of nums having length k and consisting of indices i0 < i1 < ... < ik-1 is balanced if the following holds: * nums[ij] - nums[ij-1] >= ij - ij-1, for every...

leetcode.com

Q4 cũng giống bài này nha ae dùng đc segment tree, mới tuần trước làm virtual thấy

Nhấp để mở rộng...

Windows 2001 đã nói:

Spoiler: Q4 O(n)

Python:

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        answer = 0

        current_diff = 0
        diff_freq = {0: 1}
        count_start_pos = 0

        for num in nums:
            if num == target:
                count_start_pos += diff_freq.get(current_diff,0)
                current_diff += 1
            else:
                current_diff -= 1
                count_start_pos -= diff_freq.get(current_diff,0)

            answer += count_start_pos
            diff_freq[current_diff] = diff_freq.get(current_diff,0) + 1

        return answer

Nhấp để mở rộng...

analogy.2 đã nói:

Spoiler: Q4 prefix sum + sorted list

Python:

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        res = 0
        n = len(nums)
        prefix = [0]*(n+1)
        for i in range(n):
            num = nums[i]
            if num == target:
                prefix[i+1]=prefix[i]+1
            else:
                prefix[i+1]=prefix[i]-1
        s = SortedList()
        res = 0
        for num in prefix:
            l = s.bisect_left(num)
            res+= l
            s.add(num)
        return res

Nhấp để mở rộng...

analogy.2 đã nói:

đoạn count_start_pos ý tưởng là sao vậy thím

Nhấp để mở rộng...

freedom.999 đã nói:

Fen đưa đoạn tính prefix sum rồi add vô sl vô 1 loop là được, dùng 1 biến count là đủ rồi

Nhấp để mở rộng...

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        res, count = 0, 0
        n = len(nums)
        s = SortedList()
        for i in range(n+1):
            res += s.bisect_left(count)
            s.add(count)
            if i < n:
                count = count+1 if nums[i]==target else count-1
        return res

Windows 2001 đã nói:

count_start_pos là số vị trí để mảng con bắt đầu tại đó, kết thúc ở num có target chiếm đa số (là những vị trí mà diff < current_diff).
Ý tưởng là ở mỗi bước current_diff (hiệu số giữa số giá trị bằng target và số giá trị không bằng target) chỉ lên xuống 1 đơn vị => Tận dụng count_start_pos ở vị trí trước đó rồi cộng trừ vào, không phải đếm lại từ đầu

Nhấp để mở rộng...