PROBLEM LINK:
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.