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

#define i64 long long
class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        set<pair<i64,i64>>s;
        i64 base1=31,base2=37;
        i64 mod1=(1e9+7),mod2=(1e9+9);
        int n=target.size();
        i64 pow1[n+1];
        i64 pow2[n+1];
        for(auto x:words){
            i64 val1=0,val2=0;
            for(int j=0;j<x.length();j++){
                val1=(val1*base1+(x[j]-'a'+1))%mod1;
                val2=(val2*base2+(x[j]-'a'+1))%mod2;
                s.insert(make_pair(val1,val2));
            }
        }
        i64 hash1[n+1];
        pow1[0]=1;
        hash1[0]=0;
        i64 hash2[n+1];
        pow2[0]=1;
        hash2[0]=0;
        for(int i=1;i<=n;i++){
            pow1[i]=(pow1[i-1]*base1)%mod1;
            hash1[i]=((hash1[i-1]*base1)%mod1+(target[i-1]-'a'+1))%mod1;
            pow2[i]=(pow2[i-1]*base2)%mod2;
            hash2[i]=((hash2[i-1]*base2)%mod2+(target[i-1]-'a'+1))%mod2;
        }
        int cl=0,cr=0;
        int nl=0,nr=0;
        int cur=0;
        for(int i=0;i<=n;i++){
            if(nr<i) return -1;
            if(i>cr){
                cur+=1;
                cr=nr;
            }
            int l=i+1,r=n;
            int ans=-1;
            while(l<=r){
                int m=(l+r)>>1;
                int len=m-i;
                i64 hashVal1=(((hash1[m]-hash1[i]*pow1[len]%mod1))%mod1+mod1)%mod1;
                i64 hashVal2=(((hash2[m]-hash2[i]*pow2[len]%mod2))%mod2+mod2)%mod2;
                if(s.count(make_pair(hashVal1,hashVal2))>0){
                    ans=m;
                    l=m+1;
                }
                else r=m-1;
            }
            if(ans!=-1) nr=max(nr,ans);
        }
        return cur;
    }
};

thanhdonguyen01 đã nói:

Thấy sol bọn nó chơi Z algo mới pass

1 số thì chơi hash được
Bọn nó hash thì AC, e hash thì WA mấy test cuối

N^2 thì lên 25 * 10^8 rồi thím, sống sao được

• 1 <= target.length <= 5 * 104

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

nahnahinin đã nói:

vừa làm thử hash 2 base, 2 mod thì mới xanh, mà đọc code thằng top 1 sao nó hash vớ vẩn vẫn pass được tài thật

Java:

#define i64 long long
class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        set<pair<i64,i64>>s;
        i64 base1=31,base2=37;
        i64 mod1=(1e9+7),mod2=(1e9+9);
        int n=target.size();
        i64 pow1[n+1];
        i64 pow2[n+1];
        for(auto x:words){
            i64 val1=0,val2=0;
            for(int j=0;j<x.length();j++){
                val1=(val1*base1+(x[j]-'a'+1))%mod1;
                val2=(val2*base2+(x[j]-'a'+1))%mod2;
                s.insert(make_pair(val1,val2));
            }
        }
        i64 hash1[n+1];
        pow1[0]=1;
        hash1[0]=0;
        i64 hash2[n+1];
        pow2[0]=1;
        hash2[0]=0;
        for(int i=1;i<=n;i++){
            pow1[i]=(pow1[i-1]*base1)%mod1;
            hash1[i]=((hash1[i-1]*base1)%mod1+(target[i-1]-'a'+1))%mod1;
            pow2[i]=(pow2[i-1]*base2)%mod2;
            hash2[i]=((hash2[i-1]*base2)%mod2+(target[i-1]-'a'+1))%mod2;
        }
        int cl=0,cr=0;
        int nl=0,nr=0;
        int cur=0;
        for(int i=0;i<=n;i++){
            if(nr<i) return -1;
            if(i>cr){
                cur+=1;
                cr=nr;
            }
            int l=i+1,r=n;
            int ans=-1;
            while(l<=r){
                int m=(l+r)>>1;
                int len=m-i;
                i64 hashVal1=(((hash1[m]-hash1[i]*pow1[len]%mod1))%mod1+mod1)%mod1;
                i64 hashVal2=(((hash2[m]-hash2[i]*pow2[len]%mod2))%mod2+mod2)%mod2;
                if(s.count(make_pair(hashVal1,hashVal2))>0){
                    ans=m;
                    l=m+1;
                }
                else r=m-1;
            }
            if(ans!=-1) nr=max(nr,ans);
        }
        return cur;
    }
};

Mã:

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

vi_tieu_bao đã nói:

Chúc mừng thớt đạt guardian. Minh chứng cho sự kiên trì. Xin hỏi chủ thớt có con nhỏ chưa với sắp xếp time cày ntn thế @freedom.9 TIA

via theNEXTvoz for iPhone

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

freedom.9 đã nói:

Chia sẻ mình ý tưởng thử proplayer, sao lại xài đc bisearch trên hash thế

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

nahnahinin đã nói:

là sao thím, ý tưởng bài này à hay ý tưởng binary serach?
em dùng mấy biến tạm hơi khó hiểu chứ chúng nó toàn segtree/BIT để rmq cho đỡ phải nghĩ.

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

freedom.9 đã nói:

Mình chưa lên guardian fence, mới hơn 2k 1 tí hi vọng 3 4 tháng nữa có thể lên được.
Mình chưa có con, ra tết vợ mới đẻ. Thời gian thì ngày nào cũng vô học với làm vài bài, gặp thuật toán nào khó khó thì search youtube rồi nghiền ngẫm thôi, muốn học thì sắp xếp ngày vài tiếng học vô tư mà.

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

freedom.9 đã nói:

Có rank rồi ae, rank 1k1 mà đc cộng có 2 chục điểm thế này bao giờ mới lên bảo vệ nổi. Chắc muốn lên bảo vệ phải tầm 7 800 rating đều đều khó vl

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

vicejuniordev đã nói:

Điểm danh phát :
Xem tệp đính kèm 2695427

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

lilleboybk đã nói:

Xem tệp đính kèm 2695450
Em cũng xong rồi nhưng mà ăn 3 bọ. Lâu lắm mới có 1 contest Q4 ko khó để làm được cả.

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

freedom.9 đã nói:

Ủa Q4 với Q3 khác gì nhau ae? đều xài sliding windows mà

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