Maximise Function Solution Codechef

Maximise Function Solution February Challenge 2021

You are given a sequence A1,A2,…,ANA1,A2,…,AN. Find the maximum value of the expression |Ax−Ay|+|Ay−Az|+|Az−Ax||Ax−Ay|+|Ay−Az|+|Az−Ax| over all triples of pairwise distinct valid indices (x,y,z)(x,y,z).

Also See: February Long Challenge 2021 Solutions

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output

For each test case, print a single line containing one integer ― the maximum value of |Ax−Ay|+|Ay−Az|+|Az−Ax||Ax−Ay|+|Ay−Az|+|Az−Ax|.

Constraints

  • 1≤T≤51≤T≤5
  • 3≤N≤1053≤N≤105
  • |Ai|≤109|Ai|≤109 for each valid ii

Subtasks

Subtask #1 (30 points): N≤500N≤500

Subtask #2 (70 points): original constraints

Example Input

3
3
2 7 5
3
3 3 3
5
2 2 2 2 5

Example Output

10
0
6

Explanation

Example case 1: The value of the expression is always 1010. For example, let x=1x=1, y=2y=2 and z=3z=3, then it is |2−7|+|7−5|+|5−2|=5+2+3=10|2−7|+|7−5|+|5−2|=5+2+3=10.

Example case 2: Since all values in the sequence are the same, the value of the expression is always 00.

Example case 3: One optimal solution is x=1x=1, y=2y=2 and z=5z=5, which gives |2−2|+|2−5|+|5−2|=0+3+3=6|2−2|+|2−5|+|5−2|=0+3+3=6.

Follow us on telegram for quick update an abundance of free knowledge: Click Here

Solution

Program C:

#include <stdio.h>
int main(void)
{
    long long int sai,sur,qwemax,qwemin;
    scanf("%lld",&sai);
    for(int i=0;i<sai;i++)
    {
        scanf("%lld",&sur);
        long long int gan[sur];
        for(int j=0;j<sur;j++)
        {
            scanf("%lld",&gan[j]);
        }
        qwemax=gan[0];
        qwemin=gan[0];
        for(int j=1;j<sur;j++){
        if(qwemax<gan[j])
        {
            qwemax=gan[j];
        }
        if(qwemin>gan[j])
        {
            qwemin=gan[j];
        }
    }
    printf("%lld\n",2*(qwemax-qwemin));
    }
return 0;
}

Program C++:

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--){
	int n;
	cin >> n;
	
	std::vector<long long> v(n);
	for(int i = 0; i< n; i++)
	    cin >> v[i];
	    
	long long min1 = 1e9, min2 = 1e9, min3 = 1e9;
	long long mx1 = -1e9, mx2 = -1e9, mx3 = -1e9;
	
	min1 = *min_element(v.begin(), v.end());
	mx1 = *max_element(v.begin(), v.end());
	for(int i = 1; i< n-1; i++)
	{
	    mx2 = max(mx2, (abs(mx1-min1) + abs(mx1 - v[i]) + abs(v[i]- min1)));
	}
	
	cout << mx2 << "\n";
	}
	return 0;
}

Program Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0){
		int n=sc.nextInt();
		long a[]=new long[n];
	    for(int i=0;i<n;i++)
	    a[i]=sc.nextLong();
	    Arrays.sort(a);
	    
	    long sum=0;
	    for(int i=0;i<n-1;i++)
	    {
	     sum+= 2*Math.abs(a[i]-a[i+1]);  
	    }
	    System.out.println(sum);
		}
	}
}

Program Python:

for _ in range(int(input())):  # takes the input cases
    n = int(input())
    k = list(map(int, input().split()))
    k.sort()
    x, y, z = k[0] - k[1], k[1] - k[-1], k[-1] - k[0]
    print(abs(x) + abs(y) + abs(z))

Codechef Long Challenges

September Long Challenge 2021 Solution

February Long Challenge 2021

Leave a Comment