6 days ago

Sahil Das • 10

Kharagpur

Flip Operations Solution->

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int n;
    vector<vector<int>>adj;
    int cnt=0;
    void f(int node,vector<int>& ini, vector<int>& expi,int of,int ef)
    {
        if(ini[node]!=expi[node])
        {
            if(node%2)
            {
                if(of%2==0)
                {
                    of++;
                    cnt++;
                }
            }
            else
            {
                if(ef%2==0)
                {
                    ef++;
                    cnt++;
                }
            }
        }
        for(auto &u:adj[node])
        {
            f(u,ini,expi,of,ef);
        }
        return;
    }
    int minOperations(vector<int>& tf, vector<int>& tt, vector<int>& ini, vector<int>& expi) {
       n=ini.size();
       adj.resize(n);
       for(int i=0;i<tf.size();i++)
       {
           adj[tf[i]].push_back(tt[i]);
       }
       int oddflip=0,evenflip=0;
       f(0,ini,expi,oddflip,evenflip);
       return cnt;
    }
};

int main() {
    Solution sol;
    vector<int> tree_from = {0, 1, 0, 1};
    vector<int> tree_to = {1, 2, 3, 4};
    vector<int> initial = {1, 0, 1, 1,  0};
    vector<int> expected = {1, 1, 0,1,1};

    int result = sol.minOperations(tree_from, tree_to, initial, expected);
    cout << "Minimum operations needed: " << result << endl;

    return 0;
}