Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	Um_nik	3396

#	User	Contrib.
1	Um_nik	162
2	cry	161
3	maomao90	160
4	-is-this-fft-	159
5	awoo	158
6	atcoder_official	157
7	nor	155
7	adamant	155
9	maroonrk	152
10	Dominater069	149

PUSSY_LICKING_LOLI_69's blog

Help me with a string problem

By PUSSY_LICKING_LOLI_69, history, 4 days ago, In English

Given 2 strings $$$A$$$ and $$$B$$$, count how many $$$DIFFERENT$$$ strings that can be created by combining a prefix of $$$A$$$ and a prefix of $$$B$$$ (the prefix of $$$A$$$ is written first, then the prefix of $$$B$$$)

Constraints:

$$$|A|,|B| <= 1e5$$$

both strings only have ASCII characters from $$$a$$$ to $$$z$$$

can some one come up with a solution, I would really appreciate it :D

Full text and comments »

Help me with this data structure problem pls!

By PUSSY_LICKING_LOLI_69, history, 9 days ago, In English

Given an array A of size n. Do these q queries:

1 pos x: assign A[pos] = x;

2 l r k: find k-th smallest element in range [l,r]

Constraints:

n,q <= 1e5

A[i], x <= 1e9

My first aproach was to use a Wavelet tree with a BST(specifically a Treap) on each of its nodes. This gives a time complexity of O(n*log^2) and can do online queries(I still did it offline, i had to read all the input and compress the values because i don't want to make the Wavelet tree dynamic). However it has a really high constant factor and it takes 7-8 seconds to run with the full constraints.

Here's my code if you're interested (sorry if it's poorly written):

My Code

#include <bits/stdc++.h>
using namespace std;

//#define int long long //emergency debug

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define hellnah cout<<"NO\n"
#define fuckyeah cout<<"YES\n"
#define en '\n'


const ll oo = 1e9;
const ll mod = 1e9+7;

ll Rand(ll l, ll r){
    ll res = 0;
    for(int i = 0;i<4;i++) res = (res<<15)+ (rand()&((1<<15)-1));
    return res%(r-l+1)+l;
}


struct Treap{
    struct Node{
        Node* c[2];
        int key, pri;
        int sz, ma;

        Node(int x){
            c[0] = c[1] = NULL;
            ma = key = x;
            sz = 1;
            pri = Rand(1,2e9);
        }
    };
    Node* root = NULL;

    void recalc(Node* u){
        u->ma = u->key;
        u->sz = 1;
        if(u->c[0]!=NULL) u->ma = max(u->ma, u->c[0]->ma), u->sz+=u->c[0]->sz;
        if(u->c[1]!=NULL) u->ma = max(u->ma, u->c[1]->ma), u->sz+=u->c[1]->sz;
    }

    Node* merge(Node* u, Node* v){
        if(u==NULL) return v;
        if(v==NULL) return u;

        if(u->pri >= v->pri){
            u->c[1] = merge(u->c[1], v);
            recalc(u);
            return u;
        }
        else{
            v->c[0] = merge(u, v->c[0]);
            recalc(v);
            return v;
        }
    }

    pair<Node*, Node*> split(Node* u, int k){

        if(u==NULL) return {NULL, NULL};

        if(u->sz==1){
            if(u->key<=k) return {u,NULL};
            return {NULL,u};
        }


        if(u->c[0]!=NULL && u->c[0]->ma>=k){
            pair<Node*, Node*> tmp = split(u->c[0],k);
            u->c[0] = tmp.s;
            recalc(u);
            return {tmp.f,u};
        }
        else if(u->key > k){
            Node* tmp = u->c[0];
            u->c[0] = NULL;
            recalc(u);
            return {tmp,u};
        }
        else{
            pair<Node*, Node*> tmp = split(u->c[1],k);
            u->c[1] = tmp.f;
            recalc(u);
            return {u, tmp.s};
        }
    }

    void add(int k){
        Node* node = new Node(k);
        pair<Node*, Node*> tmp = split(root, k);
        root = merge(tmp.f, merge(node, tmp.s));
    }

    void del(int k){
        pair<Node*, Node*> tmp = split(root, k-1);
        pair<Node*, Node*> tmp2 = split(tmp.s, k);
        delete(tmp2.f);
        root = merge(tmp.f, tmp2.s);
    }

    int getpos(int k){
        Node* u = root;
        int res = 0;
        while(u != NULL){
            if(u->key<=k) res++;
            if(u->c[0]!=NULL){
                if(u->c[0]->ma>k) u = u->c[0];
                else{
                    res+=u->c[0]->sz;
                    u = u->c[1];
                }
            }
            else u = u->c[1];
        }

        return res;
    }
};




int n,q;
int a[100005];
int unzip[200005];
ii abc[200005];
iii que[100005];

Treap st[800005];

void ADD(int id, int l, int r, int val, int pos){
    st[id].add(pos);
    //return;
    if(l==r) return;

    int m = l+r>>1;
    if(val<=m) ADD(id*2,l,m,val,pos);
    else ADD(id*2+1,m+1,r,val,pos);
}

void DEL(int id, int l, int r, int val, int pos){
    st[id].del(pos);
    //return;
    if(l==r) return;

    int m = l+r>>1;
    if(val<=m) DEL(id*2,l,m,val,pos);
    else DEL(id*2+1,m+1,r,val,pos);
}

int GET(int L, int R, int k){
    int id = 1;
    int l = 1, r = n+q;
    while(l!=r){
        int m = l+r>>1;
        int tmp = st[id*2].getpos(R) - st[id*2].getpos(L-1);
        if(tmp>=k) id = id*2, r = m;
        else k-=tmp, id = id*2+1, l = m+1;
    }
    return unzip[l];
}


int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


    srand(time(0));
    cin>>n>>q;
    for(int i = 1;i<=n;i++) cin>>abc[i].f, abc[i].s = i;

    for(int i = 1;i<=q;i++){
        int t; cin>>t;
        int x,y,z;
        if(t==1){
            cin>>x>>y;
            que[i].s = -1;
            que[i].f.f = x;
            abc[i+n] = mp(y, -i);
        }
        else{
            cin>>x>>y>>z;
            que[i] = mp(mp(x,y),z);
        }
    }

    sort(abc+1, abc+n+q+1);
    int it = 0;
    for(int i = 1;i<=n+q;i++){
        if(abc[i].f!=abc[i-1].f) ++it, unzip[it] = abc[i].f;

        if(abc[i].s<0){
            int x = -abc[i].s;
            if(que[x].s==-1) que[x].f.s = it;
            //else que[x].s = it;
        }
        else a[abc[i].s] = it;
    }



    for(int i = 1;i<=n;i++) ADD(1,1,n+q,a[i],i);//, cout<<a[i]<<' '<<i<<en;

    for(int i = 1;i<=q;i++){
        int x,y,z;
        x = que[i].f.f;
        y = que[i].f.s;
        z = que[i].s;

        if(z==-1){
            DEL(1,1,n+q,a[x],x);
            a[x] = y;
            ADD(1,1,n+q,a[x],x);
            continue;
        }

        cout<<GET(x,y,z)<<en;
    }

    return 0;
}



//flashbang

It is allowed to do queries offline, and the problem also has a tag of paralel binary search.

Can someone please show me the intended solution with paralel binary search (or even optimize my current code) ?

UPDATE: Solution founded :D https://robert1003.github.io/2020/02/05/parallel-binary-search.html#a-hrefhttpacmhdueducnshowproblemphppid5412hdu5412---crb-and-queriesa

Full text and comments »

Why is this throwing an error?

By PUSSY_LICKING_LOLI_69, history, 10 days ago, In English

I've been messing with struct and pointers in C++ and got this problem.

This code gives an error saying " ‘x’ does not name a type " at the line marked below

struct A{
    A *a;
};

struct B{
    A *x;
    x = NULL; // this line gives error
};

What causes this and how do I fix this problem?

Full text and comments »

PUSSY_LICKING_LOLI_69
10 days ago
1

Differences between (a+=b)%p; and a =(a+b)%p;

By PUSSY_LICKING_LOLI_69, history, 4 weeks ago, In English

I recently came across this problem while solving E1 of Codeforces Round 967 (Div. 2)

My original code used (a+=b)%p; and it worked perfectly with small test cases, but it gave WA when the test cases get larger. After i changed it to a =(a+b)%p; the code got accepted.

I'm a bit frustrated because it took me until after the contest was finished that i found the dumb mistake that probably stopped me from getting the Candidate Master title, so I made this post to discuss the differences between those 2 syntax to help people avoid the same mistake as me (and mostly just for me to vent T^T )

Here's my original code (Please don't pay attention to the dumb variable names hehe)

