GCAC - Open Discussion

general
, ,
1

Hello community!
I know the problem GCAC was not that difficult and implementation based. But what if the constraints of N and M were quite high?? Also, it was mentioned in the problem that the students enter the placement in order i.e. 1,2,3,…,N and if any student’s demands are fulfilled, he(/she) is selected. What if it is not so and after examining all the students, the company selects the students which demand lowest salary along with fulfilling their criteria!

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 :slight_smile:

2

Will not it become quite a like best pair matching problem then?? here… https://en.wikipedia.org/wiki/Stable_marriage_problem

1 Like
3

The real Q is what if 2 companies offer same salary. I think it will be a wild card entry for dp :stuck_out_tongue:

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 :slight_smile:

1 Like
4

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?
Umm yea possibly but I think there must be a way.

Nice solution! I followed almost the same procedure!! Although enjoy reading your comments everytime xD

5

Never thought of that! Thanks for sharing @kauts_kanu

6 
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).

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 :stuck_out_tongue:

7

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).

1 Like
8

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 :slight_smile:

9

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.

2 Likes
10

I think I get it now. Thanks :slight_smile:

11

Glad to see even the problem author giving his thoughts!! Thanks @naksh9619 for sharing!!

12

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.