Help me understand why there was a problem with my code

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

Комментарии (2)

Написать комментарий?

vgtcross

4 месяца назад, # |

+10

possible.push_back(d/2); in the first solution is incorrect. In general, you can't always reach $$$\left\lfloor d/2\right\rfloor$$$ points, for example in this test:

The correct value would be $$$\left\lfloor (d-1)/2\right\rfloor$$$. But in the second solution, this line doesn't exist, or in other words, this line of code doesn't help the solution. You can just remove it and the solution will be correct.

→ Ответить

0gnjen1

4 месяца назад, # ^ |

Wow, I can't believe I managed to oversee that. Thank you a lot man :D

№	Пользователь	Рейтинг
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

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	157
6	maroonrk	155
7	-is-this-fft-	152
8	Petr	146
8	orz	146
10	BledDest	145

Блог пользователя 0gnjen1