Blog entries - Codeforces

#	User	Rating
1	tourist	3947
2	jiangly	3734
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	ecnerwala	3581
8	Geothermal	3569
8	cnnfls_csy	3569
10	ksun48	3479

#	User	Contrib.
1	awoo	164
2	maomao90	160
3	adamant	156
3	nor	156
5	atcoder_official	155
5	-is-this-fft-	155
7	maroonrk	153
7	cry	153
9	SecondThread	147
10	Petr	146

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's blog