### passworld's blog

By passworld, 7 years ago,

## 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!

• +18

By passworld, 7 years ago,

### Here is a hard problem for me:

time limit per test4 seconds memory limit per test256 megabytes

Given a,b (1<a<b<1000,integer) and (a,b)=1

Try to find an array P[ ] (size unknown)so that:

• there exist a positive integer k so that:
• ( Sum of P[i] )== k * a
• For all i : ( k*b ) % P[i]==0 and then we note A[i]=k*b/P[i]

We want to output A[].

NOTE: elements in P[ ] are(is) positive integer and size of P[ ] should be as small as possible and if it is tied for some possible arrays with equal minimal size, choose one array that elements ofA[ ] are as small as possible. (not element of P[],where I typoed before ,I am so sorry for that!)

sample in a=3 b=10 ; sample out A={5,10}

• +5

By passworld, 7 years ago,

I want to count for every number ,say A[i] ,how many numbers there are that is smaller than Ai with id smaller than i. For example , here is an array: 5 3 7 2 9 6 ,the anwser is 0 0 2 0 4 3 Is there any fast algorithm that can solve this problem? Thank you for your help!

• -2

By passworld, 7 years ago,

I want to find a free , simple and powerful software to draw graph structure and mark on it easily. (just like some graph appear on some tutorials ) Any recommendation? Thank you very much!