PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Stylianos Kasouridis
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium-Hard.
PREREQUISITES:
Strongly Connected Components, Dynamic Programming, Topological sorting.
PROBLEM:
In N cities having their budget given by array B connected by M directed roads, a tax collector may start collecting tax from any city and when he enters a city from where he hadn’t yet received any tax, he may collect a fixed amount X from every city which can be reached from current city, as well as current city, can be reached from that city. If X > B[i] for some city, that city refuses to pay tax at all. If he has already collected tax from this city, he cannot collect tax again from this city. Find out the maximum amount of tax the tax collector can collect if he chooses the value of X carefully, making sure that no more than K cities are not paying taxes.
QUICK EXPLANATION
- The statement “Cities reachable from current city and also, the current city being reachable from those cities” means the strongly connected components in a directed graph. Hence, for each Strongly Connected Component, we may choose the same value of X.
- For each SCC, we may calculate val[i] as the maximum amount of tax we may collect in current SCC if i cities refuse to pay tax. It can be computed by sorting the budgets of all nodes present in the same SCC and doing basic math.
- Now, after collecting tax from current SCC, the tax collector may move to any other SCC whose node is connected to any node of current SCC. Having calculated the maximum tax within SCC, we need to merge the results, which may be done using Dynamic Programming, if we consider each SCC as a node in the new graph and use DP on topological sorting.
- For each SCC, we shall compute the best[i] array denoting the maximum amount of tax we may collect from SCC’s reachable from current SCC. Now, we may find the maximum tax collectible if we start our path in this SCC.
- If DP[x][i] denote Maximum tax collectible if starting from SCC x and i cities refusing to pay, DP[x][i] = max(val[j] + best[i-j]) for all 0 \leq j \leq min(K, SZ) where SZ is the size of current SCC.
EXPLANATION
Initially, assume that the whole graph is a single Strongly Connected Component. So, all nodes are reachable from any node. Hence, the tax collector may announce an amount X and cities with budget less than X protest. It can be seen that higher the value of X, tax collected may be higher, but the number of cities protesting may also increase.
Clearly, if we take the budgets of all cities in same SCC and sort them, say given by array b, we can collect b[i]*(SZ-i) tax with i cities protesting. (Assuming zero-based indexing).
It is easy to see, that in the best case, X coincide with one of the budget amounts. This can be proved by contradiction.
Lemma: In the optimal case, X coincide with one of the budget amounts.
Proof: Let’s assume that X doesn’t coincide with the budget of any city in SCC. Suppose the next higher budget amount is Y = X+ d, d > 0. It can be seen, that the number of cities paying tax is the same in both cases, say C. So, by announcing X tax, we collected X*C tax while if we announced Y, we may collect tax Y*C = X*C + d*C which is strictly greater than X*C. Hence, we lost the tax d*C and hence, such value of X is never optimal.
So, We know, X has to be one of the budget amounts in the optimal case. So, We basically check each budget value and see the tax collected as well as the number of cities not paying taxes.
Now that we have solved the problem for one SCC, Let’s make another directed graph where each SCC represent a single node. It can be easily proved that this graph doesn’t contain cycles.
Now, Each node has a corresponding val array, representing the maximum tax collectible val[i] in that SCC, if i cities protest. We have to calculate the maximum tax over the path iterated by the tax collector.
We know, once he leaves one SCC, he cannot come back again, so, this graph is directed.
Now, Let us use Dynamic Programming on this reduced graph where DP[x][i] denote the maximum tax collected if tax collected starts from SCC x and at most i cities protest. For SCC’s having no outgoing edge to other SCC, DP[x] is same as the val array.
Now, suppose current SCC is connected to many other SCC by outgoing edge. So, we need to calculate DP array for all those SCCs before calculating for this SCC. This imples, we need to process SCCs in topological order. Suppose we have DP calculated for all SCCs connected by edge outgoing from current SCC. For each i, we may simply take maximum tax collected in any of these SCCs with i cities protesting. Let us call it best[i]. So, to calculate DP[x][i] we may choose j cities in current SCCs at protest and (i-j) cities in other SCCs at protest, for 0 \leq j \leq min(K, SZ). So, we have DP[x][i] = max(val[j]+best[i-j]) for 0 \leq j \leq min(SZ, K).
The maximum tax collected is the maximum of tax collected from any city.
For finding SCCs, Tarjan’s algorithm may be used which you may find here.
For those facing problem with this Dynamic Programming, may imagine it to be similar to Dynamic Programming for longest path in DAG, which you may find here.
Time Complexity Analysis
The time complexity of this solution is O((N+M)*K+N*logN).
Input is of size M. Finding out Strongly Connected Components take O(N) time, sorting budgets may take O(N*log(N)) in the worst case. (It can be improved to N*logK using heaps). After that, calculating val array for each SCC takes O(min(SZ, K)) time. Topological sorting takes O(N) time in the worst case (Each node being its own SCC). For Dynamic Programming, Time taken at each node in the reduced graph is O(K*SZ) where SZ is the size of SCC. Since \sum SZ_x = N, Time complexity of this step comes down to O(N*K). Also, calculating the best array takes x*K time where x denote the outdegree of current node representing current SCC. Since \sum x = M in worst case, This part takes O(M*K) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 