My Code

#include <bits/stdc++.h>
using namespace std;

//#define int long long //emergency debug

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define hellnah cout<<"NO\n"
#define fuckyeah cout<<"YES\n"
#define en '\n'

const ll oo = 1e9;
int t;
int n,k,p;

//ll dp[505][505][505];
ll dp2[505][505];
//ll dp3[505][505];
ll c[505][505];
ll fac[505];


ll po(ll x, ll y){
    if(y==0) return 1;
    ll tmp  = po(x,y/2);
    if(y%2==0) return tmp*tmp%p;
    return tmp*tmp%p*x%p;
}

ll C(int u, int x){
    if(x==0||u==0) return 1;
    ll res = po(fac[x], p-2);
    ll N = (po(2,u)-1+x-1+p)%p;
    while(x--){
        res = res*N%p;
        N--;
    }
    return res;
}

void init(){
    fac[0] = 1;
    for(int i = 1;i<=k;i++) fac[i] = fac[i-1]*i%p;
    
    for(int i = 0;i<=n;i++)
        for(int j = 0;j<=k;j++) dp2[i][j] = 0, c[i][j] = C(i,j);
        
}

void work(){
    cin>>n>>k>>p;
    
    init();
    
    for(int i = 1;i<=k;i++) dp2[n][i] = 1;
    ll asdf;
    for(int i = n-1;i>0;i--){
        for(int j = 0;j<=k;j++)
            for(int z = j+1;z<=k-j;z++) asdf = c[n-i][j]*dp2[i+1][z]%p, dp2[i][j+z] = (dp2[i][j+z]+asdf*2%p)%p;

        //////////////////////////////////////////////////////////////////////////
        //////////////////////////////////////////////////////////////////////////
        for(int j = 2;j<=k;j++) (dp2[i][j]+=dp2[i][j-1])%p;// look at this line
        //////////////////////////////////////////////////////////////////////////
        //////////////////////////////////////////////////////////////////////////
        
    }
    cout<<dp2[1][k]<<en;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) work();
    return 0;
}
//flashbang

It only worked on test 1, and failed test 2. However, when i changed this line, it worked perfectly

//for(int j = 2;j<=k;j++) (dp2[i][j]+=dp2[i][j-1])%p;
for(int j = 2;j<=k;j++) dp2[i][j]=(dp2[i][j]+dp2[i][j-1])%p;

Can anyone explain why this single line broke my code? :(

Full text and comments »

PUSSY_LICKING_LOLI_69
4 weeks ago
5