Hakerrank deque i timeout problem – jak zoptymalizować kod?

0

https://www.hackerrank.com/challenges/deque-stl/problem

Mam timeout a już nie wiem co robić, jak zoptymalizować
Z góry dziękuję za pomoc

void printKMax(int A[], int n, int k)
{
	//Write your code here.
    std::deque<int> deqWindow;
    deqWindow.push_back(A[0]);
    
    auto maxIndex = 0;
    
    for(int i = 1; i < n; ++i)
    {
        if(deqWindow.size() == k)
        {
            std::cout<<deqWindow[maxIndex]<<' ';
            deqWindow.pop_front();
            --maxIndex;
            
            if(maxIndex < 0)
            {
                maxIndex = 0;
                for(int ih = 1; ih < deqWindow.size(); ++ih)
                {
                    if(deqWindow[maxIndex] < deqWindow[ih])
                    {
                        maxIndex = ih;
                    }
                }
            }
        }
        
        if(deqWindow[maxIndex] < A[i])
        {
            maxIndex = deqWindow.size();
        }        
        
        deqWindow.push_back(A[i]);
    }
    std::cout<<deqWindow[maxIndex]<<'\n';
}
0

Pro-tip: szukaj nowego max tylko jeśli właśnie wyciągnąłeś stary max z kolejki (plus minus).

1

nie jestem w stanie zrozumieć co ten kod ma niby robić.
Na pewno nie to co opisuje zadanie.

Napis to od nowa zaczynając od właściwego zapełniania i opróżniania deqWindow.

0

Ok sam spróbowałem to zadnie i jest ono o wile trudniejsze niż się wydaje.

Przykładowo taki algorytm jest za wolny i trzeba wymyślić coś lepszego:

#include <iostream>
#include <deque> 
#include <algorithm>
#include <vector>

using namespace std;

void printKMax(const vector<int> arr, int k){
	int i;
    deque<int> mydeque;
    
    for (i = 0; i < k; ++i) {
        mydeque.push_back(arr[i]);
    }
    
    cout << *std::max_element(mydeque.begin(), mydeque.end());
    
    for (; i < arr.size(); ++i) {
        mydeque.pop_front();
        mydeque.push_back(arr[i]);
        cout << ' ' << *std::max_element(mydeque.begin(), mydeque.end());
    }
    cout << '\n';
}

int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
	int t;
	cin >> t;
	while(t>0) {
		int n,k;
    	cin >> n >> k;
    	int i;
    	vector<int> arr(n);
    	for(i=0;i<n;i++)
      		cin >> arr[i];
    	printKMax(arr, k);
    	t--;
  	}
  	return 0;
}
0

Podpowiedź (wycięte to co najbardziej istotne):

void printKMax(const vector<int> arr, int k){
    int i;
    deque<int> indexes;
    for (i = 1; i < k; ++i) {
         … … …
    }

    cout << arr[indexes.front()];

    for (; i < arr.size(); ++i) {
        … … …
        cout << arr[indexes.front()];
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while(t>0) {
        int n,k;
        cin >> n >> k;
    	vector<int> arr(n);
        for(int i=0;i<n;i++)
            cin >> arr[i];
        printKMax(arr, k);
        cout << '\n';
    	t--;
    }
    return 0;
}
0

Ja już napisałem podpowiedź. Nie wiem czy super wydajne, ale przeszło na HackerRank (i nie wiem co to drzewo podziałowe).
Zamortyzowana złożoność O(n).

Podpowiem jeszcze tyle, że przypadek złośliwy, który by dał złożoność O(n^2) to tablica gdzie przeważa ta sama (maksymalna) wartość.
Na szczęście na Hackerrank nie wystąpił.

0
vpiotr napisał(a):

Pro-tip: szukaj nowego max tylko jeśli właśnie wyciągnąłeś stary max z kolejki (plus minus).

Wydaje mi się że tak właśnie robię.

0
Staszek12 napisał(a):
vpiotr napisał(a):

Pro-tip: szukaj nowego max tylko jeśli właśnie wyciągnąłeś stary max z kolejki (plus minus).

Wydaje mi się że tak właśnie robię.

W takim razie jedyne co mi przychodzi do głowy to to że gdzieś ten maxIndex zaczyna mieć niewłaściwe wartości.
Co na pierwszy rzut oka nie jest możliwe.
W moim rozwiązaniu korzystam z wartości zamiast z jej indeksu - wtedy nie ma takiego problemu.

0

zmieniłem index na iterator - też nie działa, tj timeout jak jest tak był

void printKMax(int A[], int n, int k)
{
	//Write your code here.
    std::deque<int> deqWindow;
    
    for(int i = 0; i < k; ++i)
    {
        deqWindow.push_front(A[i]);
    }
    
    const auto &getMaxID = [&]()
    {
        return std::max_element(deqWindow.begin(), deqWindow.end());
    };
    
    auto maxIndexItr = getMaxID();
    
    std::cout<<*maxIndexItr<<' ';
    
    for(int i = k; i < n; ++i)
    {
        deqWindow.pop_back();
        deqWindow.push_front(A[i]);
        
        if(maxIndexItr == deqWindow.end())
        {
            maxIndexItr = getMaxID();
        }
        else
        {
            if((*maxIndexItr) < A[i])
            {
                maxIndexItr = deqWindow.begin();
            }
        }
        
        std::cout<<*maxIndexItr<<' ';
        
    }
    std::cout<<'\n';
}

0

Ten kod ma złożoność kwadratową. To jest to samo co ci podałem na tacy, ale brzydziej napisane.
Musisz wymyśleć metodę by obliczanie maksimum z deqWindow maiło złożoność czasu stałego a nie liniowego.
Nie jest to proste do wymyślenia, ale się da.

1 użytkowników online, w tym zalogowanych: 0, gości: 1