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

freedom.99 đã nói:

Rút ống thở q4 rồi

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

Windows 2001 đã nói:

Solution Q4 cuối cùng của tui vẫn mất 11000ms. May là Leetcode thoáng, chứ giới hạn 2-3s như Codeforce thì không qua nổi câu này

Spoiler: Code

Python:

class Solution:
    def maximumAND(self, nums: List[int], k: int, m: int) -> int:
        # Chuyển số thành mảng bit
        def to_bit_array(val):
            arr = []
            for i in range (32):
                arr.append(val%2)
                val >>= 1
            return arr[::-1]

        # Chuyển mảng bit thành số
        def to_int(arr):
            num = 0
            for bit in arr:
                num <<= 1
                num += bit
            return num

        # Đếm số lần cộng để (val & target) == target
        def count_ops(val, target):
            result = 0
            i = 0
            while i < 32:
                if val[i] < target[i]:
                    break
                i += 1

            while i < 32:
                result = (result << 1) + target[i] - val[i]
                i += 1

            return result

        n = len(nums)
        for i in range (n):
            nums[i] = to_bit_array(nums[i])
          
        target = [0] * 32
        for bit_number in range (32):
            # Thử tăng bit trong đáp án lên 1
            target[bit_number] = 1

            # Đếm số lần cộng để từng phần tử có thể đưa vào subset
            necessary_ops = [0] * n
            for i in range (n):
                necessary_ops[i] = count_ops(nums[i], target)

            # Kiểm tra xem có thể chọn m phần tử không
            necessary_ops.sort()
            if sum(necessary_ops[:m]) > k:
                # Không thỏa mãn, đặt lại bit trong đáp án về 0
                target[bit_number] = 0

        return to_int(target)

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

class Solution:
    def maximumAND(self, arr: List[int], K: int, M: int) -> int:
        def dfs(A, bit, k):
            if len(A) < M or k <= 0 or bit < 0:
                return 0
            mod = 1 << bit
            N = len(A)
            A.sort(reverse=True)
            cnt = 0
            for n in A:
                cnt += n >> bit & 1
            new_A = []
            if cnt >= M:
                for n in A:
                    if n >= mod:
                        new_A.append(n % mod)
                return dfs(new_A, bit-1, k) + mod
            new_k = k
            for n in A:
                if n >= mod:
                    new_A.append(n % mod)
                if n < mod:
                    new_A.append(0)
                    new_k -= mod - n
                if len(new_A) == M:
                    break
            if new_k >= 0:
                return mod + dfs(new_A, bit-1, new_k)
            else:
                new_A = []
                for n in A:
                    new_A.append(n % mod)
                return dfs(new_A, bit-1, k)
        return dfs(arr, 31, K)

datxaban1 đã nói:

em mới tập tành contest, theo các bác có nên resolve những contest đầu từ 2016 không nhỉ?

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

athxzz đã nói:

từ 2006 hay 1996 cũng được mà fen

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

JakovichTimViec đã nói:

Cày 1 tháng lên full 4 bài thì kinh dị quá bác ơi

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

aNotHeRNo0b đã nói:

Bác ý chuyên Toán quốc gia

Anh em nên cân nhắc context không lại tẩu hỏa nhập ma đấy. Nma đúng là phải hard mới lên được

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

JakovichTimViec đã nói:

Người ta là thế, chả bù cho trư cày hơn 2 năm mà vẫn còn 3q gang dài. Đã thế còn ngu toán cực

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

khoadz đã nói:

vc contest tuần này khó thế nhỉ )

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

meomeonopew đã nói:

em chưa làm bài 3,4 giờ mới chuẩn bị đọc đề, nhưng mà bài 1 2 là bài easy trá hình :')

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