PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Surya Prakash and Akash Bhalotia
Tester: Samarth Gupta
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
None
PROBLEM
Given powers of N people standing in the queue in the array A, the following happens every second until the queue is not empty.
- The person in front of the queue uses the ATM and then leaves the queue.
- After the first step, if the queue is empty, the process stops. Otherwise, for each person from left to right (except for the first person in the queue), if the person has a \textbf{strictly greater} power level than the person in front of him, he will overtake the person in front, i.e. their positions get swapped. Note that the overtaking happens one after the other from left to right, i.e. state of the queue changes after every overtake.
For each person, find the time at which they will use the ATM.
QUICK EXPLANATION
- In i-th minute, the person with maximum power among first min(N, 2*i-1) shall use ATM, since only first min(N, 2*i-1) positions can reach front of queue in i seconds.
- This process can be simulated using a max heap, breaking ties by original position in the queue.
EXPLANATION
Let’s assume person p has the larger power than all people in front of him. Then we can see that until p-th person is not at front of the queue, he shall always overtake in the second step. If there were x people before person p before this second, now there can be at most x-2 people before him. So every second, this person moves 2 units closer to the start of the queue. This person cannot move to head any faster.
Hence, after \lceil x/2 \rceil-th second, this person shall be in front of the queue.
Generailization
Earlier, we tried to compute when person p reaches the front of the queue. Now, let’s try finding the set of people, who can reach the front of the queue in the first i seconds.
Before the first operation, only the first person can be at the start of the queue.
Before the second operation, Any from the first three people can be at the start of the queue.
Before the third operation, Anyone among the first five people can reach start of queue.
We can generalize to see that before i-th second, anyone from the first min(N, 2*i-1) people can reach the start of the queue if they have maximum power.
Let’s consider the person with maximum power among the first min(N, 2*i-1) people. This person always overtakes due to maximum power so this person must be at the start of the queue if not already removed before the i-th operation.
So, for i-th operation, the person having maximum power among the first min(N, 2*i-1) people in the original queue, which is not yet removed, shall be the person at the start of the queue.
Considering example
5
2 3 4 1 5
Before the first operation, only the first person can be at the start of the queue.
Before the second operation, the person with maximum power among the first 3 people, which is the person with power 4, is at the front.
Before the third operation, the person with maximum power among the first 5 people is the person with power 5.
And so on.
Implementation
Let’s assume there’s a data structure DS, which can handle the following operations
- Push: Insert a person with index i and power x
- Poll: Find the person with maximum power, breaking ties by index
Let’s simulate operations one by one. Also, maintain P as the index of first person not included yet. Before the first operation, only the first person is added to DS. After each operation, two more people are added to DS, until all people are present in DS. For each operation, Polling the best person from DS gives the person at the start of the queue.
Above functionality is present in a data structure called Priority Queue, also known as Heap.
TIME COMPLEXITY
The time complexity is O(N*log(N)) per test case.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
struct cmp{
bool operator()(const pair<int, int> &x, const pair<int, int> &y) const{
if(x.first != y.first)return x.first < y.first;
return x.second > y.second;
}
};
void solve(){
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
vector<int> ans(n);
set<pair<int, int>, cmp> st;
st.insert({a[0], 0});
for(int i = 1, j = 1; i <= n; i++){
int id = st.rbegin()->second;
st.erase({a[id], id});
ans[id] = i;
if(j < n){
st.insert({a[j], j}); ++j;
}
if(j < n){
st.insert({a[j], j}); ++j;
}
}
for(int i = 0; i < n; i++){
if(i)cout << " ";
cout << ans[i];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
for(int i = 0; i < t; i++){
if(i)cout << '\n';
solve();
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
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) {
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;
}
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 readEOF(){
assert(getchar()==EOF);
}
#define N 200005
int seg[4 * N][2];
void update(int st, int l, int r, int idx, int val)
{
if(l == r)
{
seg[st][0] = val;
seg[st][1] = l;
return;
}
int mid = (l+r)/2;
if(idx <= mid)
update(2*st, l, mid, idx, val);
else
update(2*st + 1, mid+1, r, idx, val);
if(seg[2*st][0] >= seg[2*st + 1][0])
seg[st][0] = seg[2*st][0], seg[st][1] = seg[2*st][1];
else
seg[st][0] = seg[2*st + 1][0], seg[st][1] = seg[2*st + 1][1];
}
pair<int, int> query(int st, int l, int r, int ql, int qr){
if(l > qr || r < ql){
return {-1, 0};
}
if(l >= ql && r <= qr)
return {seg[st][0], seg[st][1]};
int mid = (l + r)/2;
pair<int, int> p = query(2*st, l, mid, ql, qr);
pair<int, int> q = query(2*st + 1, mid + 1, r, ql, qr);
if(p.first >= q.first)
return p;
return q;
}
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
t = readIntLn(1, 20000);
int sum = 0;
while(t--){
int n;
n = readIntLn(1, 200000);
sum += n;
assert(sum <= 2e5);
vector<int> vec(n + 1);
for(int i = 1 ; i <= n ; i++){
if(i == n)
vec[i] = readIntLn(1, n);
else
vec[i] = readIntSp(1, n);
update(1, 1, n, i, vec[i]);
}
vector<int> ans(n + 1);
for(int i = 1 ; i <= n ; i++){
pair<int, int> p = query(1, 1, n, 1, min(2*i - 1, n));
ans[p.second] = i;
update(1, 1, n, p.second, 0);
}
for(int i = 1 ; i <= n ; i++)
cout << ans[i] << " ";
cout << '\n';
}
readEOF();
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class ATMQ{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
Person[] P = new Person[1+N];
for(int i = 1; i<= N; i++)P[i] = new Person(i, ni());
PriorityQueue<Person> maxHeap = new PriorityQueue<>();
int ptr = 1;
for(int i = 1; i<= N; i++){
int upto = Math.min(2*i-1, N);
while(ptr <= upto)maxHeap.add(P[ptr++]);
Person front = maxHeap.poll();
front.time = i;
}
for(int i = 1; i<= N; i++)p(P[i].time+" ");pn("");
}
class Person implements Comparable<Person>{
int idx, power, time;
public Person(int i, int p){
idx = i;
power = p;
time = -1;
}
public int compareTo(Person p){
if(power != p.power)return Integer.compare(p.power, power);//Person with larger power first
return Integer.compare(idx, p.idx);//Breaking ties with index
}
}
//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 ATMQ().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. 
…
… cuz i was too hung up on the counting problem