thảo luận Leetcode contest, đường tới Guardian

  • Người tạo chủ đề Người tạo chủ đề freedom.9
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
Cái cách tính prefix and set của t chính là dp nhưng là bottom up đó. Lúc đó t chỉ nghĩ đơn giản là: AND(x,...,y) >= min(x,..,y)nên khả năng nó sẽ trùng nhiều. Rồi làm luôn cách đó. Chứ cũng k có tgian suy nghĩ kỹ proof.
 
freedom.9 đã nói:
We know that AND operation is non-increasing in nature(constant or decreasing). so we know that
adjacent equal elements will lead to AND being constant so first just remove all equal adjacent elements and then
for each element start taking AND within a loop that will run just 31 times for each element.
Because now two adjacent elements are not equal so they would differ in atleast 1 bit making that bit 0, so in atmax
31 moves, the AND becomes 0 and then will remain 0.
So for each element, keep on performing the loop till i + 31, and stop if curr_and <= k or curr_and = 0.
TC: O(UNQ*31) where UNQ = number of distinct elements.

Vẫn còn non thật =((, quá đơn giản mà ko nghĩ ra
Nhấp để mở rộng...
Cái "atmax 31 moves, the AND becomes 0 and then will remain 0" em nghĩ ko đúng, ví dụ như mảng con "6,5,6,5..." thì sau 31 lần, AND vẫn ra 4 chứ
 
Q4 nghĩ ra ý tưởng dùng DP + Binary Search ngay nhưng phải mất hơn 1 tiếng rưỡi để code được theo nó =(( .

Java: 
class Solution {
    int ansFromTo(int from, int to, int[][] count) {
        int[] res = new int[30];
        for (int j = 0; j < 30; j++) {
            res[j] = count[to][j] - (from == 0 ? 0 : count[from-1][j]);
        }
        // System.out.println("from: " + from + " to: " + to + " res: " + Arrays.toString(res));
        int ans = 0;
        for (int j = 29; j >= 0; j--) {
            ans = ans << 1;
            int bit = res[j] > 0 ? 0 : 1;
            ans = ans | bit;
            // ans += bit * Math.pow(2, j);
        }
        return ans;
    }
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length;
       
        int[][] count = new int[n][30];
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int j = 0;
            while (j < 30) {
                int prev = (i == 0) ? 0 : count[i-1][j];
                count[i][j] = prev + ((num % 2 == 0) ? 1 : 0);
                num = num/2;
                j++;
            }
        }
        // System.out.println(Arrays.deepToString(count));
       
       
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            // System.out.println("i: " + i);
            int l = -1;
            int r = i+1;
            while (r - l > 1) {
                int m = (l+r)/2;
                int val = ansFromTo(m, i, count) - k;
                // System.out.println("l: "+ l + " r: " + r + " m: " + m + " i: " + i + " is: " + ansFromTo(m, i, count));
                ans = Math.min(Math.abs(val), ans);
                if (val < 0) {
                    l = m;
                }
                else if (val > 0) {
                    r = m;
                }
                else {
                    break;
                }
            }
            if (ans == 0) {
                break;
            }
        }
       
        return ans;
    }
}
 
Sửa lần cuối:
seastar đã nói:
Bài 4 t dùng set để tính prefix and. Hết contest mới làm xong, :ah:

Python: 
class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        ret = abs(nums[0] - k)
        pre = {nums[0]}
        for x in nums:
            next_set = {x}
            ret = min(ret, abs(x - k))
            for y in pre:
                next_set.add(y & x)
                ret = min(ret, abs((y & x) - k))
            pre = next_set
        return ret
Nhấp để mở rộng...
Sau 1 hồi suy nghĩ thì cũng ra được cái proof cho cách giải này.

Có thể dễ dàng thấy được TC của bài toán là O(n * len(pre)). Mấu chốt ở đây là cần tính được cái size của pre trong worse case.

giả sử mình có 1 chuỗi là: nums = x0, x1, x2, x3, .., xn
trong đó cái pre tại vị trí k là
Mã: 
pre tại vị trí k = set(pre0, pre1, pre2,..., prek)
với:
pre0 = x0 & x1 & x2 & ... & xk
pre1 = x1 & x2 & ... & xk
pre2 = x2 &... & xk
...
prek = xk

suy ra:
pre0 = x0 & pre1
pre1 = x1  & pre2
pre2 = x2 & pre3
....

Do tính chất của phép & nên sau mỗi lần & thì số bit 1 sẽ chỉ giữ nguyên hoặc giảm đi, từ đó suy ra trường hợp worse case để cái len(set(pre0,pre1,pre2,....,pre3)) lớn nhất đó là sau mỗi lần & thì chỉ mất đi 1 bit 1. Mà 1 <= nums[i] <= 10^9 nên suy ra cái len(set(pre0,pre1,pre2,....,pre3)) = 31 trong trường hợp worse case.

Tóm lại độ phức tạp cuối cùng của bài toán này với cách giải bên trên là O(n)

P/S: Cách dùng dp top-down theo idx, cur_and thì TC cũng tương tự.
 
Sửa lần cuối:
Weekly Contest Q4. https://leetcode.com/problems/find-subarray-with-bitwise-and-closest-to-k/description/
Mình có giải theo hướng như sau:
Python: 
class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pref = []
        curr = [0 for i in range(32)]
        for num in nums:
            b = bin(num)[2:]
            for i, j in enumerate(b[::-1]):
                curr[i] += 1 if j == '1' else 0
            pref.append([i for i in curr])

        pref.append([0 for i in range(32)])
        res = abs(nums[0] - k)

        @cache
        def calcAND(start, en):
            res = 0
            f1 = pref[start]
            f2 = pref[en]
            for i in range(32):
                if f2[i] - f1[i] == en - start:
                    res += 2 ** i
            return res

        for i in range(n):
            res = min(abs(nums[i] - k), res)
            if nums[i] < k:
                continue

            if nums[i] == k:
                return 0

            l, r = i - 1, n - 1
            while l <= r:
                mid = (l + r) // 2
                v = calcAND(i - 1, mid)
                res = min(abs(v - k), res)
                if v < k:
                    r = mid - 1
                elif v > k:
                    l = mid + 1
                else:
                    return 0

        return res

Ý tưởng là lưu prefix set bit của dãy để tính toán nhanh AND của subset, sau đó duyệt i từ 0 - n-1, với mỗi i dùng binary search tìm giá trị gần k nhất do giá trị AND của các subset bắt đầu từ phần tử i là dãy giảm dần.

TC của thuật toán là O(nlog(n)), tuy nhiên không hiểu sao submit vẫn bị TLE. Không biết TC của mình ước lượng có bị sai không ạ?
 
hieunm3538 đã nói:
Weekly Contest Q4. https://leetcode.com/problems/find-subarray-with-bitwise-and-closest-to-k/description/
Mình có giải theo hướng như sau:
Python: 
class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pref = []
        curr = [0 for i in range(32)]
        for num in nums:
            b = bin(num)[2:]
            for i, j in enumerate(b[::-1]):
                curr[i] += 1 if j == '1' else 0
            pref.append([i for i in curr])

        pref.append([0 for i in range(32)])
        res = abs(nums[0] - k)

        @cache
        def calcAND(start, en):
            res = 0
            f1 = pref[start]
            f2 = pref[en]
            for i in range(32):
                if f2[i] - f1[i] == en - start:
                    res += 2 ** i
            return res

        for i in range(n):
            res = min(abs(nums[i] - k), res)
            if nums[i] < k:
                continue

            if nums[i] == k:
                return 0

            l, r = i - 1, n - 1
            while l <= r:
                mid = (l + r) // 2
                v = calcAND(i - 1, mid)
                res = min(abs(v - k), res)
                if v < k:
                    r = mid - 1
                elif v > k:
                    l = mid + 1
                else:
                    return 0

        return res

Ý tưởng là lưu prefix set bit của dãy để tính toán nhanh AND của subset, sau đó duyệt i từ 0 - n-1, với mỗi i dùng binary search tìm giá trị gần k nhất do giá trị AND của các subset bắt đầu từ phần tử i là dãy giảm dần.

TC của thuật toán là O(nlog(n)), tuy nhiên không hiểu sao submit vẫn bị TLE. Không biết TC của mình ước lượng có bị sai không ạ?
Nhấp để mở rộng...
Cái này hóng các cao nhân trong topic thôi :sweat: leetcode time complexity ảo quá.
Hình như bài 4 bữa trước chỉ có mỗi 1 fence trong topic giải được còn lại rụng hết.

via theNEXTvoz for iPhone
 
freedom.9 đã nói:
Cái này hóng các cao nhân trong topic thôi :sweat: leetcode time complexity ảo quá.
Hình như bài 4 bữa trước chỉ có mỗi 1 fence trong topic giải được còn lại rụng hết.

via theNEXTvoz for iPhone
Nhấp để mở rộng...
Em pass được 809/816 test, chạy test cuối mất 8800ms trong khi lời giải thấy chỉ O(nlog(n)), limit cũng chỉ 10^5 mà ta
 
hieunm3538 đã nói:
Weekly Contest Q4. https://leetcode.com/problems/find-subarray-with-bitwise-and-closest-to-k/description/
Mình có giải theo hướng như sau:
Python: 
class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pref = []
        curr = [0 for i in range(32)]
        for num in nums:
            b = bin(num)[2:]
            for i, j in enumerate(b[::-1]):
                curr[i] += 1 if j == '1' else 0
            pref.append([i for i in curr])

        pref.append([0 for i in range(32)])
        res = abs(nums[0] - k)

        @cache
        def calcAND(start, en):
            res = 0
            f1 = pref[start]
            f2 = pref[en]
            for i in range(32):
                if f2[i] - f1[i] == en - start:
                    res += 2 ** i
            return res

        for i in range(n):
            res = min(abs(nums[i] - k), res)
            if nums[i] < k:
                continue

            if nums[i] == k:
                return 0

            l, r = i - 1, n - 1
            while l <= r:
                mid = (l + r) // 2
                v = calcAND(i - 1, mid)
                res = min(abs(v - k), res)
                if v < k:
                    r = mid - 1
                elif v > k:
                    l = mid + 1
                else:
                    return 0

        return res

Ý tưởng là lưu prefix set bit của dãy để tính toán nhanh AND của subset, sau đó duyệt i từ 0 - n-1, với mỗi i dùng binary search tìm giá trị gần k nhất do giá trị AND của các subset bắt đầu từ phần tử i là dãy giảm dần.

TC của thuật toán là O(nlog(n)), tuy nhiên không hiểu sao submit vẫn bị TLE. Không biết TC của mình ước lượng có bị sai không ạ?
Nhấp để mở rộng...
Bác thử dùng dịch bit thay vì dùng lũy thừa xem ổn hơn không, đoạn này:
Python: 
2 ** i
Nguyên nhân TLE có thể do O(nlogn) nhưng hằng số lại lớn (32*nlogn), nên có thể phải tối ưu từng phần nhỏ.
 
devhockem đã nói:
Bác thử dùng dịch bit thay vì dùng lũy thừa xem ổn hơn không, đoạn này:
Python: 
2 ** i
Nguyên nhân TLE có thể do O(nlogn) nhưng hằng số lại lớn (32*nlogn), nên có thể phải tối ưu từng phần nhỏ.
Nhấp để mở rộng...
Đúng là vấn đề nằm ở hàm Calc này thật, do O(32*nlogn) chạy lâu thật bác ạ =))) Cơ mà không biết tối ưu làm sao phần này nữa
 
