Google Code Jam 2014 – Round 1 A

Posted on by

Full Binary Tree seemed more straightforward to me as compared to Charging Chaos. Right after reading the problem, the solution was almost ready in my mind and I knew that I’ll have to handle the case where a node has more than 2 children.
@Full Binary Tree:
We just had to perform DFS on a graph (tree) considering all nodes as root, one at a time, and in that process, choose either 0 or 2 children nodes for every child node. If a node had > 2 children, we had to choose the child with further highest number of children and the child with 2nd highest number of children.
From this problem, I learnt how the parent of a node and its number of children must be stored, when it is required for further computation.

@Charging Chaos:
In , a very careful observation had to be made that only ‘N’ combinations of flips were possible as the bitsets of the devices were fixed, only bitsets of outlets had to be manipulated.
So,
– Get a flip[] combination that matches outlet[0] to the i’th device.
– Apply this combination to rest of the outlets.
– See if the current combination of outlets matches the combination of devices.
– Choose the combination that requires minimum number of flips.


My mistakes during the contest:

1. Even though I was more confident about solving B, I decided to spend time thinking about A. I should have solved B first completely and then come back to A.
2. At times, thoughts about both problems were coming to my mind and I was getting slightly tensed unnecessarily, because I could not find the algorithm to solve A.

Learnings:

1. Focus on the limits of the large dataset and understand what is the expected complexity of the solution.
2. While getting the maximum number from a loop, I used to set values like 123456789 or 99999999 as the initial value. But the safest value to use would be INT_MAX (or other maximum limits as per datatype and limits), just to be safe to prevent small bugs.
3. If we have two std::set< … > containers, we can compare them using the ‘==’ operator.

Here are the codes for both problems.

Problem A –

#include <iostream>
#include <set>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;

int main()
{
    int T;
    cin>>T;
    for(int cases=1;cases<=T;cases++)
    {
        int n,l;
        cin>>n>>l;
        vector<string> a(n), b(n);
        
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<n;i++)
        {
            cin>>b[i];
        }
        set<string> bb(b.begin(),b.end());
        
        int result = INT_MAX;
        for(int i=0;i<n;i++)
        {
            
            set<string> aa;
            vector<bool> flip(l);
            for(int j=0;j<l;j++)
                flip[j]=(a[0][j]!=b[i][j]);
            for(int j=0;j<n;j++)
            {
                string x = a[j];
                for(int k=0;k<l;k++)
                    x[k]=(char)(x[k]^flip[k]);
                aa.insert(x);
            }
            if(aa==bb)
            {
                int count=0;
                for(int j=0;j<l;j++)
                    count+=flip[j];
                result=min(result,count);
            }
        }
        if(result==INT_MAX)
            cout<<"Case #"<<cases<<": NOT POSSIBLE\n";
        else
            cout<<"Case #"<<cases<<": "<<result<<"\n";
    }
}

Problem B –

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

void dfs(int r, vector<vector<int> > & G, vector<int> &par, vector<int> &A)
{
    for(vector<int>::iterator it = G[r].begin(); it != G[r].end(); ++it)
    {
        if(par[*it]==-1) // if parent of current element has not been assigned
        {
            par[*it] = r; // assign parent
            dfs(*it,G,par,A); // perform dfs with current node as parent
        }
        // Among all nodes adjacent to a given node, select 2 nodes with more no. of children than all other nodes
        int idx=0, max1=-12345678, max2=-12345678;
        for(vector<int>::iterator it = G[r].begin(); it!=G[r].end(); ++it)
        {
            if(A[*it] > max1 && par[*it]==r)
            {
                max1 = A[*it];
                idx = *it;
            }
        }
        for(vector<int>::iterator it = G[r].begin(); it!=G[r].end(); ++it)
        {
            if(A[*it] > max2 && par[*it]==r && *it!=idx)
            {
                max2 = A[*it];
            }
        }
        A[r]=max(1,1+max1+max2);
    }
}

int main()
{
    cin.sync_with_stdio(0);
	cin.tie(0);
    int T;
    cin>>T;
    for(int cases=1;cases<=T;cases++)
    {
        cout<<"Case #"<<cases<<": ";
        int n;
        cin >> n;
        vector<vector<int> > G(n);
        
        for(int i=0;i<n-1;i++)
        {
            int a,b;
            cin >> a >> b;
            
            G[--a].push_back(--b);
            G[b].push_back(a);
        }
        int ans=0;
        for(int root=0;root < n;root++)
        {
            vector<int> A(n,1);
            vector<int> par(n,-1);
            par[root]=root;
            dfs(root,G,par,A);
            ans = max(ans,A[root]);
        }        
        cout<<n-ans<<"\n";
    }
}