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

From

Oleg I. Khovayko ()

To

Anthony Volkov

Date

2002-12-09T19:05:26Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

Anthony Volkov wrote:
> 
> 
> Есть такое предложение:

Что-то я недопонял в твоем алгоритме.
Давай на примере. Пусть есть матрица:

0:  -1   0   1
1:   0   0   0
2:   1   0  -1

> 
> 1) Найти суммы полных строк

Находим. Получаем все нули:

> 2) Найти среди них максимальную и минимальную

Ни того, ни другого не нашли. Что дальше делать будем?

> 3) Определить диапазон строк, в который входит максимальная, но не входит
> минимальная.

Хорошо. Предположим, что максимальная сумма у строки 0.
Каков диапазон строк для этой суммы? Очевидно, [0..2]!

> 4) Ту же операцию провести для столбцов.

Сделали. Тоже получили [0..2].

> 5) Решение = персечение получившихся диапазонов.

Итого, решение - вся матрица. То есть считается, что макс. сумма = 0.
На самом же деле, есть два эквивалентных решения: (2,0,2,0) и (0,2,0,2),
где сумма равна 1.

> 
> Критика принимается в полной мере и даже приветствуется.

Ну вот она, критика...

------------------------

На самом деле, я придумал, как оптимизировать вычисление суммы 
произвольного прямоугольника для переборной задачи. Если площадь
умеем считать быстро, то получится 4 вложеных цикла до сотни, то есть 
100 миллионов операций. Это порядка десятков секунд времени.
Что явно менее 15 минут лобового решения.

А быстро сумму прямоугольника считать можно вот как:

1. Заводим дополнительную таблицу "с рамочкой" размером 102x102 из 
int-ов, где каждая клетка x[i+1,j+1] содержит сумму чисел в 
прямоугольнике (0,0,i,j). То есть нулевые столбец и строка будут 
содержать нули. Такая вспомогательная матрица считается очень 
быстро методом ДП. Если надо, процедуру напишу.

Пример: Входная матрица:

1 2
3 4

матрица x:

0  0  0  0
0  1  3  3
0  4 10 10
0  4 10 10


2. Легко видеть, что сумма любого прямоугольника (I,J,i,j)
есть:
S = x[i+1,j+1] + x[I,J] - x[I,j+1] - x[i+1,J]

(I,J) - левый верхний угол, (i,j) - правый нижний.


-- 
#include <best/regards.hpp>
Oleg I. KHOVAYKO  
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
 * Origin: National Center for Biotechnology Information (2:5020/400)