Masab's blog

By Masab, history, 3 months ago, In English

Suppose, I have given N distinct pairs(x, y) of elements. Choose k pairs from these elements every time. Count the chosen ways when number of distinct value is equal to R in the chosen pairs.

Constraints: N = 100 K >= 50 k <= R <= 2K.

Example: Given, N = 6, k = 3, r = 4.

Pairs: a. (1, 2) b. (1, 3) c. (2, 4) d. (2, 5) e. (3, 4) f. (4, 5)

Now if we choose pairs (a, b, e), the distinct values are:- S = {1, 2, 3, 4} Number of Distinct values |S| = 4 and |S| == R. So, this is a valid combination.

If we choose pairs (c, d, e}, the distinct values are:- S = {2, 3, 4, 5} Number of Distinct values |S| = 4 and |S| == R. So, this is a valid combination.

But, if we choose pairs (a, b, f), the distinct values are:- S = {1, 2, 3, 4, 5} Number of Distinct values |S| = 5 and |S| > R. So, this is not a valid combination.

In this example, there is more valid and invalid combinations. I have to count the valid combination for bigger datasets. Is there any combination formula or Dynamic Programming solution for this problem. An algorithm would be very helpful.

Read more »

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