основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
Ilya_Porublyov
здесь был не раз


Рег.: 05/22/04
Сообщений: 33
Из: Cherkasy & Kyiv, Ukraine
решение линии японского кроссворда
      #11978 - 08/30/06 02:49 AM

Доброго времени суток.

Дошли до меня такие слухи, вроде когда-то в течение прошлого года где-то на какой-то эйсиэмке была по сути задача анализа линии японского кроссворда (только сформулированная в терминах каких-то закодированных сообщений), и предлагалось решать её при размере линии до 10000 и при ограничениях по памяти 64M, по времени 2sec.

Как человек, волею случая частично связанный с алгоритмами решения японских кроссвордов, я весьма интересуюсь точным условием той задачи, а также предполагаемыми методами её решения.

Только очень прошу не отсылать к (моей же) статье о решении Я.К. с алголиста. Кстати, теперь уже точно знаю, что рассмотренный там метод -- не лучший. Что ж никто не напишет нормальную статью по какому-нибудь более эффективному методу?

--------------------
Ilya Porublyov


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
EfremovAleksei
здесь был не раз


Рег.: 03/05/06
Сообщений: 36
Re: решение линии японского кроссворда [Re: Ilya_Porublyov]
      #11983 - 08/30/06 08:24 AM

На летних сборах - 2004 тоже была такая задача.
А где описаны алгоритмы решения японского кроссворда?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Ilya_Porublyov
здесь был не раз


Рег.: 05/22/04
Сообщений: 33
Из: Cherkasy & Kyiv, Ukraine
Re: решение линии японского кроссворда [Re: EfremovAleksei]
      #11988 - 08/31/06 12:45 AM

Ну, задача со сборов 2004 года тут немножно ни при чём, т.к. она, по-видимому, могла быть решена теми алгоритмами, которые я знаю. А я слышал, вроде на какой-то эйсиэмке требовали более эффективный алгоритм. И меня интересуют подробности именно оттуда.

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

Более подробно о том, где находится моя статья. Прямо на главной странице сайта (не форума, а именно сайта) среди всего прочего есть такой линк махонькими буквами: "Японский кроссворд", направленный на страничку http://algolist.manual.ru/misc/japancross.php. И там есть статья. Только это не лучший из методов, которые я знаю на данный момент (спасибо Илье Посову, сообщившему о другом, несколько более эффективном методе, а также Илье Юнееву, нашедшему в моей реализации досадную ошибку, не влияющую на правильность но снижающую эффективность работы программы), а статью никак не перепишу...

А с учётом того, что вроде бы на какой-то эйсиэмке требовали ещё более эффективный алгоритм, терзают меня смутные сомнения что переписывать статью с использованием всего, что я теперь уже знаю, всё равно нецелесообразно, т.к. получается что наверно есть какой-то ещё более эффективный алгоритм.

Редактировал Ilya_Porublyov (08/31/06 12:58 AM)


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Michael_Rybak
здесь был не раз
*****

Рег.: 07/09/06
Сообщений: 47
Из: Kyiv, Ukraine
Re: решение линии японского кроссворда [Re: Ilya_Porublyov]
      #11990 - 08/31/06 02:36 AM

Пусть w - ширина линии, k - количество блоков (k < w).

Одну линию можно проанализировать за O(w (log w) ^ 2). Я опишу начало такого решения, остановлюсь на O(w ^ 2).


Клетки и блоки нумеруем с нуля.

Введем обозначения для клеток - белые, черные и серые. Хотим установить цвет для тех серых клеток, для которых это возможно.

1. За 2 линейных прохода заполняем массивы RW, LW, RB, LB, RG, LG. Здесь R - right, L - left, W - white, B - black, G - grey. Все 6 массивов - размерностью [ w ]

Значение RW[ i ] - это индекс ближайшей (справа) к i белой клетки, и т.д.

2. Заполним массив front_len[ k ] так.

Рассмотрим блок номер i. Разместим все блоки от нулевого до i-го как можно левее, вплотную. Координату ближайшей белой или серой (той, которая ближе) клетки, следующей за последним блоком, запишем в front_len[ i ].

Значение front_len[ i ] будем вычислять, опираясь на front_len[ i - 1 ], с помощью массивов RW, LW и т.д.

Легко видеть, что весь массив front_len[ ] будет заполнен за один линейный проход по линии.

При этом если в какой то момент не получится расположить следующий блок, это значит, что решение отсутствует. front_len[ k - 1 ] считаем равным w.

3. Аналогично заполняем массив back_len[ ] - располагая блоки как можно правее, начиная с последнего.

4. Теперь нужно выяснить, какие из серых клеток могут оказаться белыми, и какие - черными. Если какая-то клетка не может оказаться ни белой, ни черной, то решения нету. Если и той, и другой - оставим ее серой. Иначе перекрасим в единственно возможный цвет.

Вот здесь я остановлюсь. За O(w ^ 2) теперь это сделать элементарно: для каждой серой клетки, чтобы проверить, может ли она быть белой, перебираем количество блоков слева и справа от нее, а чтобы проверить, может ли она быть черной - перебираем номер блока, которому она будет принадлежать. Все проверки внутри тел соответствующих циклов выполняются за константу с помощью построенных массивов.

Для w порядка 10000 такое решение должно спокойно проходить за 2 секунды.


п.4 можно реализовать за O(w (log w) ^ 2) с помощью структуры, которая позволит за (log w) ^ 2 увеличить на данном отрезке только те ячейки, поверх которых можно расположить блок определенной ширины. Это для определения того, может ли клетка быть черной. А для определения, может ли клетка быть белой, достаточно обычного бинарного дерева, которое позволяет за логарифм увеличить значения на заданном интервале.

Я понимаю, что последний абзац очень далек от конкретики . Если *очень* сильно нужно, могу написать и рассказать подробнее. Хотелось бы, конечно, чтоб можно ее было сдать на каком-нибудь OJ.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 411 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 11001

Rate this topic

Переход в