saketag007's blog

By saketag007, history, 4 years ago, In English

I was given 'n' rectangles represented by their diagonals on a 2-d plane. Then i would be asked multiple queries , in which i would be given an integer 'x' and i was asked to find the number of integer coordinates in the intersection regions of exactly 'x' rectangles. Suppose q = 4 , then i have to find the number of integer co-ordinates in the intersection region of exactly 4 rectangles . The rectangles could be in the form of a cluster so there could be more than one group of 4 rectangles , in that case i should return the sum of number of integer coordinates of all that intersections.

Constraints:-

Number of Rectangles — 0<n<10^5

Number of Queries — 0<n<10^5

Any tips would be helpful.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By saketag007, history, 5 years ago, In English

Given two arrays A and B of size n and m respectively. We can choose an element from A and one from B such that C=Ai + Bj . We have to compute all possible ways to from a sum C and also all unique sums.

Constraints:-

0<A,B<=10^5 // Size of array A and B

0<=Ai,Bi<=10^6

Sample I/P:-

2 3 //Size of array A and B

5 6 // Elements of array A

2 2 3 //Elements of array B

Sample O/P:-

7 2

8 3

9 1

Explanation:- 7 can be formed in two ways by A1+B1 , A1+B2 (using 1-based indexing)

8 can be formed in 3 ways by A1+B2 , A2+B1 , A2+B2

9 can be formed in 1 way by A2+B3

Please help me with a solution less than (n*m).

Have a look on my code:- Link here

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it