Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

no_life's blog

By no_life, history, 5 months ago, In English,

We all know that the number of solutions to a+b = 3 (where a and b are non negative) can be easily found out by stars and bars theorem. So answer of the above is 4. { (3,0),(0,3),(1,2),(2,1)}. But I want the answer to be 2 as the first two and last two are equivalent. Formally, as the stars and bars give the number of ordered sets, I want to find out the number of unordered sets.

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

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

Number of ordered sets ((a+b)/2)+1 if i understood your question correctly.

»
5 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

This can be solved by dynamic programming the general case. First of all define P(N,K) as the number of ways you can represent N using K numbers in ascending order.

Now for solving P(N,K), if K > N then answer is 0, otherwise let's distribute 1 item on each set. Your task is now to distribute N — K items without breaking the ascending order.

If you place an item, in the ith set, you must use n — i — 1 items for later sets to compensate. So you can just apply dynamic programming and solve it O(N*K).

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

?detaR tI sI

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

I'm gonna take a guess and say that you are looking for the partitions of a number. https://en.wikipedia.org/wiki/Partition_(number_theory) You can check here for fancy formulae, or just look for a dp solution :)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Input

    N = 64, K = 3

    Output

    7

    This can be expressed as a product of three integers in the following ways:

    1 x 1 x 64

    1 x 2 x 32

    1 x 4 x 16

    1 x 8 x 8

    2 x 2 x 16

    2 x 4 x 8

    4 x 4 x 4

    Therefore, 7 ways.