PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Soumyadeep Pal
Tester : Radoslav Dimitrov
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy - Medium
PREREQUISITES:
Observation, Queue, Binary Search
PROBLEM:
There are N people, numbered from 1 to N. They go to a cinema hall. Each of them buys a ticket, which has a number written on it. The number on the ticket of the i^{th} person is A_i.
There are infinite seats in the cinema hall. The seats are numbered sequentially starting from 1. All the N people stand in a queue to get their respective seats. Person 1 stands at the front of the queue, Person 2 stands in the second position of the queue, so on up to Person N who stands at the rear of the queue. They were given seats in this manner:
Let the number on the ticket of the person currently standing in front of the queue be X. If the X^{th} seat is empty, the person gets out of the queue and takes the X^{th} seat. Otherwise, the person goes to the rear of the queue, and the number on his ticket is incremented by one - that is, it becomes X+1.
Print the seat number occupied by each of the N people.
EXPLANATION:
Let us try to do as the problem speaks:
Whenever we find a person which has the number X on his ticket and if the X^{th} seat is empty, then we can simply allot a seat to that person and remove him from the queue. Otherwise, we increment his seat number and make him go to the last of the queue. We keep on doing so until there is no person left in the queue.
The method is correct but it is quite slow and hence it will result in TLE. One of the worst-case for this method is when all people standing in the queue want the same seat. Then it is quite easy to see that it takes a whole iteration of the queue to allot a seat to a single person.
Let’s see what are the optimizations we can do. Instead of finding a seat for a person, let’s try to find a person for the seat.
What is the largest seat number that will be allocated to any person standing in the queue?
-
From the problem constraints A_i \le N, it means initially no person can have a ticket that has a seat number greater than N. Now in the worst case, all the people have a ticket which has seat number N written on it.
-
It is quite easy to see that in one whole iteration of the queue, at least one person will get a seat. Hence we can say that the largest seat that will be allocated to any person will be 2*N-1.
In other words, we only need seat numbers 1 to 2*N-1 to allocate seats to every person standing in the queue.
We can make another observation that a seat number S can only be allotted to those people which have a ticket number less than or equal to S.
Claim: A seat number S is allotted to a person who has a ticket number next smaller to S.
Proof
Suppose there are three people which have a ticket number lower than S. Let’s say their ticket numbers are a,b, and c such that a<b<c. Now in every iteration, each person ticket number will be increased by 1, and c being closest to S requires fewer iterations to get incremented to S. Once it reaches the value S, the person gets the seat S.
Also if there are two or more person which has same ticket number and is next smaller to S, then the person which is present earlier in the queue gets the seat S.
Now, once we know which seat will be allotted to which person, we can simply print the seat numbers occupied by every person.
Rest is implementation, try to implement it and if there are any doubts in implementation please let me know in the comments section.
TIME COMPLEXITY:
O(N*log(N)) per test case
SOLUTIONS:
Author
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n, ans[N];
deque<int> d[N];
set<int> tickets;
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
tickets.insert(x);
d[x].push_back(i);
}
for (int pos = 1; pos <= 2 * n - 1; pos++) {
auto it = tickets.upper_bound(pos);
if (it == tickets.begin()) continue;
it--;
int person = d[*it].front();
d[*it].pop_front();
ans[person] = pos;
if (d[*it].empty()) tickets.erase(it);
}
for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
cout << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t ; cin >> t;
while (t--) {
solve();
}
return 0;
}
Tester
import heapq
def solve_case():
n = int(input())
a = [int(x) for x in input().split()]
ppl = [[] for i in range(2 * n + 4)]
for i, x in enumerate(a):
ppl[x].append(i)
h = []
ans = [-1] * n
for pos in range(1, 2 * n + 1):
for i in ppl[pos]:
heapq.heappush(h, (-pos, i))
if len(h) > 0:
ans[heapq.heappop(h)[1]] = pos
print(*ans)
cases = int(input())
for _ in range(cases):
solve_case()