# CHEFPAT - Editorial

Setter:
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

Easy

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.

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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int 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
forn(tc, T)
{
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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}

Feel free to share your approach. Suggestions are welcomed as always.

2 Likes

I used a map of queue
map<ll,queue >m;
here is my soln
https://www.codechef.com/viewsolution/43010854

2 Likes

I have done this code can anyone please tell me my mistake.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

bool sortbysec(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second > b.second);
}

int main()
{
int T;
cin>>T;
for(int  i=0; i<T; i++)
{
int n;
cin>>n;
int arr1[n];
int arr2[n];
for(int i=0; i<n; i++)
{
int k;
cin>>k;
arr1[i] = k;
arr2[i] = i;
}
vector<pair<int, int>> vect;

for (int i=0; i<n; i++)
vect.push_back( make_pair(arr2[i], arr1[i]) );

sort(vect.begin(), vect.end(), sortbysec);
int ans[n];
int c = 1;
for (int i=0; i<n; i++)
{
// 		cout << vect[i].first << " "
// 			<< vect[i].second << endl;
ans[vect[i].first] = c;
c++;
}
for(int e: ans)
cout<<e<<" ";
cout<<endl;
}
return 0;
}

I have added the Header file correctly iostream and all that is required my all-test cases running but while submitting its showing issue.

its better to include only one header file
#include<bits/stdc++.h>

what is wrong with this approach ? please suggest something, all given test cases are running correctly. is there any edge case ?

import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
StringBuilder sbr = new StringBuilder();
while (t-- > 0) {
Integer[] arr = new Integer[n];
Integer[] temp = new Integer[n];
for (int i = 0 ;i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
temp[i] = arr[i];
}
Arrays.sort(temp, Collections.reverseOrder());
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(temp[0], 1);
for (int i = 1; i < n; i++) {
if (temp[i] != temp[i-1]) {
map.put(temp[i], i+1);
}
}
for (int i = 0; i < n; i++) {
int val = map.get(arr[i]);
sbr.append(val + " ");
map.put(arr[i], val + 1);
}
sbr.append("\n");
}
System.out.println(sbr);
}
}
1 Like

This is what I used for my approach though it gives WA. Could you please tell me where I seem to be going wrong?

#include <bits/stdc++.h>
using namespace std;
#define ll long long int

void fast_io(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}

bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b) {
return (a.second < b.second);
}

bool sortbygreater(const pair<ll,ll> &a, const pair<ll,ll> &b) {
return (a.first > b.first);
}

int main(){
fast_io();
ll tc;
cin>>tc;
while(tc--){
ll n;
cin>>n;
vector<pair<ll,ll>> lvl(n),cpy(n);
for(ll i=0; i<n; i++){
cin>>lvl[i].first;
lvl[i].second = i+1;
}
cpy = lvl;
sort(cpy.begin(), cpy.end(), sortbygreater);
ll time=1;
for(ll i=0; i<n; i++){
cpy[i].first = time;
time++;
}
sort(cpy.begin(), cpy.end(), sortbysec);
for(ll i=0; i<n; i++){
cout<<cpy[i].first<<' ';
}
cout<<'\n';
}
return 0;
}

whats wrong with this code please anyone help,as its printing extra
#include
#include<bits/stdc++.h>
using namespace std;

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
int a[n],c[n];
for(int i=0;i<n;i++){
cin>>a[i];
c[i]=a[i];

}
sort(a,a+n);
reverse(a, a+n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(c[i]==a[j]){
cout<<j+1<<" ";
}
}
}
cout<<"\n";

}

return 0;

}

1 Like

What if a.second == b.second ?
This was mentioned in the problem.

I am not aware of CPP, but I guess this is causing issue.

1 Like

This implementation would time out. This is absolutely not the way to solve this problem.

My Code is Giving Wrong Answer, even Though Logic Seems correct to me and sample test cases are right . Pls Help me
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define i(n) int n;cin>>n;for(int i=0;i<(n);i++)cin>>arr[i];
#define f(arr,n) int arr[n]={0}; for(int i=0;i<n;i++)cin>>arr[i];
#define w(t) int t;cin>>t;while(tâ€“)
#define c(n) for(int i=1;i<=n;i++)cout<<arr[i]<<" ";
#define yes cout<<â€śYESâ€ť<<endl
#define no cout<<â€śNOâ€ť<<endl
const int MAXX = 1e9 + 7;
void solve(){
int n;
cin>>n;
int arr[n] = {0};

for (int i = 0; i < n; i++)
{
cin>>arr[i];

}
//Patients with More Illness and Ahead in Queue are Treated First

int cnt[1001] = {0};
int occurences[n] = {0};
for (int i = 0; i < n; i++)
{
occurences[i] = cnt[arr[i]];
cnt[arr[i]]++;
}
int preFixsum[1001] = {0};
preFixsum[1000] = cnt[1000];
for (int i = 999; i >= 0; i--)
{
preFixsum[i] = preFixsum[i+1] + cnt[i];
}
for (int i = 0; i < n; i++)
{
cout<<preFixsum[arr[i]+1] + occurences[i] + 1<<" ";
}
cout<<endl;

}
signed main(){
int t;
cin>>t;
while (t--)
{
solve();
}

return 0;
}

Can anyone help in making my approach more efficient, i was getting TLE, i think the code is correct but dunno how to optimise it.
codechef.com/viewsolution/43032977

You might want to optimise your code.

int x = distance(arr, find(arr, arr + a, dup[a-wow]));

What does this do?
Because, except that, I donâ€™t find anything that consumes time.

in setterâ€™s solution if we take vector<vector<int,2>> temp; and in comparator function we use (vector<int,2> a,vector<int,2> b) then it shows error.
but if we use array itâ€™s fine. plz help, I am not much familiar with STL.

I tried it in the below way, I got TLE, how to optimise it? please help me out!

for _ in range(int(input())):
N = int(input())
no = list(map(int,input().split()))
a = no.copy()
an = list()
for i in range(0,N):
an.append(0)

no.sort(reverse=True)
j=1
for i in no:
ind  = a.index(i)
an[ind]=j
j+=1
a[ind]='a'
for y in an:
print(y,end=" ")
print()

This is an O(N^2) loop. Try using a pair or a triple to store the indices. You can even look into other submissions for better understanding.

Oh so this canâ€™t be optimised. Thank you suman!

I think you should break from the second for loop after finding the index.

Even that would result in TLE for worst case input.

Can someone please tell me where my code is going wrong.

#include<bits/stdc++.h>
using namespace std;
#define int long long

bool sortDesc(const pair<int,int> &a, const pair<int,int> &b) {
return (a.first > b.first);
}

bool sortBySec(const pair<int,int> &a, const pair<int,int> &b) {
return (a.second < b.second);
}

int32_t main() {

int T;
cin >> T;

while (T--) {

int N, x;
cin >> N;

vector<pair<int, int>> A;

for (int i = 0; i < N; i++) {
cin >> x;
A.push_back({x, i});
}

sort(A.begin(), A.end(), sortDesc);

for (int i = 0; i < N; i++) {
A[i].first = i+1;
}

sort(A.begin(), A.end(), sortBySec);

for (int i = 0; i < N; i++) {
cout << A[i].first <<" ";
}

cout << '\n';

}

return 0;

}