PROBLEM LINK:
Author and Editorialist: Lalit Kundu
Tester: Kamil Debowski
DIFFICULTY:
cakewalk
PREREQUISITES:
basic programming, sorting
PROBLEM:
You are given list of N special friends of Chef and M posts in ChefBook, where each post has f - the Id of friend who created the post, p - the popularity of the post and c - the contents of the post.
BookChef uses following algorithm to show posts in feed of Chef:
- First posts of special friends are shown. Popular posts are shown first.
- All other posts are shown after posts of special friends and are arranged in decreasing order of popularity.
Your task is to output the contents of posts in correct order.
EXPLANATION:
================
The idea is very simple. Break down posts into two types: posts by special friends and posts by others. For each type, sort the posts in decreasing order of popularity and then output the contents. You need to know any basic sorting algorithm. Also, you need to maintain a structure for storing posts information which can be
struct
in C++,
tuple
in Python or even
list
available in most programming languages. Next is you need sort an array of this structure according to one of the specific fields, for which you need to write a custom compare function.
To avoid writing custom compare function, you can do things a little intelligently. You must notice that once we’ve separated posts based on whether they’re from special friends or not, we don’t need to maintain the Id of the friend who created the post. In C++, if we sort a
pair <T1, T2>
, it’s sorted in increasing order of first element. So, we can maintain a list of
pair< int, string >
where first element is the popularity and second is the content of the post. We maintain two different lists for each type.
Shown below is the pseudo code along with some C++ constructs. You can read setter’s and tester’s solutions for example implementations.
//Array for marking Ids of special friends. Special[i] is 1 if friend with Id i is special
bool Special[MAXID]
scan(T)
for test = 0 to T - 1:
scan(N, M)
pair<int, string> listSpecial, listNormal;
for i = 0 to N - 1
scan(x)
Special[x] = 1
for i = 0 to M - 1
scan(f, p, s)
if Special[f]:
listSpecial.push_back( {p, s} )
else:
listNormal.push_back( {p, s} )
sort(listSpecial)
sort(listNormal)
reverse(listSpecial)
reverse(listNormal)
for i in listSpecial:
print i.second
for i in listNormal:
print i.second
COMPLEXITY:
================
O(N + M \text{log} M) to read special friends and then sort the two lists of posts. Since, we can check whether each friend is special or not in O(1), the complexity is not affected by these operations.