150iq's blog

By 150iq, 7 weeks ago,

Problem Statement:

There are N patients (numbered from 0 to n — 1) who want to visit the doctor. The doctor has S possible appointment slots, numbered from 1 to S. Each of the patients has two preferences. Patient K would like to visit the doctor during either slot A[k] or slot B[k]. The doctor can treat only one patient during each slot.

Is it possible to assign every patient to one of their preferred slots so that there will be at most one patient assigned to each slot?

Input: Two arrays A and B, both of N integers, and an integer S

1 <= N <= 10^6

1 <= S <= 2*10^6

1 <= A[i] <= S

1 <= B[i] <= S

no patient has two preference for the same slot i.e. A[i] != B[i]

Output: print "true" if it is possible to assign every patient to one of their preferred slots, one patient to one slot, and "false" otherwise.

• -7

 » 7 weeks ago, # |   -10 Auto comment: topic has been updated by 150iq (previous revision, new revision, compare).
 » 7 weeks ago, # |   -20 please someone tell the possible soln. or either say its too standard or its impossible to solve in given constraints. but please leave a comment before downvoting.
•  » » 7 weeks ago, # ^ |   0 Thanks but now you'll get downvoted too :" )
•  » » » 7 weeks ago, # ^ |   0 And it's not surprising. Considering how fishy it looks when 3 different persons (I'm also counting this guy) are suddenly asking for hints or solutions for the same problem roughly at the same time.
•  » » » » 7 weeks ago, # ^ |   +1 It ended at 2:00 PM (UTC+5.5) i.e. roughly 3 hours from now. I don't know why nobody is helping
•  » » » » » 7 weeks ago, # ^ |   -8 Nowadays most people starts downvote the genuine blog. If you can't solve the problem then please don't downvote. And i don't understand is there is nobody on codeforces who can give some hint to solve this problem. This is very demotivating for the person who writes blog for help. Plz help to grow community.
 » 7 weeks ago, # |   +1 I think you need to build a graph and check it for bipartition
 » 7 weeks ago, # |   -26 Some people are always ready to start totally shit discussion on shit topics like Bugaboo or problem but they never help people who write blog for problem discussion.
•  » » 7 weeks ago, # ^ |   0 It is because some people ask for solutions from ongoing contests. So, if you genuinely want to ask solution to a problem then post the link to the problem rather than writing a complete problem statement yourself.
•  » » » 7 weeks ago, # ^ |   0 How difficult is it to understand for you that some problems aren't available after the contest/coding round ends. Don't put false allegations on someone based on your incomplete knowledge.
•  » » » » 7 weeks ago, # ^ |   0 I haven't said that you posted it for cheating. I was generally saying that always put link for asking doubts and if the link is not available then at least specify the contest name or something so that someone who gives that contest can confirm.
•  » » » » » 7 weeks ago, # ^ |   +6 Okay sorry! It was asked in American Express Coding Round.
 » 7 weeks ago, # |   +3 Can you share the source of the problem? How can we know this problem isn't asked in an ongoing contest.
•  » » 7 weeks ago, # ^ |   -6 Most Interview problems aren't accessible after the interview.
 » 7 weeks ago, # |   +8
•  » » 7 weeks ago, # ^ |   0 I also thought of the same but the complexity may not be suitable for the constraints. I think we have to use the property of each patient having exactly two distinct preferences to make it O(n) complexity.
 » 7 weeks ago, # |   +3 There are two ways to solve this problem:1) Build a graph (man — > slot), and just find the size of maximum matching, this solution will work if you use the optimizations from this post (https://codeforces.com/blog/entry/17023). If the size of the maximum matching is equal to the number of people, the answer is "true", otherwise "false".2) The second solution, let's initially do this, take all the slots in which only one patient can go and let's say that this person will go to this slot, we will repeat this until such slots remain. This can be simulated in O(NlogN). Now we know that more than one person goes to each of the remaining slots, or there are no more people who can go to the slot. Let's imagine a graph where an edge represents a person and a vertex represents a slot. A person will connect two slots that he can go to. (You don't need to add people that we deleted while performing the actions from the first paragraph). Now let's note that each vertex will stand in a cycle, which means that for each remaining slots with a degree greater than one, there will be a patient. Finally we calculated the number of people who will find a free slots, if all n people have found an slot, then the answer is "true", otherwise "no", works in O(nlogn).
•  » » 7 weeks ago, # ^ |   0 Thanks a lot! I really liked your approach : )
 » 7 weeks ago, # | ← Rev. 2 →   +3 Consider an edge between A[i] and B[i], BFS.
•  » » 7 weeks ago, # ^ |   0 Can you please elaborate a little?
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 My idea is we should build a graph and connect the all the A[i]s and B[i]s. Now let's BFS all the components, if we get a way that numbers of detected vertices equal to N, we get the answer, else print "false".
•  » » » 7 weeks ago, # ^ |   0 Maybe it requires some more functions than regular BFS, but i think it will work.
 » 4 weeks ago, # | ← Rev. 3 →   0 So, I had this problem in one of my interview tests too and considering that this problem is from a contest that is already over, here's what I did. I approached the problem as a cartesian system of co-ordinates, each being a unique pair and so, non-unique pairs would immediately return false. bool solution(vector &A, vector &B, int S) { set> slots; //set to store pairs of co-ordinates, because sets don't contain duplicate values int x = A.size(); //to be used in place of vector size thingy if(x > S) return false; //to check whether the arrays are larger than the doctor's available time //The magic begins... for(int i=0; i< x;i++){ pair current = make_pair(A[i], B[i]); //create a co-ordinate pair for each index pair currRev = make_pair(B[i], A[i]); //create a reverse co-ord pair if the "current" pair won't work if (slots.find(current) == slots.end()) slots.insert(current); //insert non-reversed pair if it doesn't already exist else if (slots.find(currRev) == slots.end()) slots.insert(currRev); //insert reversed pair if the non-reversed pair already exists else return false; // if both pair already exists, then the slot is already full for the given time and so it should already be returned as false, as there won't be a unique available time } return true; //return true if everything works out great! } I am posting my solution believing that the contest is already over. If you don't want this solution, I can delete it. I just wanted to help :)Oh, and if you have got a better approach, I'd really love to learn it. Thanks :)
•  » » 4 weeks ago, # ^ |   0 Seems fine to me bro!