Blog entries - Codeforces

#	User	Rating
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	SecondThread	145
9	pajenegod	145

Today I spent a few hours solving problem C from the Codeforces Round 917. Most of the time was spent on me not understanding why my code won't work even after spending a lot of time trying to find the bug. It turned out to be a really weird 'bug' which I really can't understand. I managed to fix the code and get AC in the end but it was basically on accident.

I will put comments next to the lines of code that I changed so you can find your way around my messy code a little more easily.

Submission for code 1 right here

Code with the 'bug'

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

    int64_t calc_score(vector<int>& arr){
    	int64_t score = 0;
    	for(int i=0; i<arr.size(); i++){
    		if(arr[i]==(i+1)) score++;
    	}
    	return score;
    }
    int main(){
    	int t; cin >> t;
    	while(t--){
    		int n, k, d; cin >> n >> k >> d;
    		vector<int> a (n);
    		for(auto& x : a) cin >> x;
    		vector<int> v (k);
    		for(auto& x : v) cin >> x;
    		vector<int64_t> possible;  // here I was using a vector to store all possible solutions
    		possible.push_back(d/2);  // a difference in code here
    		possible.push_back(calc_score(a)+(int64_t)((d-1)/2)); // also here
    		int counter = 0;
    		while(d>1 && ((counter+1)<=n*2)){
                        d--;
    			int b = v[counter%k];
    			for(int i=0; i<n; i++) a[i] += (i<b ? 1 : 0);
    			int64_t score = calc_score(a);
    			if(d>0) possible.push_back(score+(int64_t)((d-1)/2)); // aaand here
    			counter++;
    		}
    		int64_t ans = 0;
                for(const auto& score : possible) ans = max(ans, score); // here too
    		cout << ans << '\n';
    	}
    }

Submission for code 2 right here

Code without the 'bug'

    #include <bits/stdc++.h>
    using namespace std;
     
    int64_t calc_score(vector<int>& arr){
        int64_t score = 0;
            for(int i=0; i<arr.size(); i++){
         	if(arr[i]==(i+1)) score++;
            }
            return score;
    }
    int main(){
        int t; cin >> t;
        while(t--){
        	int n, k, d; cin >> n >> k >> d;
        	vector<int> a (n);
        	for(auto& x : a) cin >> x;
        	vector<int> v (k);
        	for(auto& x : v) cin >> x;
        	int64_t ans = 0; // these are the corresponding lines that gave AC
        	ans = max(ans, calc_score(a)+(int64_t)((d-1)/2)); // this line too
        	int counter = 0;
        	while(d>1 && ((counter+1)<=n*2)){
                            d--;
        		int b = v[counter%k];
        		for(int i=0; i<n; i++) a[i] += (i<b ? 1 : 0);
        		int64_t score = calc_score(a);
        		if(d>0) ans = max(ans, score+(int64_t)((d-1)/2)); // and also this one
        		counter++;
        	}
       		cout << ans << '\n';
       	}
    }

I know using a vector was redundant but I don't see a single reason why it gives a wrong answer? I really hope someone with more knowledge will be able to help me understand why this was happening so I can avoid a similar bug in the future :D

Full text and comments »

0gnjen1's blog