# USACO 2018 December Contest, Bronze Problem 3. Back and Forth

Problem

While solving the problem, I encountered a bug that caused the i value within the for loop to randomly become 1000, 1999, and other incorrect numbers. I was wondering where this originated from within the code, and how I could possibly fix it. Thanks!

#include <bits/stdc++.h>

using namespace std;

set<int> b1, b2, ans;

int c1[101] = {}, c2[101] = {};

void search(int m, int n) {
if(n == 4) {
ans.insert(m);
return;
}

if(n % 2 == 0) {
for(int i : b1) {
cout<<i<<endl;
c1[i]--;
c2[i]++;
if(c1[i]==0) {
b1.erase(i);
}
b2.insert(i);
search(m-i,n+1);
c1[i]++;
c2[i]--;
if(c2[i]==0) {
b2.erase(i);
}
b1.insert(i);
}
}

else{
for(int i : b2) {
cout<<i<<endl;
c2[i]--;
c1[i]++;
if(c2[i]==0) {
b2.erase(i);
}
b1.insert(i);
search(m+i,n+1);
c2[i]++;
c1[i]--;
if(c1[i]==0) {
b1.erase(i);
}
b2.insert(i);
}
}

}

int main() {
freopen("backforth.in","r",stdin);
freopen("backforth.out","w",stdout);

for(int i = 0; i < 10; i++) {
int t; cin>>t;
b1.insert(t);
c1[t]++;
}

for(int i = 0; i < 10; i++) {
int t; cin>>t;
b2.insert(t);
c2[t]++;
}

search(1000, 0);

cout<<(int) ans.size();
}

Just to make sure, you’re talking about the for loops in the main method, correct?

I meant the ones in the search loop, sorry

Try putting more debug prints. The only way the for loop would “randomly” go through those outrageous values is if you put them in there in the first place.

Here is updated code:

#include <bits/stdc++.h>

using namespace std;

set<int> b1, b2;
set<int> possible;
vector<int> a;

int c1[101] = {}, c2[101] = {};

void search(int m, int n) {
cout<<m<<" "<<n<<endl;
if(n == 4) {
possible.insert(m);
return;
}

if(n % 2 == 0) {
for(int i : b1) {
if(i>100) {
cout<<i<<endl;
return;
}
cout<<i<<endl;
c1[i]--;
c2[i]++;
if(c1[i]==0) {
b1.erase(i);
}
b2.insert(i);

search(m-i,n+1);

cout<<m<<" "<<n<<endl;
c1[i]++;
c2[i]--;
if(c2[i]==0) {
b2.erase(i);
}
b1.insert(i);

}
}

else{
for(int i : b2) {
if(i>100) {
cout<<i<<endl;
return;
}
cout<<i<<endl;
c2[i]--;
c1[i]++;
if(c2[i]==0) {
b2.erase(i);
}
b1.insert(i);
search(m+i,n+1);
cout<<m<<" "<<n<<endl;
c2[i]++;
c1[i]--;
if(c1[i]==0) {
b1.erase(i);
}
b2.insert(i);

}
}

}

int main() {
freopen("backforth.in","r",stdin);
freopen("backforth.out","w",stdout);

for(int i = 0; i < 10; i++) {
int t; cin>>t;
b1.insert(t);
c1[t]++;
}

for(int i = 0; i < 10; i++) {
int t; cin>>t;
b2.insert(t);
c2[t]++;
}

search(1000, 0);
}

What I realized was that for some reason, when I reached the end, or when n=4, the adding of the end value to the possible set somehow caused it to be added into the b1 set, and if I removed the possible set, the error would disappear. Is there some part of the set functionality that is causing this?