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.

Auto comment: topic has been updated by 150iq (previous revision, new revision, compare).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.

Thanks but now you'll get downvoted too :" )

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.

It ended at 2:00 PM (UTC+5.5) i.e. roughly 3 hours from now. I don't know why nobody is helping

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.

I think you need to build a graph and check it for bipartition

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.

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.

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.

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.

Okay sorry! It was asked in American Express Coding Round.

Can you share the source of the problem? How can we know this problem isn't asked in an ongoing contest.

Most Interview problems aren't accessible after the interview.

This may help https://www.geeksforgeeks.org/maximum-bipartite-matching/!!

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

Thanks a lot! I really liked your approach : )

Consider an edge between A[i] and B[i], BFS.

Can you please elaborate a little?

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

Maybe it requires some more functions than regular BFS, but i think it will work.

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.

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

Seems fine to me bro!