Help with Independent Set Problem from Atcoder Educational DP Contest

general
, ,
1

I was solving the Independent Set problem from Atcoder Educational DP Contest (P - Independent Set).

Some assumptions that I made to solve this problem: Any node can be taken as the root node of the tree and then the subtrees can be assigned unique root nodes (i.e. the children of the parent node act as the root nodes of the subtrees).

Approach: I thought of calculating the number of ways to color a subtree with root node j for all valid j, first after painting the parent node as white and then after painting the parent node as black. After that the number of ways to color the tree is the sum of the products of number of ways to color each subtree (whose parent node is the child of the parent node of the whole tree) in both the cases. Then the bases cases will be the ones where we are painting the leaf nodes. A leaf node can be painted either black or white if its parent is painted white and it can only be painted white if its parent node is painted black.

For example, if I have a tree like 1----0----2, and I take 0 as the root node, when I paint 0 with white, subtree with root node 1 can be painted in 2 ways and subtree with root node 2 can also be painted in 2 ways, so number of ways to paint the tree when root node 0 is painted white = 2x2 = 4. Now, if I paint 0 with black then first subtree can only be painted in one way, similarly second subtree can also be painted in only one way, so the number of ways to paint the tree when 0 is painted black = 1x1. Therefore, total number of ways to paint the tree is 4+1 = 5.

I tried to code the above approach using DFS, but it works only for three of the sample test cases, in other words it simply doesn’t work. Following is that code:

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

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;

ll degree[maxn] = {0};
int parent[maxn] = {-1};
bool color[maxn] = {false};
bool used[maxn] = {false};
ll dp[maxn] = {-1};

void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
    degree[u]++, degree[v]++;
}

ll dfs(int u, vector<int> adj[])
{
    used[u] = true;
    if(degree[u] == 1)
    {
        if(parent[u] != -1)
        {
            if(!color[parent[u]]) return 1;
            else return 2;
        }
    }
    if(dp[u] != -1) return dp[u];

    color[u] = true;
    ll ways = 0, p = 1;
    for(int v : adj[u])
    {
        if(!used[v])
        {
            parent[v] = u;
            p = (p*dfs(v,adj))%mod;
            used[v] = false;
        }
    }
    ways = (ways%mod + p%mod)%mod;

    color[u] = false;
    p = 1;
    for(int v : adj[u])
    {
        if(!used[v])
        {
            p = (p*dfs(v,adj))%mod;
        }
    }
    ways = (ways%mod + p%mod)%mod;
    used[u] = false;

    return dp[u] = ways;
}

int main()
{
    FASTIO
    int n, x, y;
    cin >> n;
    vector<int> adj[n];
    for(int i=0; i<n-1; i++)
    {
        cin >> x >> y;
        addEdge(adj,x-1,y-1);
    }
    dfs(0,adj);
    cout << dp[0] << "\n";
    return 0;
}

Is my approach correct? And if it is, then what changes should I make to the code? Any help is highly appreciated. :slightly_smiling_face:

2

Are you calling 2 DFS at each node? That is actually O(2^{|V|}). That won’t pass.

3

Yes. I call one DFS after painting the root node as white and the second DFS after painting the root node as black.

4

I think I messed up with the time complexity by incorrectly assuming it to be 2x|V|.

5

Oh wait I looked through your code. The second DFS doesn’t recurse at all, because the DP value is already set, so it just ignore the color for the second DFS and returns the current value. Fixing that will cause your code to become O(2^{|V|}).

6

So is it that my logic is correct but the implementation is wrong?

7

Fixing that will cause your code to become O(2^{|V|})

8

This means that the only option is to abandon this approach :slightly_frowning_face: . Alright then. Now, how do I solve this problem? :thinking:

9

@everule1 What should be the approach? What are the techniques needed to solve this problem?

10

Root the tree at 1.

Let dp1_i denote the number of ways to color the subtree of i with respect to 1 such that i is colored black, and vice versa for dp2_i.

Now consider dp1_i. All of it’s children must be colored white. So dp1_i = \prod dp2_j where j is child of i.

For dp2_i, It’s children can be colored white or black. So dp2_i = \prod (dp1_j + dp2_j) where j is child of i.

Base case will be dp1_i = 1 and dp2_i = 1, if i is leaf node.

The answer will be dp1_1 + dp2_1 because the subtree of 1 is the whole tree.