hieunm3538 đã nói:
Đúng là vấn đề nằm ở hàm Calc này thật, do O(32*nlogn) chạy lâu thật bác ạ :LOL:) Cơ mà không biết tối ưu làm sao phần này nữa
Nhấp để mở rộng...
Mình cũng không rõ lắm về Python. Cách của mình giống cách của bạn, nếu mình dùng lũy thừa thì cũng chỉ pass 810 cases.
Mã: 
int ansFromTo(int from, int to, int[][] count) {
    int[] res = new int[30];
    for (int j = 0; j < 30; j++) {
        res[j] = count[to][j] - (from == 0 ? 0 : count[from - 1][j]);
    }
    // System.out.println("from: " + from + " to: " + to + " res: " + Arrays.toString(res));
    int ans = 0;
    for (int j = 29; j >= 0; j--) {
        ans = ans << 1;
        int bit = res[j] > 0 ? 0 : 1;
        ans = ans | bit;
        // ans += bit * Math.pow(2, j);
    }
    return ans;
}
 
devhockem đã nói:
Mình cũng không rõ lắm về Python. Cách của mình giống cách của bạn, nếu mình dùng lũy thừa thì cũng chỉ pass 810 cases.
Mã: 
int ansFromTo(int from, int to, int[][] count) {
    int[] res = new int[30];
    for (int j = 0; j < 30; j++) {
        res[j] = count[to][j] - (from == 0 ? 0 : count[from - 1][j]);
    }
    // System.out.println("from: " + from + " to: " + to + " res: " + Arrays.toString(res));
    int ans = 0;
    for (int j = 29; j >= 0; j--) {
        ans = ans << 1;
        int bit = res[j] > 0 ? 0 : 1;
        ans = ans | bit;
        // ans += bit * Math.pow(2, j);
    }
    return ans;
}
Nhấp để mở rộng...
1717496987503.png

