Hello community! I think we need to use Priority Queue in this case but am not able to perfectly figure out the solution. I know I am not at all good with explaining stuff. Hope my questions make sense and feel free to make any edits. Hope to see many people actively participating in discussion :)
This question is marked "community wiki".
asked 18 Aug '17, 15:56

The real Q is what if 2 companies offer same salary. I think it will be a wild card entry for dp :p Also, if N and M were high, upto 10^5, then wont storing the array be a problem? One way to tackle this would be to take not to take entire input at once, and take it line by line, store the row of matrix in a string variable, process it, and then take next line in same variable (to save memory). Give a look to my solution if it helps you https://www.codechef.com/viewsolution/14779158 I think you will need to read the entire string, because theres no way to determine the highest package before reading the entire string. We need to read it to determine what companies selected the candidate after all! I cant think of a solution quicker than O(NM). Will be glad if anyone can say otherwise :) answered 18 Aug '17, 16:03
Hey @vijju123. Thanks for sharing your thoughts! Also, if N and M were high, upto 10^5, then wont storing the array be a problem? Nice solution! I followed almost the same procedure!! Although enjoy reading your comments everytime xD
(18 Aug '17, 16:37)
This can help memory wise, but we still need to look at the string to see which companies selected and which is highest among them. Cant think better than O(MN) atm. BTW, thanks. Glad someone likes the comments :p
(18 Aug '17, 18:05)
1
we can make n,m large and remove the qual matrix from input then it can be solved in O(n log(m)) using binary search if the first come first serve criteria is preserved too else it can have a nice dynamic solution too if first come first serve is removed too along with removed qual matrix that means every candidate has qualified in every company.If we have to input qual matrix then it will have mn entries and its complexity will increase to O(nm).
(18 Aug '17, 18:14)
Yes, if matrix is preserved, it increases to O(MN). Can you explain on binary searching one? Like, if i am getting it correctly, in binary search soln. , if we are still given string representing who selected the candidate and who didnt, then wont reading it take us back to O(NM)? But i think I am getting it incorrectly, so please clarify :)
(18 Aug '17, 18:17)
2
Binary search will work only if we remove qual matrix also as i mentioned it in my previous comment.Whenever we need to read qual matrix it will result in O(MN) complexity.
(18 Aug '17, 18:36)
I think I get it now. Thanks :)
(18 Aug '17, 18:39)
Glad to see even the problem author giving his thoughts!! Thanks @naksh9619 for sharing!!
(18 Aug '17, 18:52)
showing 5 of 7
show all

I dont think there's a need to search for whether a company hired for a student or not.You can just form a two dimension array whose first row will contain the salary they will give and the second row will consist of the number of students they hired. You can check out my solution: https://www.codechef.com/viewsolution/14914344 The number of students who got the job will be the sum of the second row and the no of zeroes shows the number of companies who didnt got any student and the total slaray will be sum of the multiplied salary with the number of students hired. answered 18 Aug '17, 20:50

Will not it become quite a like best pair matching problem then?? here.. https://en.wikipedia.org/wiki/Stable_marriage_problem
Never thought of that! Thanks for sharing @kauts_kanu