passworld's blog

By passworld, 7 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!

Read more »

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

By passworld, 7 years ago, In English

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

Thank you in advance!

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

Read more »

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

By passworld, 7 years ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

By passworld, 7 years ago, In English

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!

Read more »

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