Mình cũng giống bác, vậy bài này phải tối ưu hơn 32nlog(n) thì mới pass được rồi
 
Vừa thử làm xong. Bài 4 này giống bài nào đợt trước ấy nhỉ. Tính chất là càng AND nhiều số thì giá trị càng giảm nên dùng sliding window thôi
Python: 
class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        res = float('inf')
        start = 0
        count_bit = defaultdict(int)

        def get_curr_and(end):
            length = end - start + 1
            res = 0
            for bit_index in range(32):
                bit_val = 1 << bit_index
                if count_bit[bit_index] == length:
                    res |= bit_val
            return res

        def add_num(num):
            nonlocal count_bit
            for bit_index in range(32):
                bit_val = 1 << bit_index
                if bit_val & num:
                    count_bit[bit_index] += 1

        def remove_num(num):
            nonlocal count_bit
            for bit_index in range(32):
                bit_val = 1 << bit_index
                if bit_val & num:               
                    count_bit[bit_index] -= 1 

        for end, num in enumerate(nums):
            add_num(num)

            while start <= end and get_curr_and(end) < k:
                res = min(k - get_curr_and(end), res)
                remove_num(nums[start])
                start += 1
            
            res = min(abs(k - get_curr_and(end)), res)
        
        return res
 
hieunm3538 đã nói:
Đúng là vấn đề nằm ở hàm Calc này thật, do O(32*nlogn) chạy lâu thật bác ạ =))) Cơ mà không biết tối ưu làm sao phần này nữa
Nhấp để mở rộng...
Đệt do phần này hả em, anh cũng pass hết còn 10 test cases mà cũng xài hàm pow. Fak.
Dùng bitshift thôi chứ đừng dùng hàm pow.
Ans = ans | 1 << i sẽ cho ra kết quả tương tự thử.
Mà bitshift cũng nlogn mà 🧱


