Problem
Chef has opened up a new restaurant. He picks out the positive reviews and posts it on the website of the restaurant. A review is represented by an integer which is the overall rating of the restaurant as calculated by that particular review. A review is considered to be positive if it is among the top one-third of the total reviews when they are sorted by their rating. So here is what the Chef wants from you: Given the reviews (ratings) by different critics, the Chef needs you to tell him what is the minimum rating that his website will be displaying.
The new reviews keep coming in. And the Chef wants your website ratings to be up-to-date. So you should keep updating the ratings there. At any point of time, the Chef might want to know the minimum rating being displayed.
Example
Suppose the ratings given by 8 different reviews are as follows:
2 8 3 1 6 4 5 7
Then the top one-third reviews will be 8 and 7. Note that we considered one-third to be 8/3=2 top reviews according to integer division.
Input
First line of the input file consists of a single integer N, the number of operations to follow. The next N lines contain one operation each on a single line. An operation can be of 2 types:
1 x
Add a review with rating ‘x’ to the existing list of reviews (x is an integer)
2
Report the current minimum rating on the website
Output
For every test case, output a single integer each for every operation of type 2 mentioned above. If no review qualifies as a positive review, print “No reviews yet”.
Constraints
1 ≤ N ≤ 250000
1 ≤ x ≤ 1000000000
Sample Input
10 1 1 1 7 2 1 9 1 21 1 8 1 5 2 1 9 2
Sample Output
No reviews yet 9 9
Solution I
Approach
This problem could be solved easily by using Heap data structure (you could read about Heap data structure here). We will maintain two heaps: maxHeap (a max heap) & topRating (a min heap).
maxHeap will be containing bottom 2/3rd ratings in max heap order i.e. maxHeap.front() at any time will give the highest (2/3rd) rating from reviews.
While, topRating will be containing top 1/3rd ratings in min heap order i.e. topRating.front() at any time will give the lowest (1/3rd) rating from reviews.
So, whenever a new rating comes, we will be checking in which of the two heaps should this rating go ie.
- If current rating x is less than topRating.front(), we will add it to maxHeap.
- If current rating x is greater than topRating.front() and less than maxHeap.front(), we will add maxHeap.front() to topRating and x to maxHeap.
- Else if current rating x is greater than topRating.front() and also greater than or equal to maxHeap.front(), we will add rating x to topRating.
While doing the above operations we will also be ‘maintaining the size of topRating heap’, so that topRating.size() will always be 1/3rd of the total number of ratings:
- If topRating.size() becomes less than 1/3rd the size of total reviews, we will remove the maximum (front) element of maxHeap and add it to topRating.
- If topRating.size() becomes greater than 1/3rd the size of total reviews, we will remove the minimum (front) element of topRating and add it to maxHeap.
Code Implementation
//
// main.cpp
// Restaurant Rating (Codechef)
//
// Created by Himanshu on 02/11/22.
//
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
long int x, ctr=0, n, pos, T;
vector<long int> maxHeap, topRating;
scanf("%ld", &T);
make_heap(maxHeap.begin(), maxHeap.end());
make_heap(topRating.begin(), topRating.end(), greater<int>());
// Adding a bottom sentinel ‘0’
topRating.push_back(0);
push_heap(topRating.begin(), topRating.end(), greater<int>());
while (T > 0) {
scanf("%ld", &n);
if (n == 1) {
scanf("%ld", &x);
// Integer to maintain current
// total number of reviews
ctr++;
if (x < topRating.front()) {
maxHeap.push_back(x);
push_heap(maxHeap.begin(), maxHeap.end());
// Updating the top 1/3rd rating,
// maintaining the topRating size to 1/3rd of total
if (ctr/3 > topRating.size()) {
topRating.push_back(maxHeap.front());
push_heap(topRating.begin(), topRating.end(), greater<int>());
pop_heap(maxHeap.begin(), maxHeap.end());
maxHeap.pop_back();
}
} else {
// Removing the bottom sentinel
if (topRating.front() == 0) {
pop_heap(topRating.begin(), topRating.end(), greater<int>());
topRating.pop_back();
}
if (maxHeap.size() > 0 && maxHeap.front() > x) {
topRating.push_back(maxHeap.front());
push_heap(topRating.begin(), topRating.end(), greater<int>());
pop_heap(maxHeap.begin(),maxHeap.end());
maxHeap.pop_back();
maxHeap.push_back(x);
push_heap(maxHeap.begin(), maxHeap.end());
} else {
topRating.push_back(x);
push_heap(topRating.begin(), topRating.end(), greater<int>());
}
// Updating the top 1/3rd rating,
// maintaining the topRating size to 1/3rd of total
if (ctr/3 < topRating.size()) {
maxHeap.push_back(topRating.front());
push_heap(maxHeap.begin(), maxHeap.end());
pop_heap(topRating.begin(), topRating.end(), greater<int>());
topRating.pop_back();
}
// Adding a bottom sentinel
if (topRating.size() == 0) {
topRating.push_back(0);
push_heap(topRating.begin(), topRating.end(), greater<int>());
}
}
} else {
pos = ctr/3;
if (pos <= 0) {
printf("No reviews yet\n");
} else {
printf("%ld\n",topRating.front());
}
}
T--;
}
return 0;
}
Time Complexity: O(n*logn)
Solution II
This problem could also be solved by using C++ multiset data structure and advance() method of <iterator> class.
Approach
Keep inserting the new ratings into the multiset. The minimum rating being displayed can be found by finding the (n/3)rd smallest element in the tree, where n is the total number of reviews in the tree. This solution would have a time complexity of O(log n) for insertion and retrieval of elements. However, it may give TLE (Time Limited Exceeded) on a large input.