Connection Status:
Competition Arena > IDs

IDs

Rookie SRM 14 · 2022-06-13 · by lars2520

Rookie SRM 14 · 2022-06-13 · by lars2520 · Advanced Math
Class Name: IDs
Return Type: double
Method Name: collisionProbability
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

You are working on the backend of a particular system in which you want to assign a unique ID to each client. However, the system is distributed, and there are a number of components, each of must be able to assign IDs to clients. Thus, you have to figure out how to assign each client a unique ID, while maintaining the distributed nature of the system. In other words, you want to have each of the components assign the IDs with as little communication between the components as possible. You have decided that it is more important that the system remain as distributed as possible than it is that all of the clients have unique IDs. Thus, you are considering having each of the components independently assign IDs randomly from a large pool of possible IDs, and synchronizing the assigned IDs at the end of each day. In other words, each component will update its list of available IDs at the end of each day, based on the IDs assigned by all of the components.

Your task is to simulate this system and figure out the probability that an ID is assigned by more than one component. You will be given an int, num, which represents the number of IDs in the pool of possible IDs that each component may assign at the beginning of some day. You will also be given a int[], counts, each of whose elements represents the number of IDs that some component assigns during the day. You are to return a double representing the probability that more than one component will assign the same ID.

Notes

  • Due to memory constraints in the components, they do not 'remember' the IDs that they have assigned. Thus, it is possible for two components to both assign a particular ID, and also for a single component to assign a particular ID more than once.
  • Note that because the return type is a double, your result need not be precisely the same as the result of the reference solution. As long as your result is either within 10-9 of the reference result, or within (10-9 * reference result) of the reference result, your solution will be judged correct. In other words, as long as the first 10 digits of your solution's result are within one of the reference result, you will be judged correct.

Constraints

  • num will be between 1,000 and 2,000,000,000, inclusive.
  • counts will contain between 2 and 50 elements, inclusive.
  • Each element of counts will be between 0 and 1,000, inclusive.
Examples
0)
1000
{1,2}
Returns: 0.002998000000000056

There are a total of three clients during this day. Lets call them c1, c2, and c3. There are 4 possible ways for a particular ID to be assigned to more than one person: 1) c1 and c2 get the same ID, while c3 gets a different ID 2) c1 and c3 get the same ID, while c2 gets a different ID 3) c2 and c3 get the same ID, while c1 gets a different ID 4) c1, c2, and c3 all get the same ID. (1), (2), and (3) all have the same probability of 999/1,000,000. (4) has a probability of 1/1,000,000. So, the total probability is (999+999+999+1)/1,000,000 = 0.002998. (Note that the extra digits are due to double imprecision)

1)
1000
{234,543,640}
Returns: 1.0

Here, there are more clients than IDs, so there must be some ID which is assigned to more than one person.

2)
2000000000
{100,150,482,71,349,57,751,673,761,942}
Returns: 0.004688119695273496

With 2 billions IDs, the chance that collision will occur is relatively small.

3)
200000000
{100,150,482,71,349,57,751,673,761,942}
Returns: 0.04590472119127553

This is the same as example 2, except the pool has been reduced by a factor of 10. It seems somewhat counterintuitive that when assigning a total of only 4336 out of 200 million IDs, there is about a 4.6% chance of a collision, but it is true.

4)
2000000000
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
Returns: 0.4647346684700865
7)
4756
{0,1,0,0}
Returns: 0.0

If only one ID gets assigned, the probability of a collision is 0.

Submissions are judged against all 70 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class IDs with a public method double collisionProbability(int num, vector<int> counts) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous