FAILED RANGES HackerEarth Question

 Failed ranges

Max. score: 114

You are given two sorted arrays A and B of sizes N and M respectively. C is the following:

• An array of size N∗M such that C[k]=(A[i]+B[j]) for all possible i and j.
• C is a sorted array.

Example

• A = {1,2,3}, B = {1,3,6} then C = {2,3,4,4,5,6,7,8,9}

• 2 is first largest

• 3 is second largest

• 4 is third largest

• 4 is fifth largest

• 5 is sixth largest

Task

You are given two integers X and Y. Determine all the possible pairs of i,j such that A[i]+B[j] is:

• Greater than the  Xth  greatest element of array C 
• Less than the  Yth  greatest element of array C

This means that you have to determine all possible i and j such that Xth greatest<A[i]+B[j]< Yth greatest

Input format

• The first line contains two space-separated integers N and M as described in the problem statement.
• The second line contains N space-separated integers denoting the elements of array A.
• The third line contains M space-separated integers denoting the elements of array B.
• The fourth line contains two space-separated integers X and Y as described in the problem statement.

Output format

Print the output in two lines as follows:

• First line: Print the number of pairs of i and j that satisfy the input that is provided.
• Second line: Print all such pairs as described in the output format in sorted order.

 Constraints

• 1≤N, M≤100000
• 1≤X<Y≤N∗M
• 1≤A[i],B[j]≤10^8
• 1≤Y−X≤100000

SAMPLE INPUT

 

2 4
1 4
2 3 5 7
2 6

SAMPLE OUTPUT

 

3
(1,3) (2,1) (2,2) 

Explanation

For given arrays A and B, all possible combinations of A*B in sorted order (sorted by sum value)

(Sum, A's index, B's index) ->

(3,1,1) (4,1,2) (6,1,3) (6,2,1) (7,2,2) (8,1,4) (9,2,3) (11,2,4) 

Solution for given X and Y will be ->

3 (Number of Pairs)

(1,3) (2,1) (2,2) (All pairs in form (A's index, B's index))

 

Output

3

(1,3) (2,1) (2,2)

 

 

Time Limit:5.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

Marking Scheme:Score is assigned if any testcase passes.

Allowed Languages:Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic