BOOKCHEF - Editorial

PROBLEM LINK:

Practice
Contest

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.

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

1 Like

hello,
Please help, I am not able to find error in my code. I got wrong answer.
Here is the link : https://www.codechef.com/viewsolution/11937898

Please help me. My code is giving a SIGSEGV and i am a noob. (LINK)

your code goes here

def bubblesortshort(alist):
exchanges=True
passnum=int((len(alist)/2)-1)
while passnum>0 and exchanges:
exchanges=False
for i in range(passnum):
if int(alist[i])<int(alist[i+2]):
exchanges=True
temp1=alist[i]
temp2=alist[i+1]
alist[i]=alist[i+2]
alist[i+1]=alist[i+3]
alist[i+2]=temp1
alist[i+3]=temp2
i=i+2
passnum=passnum-1
return alist

def sortingChef(listItem):
i=[]
for j in listItem:
i+=j.split(’-’)
i=bubblesortshort(i)
return i

def inputChef():
inputLine1=(input())
inputLine1=inputLine1.split(’ ‘)
numberOfSpecialFriends=inputLine1[0]
numberOfposts=int(inputLine1[1])
inputLine2=input()
inputLine2=inputLine2.split(’ ‘)
outputList=[]
inputLine3=[]
inputLine4=[]
inputLine5=[]
inputLine6=[]
finalList=[]
for j in range(0,numberOfposts):
x,y,z=(input().strip().split(’ ‘))
inputLine3.append((x)+(y)+’-’+z)

inputLine3.sort()

for i in range(0,len(inputLine3)):
	f=str(inputLine3[i][0:1])
	value=False
	for k in range(0,len(inputLine2)):
		if(f == inputLine2[k]):
			inputLine4.append(inputLine3[i][1:])
			value=True
			break
		elif(f!=inputLine2[k] and value==False):
			inputLine5.append(inputLine3[i][1:])
			value=True

for item in inputLine5:
	if item not in inputLine4:
		inputLine6.append(item)
		
inputLine4=sortingChef(inputLine4)
inputLine6=sortingChef(inputLine6)
i=0
while i <len(inputLine4):
	finalList.append(inputLine4[i+1])
	i=i+2
j=0
while j<len(inputLine6):
	finalList.append(inputLine6[j+1])
	j=j+2

print(finalList)

inputChef()

I have done this code in python but it is saying run time error but it is working on ideone.com

Hi,
i am a beginner and have coded this using simple algorithms.
Although i am getting correct answers whenever i test it on my system by self constructed test values still code chef says wrong answer.

My code is in C.

It can be viewed here.

Any help would be appreciated

I too have a code similar(the logic remains the same) to atishya,and I am unable to figure out what is wrong. I have the ‘right’ version of the code(something else that is accepted), but I want to know where I go wrong in this : have I missed a test case,or something like that. I even checked for end cases(n = 0,n = m), but I still get a wrong answer.
My code can be found here : https://www.codechef.com/viewsolution/11987082

Could someone please tell me what have I gotten wrong, I would appreciate it.

Hello,
I just can’t get my solution working, I get a runtime error everytime
https://www.codechef.com/viewsolution/11992581

This works for me in Visual Studio, and the code chef ide.

Please help

Hello, when I run my program against the test cases given it works, but for some reason, it doesn’t run against codechefs test cases and gives wrong output. Since I can’t see these test cases I am not understanding where I am going wrong.
My Code can be viewed here
https://www.codechef.com/viewsolution/13414455

If someone could give me a few test cases where the output is wrong, I could work on them.

Any help would be appreciated.

arr1[k].str=arr[i].str;

Shouldn’t this line be arr1[k].str = arr[j].str ?

oops, you are right but it is still a wrong answer