farmerboy's blog

By farmerboy, history, 5 months ago, In English

Hello Codeforces community,

I would like to know how to solve this problem: https://codeforces.com/gym/100371/problem/M. I looked at some submitted code but no clue how they worked, they seem to use some DP in which the state is unknown to me.

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.

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

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

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

Example

stdin stdout
5 1 0.0
10 2 0.1

Full text and comments »

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

By farmerboy, history, 18 months ago, In English

I'm writing this to see if there is anyone who is in the same situation.

I was in top 1000 in Google Code Jam 2022 Round 2. I received the code for redeeming the T-shirt at around mid-June this year. When I filled in the address form and clicked the submit button, it returned to the home page of the swag portal and there was nothing happened. When I tried to fill in the code again to see if it worked, the address form was shown again. I was pretty confused but still believed it was ok (since I submitted anyway).

Since it was written on the swag portal that they would deliver the prize in August, I've been waiting for it this whole month but there is nothing. So I emailed [email protected] and [email protected] for help. In short, they said that If the order went through, you should have received an email confirmation with an order # and unable to access the portal once redeemed. Everything is made to order so we don’t have any more product to ship to you. and Unfortunately the swag portal has closed and we won't be able to ship out anymore items.

This is pretty confusing since there was nothing in the swag portal indicating that there would be a confirmation email or something (so sorry if it did have but I was not able to see it). Is there anyone who is in the same situation? Who can I ask for help on this situation except emailing the team?

Thanks.

Full text and comments »

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

By farmerboy, history, 3 years ago, In English

Hello,

I'm quite depressed now but I would like to try for the last time.
The participants who dropped to CM after round 740 and gave round 741 are unrated in round 741 so far. The author of round 741 said that This round will be rated for the participants with rating lower than 2100. Clearly, I'm one of them.

So I kindly ask MikeMirzayanov if there is any issue with the rating system. If it simply cannot be fixed, please make an announcement before Deltix Round on Sunday, because I think that the rating will be very messed up after that round if the fix for round 741 is still pending.

Thanks.

Full text and comments »

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