Форум Всеукраїнської інтернет-олімпіади NetOI

ага, бордер и двд сделал также, но время неприемлимо 0.05 сек и получил за них 0 баллов=))

как Woods делать?

Там  використовуються наступні співвіднощення:
F(i,K1,K2) - кількість можливих заповнень перших і стовпчиків таблиці так, що в і-тому знаходяться дерева типів К1 і К2.
F(1,K1,K2)=
1).1 якщо пара (К1 К2) дозволена
2).0 інакше
F(i,K1,K2),i>1 = sum(F(i-1,K3,K4) : ( K1 K3) (K2 K4) дозволені)
складність O(N*K^4)

Відредаговано MAXXX (2010-01-30 16:28:38)

Eol написав:

ну, woods - динамика по краю. Заводим двумерный массив a[n, i] - кол-во расстановок поля 2*N и последней маской i (i - если перегнать в K-ричную систему счисления, то мы получим две цифры - это и будут два типа деревьев). Переход от a[n] к a[n+1] - это просто сопоставление всех масок.

Можно пожалуйста ссылку где об этом методе подробно расказывается.
А то я решал через матрицы. По ресурсам получилось намного эффективнее.

Задачу woods решал по аналогии с одной интересной задачей Киевской олимпиады прошлого года.

Завдання
Обчислити остачу від ділення на P кількості можливих розміщень шахових коней на дошці 4 на N, при яких вони не атакують один одного.

Вхідні дані
В єдиному рядку вхідного файлу записано два натуральних числа — довжина дошки N (2 ≤ N ≤ 109) і дільник P (2 ≤ P ≤ 109).

Вихідні дані
Єдиний рядок вихідного файлу має містити одне ціле число — остачу від ділення на P кількості можливих розміщень шахових коней на дошці 4 на N, при яких вони не атакують один одного.

Розв'язання:
Рівень 1. Можна здійснити повний перебір усіх варіантів розміщень коней з подальшою перевіркою коректності розташування. Для дошки 4×N будемо мати 2^(4N) таких розміщень. Час на перевірку коректності розташування пропорційний N. Тому таке розв’язання виконує кількість операцій, що  пропорційна N∙2^N. Таким чином можна вирахувати значення кількостей для N від 2 до 7 за час туру олімпіади, задати ці кількості сталими у коді програми і для вказанихх N виводити остачу від ділення на Р попередньо обчислені  кількості розташувань. Таке розв’язання набирає 15% балів.
Рівень 2. Знаючи кількість розташувань на дошці 4×(N – 1) для кожних можливих двох останніх стовпчиків, ми можемо досить швидко визначити такі кількості вже для дошки 4×N. Існує 28 варіантів розміщення коней у останніх двох стовпчиках, бо в кожній з 8 клітинок кінь може або бути або не бути. Зобразимо два останні стовпчики дошки, позначивши однаковими літерами поля літерами латиниці A, B, C, D.
A    B
C    D
B    A
D    C
Для коней, розташованих на останніх стовпчиках дошки, бити один одного можуть лише пари коней, що знаходяться у клітинках, позначених у таблиці ліворуч однією літерою. При допустимих розташуваннях для кожної з цих пар маємо 3 варіанти: або немає коней на обох клітинках, або кінь є на першій (згори), або кінь є на другій. Тому загальна кількість позицій — допустимих розташувань коней на двох останніх стовпчиках дошки — дорівнює  3^4 = 81. Для кожного такої позиції визначимо, які позиції можна отримати при коректному долученні ще одного стовпчика. Тоді для підрахунку кількості розташувань на дошці 4×N для певної позиції k додаємо кількості розташувань на дошці 4×(N – 1) для тих позицій, з яких можна перейти у k долученням стовпчика і знаходимо остачу від ділення цієї суми на P. Кількість операцій у такому алгоритмі буде пропорційна 3^8∙N, що має прийнятний час при N ≤ 10000. Таке розв’язання набирає 70% балів.
Рівень 3. Позначимо через А матрицю розміром 81×81, у якій елемент у рядку k і стовпчику j дорівнює 1, якщо з позиції j можна перейти до позиції k, та дорівнює 0, якщо такий перехід неможливий.
Позначимо через Bn матрицю розміром 81×1 (вектор-стовпчик, що має 81 координату), де значення у комірці (k ; 1) дорівнює кількості розміщень у таблиці 4×N з кінцевою позицією k. Усі координати B2 дорівнюють 1.
Маємо:  А∙Bn = Bn + 1  і    A^(n – 2)∙B2 = Bn  при довільному натуральному n.
Кількість допустимих розташувань — це сума всіх елементів BN .
Найскладнішу частину алгоритму — підрахунок A^N – 2 — можна здій¬сни-ти за час, що пропорційний 81^3∙ logN. Для цього спочатку обчислимо матриці A, A^2, A^4, ... , A^(2s), для всіх S, при яких 2S не перевищує N – 2. Кожну з цих матриц можна вираховувати як квадрат поперед¬ньої, отже кількість операцій для вираховування кожної з них пропорційна 81^3. Далі множимо між собою ті степені матриці А, сума степенів яких дорівнює N – 2. Ці степені відповідають відмінним від нуля розрядам двійкового розкладу N – 2. Таке розв’язання набирає 100% балів.

