PROBLEM LINK:
Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You are given the age of three children in the array A and the amount of money given to each child in the array C, determine whether the distribution is fair or not. A distribution is fair if, for every pair of children, the older child receives more money. If there is any pair of children of the same age, they should receive the same amount of money.
EXPLANATION
We can do what is stated in the problem. Consider every pair (i, j) of children, we can check
- if A_i < A_j, then C_i < C_j should hold.
- if A_i = A_j, then C_i = C_j should hold.
- if A_i > A_j, then C_i > C_j should hold.
If the above condition is not satisfied for any pair of children, the distribution is not fair.
To simplify, we can also sort on basis of age and for each consecutive pair of children (i, i+1), check
- A_i > A_{i+1} is not possible.
- if A_i = A_{i+1}, then C_i = C_{i+1} should hold.
- if A_i < A_{i+1}, then C_i < C_{i+1} should hold.
TIME COMPLEXITY
Time complexity is O(1) per test case.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int a1,a2,a3,c1,c2,c3;
int comp(int a,int b){
if(a<b)return -1;
if(a>b)return 1;
return 0;
}
int main(){
//freopen("00.txt","r",stdin);
//freopen("00o.txt","w",stdout);
T=readIntLn(1,1000);
while(T--){
a1=readIntSp(1,17);
a2=readIntSp(1,17);
a3=readIntSp(1,17);
c1=readIntSp(1,100);
c2=readIntSp(1,100);
c3=readIntLn(1,100);
if(comp(a1,a2) == comp(c1,c2) && comp(a1,a3) == comp(c1,c3) && comp(a2,a3) == comp(c2,c3)){
cout<<"FAIR"<<endl;
} else {
cout<<"NOT FAIR"<<endl;
}
}
assert(getchar()==-1);
}
Tester's Solution
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
int order(int x,int y){
if(x>y){
return 1;
}
if(x<y){
return 0;
}
if(x==y){
return 2;
}
}
int a[5],c[5];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t,t1;
cin>>t;
t1=t;
while(t--){
int i,fl=0,j;
rep(i,3){
cin>>a[i];
}
rep(i,3){
cin>>c[i];
}
rep(i,3){
f(j,i+1,3){
if(order(a[i],a[j])!=order(c[i],c[j])){
fl=1;
break;
}
}
}
if(fl){
cout<<"NOT FAIR"<<endl;
}
else{
cout<<"FAIR"<<endl;
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class EID2{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int[][] a = new int[3][2];
for(int i = 0; i< 3; i++)a[i][0] = ni();
for(int i = 0; i< 3; i++)a[i][1] = ni();
Arrays.sort(a, (int[] i1, int[] i2) -> Integer.compare(i1[0], i2[0]));
boolean fair = true;
for(int i = 1; i< 3; i++){
if(a[i][0] == a[i-1][0])fair &= a[i][1] == a[i-1][1];
else fair &= a[i][1] > a[i-1][1];
}
pn(fair?"FAIR":"NOT FAIR");
}
//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 EID2().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, if you want to. (even if its same ) . Suggestions are welcomed as always had been.