Arrogant Students

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 :

According to data structures and algorithms, 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 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();
        }
        }   
}
Previous post Files
Next post Edge Divide(C, JAVA CODE NOT INCLUDED)

Leave a Reply

Your email address will not be published. Required fields are marked *