PROBLEM LINK:Practice Setter: Stylianos Kasouridis DIFFICULTY:MediumHard. 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
EXPLANATIONInitially, 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]*(SZi)$ tax with $i$ cities protesting. (Assuming zerobased 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 $(ij)$ cities in other SCCs at protest, for $0 \leq j \leq min(K, SZ)$. So, we have $DP[x][i] = max(val[j]+best[ij])$ 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 AnalysisThe 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 Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 14 Feb, 00:13
