Problem Link:

Contest
Question

Author: [Raj Pate]

DIFFICULTY:

MEDIUM

PREREQUISITES:

ARRAY ,SLIDING WINDOW

PROBLEM:

On the lush alien world of Pandora live the Na'vi beings who appear primitive but are highly evolved.Doctor Grace runs a project which allows humans to transform in Avatar. Jake a paralyzed former Marine becomes mobile again through one such Avatar. Jake has been given a mission to become friends with the Na'vi people by transforming into Avatar.

The project runs for N days where on each day Jake can transform into Avatar for a specific amount of time. Through her experience, Doctor Grace can predict the transformation time of Jake for maximum K days. After each prediction, the next prediction occurs after F days.

Find the maximum Avatar time in each prediction.

EXPLANATION:

Observations: - Checkup is happening after every F days. - Out of f days trasformation can be predicted for max k days.

Approach: - We can use sliding window approach such that window slides after every F days and first k days of every F days can be choosen for a search of max element. - We used the deque to store the required index of max element after every iteration. - Whenever the max element comes we pop_back the element less than that element from the deque such that only the maximum element left at the back of the deque. - Corner case is there for the elements after the every possible window size. - After that we have the array of max element in every k interval. - Then we print the element in the interval of f elements.

TIME COMPLEXITY:

O(N) per test case.

CODE:

//JAY SHREE RAM

#include <bits/stdc++.h>
using namespace std;

void slidingWindowMaximum(vector<int>nums, vector<int>&ans, int k){
    int n=nums.size();
    deque<int>dq;
    for(int i=0;i<nums.size();i++){
        if(!dq.empty() && dq.front()==i-k){
            //sliding window 
            dq.pop_front();
        }
        while(!dq.empty() && nums[dq.back()] < nums[i]){
            //removing lesser element than current element
            dq.pop_back();
        }
        dq.push_back(i);
        if(i>=k-1){
            ans.push_back(nums[dq.front()]);
        }
    }

    vector<int>rem(k-1);
    int mx=0;
    // corner case
    for(int i=0;i<k-1;i++){
        mx=max(mx,nums[n-i-1]);
        rem[k-i-2]=mx;
    }
    for(int i=0;i<rem.size();i++){
        ans.push_back(rem[i]);
    }

}

int main(){
    cin.tie(0), cout.tie(0),ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        vector<int>nums;
        int n,k,f;
        cin>>n>>k>>f;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            nums.push_back(x);
        }
        vector<int>ans;
        slidingWindowMaximum(nums,ans,k);
       
        //here we are printing every f'th element.
        for(int i=0;i<ans.size();i+=f){
            cout<<ans[i]<<" ";
        }cout<<endl;
    }
    return 0;
}