PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Aleksa Plasvic
Tester: Hasan Jaddouh
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium-hard
PREREQUISITES:
Greedy, Observations and Dynamic Programming.
PROBLEM:
Given a tree-flow network with N nodes where each node can store an infinite amount of water, but each edge can transfer only given amount of water to a node from its parent, taking one second to move from parent to child. On reaching the leaf, water gets stored at the leaf. Find out minimum time by which there are at least X units of water at all leaves combined.
QUICK EXPLANATION
- Let’s find all the leaves and order them by their distance from the root from least distant to most distant.
- For each leaf x, find the minimum capacity min of all edges on the path from this leaf to the root, and subtract it from capacities of all the edges on the path of the root. Starting from the second D_x, min units of water gets stored at each leaf. Repeat this procedure for all leaves.
- Reason this works is the tree structure, and can be proven as, if we choose to divert a flow of unit x from leaf at distance y from root to a leaf at distance z from root y < z then this x units of water reach z-y seconds late than in the optimal case, making this case non-optimal.
EXPLANATION
This problem has a relatively simple solution, though may have a lot of wrong approaches that seem correct since it is hard to see why it is correct. There are two solutions, one greedy and one dynamic programming. I am explaining the greedy solution here.
Consider linear tree with N vertices where vertex i is connected to vertex (i+1) for all 1 \leq i \leq N-1. Node N is the only leaf, so we want to push as much water per second as we can. We can see, that only x units of water can reach node N per second where x is the minimum edge capacity on the path from 1 to N. It can be seen that for the first N-2 seconds, no water reaches node N. After that, x units of water reaches node N every second.
For any flow network, it is understood that when edge capacities remain the same, we do not need to change the actual flow of water between nodes for each second.
Generalizing this, we can see that for a leaf x, if D_x denote distance from root, No water reaches that leaf for first D_x-1 seconds, and after that, the maximum units of water that can reach this leaf is the minimum of the flow at any edge from root to this leaf.
A special property about tree network here is that once we decide to move x units of water from a current node to one of its children, it does not restrict the flow of other children of the current node, except reducing the water units available for other children, which would indirectly reach any other leaf. See, by sending x units of water to one leaf, we cannot lose more than x units flow for any other leaf. This allows us to use the greedy strategy below.
Find all the leaves and sort them by their distance from the root from nearest to farthest. Considering leaves one by one, Find out the minimum of all capacities of edges on the path of current leaf x to root. Suppose the minimum capacity we get is y. We can get y units every second from D_x second onwards. We subtract y from every edge capacity from root to leaf x and repeat this process for next leaf and so on.
Now, for each leaf x, we know that y units of water reach from D_x seconds onwards. Suppose there are three leaves, at depth d_1, d_2 and d_3 d_1 < d_2 < d_3 and have flow f_1, f_2 and f_3 respectively. So, for seconds 0 to second d_1-1, no water reach any leaf. From second d_1 to d_2-1, f_1 units of water flow. From second d_2 to second d_3-1, f_1+f_2 units of water flow. From d_3 second onwards, f_1+f_2+f_3 units of water keep flowing.
We can use an array to store the amount of water reaching leaf for the first time at t seconds. Then taking prefix sum array of this array gives us the units of water reaching any leaf for each second. Once water starts reaching the most distant leaf, the amount of water reaching leaf does not change.
So, for the first N seconds, we can check manually the amount of water that has reached leaves and check at every second if water reached till current second is at least X or not. If yes, we have found the minimum time. Otherwise, since we know that depth cannot exceed N, water flow after Nth second does not change, so we can find the remaining time to get at least X units of water using ceil function.
Also, there exists a dynamic programming solution in time complexity O(N^2) which was initially proposed. Refer to setter’s solution for details.
Bonus Problem
What if in place of a tree network, we have a DAG with a given set of nodes having edge capacities, can we still solve the problem? Explain your approach in comments.
Time Complexity
Time complexity is O(N^2*logN) per test case.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int maxN = 1100;
const int inf = 1e9;
int c[maxN], p[maxN];
int n, d;
int sumN;
long long dp[maxN][maxN];
int leaf[maxN];
void solve()
{
scanf("%d%d",&n,&d);
assert(n>0 && n<=1000);
assert(d>0 && d<=1000000000);
sumN+=n;
for (int i=1;i<=n;i++)
leaf[i]=0;
for (int i=2;i<=n;i++){
scanf("%d",&p[i]);
leaf[p[i]]++;
assert(p[i]>0 && p[i]<i);
}
for (int i=2;i<=n;i++){
scanf("%d",&c[i]);
assert(c[i]>0 && c[i]<=1e9);
}
for (int i=1;i<=n;i++)
if (leaf[i])
dp[0][i]=0;
else
dp[0][i]=inf;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++)
if (leaf[j])
dp[i][j]=0;
else
dp[i][j] = inf;
for (int j=n;j>=1;j--)
dp[i][p[j]]+=min(1ll*c[j],dp[i-1][j]);
}
int sum = 0;
for (int i=1;i<=n;i++){
sum+=dp[i][1];
if (sum>=d)
{
printf("%d\n",i);
return;
}
}
int ans = n + (d- sum + dp[n][1]-1)/dp[n][1];
printf("%d\n",ans);
return;
}
int main()
{
int t;
cin>>t;
assert(t>0 && t<=1000);
while(t--)
solve();
assert(sumN>0 && sumN<=50000);
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
class TREF{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
long X = nl();
int[] p = new int[n], d = new int[n];
long[] c = new long[n];
boolean[] leaves = new boolean[n];Arrays.fill(leaves, true);
int cnt = n;
for(int i = 1; i< n; i++){
p[i] = ni()-1;
d[i] = d[p[i]]+1;
if(leaves[p[i]]){
leaves[p[i]] = false;
cnt--;
}
}
int[][] leaf = new int[cnt][];
for(int i = 0,j = 0; i< n; i++)if(leaves[i])leaf[j++] = new int[]{i, d[i]};
Arrays.sort(leaf, (int[] i1, int[] i2) -> Integer.compare(i1[1], i2[1]));
for(int i = 1; i< n; i++)c[i] = nl();
long[] sum = new long[n];
for(int j = 0; j< cnt; j++){
int x = leaf[j][0];
long min = IINF;
while(x>0){
min = Math.min(min, c[x]);
x = p[x];
}
x = leaf[j][0];
sum[d[x]]+=min;
while(x>0){
c[x] -= min;
x = p[x];
}
}
long ans = 0;
for(int i = 1; i< n; i++){
sum[i]+= sum[i-1];
ans++;
X -= sum[i];
if(X<=0)break;
}
if(X>0)ans += (X+sum[n-1]-1)/(sum[n-1]);
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)5e5+1;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new TREF().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new TREF().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 