Блог пользователя stould

Автор stould, 10 лет назад, По-английски

Hello, I'm trying to solve a problem from SPOJ involving combinatorics (counting), but I cannot find a final answer... http://www.spoj.com/problems/MARBLES/

I've found some things that I guess will be useful to solve this task: You have to use at least one ball in each color, so, N-K (I will call it "X") balls left.

I need to distribute this X balls in the K colors, so I began to think: "I can use from 0 up to X balls in each color".

I'm trying hard to find out the answer, maybe am I thinking in a wrong way ?! Can you give to me some tips how to solve ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

An another thought process would be something like this - There are N-K balls, place them side by side, now we need to divide this into k partitions. i.e. put some k-1 bricks in between. How many ways can we do this?

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Huh.... I'm so sorry.. I'm thinking about N Choose (K-1) to do it.. But I guess I'm missing something.. Woow... I need K-1 bars to generate K distinct groups..

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Think of the problem this way: You have N stars in a line and you want to put K-1 bars between them (divide them in K groups), such that no two bars are in the same position (this ensures you have at least one star in each group). How would you do that?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have to place this bars in all possible locations in wich no two bars will be together...

    Why K-1 bars ?!