Algorithm

 Problem Statement for Collision

problem link- https://community.topcoder.com/stat?c=problem_statement&pm=1771&rd=4570

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 which must be able to assign IDs to clients. 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 to keep the system distributed than it is to ensure 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.



Now, there are two ways that you can do this. The first is to have each of the components assign a random ID each time from the list of available IDs obtained at the beginning of each day. In other words, have components without any memory of which IDs they have assigned during the day, which may assign the same ID more than once during the day. The second way to assign the IDs is to have the components each remember which IDs they have assigned, so that no component assigns the same ID more than once. This way, two different components may assign the same ID, but no one component will assign an ID more than once. Now, it turns out that the first system is slightly cheaper to implement, but it will clearly result in more collisions (a collision occurs when the same ID is assigned to multiple clients). So, to help decide which system to implement, you want to run a simulation.



Your task is to simulate both systems and figure out the probability that some ID is assigned to more than one client in both of the systems, and then return the difference in the two probabilities. You will be given an int, ids, which represents the number of IDs in the pool of possible IDs that each component may assign at the beginning of some day (all components draw IDs from the same pool). You will also be given a int[], assignments, each of whose elements represents the number of IDs that some component assigns during the day. You are to return a double representing the difference in the probabilities between the two systems.
 

Definition
    
Class: Collision
Method: probability
Parameters: int[], int
Returns: double
Method signature: double probability(int[] assignments, int ids)
(be sure your method is public)
    
 
 

Notes
- Your result need not be precisely the same as the result shown in the examples. As long as your result is within 1e-9 of the result in the example, your submission will be evaluated as correct.
- If more IDs are assigned than there are total IDs, return 0, since there must be a collision in this case.
 

Constraints
- ids will be between 1000 and 2147483647, inclusive.
- assignments will contain between 2 and 50 elements, inclusive.
- Each element of assignments will be between 0 and 10,000, inclusive.
 

Examples
0)  
     
{20,20}
 
1000
 
Returns: 0.2113618990410422
The probability that there will be no collision if the components have memory is about 0.45362802928706036.

The probability that there will be no collision if the components do not have memory is about 0.6649899283281026.
1)  
     
{123,456}
 
123456
 
Returns: 0.3769052883184334
 
2)  
     
{10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}
 
2147483647
 
Returns: 0.0069090268185510555
 
3)  
     
{1005,1005}
 
1000
 
Returns: 0.0

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

class Collision {
	double calc1(int sum, int ids) {
		if(sum > ids)
			return 0;
		
		double p = 1;
		for(int i = 1; i < sum; ++i)
			p *= 1.0 * (ids - i) / ids;
		return p;
	}
	
	double calc2(vector<int> assignments, int ids) {
		if(assignments[0] > ids)
			return 0;
		int sum = assignments[0];
		double p = 1;
		for(int i = 1; i < assignments.size(); ++i) {
			if(assignments[i] > ids)
				return 0;
			
			for(int j = 0; j < assignments[i]; ++j)
				p *= 1.0 * (ids - sum - j) / (ids - j);
			
			sum += assignments[i];
		}
		return p;
	}
	
public:
	double probability(vector<int> assignments, int ids) {
		int sum = 0;
		for(int i = 0; i < assignments.size(); ++i)
			sum += assignments[i];
		
		return calc2(assignments, ids) - calc1(sum, ids);
	}
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
{20,20}

Output

x
–
+
cmd
1000
Advertisements

Demonstration

TopCoder Solution SRM153-D1-450 C,C++, Java, Js and Python ,153-D1-450,TopCoder Solution