New_Beginning's blog

Number of ways to select numbers
By New_Beginning, history, 7 weeks ago, In English

Suppose I have 4 rows of numbers(The row size is n)

a1, a2 , a3 ,... an

b1, b2 , b3 , ....,bn

c1, c2, c3,... cn

d1, d2, d3,... ,dn

I need to find number of ways to select numbers from each row exactly once such that a < b < c < d.

For example if rows are

2,3,4,5

3,4,5,6,

4,5,6,7,

5,6,7,8

Then one possible way is (2,4,6,8) ; select 2 from first row, 4 from second and so on.

Other than brute force , what could be another way of solving this problem? [Note: brute force cant be used if length of rows is large]

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (2)
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by New_Beginning (previous revision, new revision, compare).

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

  1. sort a(i),b(i),c(i),d(i) increasingly. O(nlogn).

  2. for each i- count the number of j such that a(j)<b(i) (binary search). O(nlogn) or O(n).

  3. for each i- count A[i] = the number of (u,v) where v<=i and a(u)<b(v) (using the prefix sum of results obtained in step 2). O(n)

  4. do similar steps to obtain; for each i;count B[i]= the number of pair (i,j) that i<j and c(i)<d(j). O(nlogn).

  5. for each j, find the largest i such that b(i)<c(j). Put the term B[j]*A[i] in the final result.

Correct me if it is wrong.

→ Reply