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	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

PUSSY_LICKING_LOLI_69's blog

QUICK HELP NEEDED ON HOW TO CODE AND TEST IOI PROBLEMS

By PUSSY_LICKING_LOLI_69, history, 4 hours ago, In English

I am having a contest in 2 days and I didnt realize there would be 1 problem in the IOI format.

I only have experience with solving problems through stdin and stdout, but I dont know how to solve IOI problems or test my code with the given materials in the .zip files. I have tried looking for tutorials but nothing really came up.

Can someone please provide any useful resources and tutorials for me to cram up before tomorrow? Really appreciate your help

Full text and comments »

PUSSY_LICKING_LOLI_69
4 hours ago
5

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://mirror.codeforces.com/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://mirror.codeforces.com/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