Masab's blog

By Masab, history, 3 years 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.

Full text and comments »

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