Автор задачи: Сергей Могильный.

Відредаговано n1ce (2010-01-30 20:37:43)

Спасибо.
Кстати, вот этот код 

pilya написав:

Код:

.....
                else 
                {    
                    // если углы равны то проверяем данная окружнность дальше предыдущей найденой
                    if(td==dMax && (abs(pst->p->x-m[i].x)+abs(pst->p->y-m[i].y)-m[i].r)>(abs(pst->p->x-pMax->x)+abs(pst->p->y-pMax->y)-pMax->r))
                    {
                        f=1;
                        dMax=td;
                        pMax=&m[i];
                        dr=tdr;
                    }
                }
.....

совсем не нужен, т.к. вряд ли он будет выполняться из-за td==dMax,
в чем не трудно убедиться запустив проверку без него.

И еще. Насколько я понял, программа работает за O(N^2)?

Відредаговано Vinnie (2010-01-31 20:29:57)

У меня есть одна английская статья, в которой описано, как решить ее за O(NlogN), но там довольно сложный алгоритм, в котором помимо кучи вычислительной геометрии требуется ручная реализация сбалансированного двоичного дерева. Если кому интересно, могу выложить.

pilya написав:

Просто в тестах не предусмотрено нахождение нескольких окружностей к которым можно провести общую касательную.

По-моему Вам повезло , иначе ваша программа могла бы сработать  неправильно из-за сравнения td==dMax.
Смотреть например Про сравнение double

pilya написав:

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

Для определения относительного расположения окружностей Вы используете вычисление с помощью atan2 двух углов (N^2 раз). Мне кажется дешевле использовать псевдоскалярное произведение (см. Порублев, Ставровский. Алгоритмы и программы. Решение олимпиадных задач. Глава 6.).
Вашу программу можно улучшить, хотя бы исключая из дальнейшего рассмотрения уже найденные точки.

pilya написав:

Пусть меня поправит тот кто решил эту задачу другим способом.

Моя программа не набирает 60 баллов, поэтому поправлять не буду

Відредаговано Vinnie (2010-02-01 08:51:23)

pilya написав:

помоему вы не прониклись задачей одна окружность может участвовать в выпуклой оболочке максимум до 4 раз поэтому исключать окружности из рассмотрения нельзя.

Почему только до 4? Представьте себе одну большую окружность, а вокруг нее равномерно распределены 5 маленьких, причем они лежат очень близко к границе большой. Тогда большая окружность даст 5 дуг в выпуклую оболочку. Если увеличить количество маленьких, то будет еще больше.
P.S.: Вот ссылка на ту статью, о которой я говорил выше.

Vinnie написав:

По-моему Вам повезло , иначе ваша программа могла бы сработать  неправильно из-за сравнения td==dMax.
Смотреть например Про сравнение double

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

Vinnie написав:

Для определения относительного расположения окружностей Вы используете вычисление с помощью atan2 двух углов (N^2 раз). Мне кажется дешевле использовать псевдоскалярное произведение (см. Порублев, Ставровский. Алгоритмы и программы. Решение олимпиадных задач. Глава 6.).

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

Vinnie написав:

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

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

P.S.Ваша ошибка слово точки, а задача про геометрическое место точек, находящихся на равном растоянии от точки.

Відредаговано pilya (2010-02-01 19:35:31)

Полностью с Вами согласен для этого и делалась проверка на окружность самую удаленную из всех что имеют общую касательную