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

maskup đã nói:

Spoiler: Python

Python:

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
       
        numCounter = Counter(num for num in nums1 if num % k == 0)
        productCounter = Counter(num * k for num in nums2)
       
        maxNum = max(numCounter.keys(), default=0)
       
        ans = 0
        for product, productCount in productCounter.items():
            for cand in range(product, maxNum + 1, product):
                if cand in numCounter:
                    ans += numCounter[cand] * productCount
       
        return ans

Cách này có chi phí trong worst case là:
T = maxNum * (1/1 + 1/2 + ... 1/maxNum)
mà: 1/1 + 1/2 + ... 1/maxNum ~ log(maxNum)
=> T = O(maxNum * log(maxNum))

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

lilleboybk đã nói:

Cách này hay thật , ko biết leetcode có rejudge như contest hôm nọ có bài dùng GCD để pass ko.

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

maskup đã nói:

Cũng mong nó unrate, chứ contest này e hơi nát

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

NudeDuck đã nói:

mấy a Ấn xâm chiếm leader board luôn rồi

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

TLE_WA đã nói:

Spoiler: Idea q4

Đầu tiên tản mạn về naive sol sẽ tốn O(n * m) (n = len(arr) và m = len(queries))
Naive sol: với mỗi update ta tìm ra max non adjacent sum tốn O(n)
=> Ta cần phải tìm một cách giải sao cho update tốn ít hơn
=> Segment tree là một phương án hiện ra

Thực hiện ý tưởng:
Một node đại diện cho kết quả trên đoạn [l,r] sẽ gồm 4 giá trị
4 giá trị này gồm max non adjacent sum trên đoạn [l,r], [l,r-1], [l+1,r], [l+1][r-1]
Đặt 4 giá trị này là st[0], st[1], st[2], st[3]
Sau đó ta sẽ suy nghĩ xem node cha sẽ merge được từ node con bên trái và node con bên phải như thế nào:

• Suy nghĩ xem st[0], st[1], st[2], st[3] của node cha sẽ quan hệ như thế nào với các st của các node con
• Ví dụ: st[0] = max(st_left[0] + st_right[2], st_left[1] + max(st_right[0], st_right[2])

Sau đó mọi thứ rất dễ dàng với mỗi truy vấn update ta chỉ cần update giá trị trên segment tree và lấy ans + max_non_adjacent_sum trên đoạn [1,n] (hay chính là giá trị max của root node)

Spoiler: code

C++:

#define ll long long

const int MOD = 1e9 + 7; // 998244353;
const int N = 2e5 + 5;
const ll INF = 1e16;

ll a[N];
struct SegTree
{
    ll st[4 * N][4];
    SegTree(int init_size)
    {
        build(1, init_size, 1);
    }
    ll get_mx(int id) {
        return max({st[id][0], st[id][1], st[id][2], st[id][3]});
    }
    void merge(int lid, int rid, int id)
    {
        st[id][0] = max(st[lid][0] + st[rid][2], st[lid][1] + max(st[rid][2], st[rid][0]));
        st[id][1] = max(st[lid][0] + st[rid][3], st[lid][1] + max(st[rid][1], st[rid][3]));
        st[id][2] = max(st[lid][2] + st[rid][2], st[lid][3] + max(st[rid][2], st[rid][0]));
        st[id][3] = max(st[lid][2] + st[rid][3], st[lid][3] + max(st[rid][1], st[rid][3]));
    }

    void build(int l, int r, int id)
    {
        if (l == r)
        {
            st[id][0] = max(a[l], 0LL);
            for (int i = 1; i < 4; i++) st[id][i] = 0;
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, id << 1);
        build(mid + 1, r, id << 1 | 1);

        merge(id << 1, id << 1 | 1, id);
    }

    void update(ll val, int u, int v, int l, int r, int id)
    {
        if (v < l || u > r)
        {
            return;
        }
        if (l == r)
        {
            st[id][0] = max(val, 0LL);
            return;
        }
        int mid = (l + r) / 2;
        update(val, u, v, l, mid, id << 1);
        update(val, u, v, mid + 1, r, id << 1 | 1);
        merge(id << 1, id << 1 | 1, id);
    }
};

class Solution {
public:
   
    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
        int ans = 0;
        int n = nums.size();
        for (int i = 1; i <= n; i++){
            a[i] = nums[i-1];
        }
        SegTree st = SegTree(n);
        for (auto query: queries) {
            int val = query[1], pos = query[0] + 1;
            st.update(val, pos, pos, 1, n, 1);
            ans = (ans + st.get_mx(1)) % MOD;
        }
        return ans;
    }
};

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

