Как исправить ошибку «из-за истечения времени ожидания» в проблеме Манипуляции с массивами | Hackerrank? - PullRequest
Новая
       14

Как исправить ошибку «из-за истечения времени ожидания» в проблеме Манипуляции с массивами | Hackerrank?

0 голосов
/ 07 мая 2019

Я пытаюсь решить проблему манипулирования массивом на хакерранке, но это в некоторых тестовых случаях показывает «прекращено из-за тайм-аута». Как это может быть исправленным?

Вот ссылка на проблему: https://www.hackerrank.com/challenges/crush/problem

Вот мой кусок кода, пытающийся его решить. 

// Complete the arrayManipulation function below.
long arrayManipulation(int n, vector<vector<int>> queries) {
    ll* a=new ll[n];
    ll k;
    for(k=0;k<n;k++){
        a[k]=0;
    }
    ll i,j,b,c,s;
    long int m=-999999;
    for(i=0;i<queries.size();i++){
        b=queries[i][0]-1;
        c=queries[i][1]-1;
        s=queries[i][2];
        for(j=b;j<=c;j++){
            a[j]=a[j]+s;
            if(a[j]>m)
                m=a[j];
        }
    }
    delete [] a;

    return m;
}

Это один из тестовых случаев, в результате которого «прекращается из-за Тайм-аут». 

Input
10000000 100000
7253005 9867484 26205
933415 3777144 94765
4459151 9562860 92614
2789917 8588211 4461
4044644 5402538 67512
5713942 9159751 16533
9098636 9929072 64666
292166 3522306 31552
894426 9902580 83056
741032 5667470 18090
3359393 5436826 85573
6370240 8401950 79068
1996715 3345743 41927
205681 8652011 46490
210142 2696654 65379
4372756 6194007 79320
4301827 5510540 94307
2991558 7824132 2824
243063 3223110 97250{-truncated-}
<<Plz Download to view the full testcase>>

Expected Output
2490686975

1 Ответ

0 голосов
/ 08 мая 2019

Ответ: Придумайте более быстрый алгоритм.

Это непростая проблема (помечена как «сложная» на Hackerrank, хотя на самом деле это «средняя» IMHO), поэтому не ожидайте, что буквальная реализация алгоритма, как описано, решит ее. Этот алгоритм занимает O (нм) время, но есть простой метод, который занимает всего O (n + m) время. Я кодировал его на Hackerrank в 10 строках кода: он прошел все тестовые случаи с первой попытки.

Я не даю вам решение здесь, так как вы должны решить это самостоятельно, но, кроме инициализации, есть только один проход по m запросам, принимая O ( 1) объем работы для каждого, за которым следует один проход по элементам n , снова принимая O (1) для каждого. Подсказка: думайте дифференцированно.

...