# EID2 - Editorial

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

Cakewalk

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 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){
}
long long readIntLn(long long l,long long 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);
while(T--){
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 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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

String nextLine() throws Exception{
String str = "";
try{
}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.

4 Likes

When i am running below code in jupyter notebook, i am getting right answer. But on submitting it is showing wrong answer. Can anyone tell me whats wrong in this code?

T = int(input())
f = []
for i in range(T):
num = [int(x) for x in input().split()]
a = []
b = []
a.append(num[0])
a.append(num[1])
a.append(num[2])
b.append(num[3])
b.append(num[4])
b.append(num[5])

a = list(zip(a,b))
a = sorted(a)
if (a[0][0] == a[1][0] and a[0][1] == a[1][1]) and (a[1][0] == a[2][0] and a[1][1] == a[2][1]):
f.append("FAIR")
if (a[0][0] == a[1][0] and a[0][1] == a[1][1]) and (a[1][0] < a[2][0] and a[1][1] < a[2][1]):
f.append("FAIR")
if (a[0][0] < a[1][0] and a[0][1] < a[1][1]) and (a[1][0] == a[2][0] and a[1][1] == a[2][1]):
f.append("FAIR")
if (a[0][0] < a[1][0] and a[0][1] < a[1][1]) and (a[1][0] < a[2][0] and a[1][1] < a[2][1]):
f.append("FAIR")
else :
f.append("NOT FAIR")

for i in range(T):
print(f[i])

2 Likes

my solution understandable for beginners

#include <bits/stdc++.h>
using namespace std;
int age[3];
int cost[3];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t ;
cin >> t;
while(t--){
bool f = 1;
for(int i = 0; i < 3 ;++i) cin >> age[i];
for(int i = 0; i < 3 ;++i) cin >> cost[i];

for(int i = 0; i < 3 ;++i)
for(int j = 0; j < 3 ;++j){
if(i!=j){
if(age[i] < age[j]){
if(cost[i] >= cost[j]) {f = 0; break;}
}else if(age[i] == age[j]){
if(cost[i] != cost[j] ) {f = 0; break;}
}else{
if(cost[i] <= cost[j]) {f = 0; break;}
}
}
}
if(f) cout << "FAIR\n"; else cout << "NOT FAIR\n";
}

}
6 Likes

Sorting isnâ€™t required for this problem. You can simply check for the three pairs of numbers the conditions:

• 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.

My solution, implemented in C++, is here:

#include<bits/stdc++.h>

#define EXECUTE_FASTER ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl '\n'

using namespace std;

int returnDecision(int a, int b, int c, int d)
{
int flag = 0;
if (a > b && c > d)
flag = 1;
if (a == b && c == d)
flag = 1;
if (a < b && c < d)
flag = 1;
return flag;
}

int main()
{
EXECUTE_FASTER;
int t;
cin>>t;
while (t--)
{
int a1, a2, a3, c1, c2, c3;
cin>>a1>>a2>>a3>>c1>>c2>>c3;
int a = returnDecision(a1, a2, c1, c2);
int b = returnDecision(a2, a3, c2, c3);
int c = returnDecision(a1, a3, c1, c3);
if (a && b && c)
cout<<"FAIR"<<endl;
else
cout<<"NOT FAIR"<<endl;
}
return 0;
}
2 Likes

Why is this code giving wrong answer??

#include
#include<math.h>
using namespace std;

/* run this program using the console pauser or add your own getch, system(â€śpauseâ€ť) or input loop */

int main()
{
long long int n ,l,r,k,t,mi=0;float s=0;
cin >> t;
for(long long int z=1;z<=t;z++)
{

long long int a[3],b[3];
for(long long int i=0;i<6;i++)
{
if(i<3)
cin>> a[i];
else
cin>>b[i-3];
}
for(long long int i=0;i<2;i++)
{
for(int j=0;j<3-i-1;j++)
{
if(a[j]>a[j+1])
{
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
k=b[j];
b[j]=b[j+1];
b[j+1]=k;
}
}
}
l=0;
for(int j=0;j<3-1;j++)
{
if(a[j]==a[j+1] && b[j]!=b[j+1])
{
cout<<"NOT FAIR"<<endl;
l=100;
break;
}
else if(b[j]>b[j+1])
{
cout<<"NOT FAIR"<<endl;
l=100;
break;
}
}

if(l!=100)
cout << "FAIR"<<endl;
}
return 0;
}
2 Likes

Here is my solution. I used following algorithm:-
if a1-a2 has same sign as c1-c2 then it is valid distribution. Here is my code:

#include<bits/stdc++.h>
using namespace std;
int sign (int v) {
return (0<v)-(v<0);
}
int main() {
int t;
cin>>t;
while(t--) {
int a[3], c[3], b[3], d[3];
for(int i =0; i<3; i++) {
cin>>a[i];
}
for(int i =0; i<3; i++) {
cin>>c[i];
}
for(int i =0; i<2; i++) {
b[i] = a[i] - a[i+1];
}
b[2] = a[2] -a[0];
for(int i =0; i<2; i++) {
d[i] = c[i] - c[i+1];
}
d[2] = c[2] -c[0];
int flag = 1;
for(int i = 0; i<3; i++) {
if (sign(b[i]) != sign(d[i])) {
flag =0;
break;
}
}
if (flag) {
cout<<"FAIR\n";
} else {
cout<<"NOT FAIR\n";
}
}
return 0;
}
1 Like

#include <stdio.h>
struct person{
int age;
int money;
};

int main() {
int t;
scanf("%d",&t);
for(int i=0;i<t;i++){
struct person p1,p2,p3;
scanf("%d %d %d %d %d %d",&p1.age,&p2.age,&p3.age,&p1.money,&p2.money,&p3.money);
int flag=1;
if(p1.age<p2.age){
if(p1.money>p2.money) flag=-1;
}
else if(p1.age==p2.age){
if(p1.money!=p2.money) flag=-1;
}
else
{
if(p1.money<p2.money) flag=-1;
}

if(p2.age<p3.age){
if(p2.money>p3.money) flag=-1;
}
else if(p2.age==p3.age){
if(p2.money!=p3.money) flag=-1;
}else
{
if(p2.money<p3.money) flag=-1;
}

if(p3.age<p1.age){
if(p3.money>p1.money) flag=-1;
}
else if(p3.age==p1.age){
if(p3.money!=p1.money) flag=-1;
}else
{
if(p3.money<p1.money) flag=-1;
}

if(flag==1) {printf("FAIR\n");}
else
{
printf("NOT FAIR\n");
}

}
return 0;

}

1 Like

This is my code, and it didnâ€™t work. Was the easiest problem in the contest, and I couldnâ€™t make it work, Iâ€™m feeling really badâ€¦

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

int main(){
int t;
cin>>t;
while(t--){
int arr[3];
int sum[3];
for(int i=0;i<3;i++)
cin>>arr[i];
for(int i=0;i<3;i++)
cin>>sum[i];
bool flag=true;
for(int i=0;i<3;i++){
for(int j=i+1;j<3;j++){
if(arr[i]>arr[j]&&sum[i]<sum[j])
flag=false;
if(arr[i]==arr[j]&&sum[i]!=sum[j])
flag=false;
if(arr[i]<arr[j]&&sum[i]>sum[j])
flag=false;
}
}
if(flag)
cout<<"FAIR"<<endl;
else
cout<<"NOT FAIR"<<endl;
}
return 0;
}

1 Like

I am pretty sure that i covered almost every cases , please help me out if i overlooked any case .
My solution
Thank you.

1 Like

This by no means is the most efficient program nor the easiest but it was my first codechef challenge.
cases = int(input())
for case in range(cases):
data = list(map(int, input().split())) #splitting the input
fair = True
for child1 in range(2): #number of children - 1
for child2 in range(child1 + 1, 3): #from child 1 to the end
if ((data[child1] > data[child2]) and (data[child1 + 3] > data[child2 + 3])):
fair = True
elif ((data[child1] < data[child2]) and (data[child1 + 3] < data[child2 + 3])):
fair = True
elif ((data[child1] == data[child2]) and (data[child1 + 3] == data[child2 + 3])):
fair = True
else:
fair = False
break #Break out of the inner loop
if not fair: #Break out of the outer loop
break
#Printing the result
if fair:
print(â€śFAIRâ€ť)
else:
print(â€śNOT FAIRâ€ť)

1
2 13 7 46 84 84
FAIR

your code fails at this tc

3 Likes

My Solution

#include <bits/stdc++.h>
#define ll long long
#define fo(i,n) for(i=0 ; i<n ; i++)
#define Fo(i,k,n) for(i=k ; i<n ; i++)

using namespace std;

void pairsort(int a[], int b[], int n)
{
pair<int, char> pairt[n];

// Storing the respective array
// elements in pairs.
for (int i = 0; i < n; i++)
{
pairt[i].first = a[i];
pairt[i].second = b[i];
}

// Sorting the pair array.
sort(pairt, pairt + n);

// Modifying original arrays
for (int i = 0; i < n; i++)
{
a[i] = pairt[i].first;
b[i] = pairt[i].second;
}

}

int main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll t;
cin>>(t);
while(t--){

int C[3],A[3];
cin>>A[0]>>A[1]>>A[2]>>C[0]>>C[1]>>C[2];

if(A[0]==A[1]&& A[1]==A[2] && C[0]==C[1]&& C[1]==C[2])
cout<<"FAIR"<<"\n";
else if(A[0]==A[1]&& A[1]==A[2] && (C[0]!=C[1] || C[1]!=C[2]) )
cout<<"NOT FAIR"<<"\n";
else if(A[0]==A[1] && C[0]!=C[1] || A[2]==A[1] && C[2]!=C[1] || A[0]==A[2] && C[0]!=C[2] )
cout<<"NOT FAIR"<<"\n";
else{
pairsort(A,C,3);

//      cout<<C[0]<<" "<<C[1]<<" "<<C[2]<<"\n";
if(A[0]==A[1] && C[0]==C[1] && C[0]<C[2])
cout<<"FAIR"<<"\n";
else if(A[2]==A[1] && C[2]==C[1] && C[0]<C[2])
cout<<"FAIR"<<"\n";
else if(C[0]<C[1]&& C[1]<C[2])
cout<<"FAIR"<<"\n";
else
cout<<"NOT FAIR"<<"\n";

}

}

return 0;

}

