LUNCHTIM - Editorial

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:

  1. 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.

  1. 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';
    }
}
6 Likes

Even n * n submissions have passed all the test cases!
Here’s mine: n * n solution Solution: 44214102 | CodeChef
n * lg(n) solution: Solution: 44216157 | CodeChef

14 Likes

Weak cases!

@admin @iceknight1093 n^2 solutions are passing. Look at this one - Solution: 44228566 | CodeChef

5 Likes

you are right I just checked lol…

3 Likes

F in the chat for all those (including me :frowning_face:) who thought a brute force would fail for second subtask.

13 Likes

yaaa broo… :joy:

What the heck why do n*n passed? Weak cases. I saw a spike in submissions on C during the contest and was kinda surprised to see that so many people knew stack tactics and implemented them fast enough, kinda felt left behind lol, but now I know xD.

Btw here is my honest O(nlogn) solution.

I am doing the counting online using map individually for left and right halves. Same approach for NGE with a slight modification.

https://www.codechef.com/viewsolution/44205335

5 Likes

Asking for rejudging of the solutions with improved testcases.

9 Likes

This has to be done.

1 Like

@admin plz redudge so that we can know our actual standing

3 Likes

n^2 solutions aren’t just passing, they are passing with 0.04 sec. I guess even n^3 solution might pass.

1 Like

submissions division wise: Div 1 - ~150, Div 2 - ~ 1600, DIV - 3 ~ 1100

Can’t agree enough

F!! Lol

Please, rejudge this problem with proper inputs or make the round unrated. I’ve solved the problem among first 20 people in Div2 using the stack idea and got ranked among top 115, it’s no problem of mine, but if you state that N^2 won’t pass in editorial, do you even check whether it actually passes or not? The last person to come up with an O(N log N) or the ideal O(N) solution got at least a 100-150 (most likely much greater than this) lower rank than they should have. This just makes the contest completely unfair and demoralizes the participants who have actually spent time coming up with an optimal approach, just to get penalized for not attempting a trivial solution.

If rejudging is against the rules, than make the round unrated - simple as that.

2 Likes

Don’t know how, but your nlgn solution works slower than n*n on Test Cases 3 and 4. Just noticed it. Definitely poor test cases

Asking for reduging if not possible than make this contest unrated.

Plz plz plz Can anyone help me out why my code is not working, Same logic my friend applied and he got AC. But I am getting WA why?? Please help me out.
`

        int tc=sc.nextInt();
        StringBuilder sb=new StringBuilder();
        while(tc-->0) {
            int n=sc.nextInt(), ht[]=new int[n],arr[]=new int[n];
            for(int i=0;i<n;i++) ht[i]=sc.nextInt();
            for(int i=0;i<n;i++) {
                if(ht[i]==-1) continue;
                int j=i+1;
                for(;j<n && ht[j]<=ht[i];j++) arr[i]+=(ht[j]==ht[i])?1:0;
                for(int k=i+1;k<j;k++) if(ht[i]==ht[k]) { arr[k]=arr[i]; ht[k]=-1; }
            }
            for(int i=0;i<n;i++) sb.append(arr[i]).append(" ");
            sb.append("\n");
        }
        System.out.println(sb);`

Your code will fail in the test case
1
7
3 3 2 3 2 2 3
Output shoul be: 3 3 0 3 1 1 3
But your code is giving: 3 3 2 3 2 2 3
Its because you are initializing -1 to ht[k] if(ht[i]==ht[k]) which is initializing all the 3’s to -1 in the given example which leds to wrong answer.

1 Like

The editorial is very explanatory. Thank you for posting this.