JacobianDet's blog

By JacobianDet, history, 7 months ago, In English,

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.

  • Vote: I like it  
  • +4
  • Vote: I do not like it  

7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by JacobianDet (previous revision, new revision, compare).