PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter:
Tester: Istvan Nagy
Editorialist: Taranpreet Singh
DIFFICULTY
Easy
PREREQUISITES
Sorting
PROBLEM
Given the priorities of N patients standing in a line numbered from 1 to N from front of queue to end, the doctor treats the patients in non-increasing order of priorities. Among patients with same priority, the patient standing ahead of other one is treated first.
Find the waiting time for each patient assuming first patient has to wait for an hour, and treating each patient takes exactly one hour.
QUICK EXPLANATION
Sort the people standing in queue based on their priority and then by their initial position in queue. It can be seen that Person standing in position p has to wait for p hours.
EXPLANATION
Let’s represent each patient as a pair of integers (pos, priority) denoting the position of patient in queue and the priority.
Now, since pos differs for each patient, the order in which doctor treats patients is unique. Let’s try to figure out that order.
Consider two patients with priority p1 and p2 standing in this order. Now if p1 < p2, then second patient shall be treated before first patient. Hence we can swap the two patients in queue.
Considering a queue with N patients, let us perform such swaps repeatedly till there doesn’t exist any more swaps.
Above idea can be implemented by using bubble sort, by modifying the condition for performing swap.
Now that we see that sorting by priority and then pos gives the order, we can use faster sorting algorithms, preferably inbuilt sort by defining the comparator for comparing two pairs.
Hence, after sorting, we know the order in which Doctor will treat patients. Say a patient is standing at position q after sorting (0-based indexing). Then it takes one hour for doctor to get prepare and q-1 hours to treat patients, leading to waiting time 1 + (q-1) = q hours.
We can store waiting times in a separate array and print waiting times for each patient in their original order.
Another implementation
Instead of sorting, we could just add all pairs into a heap data structure, and pop the next patient one by one.
Follow up
Can you solve this problem without defining custom comparator?
Hint
Define P_i = A_i * X + i where A_i denote priority of i-th patient and X > N.
TIME COMPLEXITY
The time complexity is O(N*log_2(N)) per test case.
The memory complexity is O(N)
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int i,j;
vector<int> arr(n);
vector<array<int,2>> temp;
for(i=0;i<n;i++)
{
cin>>arr[i];
temp.push_back({arr[i],i});
}
auto cmpr = [&](array<int,2> a, array<int,2> b) {
if (a[0] != b[0])return a[0] > b[0];
return a[1] < b[1];
};
sort(temp.begin(),temp.end(),cmpr);
i=0;
while(i<n)
{
arr[temp[i][1]]=i+1;
i++;
}
i=0;
while(i<n)
{
cout<<arr[i]<<" ";
i++;
}
cout<<endl;
}
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#ifdef HOME
#include <windows.h>
#endif
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
//assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
// if(g == '\r')
// continue;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
void calc()
{
for (int M = 1; M <= 1000; ++M)
{
for (int CM = 1; CM <= 300; ++CM)
{
if (M * 10000 % (CM * CM) == 0)
{
printf("%d %d\n", M, CM);
}
}
}
}
int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T = readIntLn(1, 5);
forn(tc, T)
{
int N = readIntLn(1, 100'000);
vector<pair<int, int>> v(N);
forn(i, N)
{
if (i + 1 < N)
{
v[i] = { -1* readIntSp(1, 1000), i};
}
else
{
v[i] = { -1* readIntLn(1, 1000), i};
}
}
sort(v.begin(), v.end());
vector<int> ans(N);
forn(i, N)
{
ans[v[i].second] = i + 1;
}
forn(i, N)
{
printf("%d ", ans[i]);
}
printf("\n");
}
assert(getchar() == -1);
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class CHEFPAT{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
PriorityQueue<int[]> patients = new PriorityQueue<>((int[] i1, int[] i2) -> {
if(i1[1] != i2[1])return Integer.compare(i2[1], i1[1]);
return Integer.compare(i1[0], i2[0]);
});
for(int i = 0; i< N; i++)patients.add(new int[]{i, ni()});
int[] ans = new int[N];
for(int i = 0; i< N; i++){
int[] patient = patients.poll();
ans[patient[0]] = i+1;
}
for(int i = 0; i< N; i++)p(ans[i]+" ");
pn("");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new CHEFPAT().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 