How to solve this sitting arrangement problem?

general
, ,
1

There is a classroom which has M rows of benches in it. Also, N students will arrive one-by-one and take a seat.

Every student has a preferred row number(rows are numbered 1 to M and all rows have a maximum capacity K. Now, the students come one by one starting from 1 to N and follow these rules for seating arrangements:

  • Every student will sit in his/her
    preferred row(if the row is not
    full).
  • If the preferred row is fully
    occupied, the student will sit in the
    next vacant row. (Next row for N will
    be 1)
  • If all the seats are occupied, the
    student will not be able to sit
    anywhere.

Monk wants to know the total number of students who didn’t get to sit in their preferred row. (This includes the students that did not get a seat at all)

Input

  • First line contains 3 integers N, M and K. N - Number of students and M - Number of rows and K - maximum capacity of a row.
  • Next line contains N space separated integers Ai. Ai - preferred row of ith student.

Output

Output the total number of students who didn’t get to sit in their preferred row.

Constraints

  • 1≤N,M≤105
  • 1≤K≤500
  • 1≤Ai≤M

Sample Input

5 2 2

1 1 2 1 1

Sample Output

2

Explaination

Student 4 and student 5 did not get their preferred seats.

PLEASE DON’T PROPOSE O(N*M) SOLUTION, I HAVE ALREADY DONE THAT BUT COULDN’T GOT AC.

2

Can you provide at least one test case?

3

Here you can use the concept of hashing. Just traverse from left to right and store the frequency of element. But before this you must check whether the bucket of that row is been full upto K or not. If it has been full just you need to increase counter and moving on.

It would be more clear if you provide me the link of question so i can judge my code and then tell you whether it would be 100% correct or not.

But the concept will be used here is HASHING

4

My assumption is that ‘next’ row may not be the immediate next. It can be the first row after the current row which is not fully occupied (i.e. it has some vacancy).

This is my solution - piXyVt - Online IDE & Debugging Tool - Ideone.com

Claim: It will run in worst case O(N+M) time.

Reason: I am storing for each row, the very next row (the definition of ‘next’ I explained above) where I can find an empty seat. I also store for each row, the number of seats already occupied (count will do, since we aren’t interested in the ordering of the students in that row). Say for given Ai, if the Ai’th row has vacancy, just increment the number of occupied seats. If not, then start looking for the nearest row next to Ai’th row which has a vacancy. Suppose there are k rows in between, and the next vacant row be Aj. Then for all the k rows as well, the next vacant row will be Aj. So I update the next vacant row for all rows. Clearly updates will be at max M times. Hence O(N+M).

There will come a time when all rows are occupied. This will be checked when, in search of the very next row for Ai, we hit upon Ai itself. This means no vacancy. Then all incoming students will simply stand out. So we maintain a boolean flag to note that.

Do tell me if it doesn’t work out.

3 Likes
5

I hope that you understand how my code is working. In this answer I will just try to explain the how running time will be O(M+N).

The problem is quite trivial until you find that the row (I will call it Ai) where you have to fill has no more vacancy. How to decide which row to fill next? Naive approach would be to search for the next row every time - which was the reason it’s complexity would have been worst case O(N*M).

Now, what if you store the index of the next vacant row for each Ai? It makes things a bit simpler, as updates are now O(1). However a time will come when even this ‘next row’ becomes full (let’s call this row ‘Aj’). What then? After that, we do an exhaustive search for the row next to ‘Aj’ which has a vacancy. This particular step is O(M). When you do find one, update the next row indices for all the rows starting Ai up till the valid row next to Aj (call it Ak). (This is because starting from Ai, you won’t find an empty row until you reach Ak. So all rows from Ai to Ak will have their next row as Ak). Again this step is O(M).

The thing to note here is that these O(M) steps will occur only at certain points in our iterations from i=1 to N, and one can try to do a worst-case analysis by themselves to find that it will remain O(M) operation.

Therefore the final complexity is O(N+M). (You might have a little higher constant associated with M, but it won’t be large enough to cause any issue).

If you feel your question was answered, please mark this answer as ‘Accepted’.

1 Like
6

Please upvote me,I’m unable to post anything. Thanks in advance :slight_smile:

2 Likes
7

I don’t know why utkarsh1997’s code get AC because in his implementation on ideone because he had some bugs, one of them is found when he moved around the circular array using cyclic rotations using N(amount of students) instead of M(amount of rows).

Blockquote
Claim: It will run in worst case O(N+M) time. utkarsh1997
Blockquote

Disclaim:
The given algorithm is still O((N / K) * M) but the constant factor is lower compared with original algorithm coded by arpit728.
Example of worst case entry in that algorithm achieving O(M^2):

int n = 100000, m = n, k = 1;
vector<int> v;

for(int i = 0; i < m / 2; ++i)
{
	v.push_back(n / 2 - i);
	v.push_back(n / 2 - i);
}

Using vector v as entry of the given problem and the total iterations would be around 2500000000. This is because elements in odd positions are solved without visiting other rows than the required one and in even indexed element the amount of lookups is equal to walk to the next unvisited row, but because the ordering used above that number is the same index of the element plus one. So, it would be:
(2 - 1) + (4 - 1) + … + (m - 1) = sum of the first (m / 2) odd numbers = (m / 2)^2. sum of odd numbers.

There is an aproach O((N + M) * logM) to this problem that takes advantages of some reasoning given by utkarsh1997. Instead of looking in the array of size M for the rows, let’s maintain a set that have the index of the rows non filled yet. Initially this set has all numbers from 1 to M. Also we keep an array CAP of size M where CAP[i] = amount of students that can sit in row i in the given moment. Initially CAP[i] = k for all i, 1…N. If CAP[i] > 0 then OK and --CAP[i] and if CAP[i] = 0 after this operation then remove i from the set, else we use set lowerbound property in C++ to do a binary search and find the next row, if there is not any element greater than i then is the first one in the set. I hope you understand this. Greetings.

8

@bansal1232
I have edited the question and added a sample test with explanation.

9

“If it has been full just you need to increase counter and moving on.”

It won’t work, as you will have to assign the current student to another row (say k) which has vacancy as well. This can affect the answer in case some other student has preference row k and he finds that k is already full.

1 Like
10

@utkarsh1997

Thanks, this solution is working fine, it got me AC.
But can you please explain its complexity in more detail.

11

@blacktools
I don’t know about the implementation of @utkarsh1997 because I only used his idea and not his implementation.
You can find my implementation here.

And I think my algorithm will run in O(N+M) in worst case. Can you please propose any test case where it doesn’t confront to O(N+M) complexity.

12

Your algorithm indeed achieves a very similar complexity to O(N + M) because you implicitly use the behavior of Disjoint Set Data Structure with path compression that achieves O(f(n)*(N + M)) time complexity, where f(n) is the inverse of the extremely fast-growing Ackermann function. Thanks for showing me your code. If there is any doubts here is a link to the wikipedia page “Disjoint-set data structure - Wikipedia”.