The problem is: Given an array of 10^5 numbers and 10^5 queries, each query is like "i j" means: find the largest possible value A[y]-A[x] such that i<=x<=y<=j.

The analysis of this problem said it is easy to do with segment tree, but I have no idea, can anyone please explain how? (btw, it also has update operation, otherwise I could do it with offline semgment tree)

Thanks in advance!

Sorry but I do not know if this has a solution:

Given the area of ABKI, CDLJ, ACOM, BDPN and ABDC. Can we find area EFGH?

Thanks!

I came across a problem in stackoverflow. The problem gives you an array and a value 'K'. You can move an element to right at any position, but you can't move it more than K positions left. Find the optimal ordering on which number of inversions is minimum, e.g. array 3,2,1 has 3inversions. For K=1, solution array is: 2,1,3.

I had a greedy algorithm for this problem, but can't prove its correctness (though I'm pretty sure about its correctness):

iterate the array from left to right.
For each position i we consider a subarray from i to i+k. Then we find the minimum valued element on this subarray and insert this element at the beginning of the subarray and right shift the elements between this interval.
Now, go to position i+1 and do the same.

for example:

given array = 5 3 4 7 8 2 1 0 and K = 2

This algorithm gets the solution array as this:

3 4 5 2 1 0 7 8
minimum inversion value = 12

This is just a naive version of algorithm which we can make as fast as O(nlogn).

How would you prove it if this algorithm is right?

Help is greatly appreciated.

Hi,

I was searching for space complexity of c++ set on google, but could not find any specific information. Can anyone here help me on this? what is the worst case and best case space complexity of set?

Thanks!

Hi,

I am a beginner, please help me find the complexity of the following code:

int lim=9;
int vis[200];
void rec(int x) 
{
    if(x==100) return;
    if(vis[x]==1) return;
    vis[x]=1;
    for(int i=x;i<100;i++)
    {
        if(i-x > lim) break;
        rec(i+1);
    }
}
int main()
{
    rec(0);
}

Thanks!

UPD:

I thought that it would be a math problem, but use of memorization array made the complexity simpler, so I want to slightly modify the above code: what would be the complexity if we didn't use vis[200] array?

I analyzed it a bit, and the problem turns out to be: how many ways to sum to 'n' using values not more than 'lim'

Anyone help please! Thanks