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

TLE_WA · 26/5/24

Câu cuối cài cũng nhanh mà nhỉ, khó chịu thôi
:oh:

Mỹ Chu Lang · 26/5/24

code gần xong câu 2 thì web bị 504 error luôn rồi mấy bác ơi

freedom.9 · 26/5/24

Q3 ăn cứt gà rồi =((

NguyenQUy1801 · 26/5/24

Q4 nãy mấy người giải đc v mấy bác

vicejuniordev · 26/5/24

Q4 biết ý tưởng là dùng DP, 2 list include + exclude mà toàn ăn TLE. Bó tay.

vicejuniordev · 26/5/24

Mà nay lag vãi, submit mãi mới ăn được. Khả năng cao hôm nay lại không tính điểm

NudeDuck · 26/5/24

NguyenQUy1801 đã nói:
Q4 nãy mấy người giải đc v mấy bác

câu cuối tầm 1k, tính thêm mấy a TQ chắc tầm 1k5 đó bác

SchindlerRoman · 26/5/24

vicejuniordev đã nói:
Mà nay lag vãi, submit mãi mới ăn được. Khả năng cao hôm nay lại không tính điểm

Khoảng 10p cuối lag luôn..

lilleboybk · 26/5/24

Q3 em tưởng cách O(10^5 * 10^3) ăn TLE, ai dè vẫn accept. Em dùng counter2 đếm số phần tử n2 * k. Tìm các ước k của n1 rồi cộng dồn counter2[k] vào kết quả thôi. Có thể dùng mảng counter1 để lưu các n1 đã tính từ trước đó.

vicejuniordev · 26/5/24

lilleboybk đã nói:
Q3 em tưởng cách O(10^5 * 10^3) ăn TLE, ai dè vẫn accept. Em dùng counter2 đếm số phần tử n2 * k. Tìm các ước k của n1 rồi cộng dồn counter2[k] vào kết quả thôi. Có thể dùng mảng counter1 để lưu các n1 đã tính từ trước đó.

Trùng ý tưởng với mình này.

Mình submit lần thứ 3 cách này, vừa submit vừa run. Ai dè ăn luôn

lilleboybk · 26/5/24

Nay ngồi soi rank <1k thấy nhiều Ấn Độ thật, có những trang >=60% Ấn Độ.

TLE_WA · 26/5/24

Đầ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)

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;
    }
};

vicejuniordev · 26/5/24

Nói chung vẫn kém quá, mấy Q4 - 8pts auto toang. Lên núi tu tiếp vậy :gach:

LmaoSuVuong · 26/5/24

vicejuniordev đã nói:
Nói chung vẫn kém quá, mấy Q4 - 8pts auto toang. Lên núi tu tiếp vậy

e cũng tính lên núi tu nhưng tuần sau weekly 400 số đẹp quá, phong thủy có nên tham gia ko :smile:

Mỹ Chu Lang · 26/5/24

mấy bác code C# cho em hỏi Q2 có cách nào dùng string không bị TLE không ạ, đổi qua StringBuilder dùng hàm Append thì không bị TLE mà dùng + operator trong string thì bị

vicejuniordev · 26/5/24

LmaoSuVuong đã nói:
e cũng tính lên núi tu nhưng tuần sau weekly 400 số đẹp quá, phong thủy có nên tham gia ko

Tu nhưng vẫn phá giới được mà

via theNEXTvoz for iPhone

devhockem · 26/5/24

lilleboybk đã nói:
Q3 em tưởng cách O(10^5 * 10^3) ăn TLE, ai dè vẫn accept. Em dùng counter2 đếm số phần tử n2 * k. Tìm các ước k của n1 rồi cộng dồn counter2[k] vào kết quả thôi. Có thể dùng mảng counter1 để lưu các n1 đã tính từ trước đó.

Q3 có ae nào làm với O(n*log(n)) chưa.
Xem qua mấy ông đứng top làm thì cũng vẫn là O(n*sqrt(n)).

freedom.9 · 26/5/24

On sqrt n với nums max là 10^6 vẫn pass ko TLE.
10^5*10^3 mà vẫn pass chả hiểu kiểu mẹ gì.
Cái contest này nát vãi, ko unrate hơi phí. 10 phút cuối server còn chết ngắc luôn :sweat:

bài 4 tụi nó ko giải bằng segment tree vẫn pass ầm ầm, cheaters tùm lum

via theNEXTvoz for iPhone

lilleboybk · 26/5/24

devhockem đã nói:
Q3 có ae nào làm với O(n*log(n)) chưa.
Xem qua mấy ông đứng top làm thì cũng vẫn là O(n*sqrt(n))

Cách bác nói là dùng sàng nguyên tố để phân tích n1 thành các thừa số nguyên tố để tìm nhanh các ước nhỉ. Tại em lướt qua solutions thấy toàn O(n*sqrt(n)).

maskup · 26/5/24

devhockem đã nói:
Q3 có ae nào làm với O(n*log(n)) chưa.
Xem qua mấy ông đứng top làm thì cũng vẫn là O(n*sqrt(n)).

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))

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

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Junior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này