PROBLEM LINK:
Author: Sandeep Singh
Tester: Sunita Sen
DIFFICULTY:
MEDIUM.
PREREQUISITES:
Bitmasking
EXPLANATION:
The most important observation is that the preference subset for each query can be represented as a bitmask.
How?
Since there are only 6 brands. If each brand is represented by a bit (2^{i-1} bit where i is the brand number).
The number of Brands is 6, so the total possible bitmask we can get in a query is 2^6. Let us see how this helps to solve the problem.
If we try Bruteforce, then for each query we have to construct an array consisting of the prices of mobiles according to the preference subset of the customer. Let’s call this preference array. Then just sort the array in descending order and print the Kth value (-1 if k is greater than arrays size). But this is too time-consuming. We can make this efficient using bitmasks.
We kow the preference subset is one of 2^6 varients. Lets precalculate and sort them. We only have to sort 2^6 arrays. Then we can answer each query in constant time.
How to precalculate?
The Solution given below is more than eough to understand that. Here’s a brief explination.
For each mobile, we loop over all 2^6(64) masks and insert the price in the array of those masks in which the (i-1)^{th} bit is set where i is the brand of the mobile.
for(i = 0; i < n; ++i){
for(j = 1; j < 64; ++j){
if(j & (1 << (brand[i] - 1)))
arr[j].push_back(price[i]);
}
}
Time complexity O(2^6NlogN)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
void solve(){
int i, j, n, q;
cin >> n >> q;
vector <int> brand (n, 0), price(n, 0);
vector <int> arr[64];
for(i = 0; i < n; ++i)
cin >> price[i];
for(i = 0; i < n; ++i)
cin >> brand[i];
for(i = 0; i < n; ++i){
for(j = 1; j < 64; ++j){
if(j & (1 << (brand[i] - 1)))
arr[j].push_back(price[i]);
}
}
for(i = 1; i < 64; ++i)
sort(arr[i].begin(), arr[i].end(), greater <int>());
int nob, x, k;
while(q--){
cin >> nob >> k;
int mask = 0;
while(nob--){
cin >> x;
if(x > 6 || x < 1)
cout << "hello"<<endl;
mask |= (1 << (x - 1));
}
if(k > arr[mask].size())
cout << -1 << endl;
else
cout << arr[mask][k - 1] << endl;
}
}
int main() {
solve();
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
vector<int> arr[65];
int brand[100005];
int price[100005];
int n,q;
void go(int x){
for(int i=0; i<7; i++){
if((1<<i&x)){
for(int j=0; j<n; j++){
if(brand[j]==i+1){
arr[x].push_back(price[j]);
}
}
}
}
}
int main() {
cin >> n >> q;
for(int i=0; i<n; i++)
cin >> price[i];
for(int i=0; i<n; i++)
cin >> brand[i];
for(int i=0; i<64; i++){
go(i);
sort(arr[i].begin(), arr[i].end(), greater<int>());
}
while(q--){
int d,k;
cin >> d >> k;
int x=0;
for(int j=0; j<d; j++){
int a;
cin >> a;
x += (1<<(a-1));
}
if(arr[x].size()<k)
cout <<-1<<endl;
else
cout << arr[x][k-1] << endl;
}
return 0;
}