HOW TO SOLVE SPOJ ADAPANEL

Revision en2, by JacobianDet, 2018-08-13 18:00:44

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.

Tags combinatorics, scc

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English JacobianDet 2018-08-13 18:00:44 1
en1 English JacobianDet 2018-08-13 17:59:20 585 Initial revision (published)