passworld's blog

a counting problem
By passworld, 10 years ago, In English

Hello everyone! Here is an interesting problem on math I need help with:

Given

a set S (size n <=20) ,say S[1..n]

m (m<=10^5) subsets of S ,say Sub[1...m]

p (p<=10^5) people, say P[1..p]

Definition of one assignment

For p person, each one choose a subset ( can be the same ), so that the union of the p subsets is equal to S.

Try to count

The number of assignments. (time limit: 5 seconds)

Any hints or thoughts will be really appreciated!

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint: Think dynamic programming. Assign sets to people sequentially. After you already assigned the sets to x people, what is the smallest amount of information you need about those assignments in order to be able to count how many ways of assigning sets to the remaining people will yield a valid solution?

(Also, in the future please always post the source of a problem. There is always a lot of people trying to cheat by requesting solutions to currently running contests.)

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

    Thank you for your hint.

    You suggestion is very reasonable.

    Actually this problem is from practice problem provided many years ago and given without its online form.So it is not convenient to post the link to it here(at least I can't search it out limited to my experience and knowledge).I just challenge it and share it as a practice for fun.I thought it might be a typical problem and I want to learn from it as a beginner (after many hours of attemption on solving it). I guarantee that this is not from a running contest.Thank you very much for your kind help!

    → Reply