GOODPROB от codechef, что такое algo?

Я только решение проблем и пришли на этот одинGOODPROB от codechef, что такое algo?

Учитывая массив А, состоящий из N целых чисел - A1, A2 .... AN. Вы должны найти значение Σ MAX (i, j) * F (i, j), где 1 ≤ i < j ≤ N.

MAX (i, j) определяется как max (Ai, Ai + 1 ... Aj).

F (I, J) определяется как:

F (I, J) будет равен 1, если (Ai&Aj) = Aj or (Ai&Aj) = Ai F (I, J) будет равен 0, в противном случае. Здесь & обозначает побитовый оператор И.

ссылка: GOODPROB

Я написал довольно простое решение и получил 40 баллов, то есть он не может обрабатывать большие входы в нужное время 2 секунды.

Это был мой код

#include <iostream> 
using namespace std; 

int max(int *A, int x,int y){ 
    int m=A[x]; 
    while(x<=y){ 
     if(A[x]>m) 
      m=A[x]; 
     x++; 
    } 
    return m; 
} 

int F(int *A,int i,int j){ 
    return ((A[i]&A[j]) == A[j] or (A[i]&A[j]) == A[i])?1:0; 
    } 
int main() { 
    long N; 
    cin>>N; 
    int *A = new int[N]; 
    for(int i=0;i<N; i++) 
     cin>>A[i]; 
    long m=0; 
    for(int j=0;j<N;j++) 
     for(int i=0;i<j; i++) 
      m+= F(A,i,j)?max(A,i,j)*F(A,i,j):0; 
    cout<<m<<endl; 
    return 0; 
}

Я проверил успешные submitions там, но те заставили меня идти панику. Я даже не представлял такого большого решения для этой довольно простой проблемы. Может ли кто-нибудь придумать решение, достаточно простое для понимания.

источник

2016-08-31 Hritik

Я считаю, используя [ 'станд :: accumulate'] (HTTP://en.cppreference.com/w/cpp/algorithm/accumulate) с лямбдой может обеспечить для этого одно линейное решение. Мольба: Пожалуйста, не тратьте свое время на онлайн-кодовые суждения, скорее попытайтесь участвовать в некоторых реальных проблемах/проектах. –

Спасибо, но проекты в реальном мире довольно длинные, и я не полностью готов для них как в условиях опыта, так и во времени. – Hritik

_ «Я не полностью подготовлен ...» _ Вы не должны верить, что судьи онлайн-кода подготовят вас в любом случае для них. Вы просто узнаете плохие привычки. Работа через несколько хороших книг заставит вас подготовиться к лучшему. Мы храним список хороших книг [здесь] (http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). –

OK Это не дает вам эффективного алгоритма, но раздел комментариев не дает наилучших параметров форматирования.

Я нашел несколько небольших возможностей оптимизации. Вы повторяете заявления иногда, когда это не нужно.

m+= F(A,i,j)?max(A,i,j)*F(A,i,j):0;

Здесь Вы можете сохранить результат F(A,i,j) и вызывать эту функцию в два раза (вызовы функций могут быть дорогими).

return ((A[i]&A[j]) == A[j] or (A[i]&A[j]) == A[i])?1:0;

То же самое с A[i]&A[j]. Вы можете сохранить результат заранее.

Так что только некоторые мелочи в вашем текущем алгоритме. Насколько они помогут/улучшится, вам нужно измерить себя.

источник

2016-08-31 12:24:06 Hayt

Вы находите максимальное значение в диапазоне массива линейно. Выполнение этой задачи O (n) фактор в вашей общей сложности. И поскольку вы используете вложенные циклы и вызываете max изнутри, ваша общая временная сложность будет равна O (n^3).

Вы можете значительно уменьшить этот фактор, используя структуру данных Дерева сегментов. Используя дерево сегментов, вы можете найти максимум в диапазоне от O (log (n)) время. Снижение Общая сложность O (N^2 * LOG (N)) Для обучающей программы на Range Max/Min запрос

Range Minimum Query using Segment Tree

источник

2016-08-31 13:47:15 rishabh

GOODPROB от codechef, что такое algo?

ответ

Смежные вопросы