BBCANDY - Editorial

editorial
,
1

PROBLEM LINK:

Contest

Setter: a0n0k0i0t
Tester: a0n0k0i0t
Editorialist: a0n0k0i0t

DIFFICULTY:

Easy

PREREQUISITES:

Window sliding, map

Explanation:

Observation:

  • If you buy the i_{th} then you should buy the other candy with minimum cost in the window [i-R, i-L] for optimum solution
  • Answer will be the minimum of cost for each such i.

Subtask 1:

Make an array of each window and find minimum of each window in O(N) and do this for all i (1 \leq i \leq N).

Time complexity:

O(N^2)

Subtask 1:

To find minimum of each window maintain a map of cost of candies and at each pass remove the i-R-1 th cost and add i-L th cost to map. Minimum at each pass is the first element in map. In O(logN)
Do this for all i (1 \leq i \leq N).

Time complexity:

O(N*logN)

SOLUTION

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	// your code goes here
	ll T;
	cin>>T;
	while(T--){
		ll n,l,r;
		cin>>n>>l>>r;
		vector<ll> a(n);
		for(int i=0;i<n;i++)
			cin>>a[i];
		map<ll,ll> mp;
		ll ans=1e9;
		for(int i=0;i<n;i++){
			if(i-r-1>=0){
				mp[a[i-r-1]]--;
				if(mp[a[i-r-1]]==0){
					auto it =mp.find(a[i-r-1]);
					mp.erase(it);
				}
			}
			if(i-l>=0){
				mp[a[i-l]]++;
			}
			if(mp.size()){
				auto it =mp.begin();
				ans=min(ans,it->first+a[i]);
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}