JacobianDet's blog

HOW TO SOLVE SPOJ ADAPANEL
By JacobianDet, history, 6 years 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

»
6 years 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).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide some help on this as I'm stuck on this for more than a year?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the meaning of array here ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the combinatorics part of this question?

→ Reply