Problem Link: https://www.spoj.com/problems/ADAPANEL↵
↵
The above problem is a mix of SCC and combinatorics. I get that first we need to get the condensed components of the graph, but I am not able to get the idea for the combinatorics part. I know that number of ways to distribute n panel-blocks to n cities has to be calculated in a way like the Integer partition problem, but the constraints are of the order of 2*10^5 and the usual O(n^2) dp method for partition fails to solve this. Any help on this will be very useful to me for solving this problem.
↵
The above problem is a mix of SCC and combinatorics. I get that first we need to get the condensed components of the graph, but I am not able to get the idea for the combinatorics part. I know that number of ways to distribute n panel-blocks to n cities has to be calculated in a way like the Integer partition problem, but the constraints are of the order of 2*10^5 and the usual O(n^2) dp method for partition fails to solve this. Any help on this will be very useful to me for solving this problem.