maskup đã nói:

Spoiler: Python

Python:

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
       
        numCounter = Counter(num for num in nums1 if num % k == 0)
        productCounter = Counter(num * k for num in nums2)
       
        maxNum = max(numCounter.keys(), default=0)
       
        ans = 0
        for product, productCount in productCounter.items():
            for cand in range(product, maxNum + 1, product):
                if cand in numCounter:
                    ans += numCounter[cand] * productCount
       
        return ans

Cách này có chi phí trong worst case là:
T = maxNum * (1/1 + 1/2 + ... 1/maxNum)
mà: 1/1 + 1/2 + ... 1/maxNum ~ log(maxNum)
=> T = O(maxNum * log(maxNum))

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

h_ngyn đã nói:

Cho mình hỏi ví dụ như trong case k = 1, nums1 và nums2 đều chỉ chứa unique value và maxNum bằng max trong constraint thì coi như là mình đang chạy O(len(nums1) * len(nums2)) mà nhỉ. ._. mình có nhầm lẫn gì không ta.

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

k = 1
nums1 = [1,2,3,.., 10000]
nums2 = [1,2,3,...,500]

numCounter = {1:1, 2:1, ..., 10000:1}
productCounter = {1:1, 2:1, ..., 500:1}

Loop qua từng product:

product = 1: cands = [1, 2, ... 10000]   => loop 10000/1
product = 2: cands = [2, 4, 6, ... 10000] => loop 10000/2
prodcut = 3: cands = [3, 6, 9, ..., 9999] => loop 10000/3
...
product = i: cands = [i, i*2, i*3, ..., i * k] => loop 10000/i
...
product = 500: cands = [500, 500*2, 500*3, ..., 10000] => loop 10000/500

=> tổng loop = 10000 * (1/1 + 1/2 + ... 1/500)

maskup đã nói:

Lấy ví dụ case

Mã:

k = 1
nums1 = [1,2,3,.., 10000]
nums2 = [1,2,3,...,500]

numCounter = {1:1, 2:1, ..., 10000:1}
productCounter = {1:1, 2:1, ..., 500:1}

Loop qua từng product:

product = 1: cands = [1, 2, ... 10000]   => loop 10000/1
product = 2: cands = [2, 4, 6, ... 10000] => loop 10000/2
prodcut = 3: cands = [3, 6, 9, ..., 9999] => loop 10000/3
...
product = i: cands = [i, i*2, i*3, ..., i * k] => loop 10000/i
...
product = 500: cands = [500, 500*1, ..., 10000] => loop 10000/500

=> tổng loop = 10000 * (1/1 + 1/2 + ... 1/500)

Hy vọng nó make sense

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

NguyenQUy1801 đã nói:

bác giải thích chỗ merge em với được k ạ

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

TLE_WA đã nói:

Bạn không hiểu chỗ nào nhỉ, ở phần idea mình đã trình bày qua bạn có thể xem lại.
Bạn lấy giấy bút ra thử nếu có khúc mắc thì inbox mình nhé. Cái chính là bạn hiểu ý tưởng cách giải: tại sao cần lưu 4 giá trị cho mỗi node, update như thế nào để duy trì được yêu cầu bài toán.
Nháp ra là nhanh hiểu đoạn merge lắm.

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

NudeDuck đã nói:

Xem tệp đính kèm 2513863
Nhìn trash chưa acc xanh lá 5p xong câu 1, thêm 4p xong câu 4, 2p xong câu 2 và 5p xong câu 3

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

freedom.9 đã nói:

Tụi này nó xài chat gpt đúng ko ae, ảo vãi.

via theNEXTvoz for iPhone

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

seastar đã nói:

Chơi contest mà code có cả comment, . Này k dùng chatgpt hơi phí,

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

seastar đã nói:

Chơi contest mà code có cả comment, . Này k dùng chatgpt hơi phí,

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