Quiz Test

Concepts Used

Queues.

Difficulty Level

Hard.

Problem Statement :

Ram has recently appeared for his Physics, Maths, and Chemistry quiz where each subject has multiple quizzes. Ram's class teacher asked him to solve a challenge which would allow him some extra marks at his pending assignment work. The arrays [P1,P2,P3...,Pn], [M1,M2,M3...,Mn] and [C1,C2,C3...,Cn] contains the marks obtained by Ram in ith quiz of Physics, Maths and Chemistry respectively. His class teacher asks Ram to calculate the total marks where the value of Ram's ith quiz marks would be the sum of his marks in the ith Physics quiz, ith Maths quiz and ith Chemistry quiz. Ram is quite convinced by the task given by his teacher, but his teacher adds some twist to the task, and now she wants Ram to delete the qth smallest marks once it is answered by Ram. Seeing much complications Ram is confused and needs your help, help Ram to answer all the questions asked by his teacher.

See original problem statement here

EXAMPLE:

Input
3
1 4 6
1 2 3
4 8 9
2
1
4

Output
6
-1

Sample test case explanation
For the first query q=1,
Smallest marks are [1,1,4] for Physics, Maths and Chemistry quiz respectively. 
Therefore the output is 1+1+4=6.
For the second query q>n, therefore the output is −1.

EXPLANATION:

Push the sum of marks in each subject to the priority queue.

For each query pop out the qth element of the priority queue.

Push the rest back to the queue. Follow the code with the help of online coding classes.

SOLUTION:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    long int P[n];
    long int M[n];
    long int C[n];
    for(int i=0;i<n;i++)
        cin>>P[i];
    for(int i=0;i<n;i++)
        cin>>M[i];
    for(int i = 0; i < n; i++)
        cin>>C[i];
    priority_queue<long long int,vector<long long int>,greater<long long int>>pq;
    queue<long long int>qu;
    for(int i = 0; i < n; i++)
        pq.push(P[i] + M[i] + C[i]);
    int Q;
    cin>>Q;
    for(int i = 0; i < Q; i++)
    {
        int q;
        cin>>q;
        if(q > pq.size())
        cout<<"-1"<<endl;
        else
        {
            for(int j = 1; j < q; j++)
            {
                qu.push(pq.top());
                pq.pop();
            }
            cout<<pq.top()<<endl;
            pq.pop();
            while(!qu.empty())
            {
                pq.push(qu.front());
                qu.pop();
            }
        }
    }
}
import java.util.*;
  import java.io.*;
  public class Main {

    public static void main(String args[]) throws IOException {
      Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Long[] P= new Long[n];
        Long[] M= new Long[n];
        Long[] C= new Long[n];

         for(int i=0;i<n;i++)
              P[i]=sc.nextLong();

         for(int i=0;i<n;i++)
              M[i]=sc.nextLong();

         for(int i=0;i<n;i++)
              C[i]=sc.nextLong();



        PriorityQueue<Long> PQ = new PriorityQueue<Long>(); 
        Queue<Long> qu = new LinkedList<Long>(); 
        for(int i=0;i<n;i++){
          Long x=P[i] + M[i] + C[i];
          PQ.add(x);
        }
      int Q=sc.nextInt();
      //sc.nextLine();
     for(int i=0;i<Q;i++){

       int q=sc.nextInt();

       if(q>PQ.size())
       {
           System.out.println(-1);
       }
       else{
           for(int j=1;j<q;j++){
             Long k=PQ.peek();
             qu.add(k);
             PQ.poll();
           }

          Long x1=PQ.peek();
          PQ.poll();
          System.out.println(x1);
         while(!qu.isEmpty())
         {
           Long x=qu.element();
           PQ.add(x);
           qu.remove();
         }
       }

     }

      }

  }

Previous post Play Games 2
Next post Sum Subarray

Leave a Reply

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