Doubt in a recursive solution to an Atcoder problem

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.

1 Like

@everule1 Please help.

On a trivial analysis, the time complexity would be O(2^n), since at each state we are calling 2 recursions. However that is not the case. The number of states you will go through is at most O(n).
First you need to imagine a binary tree, where each leaf is one of the letters in the string.
This is the tree for the first test-case.


Let’s start with your second doubt. Notice that you are passing by reference, so you can think of it as a global array.

First start by imagining you are on the root node and you keep on going down. As soon as you find a negative number, you go back up. If you have tried both sides on a node and both of them lead nowhere, you’ll also go back up. Now when you go down, you need to add the character on the edge. When you come back you need to remove it. So when you call on the solve function, it is equivalent to going down an edge. When the function returns, you need to remove the value from the edge. Since you are doing that at every call of the function, your edges are correct.

Now to prove that the recursion works in O(n), we can prove that we can find a mistake in O(1). This will follow because there are only n elements, so even if we make a mistake at every step, we will have O(n)+n\times O(1)=O(n).

We will have to some casework to prove this.
Let’s start with a+b+c=1. At each step we will have a unique move, because you can only move the 1 to the other variable. So if we do not do the correct move, one of the numbers will be negative in the very next turn, and we’ll return in O(1).

Now the harder case a+b+c>1
We can prove by induction, that if we have a valid move this turn, we can also have a valid move next turn. It can be seen that a+b+c=2 is the worst case scenario, hence is equivalent to a+b+c>1.

There are 2 cases, a permutation of \{2, 0, 0\} or a permutation of \{1,1,0\}.
for \{2,0,0\}, since we have a valid move, we can move 2 to the other variable. We always have a valid move at any permutation of \{1,1,0\}.
For \{1,1,0\}, we either have two 1s, or a 1 and a 0.
If we have two 1s, then we can make one of them 2. We’ll make the one that is part of the next move 2. It can be seen that there is at least one that is part of this move, and the next move.

If it’s a 1 and 0, we can just subract from 1 and add to 0.

Thus, we can conclude that if we did a valid move, such that there is a valid move next turn, There exists at least one solution in our subtree. If we did a valid move such that there is no valid move next turn, both the recursions in the next turn will return immediately, thus finding the mistake in O(1).

2 Likes

So this means that if instead of passing by reference I had passed the string arr by value then I would not have to pop_back() at every step?

What do you mean by no of states?

No. Just the first step.

I guess states wasn’t the best way to put it. There will be only O(n) calls to the recursive function.

Time comp is O(2^n)?

No. I have proved that it is O(n) in my post already.

For example
we were always taking left node. But for last time, it did not satisfied the condition. So, it will check the right node but this also didn’t satisfied. Then, it wll check the value for right node of second last one. It also didn’t satisfied.
The answer was taking all the right nodes. So, had it not checked all the possible combinations (2^n) ?

If we did a valid move such that there is no valid move next turn, both the recursions in the next turn will return immediately, thus finding the mistake in O(1)O(1).