wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Algorithm
        
(Message started by: kutta on Dec 6^th, 2012, 12:55pm)

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⁹+7), since the answer can be very large.
Constraints

2 <= N <= 100000 (10⁵)
0 <= Ai < 1000000007 (10⁹+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 max-min;
}

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:

int ProductOfRangesUsingRunningInterval(int size, int *arr)
{

deque<int> incDQ;

deque<int> decDQ;

long long int product = 1;

for(int interval = 2; interval<=size; interval++)

{

int min;

int max;

incDQ.clear();

decDQ.clear();

incDQ.push_back(0);

decDQ.push_back(0);

for(int i=1; i<size; i++)

{

while(!incDQ.empty() && arr[i] > arr[incDQ.back()])

{

incDQ.pop_back();

}

incDQ.push_back(i);

if(incDQ.front() <= i-interval)

{

incDQ.pop_front();

}

while(!decDQ.empty() && arr[i] < arr[decDQ.back()])

{

decDQ.pop_back();

}

decDQ.push_back(i);

if(decDQ.front() <= i-interval)

{

decDQ.pop_front();

}

min = arr[decDQ.front()];

max = arr[incDQ.front()];

product = product * (max-min);

product = product % 1000000007;

}

}

return product;
}

Title: Re: Algorithm
Post by birbal on Dec 10^th, 2012, 12:13pm

Finally an optimized and simplified code :)

Code:

int ProductOfRangesSimplified(int size, int *arr)
{
long long int product = 1;
for(int i=0; i<size; i++)
{
int min = arr[i];
int max = arr[i];
for(int j=i+1; j<size; j++)
{
if(arr[j] < min)
min = arr[j];
if(arr[j] > max)
max = arr[j];
product = product * (max-min) % 1000000007;
}
}
return product;
}