NDMRK - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Nishan Singh
Tester: Felipe Mota
Editorialist: Aman Dwivedi

DIFFICULTY

Easy-Medium

PREREQUISITES

Trees, Dynamic Programming

PROBLEM:

You are given an integer K and a tree of size N, rooted at node 1. In one operation, you can either select a node of the tree and color its entire subtree or create a new (uncolored) copy of the given tree. Find the minimum number of operations required so that the total number of colored nodes among all trees is exactly K.

EXPLANATION:

Subtask 1:

As the tree is bamboo, hence we are able to color any number of nodes (1 to N) in one operation. Hence, we just want to find out the minimum number of trees that are required to color K nodes. The minimum number of trees that are required are:

cnt = \left \lceil{\frac{K}{N}}\right \rceil

The operations required to get the minimum number of trees will be (cnt-1), as it takes 1 operation to get one tree and the first tree is already gifted to us. In each tree, we need to perform a single operation to color the nodes of that tree.

Time Complexity

O(1) per test case

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

#define int long long


void solve()
{
  int n,k;
  cin>>n>>k;

  for(int i=0;i<n-1;i++)
  {
    int waste;
    cin>>waste;
  }

  int tree = k/n;
  if(k%n!=0)
    tree++;

  int ans=2*tree;

  cout<<ans-1<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  // freopen("input1.txt","r",stdin);
  // freopen("output1.txt","w",stdout);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

Remaining Tasks

Assume we are not allowed to create a new tree and we need to find the minimum number of operations required to color exactly K nodes in a single tree.

Suppose we are at some node x, and we wanted to find out the minimum number of operations that are needed to color n_1 nodes in this subtree. Let’s say there are two children c_1 and c_2 from node x and n_1 and n_2 is the size of their subtree. Now if we want to find out the number of operations required to color n_1 nodes from subtree at node x, then we could iterate on the subtree child. It means that the answer to color y nodes in some subtree rooted at x depends on its child, this gives us a hint for Dynamic Programming.

Let’s move towards Dynamic Programming.

DP[I][J] is defined as the minimum number of operations that are required to color exactly J nodes in subtree which is rooted at node I. If it is impossible to color exactly J, we can simply say DP[I][J]= \infty

During traversal, for every node I, we set DP[I][J]= 0, as it requires 0 operation to color 0 nodes. Now suppose we are at node x which have z children as c_1,c_2,\dots,c_z and n_1,n_2,\dots,n_z be the size of their subtree. Now during traversal if we have explored child c_1 and c_2, it means we knew the best answer for coloring nodes till n_1 + n_2 from subtree rooted at node x.

Now recently we had explored the child c_3. Then we can optimize our DP[x] for coloring nodes from 1 to n_1+n_2+n_3. It can be done as follows:

DP[x][itr_1+itr_2] = min(DP[n][itr_1+itr_2], DP[x][itr_1] + dp[c_3][itr_2])

where, itr_1 varies from n_1+n_2 to 0 and itr_2 will vary from 1 to n_3.

If the size of the whole subtree is less than or equal to k, then we can simply set DP[x][size]=1 as it requires 1 operation to color the whole subtree.

This way when we finish traversing we get the minimum number of operations to color nodes from 1 to min(N, K) in a tree.

Once we are done with this, the next part is easy to do.

Now let’s allow us to create a new copy of the tree and now find out the minimum number of operations required to color exactly K nodes. We can again use DP for the same. Let us define DP as:

DP_1[I] is defined as the minimum number of operations required to color i nodes in any number of trees.

DP_1[0]=0 as it requires 0 operations to color 0 nodes. Rest can be done as follows:

DP_1[I] = min(DP_1[I],1+ DP[1][J]+DP_1[I-J])

where J is the minimum of (I, N) and 1 is added as we create a new tree.

Finally DP[K]-1 gives us the required answer. We need to subtract 1 as one tree is already gifted to us.

TIME COMPLEXITY:

O(N.K + K^2) per test case

SOLUTIONS:

Setter
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;

vector<int> adj[50005];
bool vis[50005];
int dp[50005][1005];
int N,k;

int dfs(int n){
    vis[n]=1;
    int res = 1;
    dp[n][0] = 0;
    int last = 0;
    for(auto i : adj[n]){
        if(vis[i])continue;
        int nodesInChild = dfs(i);
        res += nodesInChild;
        for(int itr1 = last; itr1>=0; itr1--){
            if(dp[n][itr1]==INF)continue;
            for(int itr2 = 1; itr2<=nodesInChild; itr2++){
                if((itr1 + itr2)>k)break;
                if(dp[i][itr2]==INF)continue;
                dp[n][itr1+itr2] = min(dp[n][itr1+itr2], dp[n][itr1] + dp[i][itr2]);
                last = itr1+itr2;
            }
        }
    }
    dp[n][res] = 1;
    return res;
}


void pre(){
    for(int i =0; i<=N; i++){
        vis[i] = 0;
        adj[i].clear();
        for(int j=0;j<=k;j++)dp[i][j]=INF;
    }
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int test;
    cin >> test;
    while(test--){
        
        cin >> N >> k;
        pre();
        for(int i = 2; i<=N; i++){
            int parent;
            cin  >> parent;
            adj[parent].push_back(i);
            adj[i].push_back(parent);
        }
        dfs(1);

        vector<int> num,oper;
        for(int i = 1; i<=k; i++){
            if(dp[1][i]!=INF){
                num.push_back(i);
                oper.push_back(dp[1][i] + 1);
            }
        }

        
        int arr[k+1] = {0};
        for(int i = 0; i<=k; i++)arr[i] =INF;

        arr[0] = 0;
        for(int i = 0; i<=k; i++){
            for(int j = 0; j<num.size(); j++){
                if(i+num[j]>k)break;
                if(arr[i]==INF)continue;
                arr[i+num[j]] = min(arr[i+num[j]], arr[i] + oper[j]);
            }
        }

        cout << arr[k]-1 << "\n";
        //assert((arr[k]-1) == 2*(k/N + (k%N>0)) -1);
    }
}
Testerr
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
long long gcd(long long a, long long b){
	while(b) a %= b, swap(a, b);
	return a;
}
struct union_find {
    vector<int> parent;
    int n;
    union_find(int n) : n(n) { clear(); }
    inline void clear(){ parent.assign(n, -1); }
    inline int find(int u){ return (parent[u] < 0) ? u : parent[u] = find(parent[u]); }
    inline bool same(int u, int v){ return find(u) == find(v); }
    inline bool join(int u, int v){
        u = find(u);
        v = find(v);
        if (u != v){
            if (parent[u] > parent[v])
                swap(u, v);
            parent[u] += parent[v];
            parent[v] = u;
        }
        return u != v;
    }
    inline int size(int u){ return -parent[find(u)]; }
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = readIntLn(1, 400);
	int sum = 0;
	while(t--){
		int n = readIntSp(1, 5 * TEN(4));
		int k = readIntLn(1, TEN(3));
		sum += n * k;
		vector<vector<int>> adj(n);
		union_find uf(n);
		for(int i = 1; i < n; i++){
			int u, v = i + 1;
			if(i + 1 == n) u = readIntLn(1, n);
			else u = readIntSp(1, n);
			u--; v--;
			assert(uf.join(u, v));
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		vector<int> sz(n), ord;
		auto f = create<int>(n + 1, k + 1);
		for(int i = 0; i <= n; i++)
			for(int j = 0; j <= k; j++)
				f[i][j] = k + 100;
		f[0][0] = 0;
		int stk = 1;
		function<void(int,int)> dfs = [&](int u, int p){
			sz[u] = 1;
			for(int v : adj[u]){
				if(v == p) continue;
				dfs(v, u);
				sz[u] += sz[v];
			}
			ord.push_back(u);
		};
		dfs(0, -1);
		for(int i = 1; i <= n; i++){
			int u = ord[i - 1];
			f[i] = f[i - 1];
			for(int j = 0; j + sz[u] <= k; j++){
				f[i][j + sz[u]] = min(f[i][j + sz[u]], f[i - sz[u]][j] + 1);
			}
		}
		vector<int> ways = f[n];
		vector<int> ans(k + 1, k + 100);
		ans[0] = 0;
		for(int i = 1; i <= k; i++){
			for(int j = 1; j <= i; j++){
				ans[i] = min(ans[i], ans[i - j] + ways[j] + 1);
			}
		}
		cout << ans[k] - 1 << '\n';
	}
	assert(sum <= TEN(7));
	return 0;
}
Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mxN=5e4+5;

vector <int> adj[mxN];
vector <bool> vis(mxN);

int table[mxN][1005];
int cache[1005];
int n,k;

int dp(int x)
{
  if(x==0)
    return 0;

  int &ans=cache[x];

  if(ans!=-1)
    return ans;

  ans=1e9;

  for(int i=1;i<=min(n,x);i++)
    ans=min(ans,1+table[0][i]+dp(x-i));

  return ans;
}

int dfs(int u)
{
  vis[u]=true;
  int si=1;
  table[u][0]=0;

  int temp=0;

  for(auto x: adj[u])
  {
    if(vis[x])
      continue;

    int child = dfs(x);
    si+=child;

    for(int i=temp;i>=0;i--)
    {
      if(table[u][i]==1e9)
        continue;

      for(int j=1;j<=child;j++)
      {
        if(i+j>k)
          break;

        if(table[x][j]==1e9)
          continue;

        table[u][i+j]=min(table[u][i+j],table[u][i]+table[x][j]);
        temp=max(temp,i+j);
      }
    }
  }

  if(si<=k)
      table[u][si]=1;

    return si;
}

void pre()
{
  for(int i=0;i<n;i++)
  {
    vis[i]=false;
    adj[i].clear();

    for(int j=0;j<=k;j++)
    {
      table[i][j]=1e9;
      cache[j]=-1;
    }
  }
}

void solve()
{
  cin>>n>>k;

  pre();

  for(int i=1;i<n;i++)
  {
    int x;
    cin>>x;

    x--;
    adj[x].push_back(i);
    adj[i].push_back(x);
  }

  dfs(0);

  int ans=dp(k);

  cout<<ans-1<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  // freopen("input1.txt","r",stdin);
  // freopen("output1.txt","w",stdout);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}
4 Likes

In our DP, when we do dp[n][itr1 + itr2] = min(dp[n][itr1 + itr2], dp[n][itr1] + dp[i][itr2]);, why don’t we double count? Why don’t some of the itr1 elements in the subtree of n collide with the itr2 elements in the subtree of i? That is, aren’t there some elements which are counted in the tree rooted at n with itr1 colorings, but also counted in the tree rooted at i with itr2 colorings?

itr1 is for the child subtree that have been visited previously and itr2 is for the child subtree that is being visited currently , so how can itr1 collide with itr2 ?.

(EDIT: Nvm)

why the first sample input of question not comes under the category of simple path??

What is nx here? Should it be x?

1 Like

tree is directed

Yes it should be X , it is just a typo

How is the time complexity of the DP transitions O(N\cdot K)?

The nested loops of itr1 and itr2 run for every edge right? And the time complexity of the loops seems to be O(k^2). Can you explain how it will come out to be linear?

3 Likes

Setter’s code gives WA on submission. Please correct the code.

Tester’s code also gives WA.

Editorialist’s code gives Correct Answer tho.

2 Likes

can someone give me a testcase where my code fails. I am not able to find any bug in my code. Any help is appreciated. Thanks in advance. Link to my solution

update dp[n][res] only when res <= k … this is missing in setter’s code

How is the time complexity of solution is O(NK)? It is clearly taking ~ KK operations for each node, so the complexity must be O(N*K^2 + K^2). I thought it would cause TLE, but since most of the coders implemented it so there must be someway to prove it? Can someone give me rough proof of time complexity?

2 Likes

Proof of the time complexity (Ignoring the limit of K, so i will prove that the complexity is O(N^2)).

Lets calculate how many times we perform the
DP[x][itr1​+itr2​]=min(DP[x][itr1​+itr2​],DP[x][itr1​]+DP[c3​][itr2​])
operation.

In a tree with N nodes, we perform (N-1)^2 / 2 operations.
We will prove it with induction:

If N = 1, we need 0 operation.
If N>1:
In this step we already know the answer for all smaller trees (so we know the answer for the
subtrees).
Lets call the root r.
- if r has only 1 child: the child’s subtree needs (N-1)^2 / 2 operations (since it has N-1 nodes)
- if r has at least 2 children:
Let’s say that r has p children, and the size of their subtrees is n_1, n_2, …, n_p
This case we perform n_1 * n_2 + (n_1 + n_2) * n_3 + … + (n_1 + n_2 + … n_(p_1)) * n_p =
= (n_1 * (N - 1 - n_1) + n_2 * (N - 2 - n_2) + … + n_p * (N - 1 - n_p)) / 2 = ((N-1)^2 - n_1^2 - n_2^2 -
… - n_p^2) / 2
Adding to this that in the ith child’s subtree we perform n_i^2 / 2 operations, the total
number of operation is (N-1)^2 / 2

A similar proof works when we have the K limit

One small doubt. Consider n=3, and k=6. Let the tree be 3 node binary tree with node1 being parent of node 2 and node 3 and node 2 and node 3 are leaf nodes. Now, logically, DP[1][2]=inf since we cannot color 2 nodes by color operation at node 1.
But according to the given DP formula it turns out to be 2(value of DP[1][2]).
Please tell me if there is something that I am doing wrong or the DP formula is incorrect, or it doesnt matter if it is incorrect.

When looking at the whole tree, u color first the node 2 than the node 3. U made 2 steps, so DP[1][2]=2 is correct.

Ah…I see! Thank you busamate.

I think I might have an intuitive idea for why the complexity of dfs is O(NK).
every node either contributes to itr1’s bound (temp variable in editorialist’s code) or
it contributes to itr2’s bound(child variable in editorialist’s code)
since each node can contribute in itr1’s bound and itr2’s bound atmost k times, there will be O(N(K+K)) = O(NK) operations.

This and in the dfs call, last should be updated as last = max(last, itr1 + itr2).

For the NK part of this solution, a 2D dp table is not necessary since eventually we are only accessing the root node’s entry. We maintain only one dp array, and when we do dfs on child nodes, we keep updating this array itself.

Sample submission

The key line is line 30

  • dp[i] is the minimum cost to color i nodes, using the subtrees of the child nodes of the current node (in the end of the dfs, the current node will be root node).
  • dp_org[i] is the minimum cost to color i nodes without using the nodes in the subtree of the current node (this is why, note that on line 21, we set dp_org to be a copy of dp before iterating into my adjacency list. so the values in dp_org do not account for my subtree)
  • now, the min(.., ..) means that either we color i nodes using my children subtrees’ (dp[i]) OR we color i - sz nodes without using my subtree (dp_org[i]) and then color my whole subtree in one operation (by choosing the current node).

We ininitialize only dp[0] = 0 (0 operations to color 0 nodes). After the dfs (find_subtree_cost) is over, dp[x] will contain minimum number of operations required to color x nodes in the tree.

Hope it helps