via theNEXTvoz for iPhone
 
Sửa lần cuối:
Trạng thái
Không mở để trả lời thêm.

Chủ đề tương tự

kaiany
thảo luận Đi NVQS 2 năm, cơ hội nào cho Kỹ sư Phần mềm quay lại IT?
Trả lời
18
Lượt xem
2K
kaiany
kaiany
atomwaffen
Huyền thoại Toán học Việt Nam: Cần xem các kỳ thi mang lại gì cho học sinh
Trả lời
7
Lượt xem
744
kingvn01
kingvn01
ChatGPT AI
Choáng ngợp với nam sinh mang 156 tấm huy chương lên nhận bằng tốt nghiệp
2
Trả lời
39
Lượt xem
2K
sangbuif
sangbuif
condao
thảo luận Sóng gió ập tới, nghề lập trình đang thay đổi ra sao với AI.
9 10 11
Trả lời
205
Lượt xem
28K
martin.nguyen
martin.nguyen
BlueGecko
[Hoa Kỳ] 'Nhan sắc' của chú chó xấu nhất thế giới
2 3
Trả lời
45
Lượt xem
41K
Lee Sin Cướp Rừng
L

Thống kê chủ đề

Ngày tạo
freedom.9,
Người trả lời cuối
freedom.9,
Trả lời
2.480
Lượt xem
130.334

Chia sẻ trang này

Quay lại
Lên đầu trang