MDL - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia

Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk

PREREQUISITES:

Observation, Simulation

PROBLEM:

Given an array A consisting of N distinct integers with N \geq 3, you repeat the following process till the number of elements in array is less than 3.

  • Take the first three elements and find their median. Remove it from the array.

QUICK EXPLANATION

  • For every operation, the median element is the element which is neither maximum nor minimum. So, after applying operation, neither the minimum nor the maximum element is affected.
  • Generalizing above, we can see that the final array shall contain only the minimum and the maximum element of the initial array, in their respective order.

EXPLANATION

Let us see how the operation work.

The operation takes three elements and finds the median and delete it. Since all elements are distinct and we are considering three elements, it is easy to see that the median element is never the minimum or the maximum of the three elements. So, after the operation is applied on the triplet, it is the same as removing all three elements from the array and adding back minimum and maximum of three elements, in their order in initial array are added back.

If we keep repeating the above process, in the end, we shall be left only with the minimum and the maximum element in array. Since the order of elements never changes, we need to print the minimum and the maximum element in their relative order in the initial array.

Implementation
This solution can be implemented in two ways.

  • Just by finding the index of minimum and the maximum element in the array and printing the answer.
  • Simulating the process by noticing that the order of choosing triplets does not matter and using stack and taking the last three elements and adding back minimum and the maximum of triplet for each operation.

TIME COMPLEXITY

Time complexity is O(N) per test case.

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 119;
int q, n, A[N];
int main()
{
	scanf("%d", &q);
	for (; q; q --)
	{
	    scanf("%d", &n);
	    for (int i = 0; i < n; i ++)
	        scanf("%d", &A[i]);
	    for (int i = 0; i < n; i ++)
	        if (A[i] == * min_element(A, A + n) || A[i] == * max_element(A, A + n))
	            printf("%d ", A[i]);
	    printf("\n");
	}
	return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>

using namespace :: std;

const ll maxn=200;
const ll inf=1e9;

ll a[maxn];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll q;
	cin>>q;
	while(q --){
	    ll n;
	    cin>>n;
	    ll mn=inf,mx=0,s,t;
	    for(ll i=0;i<n;i++){
	        cin>>a[i];
	        if(mn>a[i]){
	            mn=a[i];
	            s=i;
	        }
	        if(mx<a[i]){
	            mx=a[i];
	            t=i;
	        }
	    }
	    if(s<t){
	        cout<<mn<<" "<<mx<<endl;
	    }
	    else{
	        cout<<mx<<" "<<mn<<endl;
	    }
	}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class MDL{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni();
	    int[] a=  new int[n];
	    int min = -1, max = -1; 
	    for(int i = 0; i< n; i++){
	        a[i] = ni();
	        if(min == -1 || a[min] > a[i])min = i;
	        if(max == -1 || a[max] < a[i])max = i;
	    }
	    if(min < max)pn(a[min]+" "+a[max]);
	    else pn(a[max]+" "+a[min]);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new MDL().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

why this approach did’nt worked

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{int n;
cin>>n;
int a[n];
for(int x=0;x<n;x++)
{
cin>>a[x];
}
sort(a,a+n);
int b[2];
b[0]=a[0];
b[1]=a[n-1];
for(int i=0;i<2;i++)
cout<<b[i]<<" ";
cout<<endl;
}
return 0;
}

max element could be on left of min element ,in that case your method will output “min max”,
but it should be “max min”

1 Like

Because you are sorting the array which will change the relative position of the numbers.
So you’re just outputting in the wrong order.

1 Like

Thank you!!I understood.

What this is showing Wrong Answer

nice setter solution

#include <stdio.h>
#include<stdlib.h>

int main(void) {
// your code goes here
int T;
scanf("%d",&T);
while(T–)
{
int N,p,i,j=0,k=0,min,max;
scanf("%d",&N);
p=(int
)calloc(N,sizeof(int));
for(i=0;i<N;i++)
scanf("%d",&p[i]);
min=p[0];max=p[0];
for(i=0;i<N;i++)
{
if(p[i]<min)
{ min=p[i];j=i;}
}
for(i=0;i<N;i++)
{
if(p[i]>max)
{
max=p[i];k=i;
}
}
if(j<k)
printf("%d\t%d\n",p[j],p[k]);
else
printf("%d\t%d\n",p[k],p[j]);

}
return 0;

}

//Can Anyone tell where I am wrong because i am getting correct output. Any Codechef member can help me??//
#include
#include<string.h>
#include
#include<math.h>
using namespace std;
int main()
{
int a , b , count1 = 0 , count2 = 0;
int first = INT_MIN;
int last = INT_MAX;
cin>>a;
while(a–)
{
cin>>b;
int arr[b];
for(int i=0;i<b;i++)
{
cin>>arr[i];
}
for(int i=0;i<b;i++)
{
if(first < arr[i]){
first = arr[i];
count1++;
}
if(last > arr[i]){
last = arr[i];
count2++;
}
}
if(count1>count2)
{
cout<<last<<" “<<first<<”\n";
}
else
{
cout<<first<<" “<<last<<”\n";
}
// cout<<count1<<" "<<count2;
}
}
//Can Anyone tell where I am wrong because i am getting correct output.//

How about this as the input:

2
5
5 5 5 5 5
3
1 3 1

Here’s the output it produces:

5 5
5 1

Clearly, it answers the first test case correctly, but it goes wrong as the result of further test cases are affected by the previous ones according to your program, which shouldn’t be the case. :slightly_smiling_face:

#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–)
{
int n,i;
cin>>n;
int A[n];
for(i=0;i<n;i++)
{
cin>>A[i];
}
for(i=0;i<n;i++)
{
if(A[i]== *min_element(A,A+n) || A[i]== *max_element(A,A+n))
{
cout<<A[i];
}
}
cout<<endl;
}
return 0;
}

