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
Полный текст и комментарии »
