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

Tụi leetcode này làm ăn kiểu gì, lượng users thi contest có đột biến éo đâu mà cứ tới ngày lại lag tung cả đít nhỉ. Chán thật
 
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
 
seastar said:
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
Click to expand...
Ủa lưu cả đống prefix vô set được hả fence, ảo thế nhỉ.
Má còn non quá hèn gì ko làm ra, tụi kia nó dùng dp 2 states giải cũng ra :ah: tụi nó đi cái DP đơn giản vãi cức
Cứ tưởng TLE nên phải làm sliding windows
 
freedom.9 said:
Ủa lưu cả đống prefix vô set được hả fence, ảo thế nhỉ.
Má còn non quá hèn gì ko làm ra, tụi kia nó dùng dp 2 states giải cũng ra :ah:
Cứ tưởng TLE nên phải làm sliding windows
Click to expand...
Tại vì cái AND ấy, nên nó sẽ bị trùng rất nhiều.
Thực ra hiện tại t cũng mới chỉ có cảm giác là cách sẽ pass chứ chưa thực chứng minh được. Đang ngồi nghĩ xem tại sao nó pass hay là do testcase yếu.
 
trinity said:
b4 e cũng làm sliding window, chưa biết dp thế nào
Click to expand...
Mình sliding windows bị TLE còn 10 test cases cuối, tụi nó giải DP đây fence. Vì & opeartion nó bị trùng nhiều thì phải, ko hiểu sao

Python: 
from functools import cache

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
       
        # Recursive funtion with the current index and past bitwise AND value
        @cache
        def solve(idx, curr_and):
            # If index reached at the end simply pass inf
            if idx >= n:
                return inf
           
            # No need to check the other case since if we include curr_and it will always give us 0 value
            if curr_and & nums[idx] == 0:
                return min(abs(0-k), abs(nums[idx]-k), solve(idx+1, nums[idx]))
           
            return min(abs((curr_and & nums[idx]) - k), abs(nums[idx]-k), solve(idx+1, nums[idx]), solve(idx+1, curr_and&nums[idx]))
           
        return solve(0, nums[0])
 
freedom.9 said:
Mình sliding windows bị TLE còn 10 test cases cuối, tụi nó giải DP đây fence. Vì & opeartion nó bị trùng nhiều thì phải, ko hiểu sao

Python: 
from functools import cache

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
      
        # Recursive funtion with the current index and past bitwise AND value
        @cache
        def solve(idx, curr_and):
            # If index reached at the end simply pass inf
            if idx >= n:
                return inf
          
            # No need to check the other case since if we include curr_and it will always give us 0 value
            if curr_and & nums[idx] == 0:
                return min(abs(0-k), abs(nums[idx]-k), solve(idx+1, nums[idx]))
          
            return min(abs((curr_and & nums[idx]) - k), abs(nums[idx]-k), solve(idx+1, nums[idx]), solve(idx+1, curr_and&nums[idx]))
          
        return solve(0, nums[0])
Click to expand...
e làm bruteforce TLE có 7 testcase thôi mà sliding windows những 10 tc à bác :shame:
 
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
 
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 said:
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
Click to expand...
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;
    }
}
 
Last edited:
seastar said:
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
Click to expand...
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à
Code: 
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ự.
 
Last edited:

Similar threads

Xuan Ha Thu Dong
thảo luận [Review] Cuộc sống và công việc Dev ở Hà Lan. Làm thế nào để tìm việc ở HL và châu Âu nói chung?
4 5 6
Replies
106
Views
9K
asklyking
asklyking
hatayquelua
thắc mắc Cần kiến thức gì để được nhận thực tập Dev
3 4 5
Replies
87
Views
5K
BaoC3H1
BaoC3H1
B
thảo luận Project Manager software và những case Study ?
Replies
7
Views
744
bestlife
B
Misuzulu Zulu
Thấy thức ăn là buồn nôn, 'thánh ăn' Nhật Bản tuyên bố giải nghệ
2 3 4
Replies
60
Views
8K
Anicetus
Anicetus
Masterchiefs
[HÀN QUỐC] Độc đáo cuộc thi... ai ngồi không giỏi nhất
Replies
19
Views
1K
notsad
notsad

Share this page

Back
Top