Author |
Topic: Algorithm (Read 4648 times) |
|
kutta
Newbie
Gender: 
Posts: 3
|
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
|
|
 IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
 |
Re: Algorithm
« Reply #1 on: Dec 6th, 2012, 7:58pm » |
 Quote  Modify
|
That smells suspiciously like homework to me...
I'll have to digest the question first too!
|
|
IP Logged |
a shade of wit and the art of farce.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Algorithm
« Reply #2 on: Dec 7th, 2012, 8:34am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
kutta
Newbie
Gender:
Posts: 3
|
|
Re: Algorithm
« Reply #3 on: Dec 7th, 2012, 9:47am » |
Quote Modify
|
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 (109+7), since the answer can be very large.
Constraints
2 <= N <= 100000 (105)
0 <= Ai < 1000000007 (109+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.
|
| « Last Edit: Dec 10th, 2012, 1:49am by Grimbal » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Algorithm
« Reply #4 on: Dec 10th, 2012, 11:00am » |
Quote Modify
|
#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));
}
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
kutta
Newbie
Gender:
Posts: 3
|
|
Re: Algorithm
« Reply #5 on: Dec 10th, 2012, 11:08am » |
Quote Modify
|
Thanks you are excellent 
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Algorithm
« Reply #6 on: Dec 10th, 2012, 12:07pm » |
Quote Modify
|
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;
}
|
|
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Algorithm
« Reply #7 on: Dec 10th, 2012, 12:13pm » |
Quote Modify
|
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;
}
|
|
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print