Page Contents
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
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
February Long Challenge 2021
- Frog Sort Solution Codechef
- Chef and Meetings Solution Codechef
- Maximise Function Solution Codechef
- Highest Divisor Solution Codechef
- Cut the Cake Challenge Solution Codechef
- Dream and the Multiverse Solution Codechef
- Cell Shell Solution Codechef
- Multiple Games Solution Codechef
- Another Tree with Number Theory Solution Codechef
- XOR Sums Solution Codechef
- Prime Game Solution CodeChef
- Team Name Solution Codechef
- Bash Matrix Solution CodeChef