Skip to main content

C_ Product-AtCoder Beginner Contest 233 (C++ Code and Explanation)

 C-Product AtCoder Beginner Contest 233 


Problem- https://atcoder.jp/contests/abc233/tasks/abc233_c

Approach-

Since, it is given that product of L1*L2*L3....LN is less than 100000 so we can use the brute force method for solving this question. That is by generating all possible combinations and incrementing the final answer. But the question is how to generate all possible combinations?
So, this can be done using Depth-First-Search or DFS. Starting from first row (rownumber=1), take elements row wise and for each element, move to the next row with current product (currpro) multiplied by this element (currele). As soon as we reach the row after the last one (rownumber=n), or current product (currpro) exceeds k, return the function. And now our current product (currpro) should be divided by the element (currele) to continue the process for remaining elements of the same row (rownumber). This step of dividing can also be called as Backtracking approach. Below is the code matching with the exact explanation above.

Code-

vector<ll> g[100005];
ll ansfinal=0;
void dfs(ll rownumber, ll currpro, ll k, ll n)
{
    if(rownumber==n)
    return ;
    if(currentpro>k)
    return ;
    for(auto currele:g[rownumber])
    {
        currpro*=currele;
        if(currpro==k&&rownumber==n-1)
        ansfinal++;
        dfs(rownumber+1,currpro,k,n);
        currpro/=currele;
    }
}
int main()
{
    cin>>n>>k;
    ansfinal=0;
    for(ll i=0;i<n;i++)
    {
        ll x;
        cin>>x;
        for(ll j=0;j<x;j++)
        {
            ll c;
            cin>>c;
            g[i].push_back(c);
        }
        cout<<endl;
    }
    dfs(0,1,k,n);
    cout<<ansfinal;
}

Disclaimer- Everything is published after the actual contest gets over.