задачка с acm.uva.es :)

From

Alexey Burdin (2:5012/2.89)

To

Ilia Kantor

Date

2002-12-13T22:54:56Z

Area

RU.ALGORITHMS

> from: /Unknown/
Как после вчерашнего, Ilia ?

 15:03 Понедельник Декабрь 09 2002, Ilia Kantor --> Georgy Plechanov:

 IK> Перебираем все прямоугольники, состоящие из соседних строк

 IK> for(i=0;i<100;i++)
 IK>   for(j=i;j<100;j++)

 IK>     { обработать прямоугольник из строк i..j }
    за N операций? Это как?

    Поясняй, потому что мой алгоритм более тормозной -
    порядка 3/4*N^4 сложений (longint) и N^4 извлечений из массива.
 IK> Итого, алгоритм имеет сложность n^3 = 10^6 операций. Быстрее можно,
 IK> но не так, чтобы намного. Квадратичный алгоритм мне неизвестен, да и
 IK> вряд ли есть.
    [Sorry, skipped]
    Поясни, пожалуйста, алгоритм :) Ничего не понятно.
    Тут почты не было дня 3, сорри, если что пропустил

                Всего хорошего. Alexey.
... А что подyмал кpолик, никто не yзнал,
--- потомy что кpолик был очень воспитанный.
 * Origin: While the angels and the devils (2:5012/2.89)