Blog entries - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

This may sound like a simple question to answer by saying simply solve more problems, but I'm looking for a more productive way, as I've already solved tons of problems.

So long story short, I've been trying to solve IOI 2022 D1P1 in a virtual contest for the last 4 hours on DMOJ and gave up 40 minutes before the ending of my session, as I was pissed by my poor implementation skills.

The plan went smooth — read problem, think about it for a while and implement what you get. I immediately went for finding solution to the N<300 subtask and it took me roughly ~40 minutes to get to it. And that's when hell begins, I've spent ~2.5 hours coding, testing and debugging my 50 line code that keeps producing wrong answer/does not compile. Once I've submitted, I thought cool, now I can try to optimize it down to N<3000.

In about 15-20 minutes of thinking I have a solution I believe should work (keep 3 dp arrays, with appropriate differences assigned to each of them, compress coordinates and use the same DP just instead of doing $$$O(N^3)$$$ keep the states down to roughly $$$O(N+M)$$$. Cool, I go to coding and finally rage quit after my code (in spoiler below) turns into a chaotic garbage that produces no correct answer. BTW I've tried to recreate the code by going line-by-line through my trivial DP and just changing up a bit and it went extremely bad.

Short code, which doesn't work

long long max_weights(int N,int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){
	std::map<int,int> mp;
	std::vector<int> v;
	int cur=0;
	for(int i:X)v.push_back(i);
	for(int i:Y)v.push_back(i);
	for(int i=0;i<N;i++)v.push_back(i);
	std::sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	std::vector<std::vector<long long>> dp[4];
	std::vector<std::vector<long long>> pref;
	for(int i=0;i<4;i++){
		dp[i].resize((int)v.size()+5);
	}
	for(int i:v)mp[i]=cur++;
	std::vector<int> g[(int)v.size()+5];
	std::map<std::pair<int,int>,int> mpp;
	for(int i=0;i<M;i++){
		g[mp[X[i]]].push_back(mp[Y[i]]);
		mpp[{mp[X[i]],mp[Y[i]]}]=W[i];
	}
	int sz=(int)v.size();
	for(int i=0;i<sz;i++){
		g[i].push_back(-1);
		std::sort(g[i].begin(),g[i].end());
		pref.push_back(std::vector<long long>());
		pref[i].push_back(0);
		for(int j=1;j<(int)g[i].size();j++){
			pref[i].push_back(pref[i].back()+mpp[{i,g[i][j]}]);
		}
	}
	for(int i=0;i<(int)g[0].size();i++){
		dp[0][0].push_back(0);
		dp[1][0].push_back(-pref[0][i]);
		dp[2][0].push_back(0);
		dp[3][0].push_back(0);
		int lo=0,hi=(int)g[1].size()-1;
		for(;lo<=hi;){
			int mi=(lo+hi)>>1;
			if(g[1][mi]<=g[0][i]){
				lo=mi+1;
				dp[2][0][i]=pref[1][mi];
			}else{
				hi=mi-1;
			}
		}
	}
	for(int i=1;i<N;i++){
		int k=0;
		for(int j=0;j<(int)g[i].size();j++){
			dp[0][i].push_back(0);
			long long mx=0;
			for(;k<(int)g[i-1].size()&&g[i-1][k]<=g[i][j];){
				mx=std::max(mx,dp[1][i-1][k]);
				k++;
			}
			dp[0][i][j]=std::max(dp[0][i][j],pref[i-1][k-1]+mx);
			dp[1][i].push_back(dp[0][i][j]-pref[i][j]);
		}
		k=(int)g[i-1].size()-1;
		for(int j=(int)g[i].size()-1;j>=0;j--){
			dp[3][i].push_back(0);
			long long mx=0;
			for(;k>=0&&g[i-1][k]>=g[i][j];){
				mx=std::max(mx,dp[2][i-1][k]);
				k--;
			}
			dp[3][i][(int)g[i].size()-1-j]=std::max(dp[3][i][(int)g[i].size()-1-j],-pref[i][j]+mx);
			if(!i)dp[0][i][(int)g[i].size()-1-j]=std::max(dp[0][i][(int)g[i].size()-1-j],dp[3][i][(int)g[i].size()-1-j]-pref[i][j]);
			long long nxt=std::max(dp[3][i][(int)g[i].size()-1-j],dp[0][i][(int)g[i].size()-1-j]);
			if(i!=N-1){
				int tot=0;
				int lo=0,hi=(int)g[i+1].size()-1;
				for(;lo<=hi;){
					int mi=(lo+hi)>>1;
					if(g[i+1][mi]<=g[i][j]){
						lo=mi+1;
						tot=pref[i+1][mi];
					}else{
						hi=mi-1;
					}
				}
				dp[2][i].push_back(nxt+tot);
			}
		}
	}
	long long ans=0;
	for(int i=0;i<sz;i++){
		for(int j=0;j<(int)g[i].size();j++){
			long long res=dp[0][i][j];
			ans=std::max(ans,res);
		}
	}
	return ans;
}

Naive DP

long long max_weights(int N,int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){
	long long dp[N+5][N+5][2];
	for(int i=0;i<=N;i++){
		for(int j=0;j<=N;j++){
			for(int k=0;k<2;k++){
				dp[i][j][k]=0;
			}
		}
	}
	int A[N+5][N+5];
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			A[i][j]=0;
		}
	}
	for(int i=0;i<M;i++){
		A[Y[i]][X[i]]=W[i];
	}
	for(int j=1;j<N;j++){
		for(int i=0;i<=N;i++){
			long long sum=0;
			dp[i][j][1]=std::max(dp[i][j][1],dp[i][j-1][1]);
			for(int k=i;k<N;k++){
				sum+=A[k][j-1];
				dp[k+1][j][1]=std::max(dp[k+1][j][1],dp[i][j-1][1]+sum);
			}
		}
		for(int i=0;i<=N;i++){
			long long sum=0;
			for(int k=i;k>=0;k--){
				if(k<i)sum+=A[k][j];
				dp[k][j][0]=std::max(dp[k][j][0],dp[i][j-1][0]+sum);
				dp[k][j][0]=std::max(dp[k][j][0],dp[i][j-1][1]+sum);
				if(!k)dp[k][j][1]=std::max(dp[k][j][1],dp[k][j][0]-sum);
			}
		}
	}
	long long ans=0;
	for(int i=0;i<N;i++){
		long long sum=0;
		for(int j=0;j<=N;j++){
			ans=std::max(ans,std::max(dp[j][i][0]+sum,dp[j][i][1]+sum));
			if(i<N-1)sum+=A[j][i+1];
		}
	}
	return ans;
}

Now I'm wondering, how can I improve my implementation skill on large OI problems (this is not even close to being 'large', yet I've failed). Usually I don't have much problem doing a 30-40 lines problem, but this one really got me.

Is doing easy problems a better route perhaps than doing hard ones or should I focus on implementation heavy tasks exclusively? Thanks.

Full text and comments »

nichke's blog