Here is my code for the problem at F - Three Variables Game
#include <bits/stdc++.h>
using namespace std;
bool flag = false;
void solve(int i, long long n, long long a, long long b, long long c, vector<string>& choices, string& arr)
{
if(flag) return;
else if(a<0 || b<0 || c<0) return;
else if(i == n && a >= 0 && b >= 0 && c >= 0)
{
flag = true;
cout << "Yes\n";
for(auto x : arr) cout << x << "\n";
return;
}
else
{
if(choices[i][0] == 'A' && choices[i][1] == 'B')
{
arr.push_back('A');
solve(i+1,n,a+1,b-1,c,choices,arr);
arr.pop_back();
arr.push_back('B');
solve(i+1,n,a-1,b+1,c,choices,arr);
arr.pop_back();
}
else if(choices[i][0] == 'A' && choices[i][1] == 'C')
{
arr.push_back('A');
solve(i+1,n,a+1,b,c-1,choices,arr);
arr.pop_back();
arr.push_back('C');
solve(i+1,n,a-1,b,c+1,choices,arr);
arr.pop_back();
}
else
{
arr.push_back('B');
solve(i+1,n,a,b+1,c-1,choices,arr);
arr.pop_back();
arr.push_back('C');
solve(i+1,n,a,b-1,c+1,choices,arr);
arr.pop_back();
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n, a, b, c;
cin >> n >> a >> b >> c;
vector<string> choices;
string s;
for(int i=0; i<n; i++)
{
cin >> s;
choices.push_back(s);
}
string arr;
solve(0,n,a,b,c,choices,arr);
if(!flag) cout << "No\n";
return 0;
}
Though the above code got an AC I certainly don’t know why it got an AC. I have some doubts related to this code. First of all on seeing the constraints it seems that a recursive solution doesn’t work but since this code got an AC it means recursion works, but why? Secondly I have a doubt related to the following snippet in particular (though I have taken the case AB, my doubt is in general about AC and BC also):-
if(choices[i][0] == 'A' && choices[i][1] == 'B')
{
arr.push_back('A');
solve(i+1,n,a+1,b-1,c,choices,arr);
arr.pop_back();
arr.push_back('B');
solve(i+1,n,a-1,b+1,c,choices,arr);
arr.pop_back();
}
In the above code you see the last line is arr.pop_back(), initially I hadn’t included this line and I kept getting WA in some of the test cases but then when I included this line I got an AC, I don’t understand why? Because according to me at each and every choice there is only one of the following options AB, AC or BC so shouldn’t the answer just store its previous value and then look if it is possible to solve the problem using the remaining choices. Why do I need to pop_back() the last choice included at the end of the block? It is true that the choice just above needs to be popped out so that we can solve for the case below but I don’t understand that why the only remaining choice has to be popped out? I am sorry if this feels a little confusing but this is it. Any help is highly appreciated.