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:
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:
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:
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;
}