Arrogant Students

Last Updated on April 14, 2022 by Ria Pathak

Concepts Used:

Stacks

Difficulty Level:

Hard.

Problem Statement :

Sachin is teaching a group of N students. Now every student has an arrogance level. He make all the N students lined up in a row. Now what he saw was a student was forcefully handing over his assignments to the person closest and in front of him with a lower arrogance level. So if the ith students hands over his assignments to the jth student then Sachin reducts j−i+1 marks from the class discipline.
Find the number of marks deducted after some students hand over their assignments to others.

See original problem statement here

Test Case:

Input:
1
5
1 2 3 2 1

Output:
7

Explanation:
Student standing at index 0 is the smallest and hence does not have any other student with less arrogance number than him. So, he cannot give his assignment to anybody;
Student at index 1 gives his assignment to the student at index 4 as its arrogance number is less than his. So,his contibution in deducted marks is (4-1+1)=4;
Student at index 2 gives his assignment to the one at index 3,hence his contribution becomes (3-2+1)=2;
Similarly,student at index 3 contributs (4-3+1)=2.

Solving Approach :

Starting from the last index we pop elements from stack until we encounter an element lesser than it. In the process, if stack becomes empty that means the student at that particular index does not give his assignment to any other student.We keep pushing elements to the stack.

Solutions:

#include <bits stdc++.h="">
using namespace std;
#define MOD 1000000007
void solve()
{
    long long n, i, j, ans, t;
    cin >> n ;
    vector<long long=""> a(n);
    for (i = 0; i < n; i++) cin >> a[i];
    stack<pair<long long,="" long=""> > st;
    ans = 0;
    for (i = n - 1; i >= 0; i--) {
        while (!st.empty() && st.top().first >= a[i])
                    st.pop();
        if (!st.empty())
                { 
                ans = (ans + (st.top().second - i + 1)) % MOD;
                }
        st.push(make_pair(a[i], i ));
    }
 cout << ans << "\n";
}
int main()
{  
    int t;
    cin>>t;
    while(t--)
    {
    solve();
    }
    return 0;
}

import java.util.*;
public class Solution {
    final static int M=1000000007;
    public static void solve(){
        Scanner sc=new Scanner(System.in);
        int n, i,j;
        long ans, t;
            n=sc.nextInt();
        ArrayList<long> a=new ArrayList<long>();
        for (i = 0; i < n; i++) 
        a.add(sc.nextLong());
        Stack<pair> st = new Stack<pair>();
        ans = 0;
        for (i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && st.peek().first>= a.get(i))
            st.pop();
            if (!st.isEmpty())
                    { 
                    ans = (ans + (st.peek().second - i + 1)) % M;
                    }
            st.push(new Pair(a.get(i), i ));
        }
        System.out.println(ans);
    }
    public static class Pair
    {
        long first;
        long second;
        public Pair(long first, long second)
        {
            this.first = first;
            this.second = second;
        }
    }
    public static void main(String args[])
    {  
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0)
        {
            solve();
        }
        }   
}

# your code goes here
for _ in range(int(input())):
    mod = 1000000007
    n = int(input())
    a = list(map(int, input().split()))
    st = []
    ans = 0
    for i in range(n-1, -1, -1):
        while len(st) and st[-1][0] >= a[i]:
            st.pop()
        if len(st):
            ans = (ans + (st[-1][1] - i + 1)) % mod
        st.append([a[i], i])
    print(ans)

[forminator_quiz id="1923"]

This article tried to discuss the concept of Stacks. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming.