FCF2P3 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Pritish Priyatosh Nayak

Tester: Sibasish Ghosh

Editorialist: Pritish Priyatosh Nayak

DIFFICULTY:

Easy

PREREQUISITES:

Implementation

PROBLEM:

Given a dynamic array of size N. Process B-1 queries where you have to add a new number to the array and for each query print out the sum of the smallest M numbers in the array.

EXPLANATION:

It’s solution is quite a popular algorithm.

Simply keep a priority queue and the max size of the priority queue should be M.
Also keep another variable sum to keep track of the sum of elements currently stored in the priority queue.

Whenever you need to add a new element , check if this element is greater or smaller than the biggest element stored currently in the priority queue.
If it’s smaller, then pop out the max element and subtract it’s value from the sum and add the current element to priority queue and also add it’s value to sum.
If it’s bigger, then no need to do anything.
After doing the above steps , just print the sum value for each query.

Complexity is O((B+N)logM).

See the tester/setter solution for implementation.

SOLUTIONS:

Setter's/Editorialist's Solution 
#include<bits/stdc++.h>
#define int long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repr(i,x,y) for(int i=x;i>=y;i--) 
#define mod 1000000007
using namespace std;
 
void Onigiri()
{
  int n,m,k;
  cin>>n>>k>>m;
  int a[n];
  rep(i,0,n)
  cin>>a[i];
  
  int b[k-1];
  rep(i,0,k-1)
  cin>>b[i];
 
  multiset<int,greater<int>> ms;
  int sum=0;
 
  rep(i,0,n)
  {
    if(ms.size()==m)
    {
      if(a[i]>*ms.begin())continue;
      else {
        sum-=*ms.begin();
        ms.erase(ms.begin());
        ms.insert(a[i]);
        sum+=a[i];
      }
    }
    else{
      ms.insert(a[i]);
      sum+=a[i];
    }
  }
 
  cout<<sum<<" ";
  rep(i,0,k-1){
    if(b[i]>*ms.begin()){
      cout<<sum<<" ";
    }
      else {
        sum-=*ms.begin();
        ms.erase(ms.begin());
        ms.insert(b[i]);
        sum+=b[i];
        cout<<sum<<" ";
      }
    
  }
}
signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
   int t=1; 
   cin>>t;
 
   while(t--)
   {Onigiri();cout<<"\n";}
 
   cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
   return 0;
}
Tester's Solution 
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    signed main()
    {
       ios_base::sync_with_stdio(false);cin.tie(NULL);
  
       int t,sumn=0,sumk=0;
       cin>>t;
       
       assert(t>=1&&t<=1000);
     
       while(t--)
       {
       		int n,k,m;
       		cin>>n>>k>>m;
       
       		sumn+=n;
       		sumk+=k;
     
       		assert(n>=1&&n<=100000);
       		assert(k>=2&&k<=100000);
       		assert(m>=1&&m<=n);
       		assert(sumn<=100000);
       		assert(sumk<=100000);
     
       		int a[n],b[k-1];
     
       		for (int i = 0; i < n; ++i)
       		{
       			cin>>a[i];
       			assert(1<=a[i]&&a[i]<=100000);
       		}
     
       		for (int i = 0; i < k-1; ++i)
       		{
       			cin>>b[i];
       			assert(1<=b[i]&&b[i]<=100000);
       		}
     
       		priority_queue<int> pq;
       		int sum=0;
       		for (int i = 0; i < n; ++i)
       			pq.push(a[i]),sum+=a[i];
       		
       		while(pq.size()>m)
       		{
       			sum-=pq.top();
       			pq.pop();
       		}
     
       		cout<<sum<<" ";
     
       		for (int i = 0; i < k-1; ++i)
       		{
       			sum+=b[i];
       			pq.push(b[i]);
       			sum-=pq.top();
       			pq.pop();
     
       			cout<<sum<<" ";
       		}
     
       		cout<<'\n';
       }
     
     
       cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
       return 0;
    }
1 Like