Ask for solution of problem M of 2014 Winter Programming School, Kharkiv, day 1 contest

Revision en1, by farmerboy, 2023-10-04 07:40:26

Hello Codeforces community,

I would like to know how to solve this problem:

It's problem M of 2014 Winter Programming School, Kharkiv, day 1 (E. Kapun). High league contest. If you don't want to download the statement file, I paste it below.

Problem M. Hash-table (High)

Input file: stdin
Output file: stdout
Time limit: 1s
Memory limit: 256 MB

Alex learned about a new data structure: a hash table with open addressing. Hash table with open addressing consists of $$$N$$$ cells numbered from 1 to $$$N$$$. Each of them may be empty, or storing a value.

When you insert a new value, it calculates the hash — random number between $$$1$$$ to $$$N$$$ (let’s call it $$$h$$$) — after which, if the cell under number $$$h$$$ is empty, the value is written into it. Otherwise, if the cell $$$h + 1$$$ is empty, the value is written into it, and otherwise it checks $$$h + 2$$$, $$$h + 3$$$ and so on. If the search has reached $$$N$$$-th cell, and it is not empty too, the search continues with the cell number $$$1$$$. Thus, if there are an empty place somewhere, the value anyway will be added.

For example, if the value is equal to the hash $$$h$$$, the cell turned recorded $$$h + 2$$$ then we can assume, that there were two collisions occurred. Collisions slow down the hash table, so Alex decided to find out how many collisions will be in average, if in a empty hash table insert M different values. And calculate, as always, to you.

$$$1 \leq N \leq 100$$$
$$$0 \leq M \leq N$$$

The single line contains 2 integers: $$$N$$$ and $$$M$$$.

You should print a single number — an average number of collisions. Print the answer with absolute or relative error of less than $$$10^{−7}$$$.


stdin stdout
5 1 0.0
10 2 0.1
Tags expected value, probability, dp, hard


  Rev. Lang. By When Δ Comment
en4 English farmerboy 2023-10-04 18:40:59 2 Tiny change: 'le insert M different' -> 'le insert $M$ different'
en3 English farmerboy 2023-10-04 10:43:57 8
en2 English farmerboy 2023-10-04 07:42:08 124
en1 English farmerboy 2023-10-04 07:40:26 1998 Initial revision (published)