In this HackerEarth Mobile Selection problem solution, John has opened a new mobile shop. Each mobile is having following properties associated to it :
- Operating System ( Windows, Android or iOS)
- RAM Size (2, 4 or 8 GB)
- Memory Space (32 or 64 GB)
- Price
- Rating (based on other features like camera, touch quality, etc)
Now a customer comes to the store and tells his choice of Operating System, RAM size, Memory Space, and his budget that he is willing to spend on the mobile. John will give the customer that mobile phone whose rating is maximum which also satisfies the criteria of Operating System, RAM size and Memory Space as specified by that customer and also whose price lies within the customer’s budget. If more than one eligible phone has a maximum rating then, he can give any phone to the customer.
HackerEarth Mobile Selection problem solution.
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
vector < pair <int, int> > v[18];
map < pair <string, pair <int, int> >, int> m;
int main()
{
freopen("in10.txt", "r", stdin);
freopen("out10.txt", "w", stdout);
m[mp("windows",mp(2, 32))] = 0;
m[mp("windows",mp(2, 64))] = 1;
m[mp("windows",mp(4, 32))] = 2;
m[mp("windows",mp(4, 64))] = 3;
m[mp("windows",mp(8, 32))] = 4;
m[mp("windows",mp(8, 64))] = 5;
m[mp("android",mp(2, 32))] = 6;
m[mp("android",mp(2, 64))] = 7;
m[mp("android",mp(4, 32))] = 8;
m[mp("android",mp(4, 64))] = 9;
m[mp("android",mp(8, 32))] = 10;
m[mp("android",mp(8, 64))] = 11;
m[mp("ios",mp(2, 32))] = 12;
m[mp("ios",mp(2, 64))] = 13;
m[mp("ios",mp(4, 32))] = 14;
m[mp("ios",mp(4, 64))] = 15;
m[mp("ios",mp(8, 32))] = 16;
m[mp("ios",mp(8, 64))] = 17;
int n, w, x, y, z, ind, tmp, i, j, q;
string s;
cin >> n;
assert(1 <= n && n <= 1000000);
while (n--) {
cin >> s >> w >> x >> y >> z;
assert(s == "windows" || s == "android" || s == "ios");
assert(w == 2 || w == 4 || w == 8);
assert(x == 32 || x == 64);
assert(1 <= y && y <= 1000000000);
assert(1 <= z && z <= 1000000000);
v[m[mp(s,mp(w,x))]].pb(mp(y,z));
}
for (i = 0; i < 18; ++i) {
sort(v[i].begin(), v[i].end());
for (j = 1; j < v[i].size(); ++j)
v[i][j].second = max(v[i][j].second, v[i][j-1].second);
}
cin >> q;
assert(1 <= q && q <= 1000000);
while (q--) {
cin >> s >> w >> x >> y;
assert(s == "windows" || s == "android" || s == "ios");
assert(w == 2 || w == 4 || w == 8);
assert(x == 32 || x == 64);
assert(1 <= y && y <= 1000000000);
tmp = m[mp(s,mp(w,x))];
ind = upper_bound(v[tmp].begin(), v[tmp].end(), mp(y, INT_MAX)) - v[tmp].begin();
if (!ind)
cout << -1 << endl;
else
cout << v[tmp][ind-1].second << endl;
}
return 0;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
string os[]= { "windows", "android", "ios"};
int ram[] = {2, 4, 8};
int mem[] = {32,64,-1};
vector<pair<pair<int,int>,int> > v[20];
int getIndex(string a , int b, int c)
{
int x,y,z;
for(int i=0;i<3;i++)
{
if(a == os[i])
x =i;
if(b==ram[i])
y=i;
if(c==mem[i])
z =i;
}
return x*6 + y*2 + z ;
}
int solve(string a , int b, int c,int budget){
int x = getIndex(a,b,c);
if(v[x].size()==0)
return -1;
if(v[x][0].first.first> budget)
return -1;
int ans = 0;
int low = 0;
int high= v[x].size()-1;
while(low<=high){
int mid = (low+high)/2;
if(v[x][mid].first.first<=budget)
{
ans= mid;
low = mid+1;
}
else
high = mid-1;
}
return v[x][ans].second;
}
int main()
{
int n,a,b,c,d;
string str;
cin>>n;
assert(1<=n && 1000000 >= n );
for(int i=0;i<n;i++)
{
cin>>str>>a>>b>>c>>d;
assert(str=="windows" || str =="android" || str=="ios");
assert(a==2|| a==4 || a==8);
assert(b==32 || b==64);
assert(c>=1 && c<=1000000000);
assert(d>=1 && d<=1000000000);
int x = getIndex(str,a,b);
v[x].push_back({{c,d},d});
}
for(int i=0;i<18;i++)
sort(v[i].begin(),v[i].end());
for(int i=0;i<18;i++)
{
for(int j=1;j<v[i].size();j++)
{
v[i][j].second = max(v[i][j-1].second,v[i][j].second);
}
}
int q;
cin>>q;
while(q--)
{
cin>>str>>a>>b>>c;
assert(str=="windows" || str =="android" || str=="ios");
assert(a==2|| a==4 || a==8);
assert(b==32 || b==64);
assert(c>=1 && c<=1000000000);
cout<<solve(str,a,b,c)<<"n";
}
}