format code correctly

Well caught, the conditions shouldâ€™ve been â€ś<=â€ť and â€ś>=â€ť
Thanks bro

No problem , good luck .

try this

1
2 13 7 46 84 84

Can anyone pls tell whats wrong with this code

#include
using namespace std;

int main() {
int t;cin>>t;
while(tâ€“)
{
int a[3],b[3],i;
for(i=0;i<3;i++)
{
cin>>a[i];
}
for(i=0;i<3;i++)
{
cin>>b[i];
}
int flag=0;
for(i=1;i<3;i++)
{
if(i>1)
{
if((a[i]==a[i-2]&&b[i]!=b[i-2])||(a[i]-a[i-2]>0&&b[i]-b[i-2]<=0)||(a[i]-a[i-2]<0&&b[i]-b[i-2]>=0))
flag=1;break;
}
if(a[i]-a[i-1]>0&&b[i]-b[i-1]>0)
continue;
else if((a[i]-a[i-1]<0&&b[i]-b[i-1]<0))
continue;
else if((a[i]-a[i-1]==0&&b[i]-b[i-1]==0))
continue;
else
{
flag=1;break;
}

if(i>1&&a[i]==a[i-2]&&b[i]!=b[i-2])
{
flag=1;break;
}

}
if(flag)
{
cout<<"NOT FAIR"<<endl;
}
else
{
cout<<"FAIR"<<endl;
}
}
return 0;

}

1 Like

thanx syntaxhackerâ€¦ it helped , I just wonder how I can come up with this kind of test cases like you ! Can you suggest anything .

learn about stress testing here - https://www.coursera.org/lecture/algorithmic-toolbox/stress-test-implementation-Bskph
implement it with ac solution you will find them where your code fails.
or just think about a tc

1 Like

Thank you â€¦ I shall give it a try