Олимпиадные задачи.

[lim0n]

ewert в сообщении #343293 писал(а):

...что я не понимаю алгоритм (ввиду его непрозрачности...

Алгоритм прост: используется массив для сохранения "состояний" границ клеток доски. Значение "состояния" границы зависит от количества примыкающих к ней невырезанных клеток (НК):
$3$ - НК с обеих сторон (начальное состояние);
$1$ - НК с одной стороны (плюс к периметру);
$-1$ - вырезанные клетки с обеих сторон, (внутри фигуры, минус из периметра).

Алгоритм не чувствителен к размеру доски (динамическую инициализацию массива, на что вы обратили внимание, можно заменить на статическую, но это выглядело бы очень страшно), связанности фигуры (вся надежда на соблюдение условий задачи), результат имеем после ввода координат очередной клетки.
Минус - большой расход памяти $2n(n+1)$, где $n$ - размер стороны доски.

[ewert]

lim0n в сообщении #343418 писал(а):

Алгоритм прост: используется массив для сохранения "состояний" границ клеток доски. Значение "состояния" границы зависит от количества примыкающих к ней невырезанных клеток (НК):
$3$ - НК с обеих сторон (начальное состояние);
$1$ - НК с одной стороны (плюс к периметру);
$-1$ - вырезанные клетки с обеих сторон, (внутри фигуры, минус из периметра).

Идея понятна и даже симпатична, но реализована неполноценно и потому работать не будет. Если говорить о границе не оставшейся фигуры, а вырезанной части доски, то она состоит из отрезков, находящихся или внутри доски, или по её краям. Так вот, Вы по ходу второго цикла прибавляете и те, и другие. Между тем как на самом деле внешние отрезки надо, наоборот, вычитать. Для этого достаточно немножко дополнить первый двойной (инициализирующий) цикл.

Кроме того, я не вполне уверен, что там всё в порядке с границами. Во всяком случае, в строчке

int vert[9][8], hor[9][8];

одну из пар 9 и 8 надо явно переставить. Хотя я в детали не вникал.

Да, кстати, насчёт оптимизации. Основное время у Вас занимает (если клеток вырезано немного) инициализация. Не знаю, как в Сях, но в Паскале есть процедура FillChar, позволяющая этот процесс существенно ускорить. Типа
FillChar(vert, SizeOf(vert), #3).

[lim0n]

Естественно, на каких-то наборах данных всё было протестировано.
Единственная несущественная опечатка (недостаточный размер поля вывода) - в printf("%1d: ", i+1);.
Размерности массивов - 9 (вертикальных границ) x 8(строк), 9 (горизонтальных границ) x 8 (столбцов).

ewert писал(а):

Между тем как на самом деле внешние отрезки надо, наоборот, вычитать.

Наверное, я и шахматную доску вижу не так.
Выпиленная фигура - единственная клетка в верхнем левом углу доски. Эта фигура состоит из 2-х отрезков, находящихся внутри доски, и 2-х - по её краям. Каков будет её (фигуры) периметр? $-1-1+1+1=0$?

ewert писал(а):

... в Паскале есть процедура FillChar

Да, в C есть аналог - memset.

[ewert]

lim0n в сообщении #343434 писал(а):

Выпиленная фигура - единственная клетка в верхнем левом углу доски. Эта фигура состоит из 2-х отрезков, находящихся внутри доски, и 2-х - по её краям. Каков будет её (фигуры) периметр? $-1-1+1+1=0$?

я, может, и не в тему отвечу (лень вникать), но. Естественно, в предыдущем сообщении подразумевалось, что переменная result должна инициализироваться не нулём, а 32-мя, естественно.

Ваш алгоритм основан на том, что на каждом шаге добавляется несколько внутренних отрезков, а потом при необходимости лишние (т.е. ранее необоснованно добавленные) устраняются. И это замечательно. Но, во-первых, сперва надо инициализировать исходное к-во уже имеющихся отрезков границы. А во-вторых -- теряющиеся время от времени внешние отрезки тоже нельзя забывать исключать.

[lim0n]

ewert в сообщении #343439 писал(а):

Ваш алгоритм основан на том, что на каждом шаге добавляется несколько внутренних отрезков, а потом при необходимости лишние (ранее добавленные) устраняются.

Абсолютно верно, только надо уточнить, к чему относить слово "внутренние". При добавлении новой клетки к вырезанной фигуре, к периметру прибавляются 1 (или -1) в зависимости от того, являются ли соответствующие границы (отрезки) добавленной клетки внешними (или внутренними) по отношению к самой вырезанной фигуре.
Timeline некоторой границы между клетками:
(-3) - находится на доске;
(1) - стала внешней границей выпиленной фигуры;
(-1) - оказалась внутри выпиленной фигуры.

  3   3
3 . 3 . 3 ... result = 0
  3   3
  ...

  1   3
1 х 1 . 3 ... result = 0+1+1+1+1 = 4
  1   3
  ...

  1    1
1 х -1 х 1 ... result = 4-1+1+1+1 = 6
  1    1
  ...

Это также работает и для клеток на границах доски, с той разницей, что границы этих клеток (с внешним миром?) никогда не станут внутренними по отношению к вырезанной фигуре.
Отсюда и инициализация переменной result - нет вырезанной фигуры, нет и периметра (result=0).

-- Пн авг 09, 2010 19:16:53 --

Ещё пример.

  3   3   3
3 . 3 . 3 . 3 ... result = 0
  3   3   3
  ...

  1   3   3
1 x 1 . 3 . 3 ... result = 0+1+1+1+1=4
  1   3   3
  ...

  1   3   1
1 x 1 . 1 x 1 ... result = 4+1+1+1+1=8
  1   3   1
  ...

  1    1    1
1 x -1 x -1 x 1 ... result = 8-1-1+1+1=8
  1    1    1
  ...

[ewert]

lim0n в сообщении #343451 писал(а):

При добавлении новой клетки к вырезанной фигуре, к периметру прибавляются 1 (или -1) в зависимости от того, являются ли соответствующие границы (отрезки) добавленной клетки внешними (или внутренними) по отношению к самой вырезанной фигуре.

А она (вырезаемая клетка) у Вас понятия не имеет, кто из её соседей является вырезаемым и кто нет. Её это даже и не интересует. В частности, она понятия не имеет, кто из её сторон принадлежит границе всей доски, а кто -- нет. Между тем это -- существенно.

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

Вы бы всё же добавили пару цикликов к своей инициализации.

[lim0n]

ewert в сообщении #343466 писал(а):

...

Последний пример: в доске 2х2 вырезаются все клетки (все они, по Вашей терминологии, граничные):

. .
. . result=0

x .
. . result=0+1+1+1+1=4

x x
. . result=4-1+1+1+1=6

x x
x . result=6-1+1+1+1=8

x x
x x result=8-1-1+1+1=8

Что тут не так?

[ewert]

Всё так, просто мы разные задачи решали: я считал периметр оставшейся фигуры, а Вы, как выяснилось -- вырезанной.

[Circiter]

Как эффективней найти длину песечения двух целочисленных отрезков $[a;\ b]$ и $[c;\ d]$? Сейчас я её отыскиваю как $\min(b,\ d)-\max(a,\ c)+1$, но согласно PAV'у, ветвления, использующиеся функциями минимума/максимума, есть зло.

[ewert]

Простейший вариант:

  l := b * byte(b<=d) + d * byte(d<=b) -
       a * byte(a>=c) - c * byte(c>=a) + 1;

Но это, конечно, зависит от языка и от транслятора. Впрочем, логические значения при любой реализации хранятся, скорее всего, одинаково. А лучше всего -- написать свои функции min/max в виде ассемблерной вставки, если хочется оптимизировать.

[venco]

Circiter в сообщении #343573 писал(а):

Как эффективней найти длину песечения двух целочисленных отрезков $[a;\ b]$ и $[c;\ d]$? Сейчас я её отыскиваю как $\min(b,\ d)-\max(a,\ c)+1$, но согласно PAV'у, ветвления, использующиеся функциями минимума/максимума, есть зло.

А почему Вы считаете, что функции min и max используют ветвления? Создатели компиляторов тоже знают про скорость исполнения разных инструкций:

#include <algorithm>

int a, b;

int get_min()
{
    return std::min(a, b);
}

_Z7get_minv:
.LFB382:
        movl    b(%rip), %eax
        cmpl    %eax, a(%rip)
        cmovle  a(%rip), %eax
        ret

[Circiter]

2venco

Цитата:

А почему Вы считаете, что функции min и max используют ветвления?

Потому что в той программульке я их сам определил в стиле int max(int Value1, int Value2) {return Value1>Value2?Value1:Value2;}. :)

-- Вт авг 10, 2010 21:44:59 --

Пожалуй, оставлю вычисления с $\max$/$\min$ как наиболее наглядные. :) Все на совести стандартной библиотеки. :)

[venco]

Circiter в сообщении #343606 писал(а):

Все на совести стандартной библиотеки. :)

Скорее, оптимизатора, т.к. в C++ std::min определён также.

[ewert]

А мне вот что любопытно. Команды типа CMOV... -- сравнительно недавние. В первых пентиумах их ещё не было. И как отреагирует современный транслятор (раз уж в него те команды заложены) на процессор всего лишь десятилетней давности?... Нешто попросту заткнётся?...

Хотя того, что переходы в подобных процедурах не нужны -- это, конечно, не отменяет.

[ГАЗ-67]

(Оффтоп)

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