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

freedom.9 đã nói:

Vẫn chưa thẩm được cách tính bài 4 hôm qua, mình nghĩ có thể làm được O(n) mà ko làm ra

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

class Solution {
public:
    vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) {
        int n=s.length();
        long long pre[n];
        int cal[n];
        int c[n];
        int j=n-1;
        int c1=0,c0=0;
        for(int i=n-1;i>=0;i--){
            if(s[i]=='0') c0+=1;
            else c1+=1;
            while(j>i&&(c1>k&&c0>k)){
                if(s[j]=='0') c0-=1;
                else c1-=1;
                j-=1;
            }
            cal[i]=j;
        }
        j=0;
        c1=0,c0=0;
        for(int i=0;i<n;i++){
            if(s[i]=='0') c0+=1;
            else c1+=1;
            while(j<i&&(c1>k&&c0>k)){
                if(s[j]=='0') c0-=1;
                else c1-=1;
                j+=1;
            }
            c[i]=i-j+1;
        }
        pre[0]=c[0];
        for(int i=1;i<n;i++){
            pre[i]=pre[i-1]+c[i];
        }
        vector<long long>res;
        for(auto x:queries){
            long long z=min(cal[x[0]],x[1])-x[0]+1;
            long long h=0;
            if(cal[x[0]]<x[1]){
                h=pre[x[1]]-pre[cal[x[0]]];
            }
            res.push_back(z*(z+1)/2+h);
        }
        return res;
    }
};

nahnahinin đã nói:

từ 1 điểm i, tìm điểm j xa nhất bên trái thỏa mãn điều kiện gọi là mảng cal
với mỗi query (l,r), xem xét xem cal[l]>=r không
+, Nếu có thì kết quả query ấy là 1+2+3+...+(r-l+1)
+, Nếu không thì kết quả sẽ là 1+2+3+...+(cal[l]-l+1) + với tổng đoạn từ cal[l]+1->r
Cái tổng kia tính bằng prefix_sum:
+, Với mỗi điểm i tìm điểm j xa nhất bên phải thỏa mãn
+, rồi prefix_sum cái mảng này

Spoiler: code

Java:

class Solution {
public:
    vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) {
        int n=s.length();
        long long pre[n];
        int cal[n];
        int c[n];
        int j=n-1;
        int c1=0,c0=0;
        for(int i=n-1;i>=0;i--){
            if(s[i]=='0') c0+=1;
            else c1+=1;
            while(j>i&&(c1>k&&c0>k)){
                if(s[j]=='0') c0-=1;
                else c1-=1;
                j-=1;
            }
            cal[i]=j;
        }
        j=0;
        c1=0,c0=0;
        for(int i=0;i<n;i++){
            if(s[i]=='0') c0+=1;
            else c1+=1;
            while(j<i&&(c1>k&&c0>k)){
                if(s[j]=='0') c0-=1;
                else c1-=1;
                j+=1;
            }
            c[i]=i-j+1;
        }
        pre[0]=c[0];
        for(int i=1;i<n;i++){
            pre[i]=pre[i-1]+c[i];
        }
        vector<long long>res;
        for(auto x:queries){
            long long z=min(cal[x[0]],x[1])-x[0]+1;
            long long h=0;
            if(cal[x[0]]<x[1]){
                h=pre[x[1]]-pre[cal[x[0]]];
            }
            res.push_back(z*(z+1)/2+h);
        }
        return res;
    }
};

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

freedom.9 đã nói:

cal[l]+1->r bằng prefix sum thì tại sao ko dùng prefix sum từ đầu để tính cal[r] - cal[left - 1] luôn fence nhỉ.
Hôm qua mình dùng prefix sum tính cal[r] - cal[left - 1] mà bị sai. Mà viết ra thì đúng là sai thật

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

i-am-groot đã nói:

chỗ này mình hiểu như vậy k biết đúng không
gọi prefix_sum[r] là số lượng thoả mãn có kết thúc ở r
prefix_sum[r] - prefix_sum[l - 1] sẽ không loại bỏ được hết những cái có start < l
tìm k thoả mãn cal[l] < k thì từ k đến r có thể tính đoạn này bằng prefix_sum, vì chắc chắc start của nó đã lớn hơn l

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

freedom.9 đã nói:

Xem tệp đính kèm 2643008
Mới lên được 2k lại tụt

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

nahnahinin đã nói:

Tết âm lên guardian là đẹp 2160 là lên rồi

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

vicejuniordev đã nói:

Tự hứa với bản thân 1 ngày nào đó lên Guardian post lên Voz khoe với anh em, mà giờ thấy xa vời quá. Contest thì ngày càng khó ăn, mãi chỉ loanh quanh 1k9 không ngóc lên nổi

via theNEXTvoz for iPhone

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