

Title: Algorithm Post by kutta on Dec 6^{th}, 2012, 12:55pm Given an array A1, A2, ..., AN of N integers. The task is to find the product of ranges of the segments [i, j] over 1 <= i < j <= N, where the range of the segment [i, j] means max(Ai, Ai+1, ..., Aj)  min(Ai, Ai+1, ..., Aj). N<=10^9 and Ai<=10^9 

Title: Re: Algorithm Post by Noke Lieu on Dec 6^{th}, 2012, 7:58pm That smells suspiciously like homework to me... I'll have to digest the question first too! 

Title: Re: Algorithm Post by Grimbal on Dec 7^{th}, 2012, 8:34am If I understand the question, it seems to me that just storing the result is a challenge. If N is 1E9, there are some 5.0E17 ranges. Each range gives a term with up to 9 digits. In the worst case the product would be of the close to 4.5E18 digits. 

Title: Re: Algorithm Post by kutta on Dec 7^{th}, 2012, 9:47am Input The first line contains a single integer N, then N integers A1, A2, ..., AN follow on the second line. Output Output a single line containing the required product modulo 1000000007 (10^{9}+7), since the answer can be very large. Constraints 2 <= N <= 100000 (10^{5}) 0 <= Ai < 1000000007 (10^{9}+7) All test cases, except Example, are created by the method described in Test Case Generation. Example Input 1: 3 1 2 4 Output 1: 6 Input 2: 5 5 5 5 5 5 Output 2: 0 Explanation In Input 1, we should consider 3 segments [i, j] = [1, 2], [2, 3], [1, 3]. The range of segment [1, 2] is max(1,2)  min(1,2) = 1. The range of segment [2, 3] is max(2,4)  min(2,4) = 2. The range of segment [1, 3] is max(1,2,4)  min(1,2,4) = 3. Therefore, we obtain the answer 1 * 2 * 3 = 6, and you should output 6 mod 1000000007 = 6. In Input 2, we should consider 10 segments, but all ranges of such segments are 0. And, of course, the answer is 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 = 0. Note that Example is created by manually, so these arrays are not random arrays. It is quite unlikely that the official test cases contain an array with equal elements such as Input 2. 

Title: Re: Algorithm Post by birbal on Dec 10^{th}, 2012, 11:00am #include<stdio.h> int GetMaxMinDifference(int size, int *arr,int ind1, int ind2) { int max = arr[ind1]; int min = arr[ind1]; for(int i=ind1+1; i<= ind2; i++) { if(arr[i] < min) min = arr[i]; if(arr[i] > max) max = arr[i]; } return maxmin; } int ProductOfRanges(int size, int *arr) { long long int product = 1; for(int i=0; i<size; i++) { for(int j=i+1; j<size; j++) { product = product * GetMaxMinDifference(size,arr,i,j); product = product%1000000007 ; } } return product; } int main() { int n; int *arr; scanf("%d",&n); arr = new int [n]; for(int i=0; i<n; i++) { scanf("%d",&arr[i]); } printf("Answer is :%d\n", ProductOfRanges(n, arr)); } 

Title: Re: Algorithm Post by kutta on Dec 10^{th}, 2012, 11:08am Thanks you are excellent :) 

Title: Re: Algorithm Post by birbal on Dec 10^{th}, 2012, 12:07pm This is optimized code, runs in O(n^2) time. Code:


Title: Re: Algorithm Post by birbal on Dec 10^{th}, 2012, 12:13pm Finally an optimized and simplified code :) Code:


Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 