Code 
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
const int p = 1e9 + 7;
void solve(){
    int n;
    cin>>n;
    vector<vector<int>> adj(n);
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        --u;--v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vector<ll> dpblack(n, 1);
    vector<ll> dpwhite(n, 1);
    function<void(int,int)> dfs = [&](int u, int par){
        ll &w = dpwhite[u];
        ll &b = dpblack[u];
        for(const auto &e : adj[u]){
            if(e==par){
                continue;
            }
            dfs(e, u);
            w*=(dpblack[e] + dpwhite[e]);
            b*=dpwhite[e];
            w%=p;
            b%=p;
        }
    };
    dfs(0,-1);
    cout<<(dpblack[0] + dpwhite[0])%p;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
Code I wrote before I learnt DFS 
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
using namespace std::chrono;
long long int p=1e9 +7;
int n;
vector<int> edge[100000];
bool debugging=0;
bool outputcheck=0;
bool timecheck=0;
void init(){
    if(debugging){
        
    }
    else{
        cin>>n;
        for(int i=0;i<n-1;i++){
            int a,b;
            cin>>a>>b;
            edge[--a].pb(--b);
            edge[b].pb(a);
        }
    }
}
long long int modpower(ll b,ll po, ll mod=p){
    long long int ans=1;
    while(po){
        if(po&1){
            ans*=b;
            ans%=mod;
        }
        b*=b;
        b%=mod;
        po>>=1;
    }
    return ans;
}
ll solve(){
  queue<pair<int,int>> tochk;
  vector<vector<int>> nodes;
  tochk.push(mp(0,0));
  int depth[n];
  depth[0]=0;
  ll dp[n][2];//white,black
  bool found[n]={0};
  found[0]=1;
  nodes.pb({0});
  while(!tochk.empty()){
      for(int i=0;i<edge[tochk.front().first].size();i++){
       if(!found[edge[tochk.front().first][i]]){
       found[edge[tochk.front().first][i]]=1;
       tochk.push(mp(edge[tochk.front().first][i],tochk.front().second+1));
       if(tochk.front().second+1>=nodes.size()){
           nodes.pb({edge[tochk.front().first][i]});
       }
       else{
           nodes[nodes.size()-1].pb(edge[tochk.front().first][i]);
       }
       depth[edge[tochk.front().first][i]]=tochk.front().second+1;
      }
      }
      tochk.pop();
  }
  for(int i=0;i<nodes[nodes.size()-1].size();i++){
      dp[nodes[nodes.size()-1][i]][0]=1;
      dp[nodes[nodes.size()-1][i]][1]=1;
  }
  for(int i=nodes.size()-2;i>=0;i--){
      for(int j=0;j<nodes[i].size();j++){
          dp[nodes[i][j]][0]=1;
          dp[nodes[i][j]][1]=1;
          for(int k=0;k<edge[nodes[i][j]].size();k++){
              if(depth[edge[nodes[i][j]][k]]==i+1){
                  dp[nodes[i][j]][0]*=dp[edge[nodes[i][j]][k]][0]+dp[edge[nodes[i][j]][k]][1];
                  dp[nodes[i][j]][1]*=dp[edge[nodes[i][j]][k]][0];
                  dp[nodes[i][j]][0]%=p;
                  dp[nodes[i][j]][1]%=p;
              }
          }
      }
  }
  
  return (dp[0][0]+dp[0][1])%p;
}
ll solvebad(){

}
int output(){
   
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	//cin >>t;
	t=1;
    srand(time(0));
	while(t--){
	   init();
	   if(debugging){
	       if(outputcheck){
	          if(solve()!=solvebad()){//checking for random input
	             output();
	          }
	       }
	       if(timecheck){
	           auto start=high_resolution_clock::now();
	           solve();
	           auto stop=high_resolution_clock::now();
	           auto duration = duration_cast<microseconds>(stop - start);
	           cout<<duration.count()<<" Fast\n";
	           start=high_resolution_clock::now();
	           solvebad();
	           stop=high_resolution_clock::now();
	           duration = duration_cast<microseconds>(stop - start);
	           cout<<duration.count()<<" Slow\n";
	       }
	   }
	   else{
	       cout<<solve()<<"\n";//solving it correctly
	   }
	}
}
2 Likes
11

Very helpful reply.