Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

PUSSY_LICKING_LOLI_69's blog

Help me optimize my solution for 383 Div1 D pls

By PUSSY_LICKING_LOLI_69, history, 4 weeks ago, In English

Link to the problem: https://codeforces.me/contest/741/problem/D

I came up with a solution using Small To Large and Xor Hashing, but my time complexity is $$$O(n*log^2(n)*26)$$$, which is still not optimized enough. It got the extra $$$log$$$ from using map, and I'm not sure of how to get rid of the map. Can someone help me pls?

My Code (I switched to unordered_map and it still TLEs)

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


int n;
vector<ii> g[500005];
int b[500005];
int hv[500005];
int rnk[500005];
int dp[500005];
int sz[500005];



void dfs(int u){
    sz[u] = 1;
    ii tmp = mp(0,0);
    for(ii p : g[u]){
        int v = p.f;
        int x = p.s;
        rnk[v] = rnk[u]+1;
        b[v]=b[u]^x;
        dfs(v);
        sz[u]+=sz[v];
        tmp = max(tmp,mp(sz[v],v));
    }

    hv[u] = tmp.s;
}

void hld(int u, vector<int> &sub, unordered_map<int,int> &s){


    if(hv[u]){
        hld(hv[u],sub,s);
        dp[u] = dp[hv[u]];
        for(int i = 0;i<26;i++){
            int x = b[u]^(1<<i);
            if(s.find(x)!=s.end())
            dp[u] = max(dp[u], s[x]-rnk[u]);
        }
        if(s.find(b[u])!=s.end())
        dp[u] = max(dp[u], s[b[u]]-rnk[u]);
    }

    s[b[u]] = max(s[b[u]], rnk[u]);
    sub.pb(u);




    for(ii p : g[u]){
        int v = p.f;
        if(v==hv[u]) continue;

        vector<int> sub2;
        unordered_map<int,int> s2;
        s2.reserve(sz[v]);
        hld(v, sub2, s2);
        dp[u] = max(dp[u], dp[v]);

        for(int x : sub2){
            int k = b[x];
            for(int i = 0;i<26;i++){
                int tmp = k^(1<<i);
                if(s.find(tmp)!=s.end()) dp[u] = max(dp[u], rnk[x]+s[tmp]-rnk[u]*2);
            }
            if(s.find(k)!=s.end()) dp[u] = max(dp[u], rnk[x]+s[k]-rnk[u]*2);

        }
        for(int x : sub2){
            sub.pb(x);
            s[b[x]] = max(s[b[x]], rnk[x]);
        }
    }
}


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

//    #ifndef ONLINE_JUDGE
//        freopen("abc.inp","r",stdin);
//        freopen("abc.out","w",stdout);
//    #endif

    cin>>n;
    for(int i = 2;i<=n;i++){
        int u; char c;
        cin>>u>>c;
        int x = (1<<(c-'a'));
        g[u].pb(mp(i,x));
    }


    rnk[1] = 1;
    dfs(1);


    vector<int> sub;
    unordered_map<int,int> s;

    s.reserve(n);
    hld(1, sub, s);
    for(int i = 1;i<=n;i++) cout<<max(dp[i],0)<<' '; cout<<en;

    return 0;
}

EDIT: Got rid of the map, not sure how to explain it tho. And the solution above would've WAed test 32 because i forgot to make the default value of the map to be -INF

Accepted solution: https://codeforces.me/contest/741/submission/287930415

Full text and comments »

-6

PUSSY_LICKING_LOLI_69
4 weeks ago
6

Is maximum matching on a non-bipartite graph possible?

By PUSSY_LICKING_LOLI_69, history, 4 weeks ago, In English

Given a graph with n nodes and m edges, is it possible to find the maximum number of edges such that each node is in at most one edge?

constraints:

n<=1000

m<=n*(n-1)/2

Full text and comments »

PUSSY_LICKING_LOLI_69
4 weeks ago
1

How many ways to pick AT MOST k elements from n elements?

By PUSSY_LICKING_LOLI_69, history, 2 months ago, In English

Given a fixed k (k<=1e6), make an array F of size n (n<=1e6) , with F[i] be the number of ways to pick AT MOST k elements from i elements.

Is there a way to create this array efficiently?

Full text and comments »

PUSSY_LICKING_LOLI_69
2 months ago
2

Help me with a string problem

By PUSSY_LICKING_LOLI_69, history, 2 months 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 »

PUSSY_LICKING_LOLI_69
2 months ago
0

Help me with this data structure problem pls!

By PUSSY_LICKING_LOLI_69, history, 2 months 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 »

PUSSY_LICKING_LOLI_69
2 months ago
22

Why is this throwing an error?

By PUSSY_LICKING_LOLI_69, history, 2 months 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
2 months ago
1

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

By PUSSY_LICKING_LOLI_69, history, 3 months 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
3 months ago
5