[Solved] Symmetric Swaps January Long 2023 CodeChef

Symmetric Swaps: Chef has two arrays A and B of the same size N.

In one operation, Chef can:

• Choose an index i(1≤i≤N) and swap the elements Ai​ and Bi​.

Chef came up with a task to find the minimum possible value of (Amax​−Amin​) after performing the swap operation any (possibly zero) number of times.

Since Chef is busy, can you help him solve this task?

Note that Amax​ and Amin​ denote the maximum and minimum elements of the array A respectively.

Problem: https://www.codechef.com/JAN231C/problems/SYMARRSWAP

Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains one integer N — the number of elements in each array.
  • The second line consists of N space-separated integers A1​,A2​,…,AN​ denoting the elements of the array A.
  • The third line consists of N space-separated integers B1​,B2​,…,BN​ denoting the elements of the array B.

Output Format

For each test case, output on a new line, the minimum possible value of (Amax​−Amin​) in the array �A after doing swap operation any number of times.

Constraints

• 1≤T≤10^5
• 1≤N≤2⋅10^5
• ≤Ai​,Bi​≤10^9
• The sum of N over all test cases won’t exceed 2⋅10^5.

Sample 1:

Input

3
2
1 2
2 1
3
1 5 3
2 3 1
4
4 2 5 1
5 3 4 1

Output:

0
1
3

Explanation:

Test case 11: Chef can make the following operations:

• Operation 11: Choose i=1 and swap A1​ with B1​.

By doing the above operations, array A becomes [2,2]. Here (Amax​−Amin​)=0. It can be shown that this is the minimum value possible.

Test case 22: Chef can make the following operations:

• Operation 11: Choose i=1 and swap A1​ with B1​.
• Operation 22: Choose i=2 and swap A2​ with B2​.

By doing the above operations, array A becomes [2,3,3]. Here (Amax​−Amin​)=1. It can be shown that this is the minimum value possible.

Test case 33: Chef can make the following operations:

• Operation 11: Choose i=2 and swap A2​ with B2​.
• Operation 22: Choose i=3 and swap A3​ with B3​.

By doing the above operations, array A becomes [4,3,4,1]. Here (Amax​−Amin​)=3. It can be shown that this is the minimum value possible.

Solution

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

class Codechef {
    public static void main(String[] args)
     {
     //code
     Scanner sc = new Scanner(System.in);
     int t = sc.nextInt();
     while(t-->0){
         int n = sc.nextInt();
         int arr[] = new int[n];
         int brr[] = new int[n];
         for(int i=0;i<n;i++)
            arr[i] = sc.nextInt();
         for(int i=0;i<n;i++)
            brr[i] = sc.nextInt();
         for(int i=0;i<n;i++){
             if(arr[i] < brr[i]){
                 int temp = arr[i];
                 arr[i] = brr[i];
                 brr[i] = temp;
             }
         }
         int merge[][] = new int[n][2];
         for(int i=0;i<n;i++){
             merge[i][0] = arr[i];
             merge[i][1] = brr[i];
         }
         Arrays.sort(merge,(a,b)->a[0]-b[0]);
         int maximum = merge[n-1][0];
         int minimum = merge[0][0];
         int result = maximum - minimum;
         int first_Min[] = new int[n];
         int first_Max[] = new int[n];
         int last_Min[] = new int[n];
         int last_Max[] = new int[n];
         first_Min[0] = merge[0][0];
         last_Min[n-1] = merge[n-1][1];
         first_Max[0] = merge[0][0];
         last_Max[n-1] = merge[n-1][1];
         for(int i=1;i<n;i++){
             first_Min[i] = Math.min(first_Min[i-1],merge[i][0]);
             first_Max[i] = Math.max(first_Max[i-1],merge[i][0]);
         }
         for(int i=n-2;i>=0;i--){
             last_Min[i] = Math.min(last_Min[i+1],merge[i][1]);
             last_Max[i] = Math.max(last_Max[i+1],merge[i][1]);
         }
         for(int i=n-1;i>=0;i--){
             int temp = merge[i][0];
             merge[i][0] = merge[i][1];
             // sauravhathi
             merge[i][1] = temp;
             if(i == 0){
                 maximum = last_Max[0];
                 minimum = last_Min[0];
                }
                else{
                    maximum = Math.max(first_Max[i-1],last_Max[i]);
                    minimum = Math.min(first_Min[i-1],last_Min[i]);
                }
                result = Math.min(result,maximum-minimum);
            }
            System.out.println(result);
        }
    }
}

