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

retarded_user · 6/10/24

NguyenQUy1801 đã nói:
Q4 hồi đầu tưởng có gì đặc biệt ngồi tra mấy tính chất gcd, ngẫm lại thì brute force theo mấy ước của cái nums là ra mà code méo kịp cay vl

Bác ví dụ cách brute force đc kh?

freedom.9 · 6/10/24

lovelyly đã nói:
Contest này được 2 câu, mất điểm rồi

Mình 2 câu còn ăn bugs nữa chứ, nay code ngáo thật. Q2 cứ ngồi đần ra =((

NguyenQUy1801 · 6/10/24

retarded_user đã nói:
Bác ví dụ cách brute force đc kh?

cách e hình như cũng giống mấy cách mấy bác trên làm, cũngduyệt mấy ước của nums thêm vào cái mảng, r duyệt ngược lại để trừ bớt mấy cái bị trùng, sau đáp án thì upper_bound trên cái mảng lưu của bác

TLE_WA · 6/10/24

Hướng giải:

Phân tích constraint: q >= 10^5 -> mỗi truy vấn tối đa là O(1) hoặc O(log(n))
Với mỗi x đếm số cặp (i,j) sao cho gcd(nums, nums[j]) == x (cách đếm thì sử dụng inclusion-exclusion principle như comment trong code)
[*]Sau đó sử dụng prefix sum để với mỗi truy vấn lấy được x nhỏ nhất thỏa mãn pref[x] >= id + 1 (+1 do tính theo 1-th index)

C++:

class Solution { public: vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) { int mx = *max_element(nums.begin(), nums.end()); vector<long long> f(mx+1), cnt(mx+1); for (auto&x:nums) f[x]++; // f[x] is the frequence of x appear in nums for (int i = 1; i <= mx; i++) { for (int j = i; j <= mx; j+=i){ cnt[i] += f[j]; } } // count number of num in nums that num % i == 0 for (int i = 1; i <= mx; i++) cnt[i] = cnt[i] * (cnt[i] - 1) / 2; // count number of pair (i,j) (i < j) such that nums[i] % x == 0 nums[j] % x == 0 // i.e., cnt[x] = number of pair(i,j) (i < j) such that nums[i] % x == 0 and nums[j] % x == 0 vector<long long> g(mx+1); for (int i = 1; i <= mx; i++) { g[i] = cnt[i]; } // g[x] = number of pair(i,j) (i < j) such that gcd(nums[i],nums[j]) == x for (int i = mx; i >= 1; i--) { for (int j = 2 * i; j <= mx; j += i) { g[i] -= g[j]; } } // in-ex principle g[x] = (number of pair(i,j) (i<j) such that nums[i] % x == 0 and nums[j] % x == 0) - number of pair(i,j) (i < j) such that gcd(nums[i], nums[j]) == x * k (k >= 2) // note: traverse from mx -> 1 to guarantee right result // further reading: https://cp-algorithms.com/combinatorics/inclusion-exclusion.html int q = queries.size(); vector<int> ans(q); // remain part of the problem only need to sum up gcd count and query vector<long long> pref(mx+1); for (int i = 1; i <= mx; i++){ pref[i] = pref[i-1] + g[i]; } for (int i = 0; i < q; i++){ long long id = queries[i] + 1; int j = lower_bound(pref.begin(), pref.end(), id) - pref.begin(); ans[i] = j; } return ans; } }; /* */

freedom.9 · 6/10/24

nahnahinin đã nói:
cũng đúng nhưng hơi thiếu, nsqrt(n) đếm số lượng thằng có nghiệm là x (mọi x<=max(array))
sau đó duyệt ngược từ max(array) về 1. với mỗi số i đang xét thì lại duyệt toàn bộ nghiệm của nó, để trừ đi số pair nó tạo ra.
sort cái queries lại rồi 2 con trỏ là xong.

Tính ra nếu biết cách đi từ max về 1 để tính count của gcd thì xong bài 4 rồi, mà tricky quá nhìn ko ra, mới nghĩ tới cái thằng largest mà ngu quá :ah:

lilleboybk · 6/10/24

NguyenQUy1801 đã nói:
xin ý tưởng q3 bác ơi, mấy cái constructive này khó chịu quá

Đây bác ơi, Q3 thì nếu có 1 đỉnh chỉ có 1 đỉnh kề -> bảng sẽ có 1 hàng thôi bác. Còn không chắc chắn sẽ có 4 đỉnh có 2 đỉnh kề. Mình chọn ngẫu nhiên 1 đỉnh này và dựng hàng đầu tiên. Như TC 3 là lấy đỉnh 8 -> 6 -> 3. Ô đầu của hàng 2 sẽ là đỉnh kề còn lại của ô đầu hàng 1, là đỉnh 7, có hàng tiếp: 7->4->2. Giải tay thì nhanh mà em implement mất 1h ấy.

humanversion9x · 6/10/24

freedom.9 đã nói:
Mình 2 câu còn ăn bugs nữa chứ, nay code ngáo thật. Q2 cứ ngồi đần ra

Đề câu 2 hơi rối rắm, ngồi đọc một lúc mới hiểu.

freedom.9 · 6/10/24

TLE_WA đã nói:
for (int i = 1; i <= mx; i++) { for (int j = i; j <= mx; j+=i){ cnt += f[j]; } }

Ồ đoạn này là On^2 mà nhỉ, à nhầm += i ko phải += 1

lovelyly · 6/10/24

freedom.9 đã nói:
Mình 2 câu còn ăn bugs nữa chứ, nay code ngáo thật. Q2 cứ ngồi đần ra

T cũng ăn 1 big câu 2, quên đọc dòng "If it is not possible to remove all the suspicious methods, none should be removed." :beated:

NguyenQUy1801 · 6/10/24

freedom.9 đã nói:
Ồ đoạn này là On^2 mà nhỉ

+=i mà bác nên k N^2 đâu

humanversion9x · 6/10/24

freedom.9 đã nói:
Ồ đoạn này là On^2 mà nhỉ, à nhầm += i ko phải += 1

Đoạn đấy độ phức tạp là O(mx * ln(mx)).

freedom.9 · 6/10/24

humanversion9x đã nói:
Đoạn đấy độ phức tạp là O(mx * ln(mx)).

Ừ do mình đọc đoạn đấy không kĩ, intuition chỗ này đếm khó quá

TLE_WA · 6/10/24

humanversion9x đã nói:
Đoạn đấy độ phức tạp là O(mx * ln(mx)).

đúng rồi

cái đó là tổng của chuỗi điều hòa

Sum of 1 + 1/2 + 1/3 +.... + 1/n

How do I calculate this sum in terms of 'n'? I know this is a harmonic progression, but I can't find how to calculate the summation of it. Also, is it an expansion of any mathematical function? 1 ...

math.stackexchange.com

Violet_7 · 6/10/24

Câu 4, chơi kiểu group các số chia hết 1 số g vào 1 group. Rồi chia các số group đó cho số g, rồi check số cặp nguyên tố cùng nhau. Pass 2.7 giây c++ ko bt có bị bọn lé cốt này chạy lại ko test ko :ah:

SchindlerRoman · 6/10/24

Nay 1 câu, câu 2 đọc đề mà không hiểu luôn. Chắc nên đi học tiếng anh trước :S

LmaoSuVuong · 6/10/24

cái q2 khứa top 1 contest lần này implement các bước y chang e mà sao code java e MLE còn c++ thì pass nhỉ

C++:

vector<int> rg[SZ],g[SZ];
set<int> suspicious;
void dfs(int u) {
    if(suspicious.count(u)) return;
    suspicious.insert(u);
    for(int v : rg[u]) {
        dfs(v);
    }
}
class Solution {
public:
    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
        for(int i=0;i<n;++i) {
            rg[i].clear();
            g[i].clear();
        }
        suspicious.clear();
        for(auto &v : invocations) {
            rg[v[0]].pb(v[1]);
            g[v[1]].pb(v[0]);
        }
        dfs(k);
        for(auto &v : invocations) {
            int a=v[0],b=v[1];
            if(!suspicious.count(a)&&suspicious.count(b)) {
                suspicious.clear();
            }
        }
        vector<int> res;
        for(int i=0;i<n;++i) {
            if(!suspicious.count(i)) {
                res.pb(i);
            }
        }
        return res;
    }
};

e code bằng java

Java:

class Solution {
    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        Map<Integer, List<Integer>> invoke = new HashMap();
        Map<Integer, List<Integer>> invoked = new HashMap();
        Set<Integer> removeGroup = new HashSet();

        for(int[] invocation:invocations){
            int a =  invocation[0];
            int b =  invocation[1];
            invoke.computeIfAbsent(a, ArrayList::new);
            invoked.computeIfAbsent(b, ArrayList::new);
            invoke.get(a).add(b);
            invoked.get(b).add(a);
        }
        helper(invoke, k, removeGroup);

        List<Integer> res = new ArrayList();
        for(int i =0 ;i<n;i++){
            res.add(i);
        }
        for(Integer b:removeGroup){
            if(!invoked.containsKey(b)){
                continue;
            }
            for(int a:invoked.get(b)){
                if(!removeGroup.contains(a)) return res;
            }
           
        }
        for(Integer b:removeGroup){
            res.remove(b);
        }
        return res;
    }
    public void helper(Map<Integer, List<Integer>> invoke, int k,Set<Integer> removeGroup){
        if(removeGroup.contains(k)) return;
        removeGroup.add(k);
        if(!invoke.containsKey(k)) return;
        for(Integer b:invoke.get(k)){
            helper(invoke, b,removeGroup);
        }
    }
}

athxzz · 10/10/24

target 1900 thì rank contest thường cỡ bao nhiêu thì lên dần được vậy các bác

lilleboybk · 10/10/24

athxzz đã nói:
target 1900 thì rank contest thường cỡ bao nhiêu thì lên dần được vậy các bác

Bác cứ giải Q3 trong 30-40p thì sẽ cộng tầm 50-60đ/contest ấy, tầm tháng là lên nếu ko bị hụt hơi.

freedom.9 · 12/10/24

Làm bài nào :ah:

lilleboybk · 12/10/24

Q4 thuần về toán nhỉ các bác, ngồi nghĩ mà lú quá.

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

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này