PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 2
Author: Nguyen Gia Bao
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh
DIFFICULTY:
Easy
PREREQUISITES:
Stack
PROBLEM:
N students stand in a queue, the i-th of them has height h_i. Students i and j (i < j) can see each other if h_k \leq min(h_i, h_j) for every i < k < j. Find, for each i, how many students of the same height as student i are visible to him?
QUICK EXPLANATION:
- Use a stack to find, for each i, the closest student to the left and the right of i who has height \geq h_i.
- With this information, a simple linear dynamic programming solution finds the answer, iterating once from the left and once from the right.
EXPLANATION:
Subtask 1
The condition about when students i and j can see each other can be stated as max(h_{i+1}, \dotsc, h_{j-1}) \leq min(h_i, h_j).
In the case when h_i = h_j, this is the same as max(h_i, h_{i+1}, \dotsc, h_{j-1}, h_j) = h_i
This lets us solve the first subtask by bruteforcing every possible pair of students in \mathcal{O}(n^2). Fix the index of the left student, say i. Let m be the maximum of the current range; initially, m = h_i.
Now, iterate j from i+1 to n. If h_i = h_j, and m = h_i, increase the answer for both students i and j by 1. Finally, update m by setting m = max(m, h_j).
Subtask 2
\mathcal{O}(n^2) is too slow for this subtask - we need something faster.
Fix some student i. Let’s see if we can find out how many students he sees to his left quickly (denoted by left[i]).
Let j < i be the largest index such that h_j \geq h_i (denote jump\_left[i] = j). Suppose we are able to find this fast for every index i. Does this give us a way to solve the problem faster than \mathcal{O}(n^2)? Yes!
There are two cases:
-
h_j > h_i.
Here, student i doesn’t see anyone with the same height to his left, i.e, left[i] = 0.
Proof
Let k < i with h_k = h_i.
If k < j < i, clearly student j blocks k and i from seeing each other.
If j < k < i, j was not the maximum index of a student who is at least as tall as i - a contradiction. So this case cannot happen.
-
h_j = h_i
Here, left[i] = 1 + left[j].
Proof
Let k < i with h_k = h_i.
Of course, we must also have k \leq j - because j < k < i would contradict j being maximal.
If i and k can see each other, then clearly j and k can also see each other, because max(h_k, h_{k+1}, \dotsc, h_j) \leq max(h_k, h_{k+1}, \dotsc, h_j, \dotsc, h_i).
So, i sees everyone who j can see - and in addition, sees j as well.
Hence, left[i] = left[j] + 1.
Note that we assumed a suitable j exists.
What if no such j exists?
If no such j exists, that also means that there cannot be a student with the same height as i, to the left of student i. So, the answer for student i only depends on those on his right, meaning we can simply ignore any i where this is the case.
When no such j exists, set jump\_left[i] = -1.
Putting this together, we have the following solution:
- Find jump\_left[i] for every i.
How?
This is a classic problem which can be solved with a stack.
Let S be an empty stack.
For each i from 1 to N, do the following:
While the stack is not empty:
- Let j = S.top(). If h_j \geq h_i, break.
- Else, pop j from S and continue.
If the stack is empty, jump\_left[i] = -1.
Else jump\_left[i] = S.top().
Push i onto S.
- Iterate i from 1 to N. if jump\_left[i] = -1 or h_{jump\_left[i]} > h_i, set left[i] = 0. Else, set left[i] = 1 + left[jump\_left[i]].
Repeat this procedure from the right to find jump\_right[i] and right[i] for every 1\leq i\leq N.
The final answer for i is then left[i] + right[i].
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
using namespace std;
FILE *fp;
ofstream outfile;
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();
// char g = getc(fp);
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();
// char g=getc(fp);
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,' ');
}
const int minv = 1, maxv = 1e9, maxt = 10, MAX = 100010;
const string newln = "\n", space = " ";
int main()
{
int q = readIntLn(1, 10);
// int q; cin >> q;
while(q--){
int n = readIntLn(1, MAX);
// int n; cin >> n;
vector<pii> v; v.clear();
int a[n + 2]; a[0] = a[n + 1] = 0;
for(int i = 1; i <= n; i++){
int x = (i == n ? readIntLn(minv, maxv) : readIntSp(minv, maxv));
// int x; cin >> x;
a[i] = x;
v.pb(mp(x, i));
}
sort(v.begin(), v.end(), [](const pii& A, const pii& B) {
return A.first > B.first;
});
set<int> s; s.clear();
set<int>::iterator it;
s.insert(0); s.insert(n + 1);
int id[n + 2][2];
for(int i = 0; i < n;){
int j = i;
while(j < n && v[j].first == v[i].first){
s.insert(v[j].second);
j++;
}
j = i;
while(j < n && v[j].first == v[i].first){
it = s.lower_bound(v[j].second);
it--;
if(a[*it] == v[j].first)id[v[j].second][0] = *it;
else id[v[j].second][0] = 0;
it++; it++;
if(a[*it] == v[j].first)id[v[j].second][1] = *it;
else id[v[j].second][1] = n + 1;
j++;
}
i = j;
}
int ans[n + 2][2];
for(int i = 0; i < 2; i++){
ans[0][i] = ans[n + 1][i] = 0;
}
for(int i = 1; i <= n; i++){
// cerr << id[i][0] << " " << id[i][1] << endl;
ans[i][0] = a[i] == a[id[i][0]] ? 1 + ans[id[i][0]][0] : 0;
}
for(int i = n; i >= 1; i--){
ans[i][1] = a[i] == a[id[i][1]] ? 1 + ans[id[i][1]][1] : 0;
}
for(int i = 1; i <= n; i++){
cout << ans[i][0] + ans[i][1] << (i == n ? newln : space);
}
}
assert(getchar()==-1);
}
Tester's Solution
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int main(){
fastio;
int tests;
cin>>tests;
while(tests--){
int n;
cin>>n;
int h[n+1];
// number of left seen and right seen of same height
int le[n+1] = {0}, ri[n+1] = {0};
// closest larger values to left and right
int big_left[n+1] = {0}, big_right[n+1] = {0};
for(int i = 1; i <= n; i++){
cin>>h[i];
big_right[i] = n+1;
}
map<int, int> last; // last seen of height
stack<pair<int,int>> s;
// now we will find closest element to left which is larger
// well known stack solution
for(int i = 1; i <= n; i++){
while(!s.empty() && s.top().first <= h[i]){
s.pop();
}
if(!s.empty()){
big_left[i] = s.top().second;
}
s.push(make_pair(h[i], i));
if(last[h[i]] != 0 && big_left[i] < last[h[i]]){
le[i] = le[last[h[i]]] + 1;
}
last[h[i]] = i;
}
while(!s.empty()) s.pop();
last.clear();
for(int i = n; i >= 1; i--){
while(!s.empty() && s.top().first <= h[i]){
s.pop();
}
if(!s.empty()){
big_right[i] = s.top().second;
}
s.push(make_pair(h[i], i));
if(last[h[i]] != 0 && big_right[i] > last[h[i]]){
ri[i] = ri[last[h[i]]] + 1;
}
last[h[i]] = i;
}
for(int i = 1; i <= n; i++) cout<<le[i] + ri[i]<<" ";
cout<<endl;
}
return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
using namespace std;
using ll = long long;
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int q; cin >> q;
while (q--) {
int n; cin >> n;
vector<int> h(n);
for (auto &x : h)
cin >> x;
stack<int> s;
vector<int> left_jump(n), right_jump(n);
for (int i = 0; i < n; ++i) {
while (!s.empty()) {
auto pos = s.top();
if (h[pos] >= h[i]) break;
s.pop();
}
if (!s.empty()) left_jump[i] = s.top();
else left_jump[i] = -1;
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = n-1; i >= 0; --i) {
while (!s.empty()) {
auto pos = s.top();
if (h[pos] >= h[i]) break;
s.pop();
}
if (!s.empty()) right_jump[i] = s.top();
else right_jump[i] = -1;
s.push(i);
}
vector<int> see_left(n), see_right(n);
for (int i = 0; i < n; ++i) {
if (left_jump[i] == -1 or h[i] != h[left_jump[i]]) continue;
see_left[i] = 1 + see_left[left_jump[i]];
}
for (int i = n-1; i >= 0; --i) {
if (right_jump[i] == -1 or h[i] != h[right_jump[i]]) continue;
see_right[i] = 1 + see_right[right_jump[i]];
}
for (int i = 0; i < n; ++i) {
cout << see_left[i] + see_right[i] << ' ';
}
cout << '\n';
}
}