150iq's blog

By 150iq, 7 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • -7
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Auto comment: topic has been updated by 150iq (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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, # ^ |
            Vote: I like it -8 Vote: I do not like it

          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, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it +6 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Most Interview problems aren't accessible after the interview.

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +3 Vote: I do not like it

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.cc/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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot! I really liked your approach : )

»
7 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please elaborate a little?

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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<int> &A, vector<int> &B, int S) {
    set<pair<int, int>> 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<int,int> current = make_pair(A[i], B[i]); //create a co-ordinate pair for each index
        pair<int,int> 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 :)