c++ - Effective combination algorithm to pass the time limit -

i doing practice programming problem , got stuck pass time limit on problem. there effective algorithm pass time limit?

i have sorted array, think this's still not helping much.

here's pseudocode:

sort boxa sort boxb in boxa:       j in boxb:           if i+j < value:               break           else if i+j > value:               count+=1 print count set count = 0 

the question asking output how many combination of boxa + boxb greater or equal value.

input:

5 3 1200                #number of boxa | number of boxb | value 100 110 160 750 1030    #number of boxa 400 500 500             #number of boxb 

output:

5 

explanation: there 5 ways combine boxa , boxb value >= value

1. 750 + 500 2. 750 + 500 3. 1030 + 400 4. 1030 + 500 5. 1030 + 500 

boxa , boxb can have 500000 items in list. think kind of test case make time limit on algorithm.

can show effective algorithm pass time limit problem? thank you.

for each boxes a items in a, number of boxes in b have number of items plus a, larger or equal value d equal number of boxes has number of items larger (d - a).

so, first, sort array b, each box value x in a, use binary search find starting index in b, item in boxes larger or equal d - x. add in final result (n - index) n number of item in b.

time complexity o(m log n)

example:

we have 2 array {1,5,9,2,4,5} , b {1,3,3,4,5,6,7,8};

we want find 2 boxes has sum larger 7 example.

so, each element in a

1 -> use binary search find index of smallest element greater or equal to(7 - 1) in b, @ index 5, add result (8 - 5) (with 8 number of element in b).

5 -> need find (7 - 5) in b -> have index 1 after search -> add (8 - 2) result.

...