Instructions: The precise input-output format will be speci ed by Programming TAs for submission on Hackerearth.
Problem 1. Counting Signi cant Inversions. Given an array A = [a1; a2; : : : ; an] of n integers, we say that a pair (i; j) with i < j is a signi cant inversion if ai 2aj .
Problem 2. Sum of Sets. Let A and B be two sets that each have n integers in the range from 0 to 10n. We wish to compute the Cartesian sum of A and B de ned as
C = fx + y : x 2 A and y 2 Bg :
C has numbers in the range 0 to 20n. We wish to nd the elements of C and the number of times each element of C is realized as the sum of elements of A and B. Use FFT technique to solve this problem e ciently.
1
