# LUNCHTIM - Editorial

**URL:** <https://discuss.codechef.com/t/lunchtim-editorial/87198>\
**Category:** editorial\
**Tags:** easy, editorial, stack, ltime94\
**Created:** [March 27, 2021, 1:21pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198 "2021-03-27T13:21:14Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![iceknight1093](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@iceknight1093](https://discuss.codechef.com/u/iceknight1093)\
**Post date:** [March 27, 2021, 1:21pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/1 "2021-03-27T13:21:14Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/LUNCHTIM)  
[Contest: Division 1](https://www.codechef.com/LTIME94A/problems/LUNCHTIM)  
[Contest: Division 2](https://www.codechef.com/LTIME94B/problems/LUNCHTIM)  
[Contest: Division 2](https://www.codechef.com/LTIME94C/problems/LUNCHTIM)

_ **Author:** _ Nguyen Gia Bao  
_ **Testers:** _ [Shubham Anand Jain](https://www.codechef.com/users/TheOneYouWant), [Aryan](https://www.codechef.com/users/aryanc403)  
_ **Editorialist:** _ [Nishank Suresh](https://www.codechef.com/users/IceKnight1093)

# 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**
>
> ```cpp
> #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**
>
> ```cpp
> //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**
>
> ```cpp
> #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';
> }
> }
> 
> ```

---

<div class="post-metadata">

**Author:** ![anonym\_chef](https://discuss.codechef.com/user_avatar/discuss.codechef.com/anonym_chef/32/15973_2.png) [@anonym\_chef](https://discuss.codechef.com/u/anonym_chef)\
**Post date:** [March 27, 2021, 5:56pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/2 "2021-03-27T17:56:47Z")

</div>

Even n \* n submissions have passed all the test cases!  
Here’s mine: n \* n solution [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/44214102)  
n \* lg(n) solution: [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/44216157)

---

<div class="post-metadata">

**Author:** ![ishaan\_007](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ishaan_007/32/240517_2.png) [@ishaan\_007](https://discuss.codechef.com/u/ishaan_007)\
**Post date:** [March 27, 2021, 6:30pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/3 "2021-03-27T18:30:29Z")

</div>

Weak cases!

@admin@iceknight1093 n^2 solutions are passing. Look at this one - [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/44228566)

---

<div class="post-metadata">

**Author:** ![dixith417](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dixith417/32/29454_2.png) [@dixith417](https://discuss.codechef.com/u/dixith417)\
**Post date:** [March 27, 2021, 6:34pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/4 "2021-03-27T18:34:59Z")

</div>

you are right I just checked lol…

---

<div class="post-metadata">

**Author:** ![falloutash](https://discuss.codechef.com/user_avatar/discuss.codechef.com/falloutash/32/80193_2.png) [@falloutash](https://discuss.codechef.com/u/falloutash)\
**Post date:** [March 27, 2021, 6:53pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/5 "2021-03-27T18:53:15Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![chand708333333](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@chand708333333](https://discuss.codechef.com/u/chand708333333)\
**Post date:** [March 27, 2021, 6:58pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/7 "2021-03-27T18:58:44Z")

</div>

yaaa broo… 😂

---

<div class="post-metadata">

**Author:** ![isitac](https://discuss.codechef.com/user_avatar/discuss.codechef.com/isitac/32/24644_2.png) [@isitac](https://discuss.codechef.com/u/isitac)\
**Post date:** [March 27, 2021, 7:03pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/8 "2021-03-27T19:03:50Z")

</div>

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](https://www.codechef.com/viewsolution/44205335)

---

<div class="post-metadata">

**Author:** ![mkitkat](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mkitkat/32/23077_2.png) [@mkitkat](https://discuss.codechef.com/u/mkitkat)\
**Post date:** [March 27, 2021, 7:07pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/9 "2021-03-27T19:07:06Z")

</div>

Asking for rejudging of the solutions with improved testcases.

---

<div class="post-metadata">

**Author:** ![isitac](https://discuss.codechef.com/user_avatar/discuss.codechef.com/isitac/32/24644_2.png) [@isitac](https://discuss.codechef.com/u/isitac)\
**Post date:** [March 27, 2021, 7:08pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/10 "2021-03-27T19:08:47Z")

</div>

This has to be done.

---

<div class="post-metadata">

**Author:** ![striver290](https://discuss.codechef.com/user_avatar/discuss.codechef.com/striver290/32/24644_2.png) [@striver290](https://discuss.codechef.com/u/striver290)\
**Post date:** [March 27, 2021, 7:11pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/11 "2021-03-27T19:11:23Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![studtan92](https://discuss.codechef.com/user_avatar/discuss.codechef.com/studtan92/32/27938_2.png) [@studtan92](https://discuss.codechef.com/u/studtan92)\
**Post date:** [March 27, 2021, 7:11pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/12 "2021-03-27T19:11:30Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mkitkat](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mkitkat/32/23077_2.png) [@mkitkat](https://discuss.codechef.com/u/mkitkat)\
**Post date:** [March 27, 2021, 7:14pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/13 "2021-03-27T19:14:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![cubefreak777](https://discuss.codechef.com/user_avatar/discuss.codechef.com/cubefreak777/32/215911_2.png) [@cubefreak777](https://discuss.codechef.com/u/cubefreak777)\
**Post date:** [March 27, 2021, 7:26pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/14 "2021-03-27T19:26:58Z")

</div>

Can’t agree enough

---

<div class="post-metadata">

**Author:** ![ishwar\_100](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ishwar_100/32/93344_2.png) [@ishwar\_100](https://discuss.codechef.com/u/ishwar_100)\
**Post date:** [March 27, 2021, 7:34pm UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/15 "2021-03-27T19:34:54Z")

</div>

F!! Lol

---

<div class="post-metadata">

**Author:** ![nichke](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nichke/32/104885_2.png) [@nichke](https://discuss.codechef.com/u/nichke)\
**Post date:** [March 28, 2021, 12:42am UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/16 "2021-03-28T00:42:24Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![sg1108](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sg1108/32/89772_2.png) [@sg1108](https://discuss.codechef.com/u/sg1108)\
**Post date:** [March 28, 2021, 4:17am UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/17 "2021-03-28T04:17:56Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ultravector](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ultravector/32/24644_2.png) [@ultravector](https://discuss.codechef.com/u/ultravector)\
**Post date:** [March 28, 2021, 4:25am UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/18 "2021-03-28T04:25:59Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![coder0687](https://discuss.codechef.com/user_avatar/discuss.codechef.com/coder0687/32/332230_2.png) [@coder0687](https://discuss.codechef.com/u/coder0687)\
**Post date:** [March 28, 2021, 4:53am UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/20 "2021-03-28T04:53:11Z")

</div>

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);`
```

---

<div class="post-metadata">

**Author:** ![omeshwar\_05](https://discuss.codechef.com/user_avatar/discuss.codechef.com/omeshwar_05/32/323351_2.png) [@omeshwar\_05](https://discuss.codechef.com/u/omeshwar_05)\
**Post date:** [March 28, 2021, 6:02am UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/22 "2021-03-28T06:02:02Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ppatelhemant](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ppatelhemant/32/29265_2.png) [@ppatelhemant](https://discuss.codechef.com/u/ppatelhemant)\
**Post date:** [March 28, 2021, 6:42am UTC](https://discuss.codechef.com/t/lunchtim-editorial/87198/23 "2021-03-28T06:42:17Z")

</div>

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

[Next page](https://discuss.codechef.com/t/lunchtim-editorial/87198.md?page=2)