#include <iostream>
using namespace std;
#define ll long long
#include<algorithm>
#include<vector>

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    int arr[n];
	    int brr[n];
	    
	    for(int i=0;i<n;i++)
	        cin>>arr[i];
	    for(int i=0;i<n;i++)
	        cin>>brr[i];
	    
	    for(int i=0;i<n;i++){
	        if(arr[i] < brr[i])
	            swap(arr[i],brr[i]);
	    }

	    vector<vector<int>> merge( n , vector<int> (2)); 
	     
	     for(int i=0 ; i < n ; i++){
	         merge[i][0]=arr[i];
	         merge[i][1]=brr[i];
	     }

        sort(merge.begin(),merge.end());

	     int maximum = merge[n-1][0];
	     int minimum = merge[0][0];
	     
	     int result = maximum - minimum;

	   int first_Min[n] , first_Max[n] ,last_Min[n] , last_Max[n];
	   
	   first_Min[0] = merge[0][0];
	   last_Min[n-1] = merge[n-1][1];
	   
	   first_Max[0] = merge[0][0];
	   last_Max[n-1] = merge[n-1][1]; 
	   
	   for(int i = 1 ; i < n ; i++){
	       first_Min[i] = min(first_Min[i-1] , merge[i][0]);
	       first_Max[i] = max(first_Max[i-1] , merge[i][0]);
	   }
 	     
	  for(int i = n-2 ; i >= 0 ; i--){
	      last_Min[i] = min(last_Min[i+1] , merge[i][1]);
	      last_Max[i] = max(last_Max[i+1] , merge[i][1]);
	  } 
	  
	  for(int i = n-1 ; i >=0 ; i--){
	      swap(merge[i][0] , merge[i][1]);
	      	  if( i == 0 ){
	            maximum=last_Max[0];
	            minimum=last_Min[0];
	         }
	        else{
	            maximum=max(first_Max[i-1],last_Max[i]);
	            minimum=min(first_Min[i-1],last_Min[i]);
	         }
	     result = min(result,maximum-minimum);
	  }
	  cout << result<<endl;
	}
	return 0;
}

t = int(input())
while t:
    n = int(input())
    arr = list(map(int,input().split()))
    brr = list(map(int,input().split()))
    for i in range(n):
        if arr[i] < brr[i]:
            arr[i],brr[i] = brr[i],arr[i]
    merge = []
    for i in range(n):
        merge.append([arr[i],brr[i]])
    merge.sort()
    maximum = merge[n-1][0]
    minimum = merge[0][0]
    result = maximum - minimum
    first_Min = [0]*n
    first_Max = [0]*n
    last_Min = [0]*n
    last_Max = [0]*n
    first_Min[0] = merge[0][0]
    last_Min[n-1] = merge[n-1][1]
    first_Max[0] = merge[0][0]
    last_Max[n-1] = merge[n-1][1]
    for i in range(1,n):
        first_Min[i] = min(first_Min[i-1],merge[i][0])
        first_Max[i] = max(first_Max[i-1],merge[i][0])
    for i in range(n-2,-1,-1):
        last_Min[i] = min(last_Min[i+1],merge[i][1])
        last_Max[i] = max(last_Max[i+1],merge[i][1])
    for i in range(n-1,-1,-1):
        # sauravhathi
        merge[i][0],merge[i][1] = merge[i][1],merge[i][0]
        if i == 0:
            maximum = last_Max[0]
            minimum = last_Min[0]
        else:
            maximum = max(first_Max[i-1],last_Max[i])
            minimum = min(first_Min[i-1],last_Min[i])
        result = min(result,maximum-minimum)
    print(result)
    t -= 1

Happy Learning – If you require any further information, feel free to contact me.