1 Ответ от ArtemKadeev

(5 ответов, оставленных в Algo)

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

Вы же говорите про вариант, когда К у нас близок к факториалу, т.е. надо найти один из самых длинных путей, в этом случае алгоритм действительно будет работать долго.
Но и здесь асимптотика описана верно, поскольку K становится примерно равным N!

Перейти к разделу: Algo

2 Ответ от ArtemKadeev

(2 ответов, оставленных в Problems)

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

Для проверки мы будем перебирать все разумные возможные места установки круга. Достаточно двух случаев. 1) Проведенный через две точки(в две стороны) 2) с центром в любой точке(тоже надо обязательно рассмотреть, т.к. 1 круг может покрывать всего 1 точку в оптимальном построении).

Т.о. получается n*n+n возможных расположений кругов. Найдем соответственно все их центры и за линейное время для каждого определим какие точки он накрывает и представим это в виде массива масок, поскольку у нас максимум 40 точек и это влезает в 64-bit. Теперь мы за O(n^3) получили все возможные маски, и их около n^2.
Но у нас два круга, значит мы перебираем все возможные пары масок за O(n^4) и проверяем дают ли они в итоге полное покрытие - if ( (mask(i] | mask[j]) == (1L<<n)-1 )
Если такая пара нашлась - значит покрытие данным радиусом возможно.

Общая сложность этого алгоритма выходит O(log(m)*n^4), но константа тут получается очень маленькая.

    Accepted      JAVA      0.608      2009-09-22 12:54:44

Перейти к разделу: Problems

3 Ответ от ArtemKadeev

(2 ответов, оставленных в Problems)

Для решения этой задачи надо как минимум хорошо владеть деревом отрезков. http://e-maxx.ru/algo/segment_tree
Еще там надо провести сжатие координат (т.е. отсортировать их и заменить на порядковые номера в отсортированном массиве)
В этом случае мы сможем задать массив необходимого размера, но по времени тривиальный алгоритм все еще не укладывается, для этого и нужно дерево отрезков.

Также мне кажется, что проще ничего не поворачивать, а дерево строить просто по диагоналям.
Т.е. вместо x и y брать номера диагоналей. Они легко получаются как (x+y) и (x-y+n) - часто использую эту методику для упрощения работы с диагоналями. Т.е. значения функции (x+y) будут равны для точек, находящихся на одной диагонали, которая направлена от верхнего левого угла координат. другая соответственно описывает другую диагональ. Т.о. мы можем хранить в дереве тупо координаты относительно какой либо диагонали, а время событий считать по номерам другой диагонали. Ко второй функции мы должны только прибавить какое-то n, чтобы номера всегда были положительны.

Перейти к разделу: Problems

4 Ответ от ArtemKadeev

(13 ответов, оставленных в Algo)

Кнута-Морриса-Поттера - мне так больше нравится ^^

Перейти к разделу: Algo

5 Ответ от ArtemKadeev

(10 ответов, оставленных в Problems)

ScalAr пишет:

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

По моей логике, в трехмерном пр-ве существуют только 4-вершинные выпуклые многогранники в которых каждая вершина соединена с каждой ребром. (Возможно я просто неправильно понял условие, что все отрезки между вершинами должны находиться на границе фигуры).
Т.е. если взять 5-веошинный, то отрезок между несоседними вершинами будет внутри -> фигура не соответствует условию.

Перейти к разделу: Problems

6 Ответ от ArtemKadeev

(10 ответов, оставленных в Problems)

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

Можно даже попробовать это доказать фактически для n-мерного.(на примере 4-х)

Возьмем 4-мерное пространство.
Докажем, что построение |V|<5 невозможно. Для этого берем одну вершину, от нее идет максимум три ребра.
Фигура, создаваемая этими ребрами вырождена в 4-мерном пространстве, поскольку для создания базиса надо 4 вектора хотя бы.(Т.е. можно упростить эту фигурку до 3-х мерного пр-ва)
Для 5 у нас решение есть...
Теперь докажем, что построить для |V|>5 также невозможно. Добавим к пятиугольнику еще одну вершину, тогда из нее будет выходить 5 ребер, и все они должны быть внешние. Но мы знаем, что 5 ребер не могут быть линейно независимые в 4-х мерном пр-ве => одно какое-то может быть представлено через другие 4. Тогда одно из ребер будет находиться внутри фигуры, и не являться необходимым для построения фигуры => условие про соединенность ребрами нарушается, поскольку его можно удалить.
Не очень аккуратно математически, но вполне логичное доказательство.

В итоге ответ существует только при n=5, и он нам дан в условии)

Перейти к разделу: Problems

7 Ответ от ArtemKadeev

(10 ответов, оставленных в Offtopic)

chum пишет:

В рез-те ваш "алгоритм" скажет, что данный граф -- дерево, что вопиющий гон : )
Граф должен еще не иметь циклов : )

Ну здесь проще сказать, что компонента связности, у которой |E| = |V|-1 является деревом.

Перейти к разделу: Offtopic

8 Ответ от ArtemKadeev

(5 ответов, оставленных в Offtopic)

Большое спасибо

Перейти к разделу: Offtopic

9 Тема от ArtemKadeev

(5 ответов, оставленных в Offtopic)

Любая Java программа, вне зависимости от кода отчего-то занимает 20мб памяти.
Это можно увидеть сдавая задачи с большим МЛ.

Но если МЛ = 4мб, то она выдает Runtime Error на совершенно безобидный код, который рекомендовался в FAQ.
Например этот код дал RE на задаче 101.

import java.util.*;
import java.io.*;

public class Solution 
{
  public static void main (String[] argv) throws IOException
  {
    System.out.println(5);
  }
}

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

Об этой проблеме я отписался три недели назад на форуме acm.sgu.ru, но адекватного ответа к сожалению не получил.
Хотелось бы, чтобы эта ошибка была исправлена. Тем более в свете предстоящего четвертьфинала.

Я понимаю, что все таки этот форум немного не то место, где стоит это высказывать, поэтому оффтопик...

Перейти к разделу: Offtopic

10 Ответ от ArtemKadeev

(13 ответов, оставленных в Algo)

Наверное действительно это кто-то его просто так неудачно назвал,
при этом попав в реально существующий алгоритм.

Перейти к разделу: Algo

11 Ответ от ArtemKadeev

(13 ответов, оставленных в Algo)

В том и проблема, что не он. Нашел его в книге "К.А.Родосский Алгоритм Евклида. М. Наука, 1988"
http://osnovanija.narod.ru/knigi.html
Но там что-то страшное. Глава называется "Систематическое представление элементов Эвклидова кольца"

Моих скудных познаний в абстрактной алгебре не хватило для того, чтобы понять что там написано.
Судя по всему это относится к теории чисел, не к комбинаторике.
Может кто-то сможет объяснить простым языком.

Перейти к разделу: Algo

12 Тема от ArtemKadeev

(13 ответов, оставленных в Algo)

Смотрю анкету для поступления в ЛКШ и вижу там алгоритм Паскаля.
Причем я до этого его абсолютно нигде не встречал. Погуглить как есть не удалось.
Так вот, хотелось бы узнать что это и где используется.

Перейти к разделу: Algo

13 Ответ от ArtemKadeev

(3 ответов, оставленных в Problems)

Числа в матрице могут быть отрицательными.
Т.о. не всегда лучшим ответом будет являться вся область матрицы.

Перейти к разделу: Problems