whats wrong

why this dint work
t=int(input())
for j in range(0,t):
n = int(input())
a = list(map(int,input().split()))
for i in range(0,n-2):
b=a[0:3]
b.sort()
a.remove(b[1])
print(a)

can anyone help me with this code …its perfectly working on codechef compiler
#include
#include<conio.h>
using namespace std;
int main()

{
int t, n, max, min, maxI, minI, arr[1000];
cin >> t;
for (int i = 1; i <= t; i++)
{
cin >> n;
minI = 0, maxI = 0;

for (int p = 0; p < n; p++)
{
	cin >> arr[p];
}
if (n == 0)
{
	cout << arr[0] << arr[0];
}max = arr[0];
min = arr[0];
for (int z = 0; z < n; z++)
{
	if (max < arr[z])
	{
		max = arr[z];
		maxI = z;
	}
}
for (int s = 0; s < n; s++)
{
	if (min >> arr[s])
	{
		min = arr[s];
		minI = s;
	}
}
if (maxI > minI)
	cout << min << " " << max << endl;
if (maxI <= minI)
	cout << max << " " << min << endl;

}
}

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n,max,min,max_pos=0,min_pos=0;
cin>>n;
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];

    max = arr[0];
    min = arr[0];
    for(int i=0;i<n;i++)
    {
        if(max<arr[i]) 
        {
            max = arr[i];
            max_pos = i;
        }
        if(min>arr[i]) 
        {
            min = arr[i];
            min_pos = i;
        }
    }
    
    if(max_pos<min_pos) cout<<arr[max_pos]<<" "<<arr[min_pos]<<endl;
    else cout<<arr[min_pos]<<" "<<arr[max_pos]<<endl;
    
}
return 0;

}
I am getting the correct output if I am using custom input but getting SIGTSTP as runtime error. What should I change?

check what value you have given to MIN in the beginning . Since, the value of A of i will never be less than 0 so your MIN value will always be 0.

Hi , How can I change this code to generate output in same order

/* package codechef; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();

		while ( t > 0 )
		{
			int n = sc.nextInt();
			ArrayList<Integer> arr = new ArrayList<Integer>(n);

			for (int i = 0; i < n; i++)
            	arr.add(sc.nextInt());

            Collections.sort(arr);

            while(arr.size()>=3)
            {
            	arr.remove(arr.size()/2);
            	
            }
            
            for (int i = 0; i < arr.size(); i++)
            	    System.out.print(arr.get(i) + " ");
            System.out.println();
            
            t = t - 1;
		}
	}
}