wu :: forums « wu :: forums - Algorithm » Welcome, Guest. Please Login or Register. Sep 8th, 2024, 5:06pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Eigenray, Grimbal, william wu, SMQ, ThudnBlunder, Icarus, towr)    Algorithm « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Algorithm  (Read 4648 times)
kutta
Newbie

Gender:
Posts: 3
 Algorithm   « on: Dec 6th, 2012, 12:55pm » Quote Modify

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]);
}

}
 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 incDQ;   deque 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 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 max) max = arr[j]; product = product * (max-min) % 1000000007; } } return product; }
 IP Logged

The only thing we have to fear is fear itself!
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »