hint for this question(minimize the sum)

[closed account 1TD80pDG]

https://www.hackerrank.com/contests/101hack55/challenges/minimize-the-sum/copy-from/1308625213

hello, anyone can help me. How to solve this question?

[tpb]

How many times do you people need to be told that we can't just magically access those pages! We need to sign up for babyrank and then register for the stupid "contest" and ... it's a hassle.

Post the stupid question here.

[zyan1zyan]

HERE IS TH FULL QUESTION-:
Kokka and Satara are playing a game. In this game, Kokka gives Satara a number n and n pairs of integers, the ith of which is (li,ri). Kokka wants Satara to create an array a with length n such that for each i (1 <= i <= n), li<=ai<=ri. He also wants Satara to minimize the sum
summation of |a(i) - a(i-1)| from i =2 to n.
Since Satara is very busy helping Taang save the world, she wants your help to find the minimum sum among all arrays that satisfy Kokka's condition.
Complete the function minimumSum which takes in two integer arrays l and r and returns the minimum sum among all arrays that satisfy Kokka's condition.

Input Format:

The first line contains a single integer n.

The second line contains n space-separated integers l1,l2,...ln.

The third line contains space-separated integers r1,r2,...rn.

Constraints:
2 <= n < pow(10,5)
1 <= li <= ri <= pow(10,9)

Output Format:

Print a single integer denoting the minimum sum.

Sample Input 0

5
1 2 6 1 2
3 5 8 2 3
Sample Output 0

7
Explanation 0

Let our final array be [a1,a2,a3,a4,a5].

We can see from the input that:

1<=a1<=3
2<=a1<=5
6<=a1<=8
1<=a1<=2
2<=a1<=3

To minimize the |a1-a2| + |a2-a3| + |a3-a4| + |a4-a5| sum, we can choose our array as [3,3,6,2,2]. Then |3-3|+|6-3|+|2-6|+|2-2| equals to 7.

[zyan1zyan]

@tpb
now please solve this problem.

[closed account 1TD80pDG]

sorry for that.next time will not happen.

sample input test case:
5
1 2 6 1 2
3 5 8 2 3

Let our final array be {a1,a2,a3,a4,a5};

1<=a1<=3;
2<=a2<=5;
6<=a3<=8;
1<=a4<=2;
2<=a5<=3;

to minimize the sum, |a1-a2|+|a2-a3|+|a3-a4|+|a4-a5|
we can choose our array as {3,3,6,2,2} then output is 7. |3-3|+|3-6|+|6-2|+|2-2| ==7.

[sc7]

I tried to force the ans, only got 2.81 XD

[zyan1zyan]

@sc7 what you have done.

[closed account 1TD80pDG]

@tpb ??

[sc7]

@zyan1zyan I know this approach is wrong , but I tried to check the adjancent bounds one by one, whenever numbers overlap, it will be zero, so just increase count, but the main thing is in the beginning, when we check for overlap, there can be many options, since it depends on the next to next element , that which number we have to choose, other than this, its pretty straight forward , that if lower bound a range is greater than upper bound of adjacent, we need to add lower bound(of that range) - upper bound(of adjacent) and if lower bound of adjacent is greater than upper bound of the range then we need to add lower bound(of adjacent)- upper bound(of that range)[These are the cases with no overlapping]. but this approach fails as we can see by my score :P

I will try something else, and if something makes sense, i'll let you guys know :)

[closed account 1TD80pDG]

@sc7 i try your approach but its gives 0. can you debug my code

long minimumSum(vector<int> l, vector<int> r) {
    
    // Return the minimum sum among all arrays that satisfy the condition.
    long sum=0;
    int arr[l.size()];
   
    
   for(int i=0; i<l.size()-1; i++)
   {
       int b1=min(l[i],r[i]);
       int a1=max(l[i],r[i]);
       int a2=max(l[i+1],r[i+1]);
       int b2=min(l[i+1],r[i+1]);
       
       if(b1>a2)
           arr[i]=abs(b1-a2);
       else if(b2>a1)
           arr[i]=abs(a1-b2);
           
        arr[l.size()-1]=arr[l.size()-2];   
       
   }
    for(int i=0; i<l.size()-1; i++)
    {
        sum+=abs(arr[i]-arr[i+1]);
    }
    
    
    
    return sum;
    
}

[zyan1zyan]

@sc7
can you please share you code.

[sc7]

@zyan1zyan and @ipg2016069 sorry couldn't reply, was away from my laptop, left the contest in between. I tried using greedy to get the answer, it only fetched me 10 points out of 30, maybe @tpg could help point out the mistakes..

    // Here a is the vector of numbers that are lower bounds and b are vector of numbers that are upper bounds
    vector<LL> res; //vector to store the points
	LL sum=0;   //sum
	int cnt=0;  //cnt till n-1
	LL point=b[0];  //points to the number we are at
    res.push_back(point);
	
	while(cnt<n-1)
	{
		if(point>=b[cnt+1] && a[cnt]<=a[cnt+1])  //case with overlaps
		{
			point=b[cnt+1]; 
            res.push_back(point);
	
			cnt++;
		}
        //cases without overlaps
        
		else if(point<a[cnt+1]) 
		{
			point=a[cnt+1];
            res.push_back(point);
	
			cnt++;
		}
		else if(point>b[cnt+1])
		{

			point=b[cnt+1];
            res.push_back(point);
	
			cnt++;
		}
		else cnt++;

	}
    for(int i=0;i<res.size()-1;i++)
    {
        sum+=abs(res[i+1]-res[i]);
    }
	cout<<sum<<"\n";