Fefer_Ivan's blog

Codeforces Beta Round #28 - problem C tutorial
By Fefer_Ivan, 14 years ago, translation, In English

For the first time, our team will write tutorials separetly, but we will unite the in one post after everything will be ready.
C. Bath Queue
This problem is solved by dynamic programming
Consider the following dynamics: d[i][j][k].
i --- number of not yet processed students,
j --- number of not yet processed rooms,
k --- maximum queue in the previous rooms.
The value we need is in state d[n][m][0]. Let's conside some state (i, j, k) and search through all c from 0 to i. If c students will go to jth room, than a probability of such event consists of factors: Cci --- which students will go to jth room.
(1 / j)c· ((j - 1) / j)i - c --- probability, that c students will go to jth room,and the rest of them will go to the rooms from first to j - 1th.
Sum for all с from 0 to i values of
(1 / j)c· ((j - 1) / j)i - c· Cci· d[i - c][j - 1][mx]. Do not forget to update maximum queue value and get the accepted.

Thank you for your participation. Good luck with upsolving and incoming contests. Luck - is very useful and it is good to have it.
With best regards, Ivan.

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

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Fefer,  I don't  know the third dimension, why the last answer  dp[n][m][0] 's third dimension  is 0, and how to update the third dimension (namely "mx").
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    k is maximum queue length so far. Of course, when there are m not processed rooms (i.e. all rooms haven't been processed), maximum queue is 0 (no queue yet).

    When considering room j with c students inside it, the largest queue in this room is (c + basin[j] - 1) / basin[j]. Then mx is actually the greater of this value and k (hence the 'update').
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For a particular assignment of students in the rooms , we find the probability of such an assignment  and the maximum queue length. The expected value then is the sum of products of such probabilities and their maximum queue length. Is this my correct understanding of expected values ?
→ Reply