Заочка olympiads.ru

13 лет назад, # ^ |

Не надо брать точку Ферма с вики! Там она ужасна - окружности пересекать еще... Можно пересечь 2 прямые и все.

→ Ответить

ifsmirnov

13 лет назад, # ^ |

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

→ Ответить

13 лет назад, # ^ |

Ух ты, и правда проглядел.

→ Ответить

evg-zhabotinsky

13 лет назад, # ^ |

← Rev. 2 →

-9

Можно ещё проще!

Просто гуглим "координаты точки Ферма/Торричелли/Штайнера" и смотрим первые несколько ссылок. Хотя, вообще говоря, формулы страшные.

Мне выкинуло вот это.

→ Ответить

pva701

13 лет назад, # ^ |

← Rev. 2 →

-7

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

→ Ответить

13 лет назад, # |

На 60 (и чуть больше даже) решается халявно. Строим остов тем же Примом. Перебираем все тройки точек, ищем точку Ферма (я оттуда брал ее нахождение) для каждой такой тройки, добавляем ее в граф и строим опять-таки тем же Примом остов заново. Выбираем лучший. Будет раз в 5-10 быстрее, если Прима заменить на Крускала, только ребра сортить не N³ раз, а один раз в самом начале. Ну и конечно вываливаться из него, если в дереве уже N вершин (считая точку Ферма). Ассимптотика - N⁵, но константа небольшая.

→ Ответить

ifsmirnov

13 лет назад, # ^ |

На 60 это и предполагалось. Полное решение получается из этого, если понять, как при добавлении новой точки быстро (за O(1)) перестраивать остов.

→ Ответить

pva701

13 лет назад, # ^ |

может это можно как то так решить: построим в самом начале остов без точки, потом перебираем 3 точки, знаем для них где изумруд, вот этот изумруд бьет на 3 компонеты все дерево, зафиксировали три точки (i,j,k) переходим к паре (i,j,k+1), точка k + 1 будет в какой то из 3х компонет, ну если она в той компонете, в которой была точка k, то все в приципе так же и остается, только меняется изумруд, если же k в какой то из "чужих" компонент (то есть либо в компоненте точки i либо j) то при добавлении ребра образуется цикл в этой компоненте, нужно удалить 1 ребро в этом цикле, ну очевидно чтобы оно было максимального веса (ну вроде эту информацию можно предпосчитать флойдом, для каждой пары вершин ij знать какого макс веса лежит между ними ребро)

→ Ответить

13 лет назад, # |

А как K решается? Я придумал только какое-то дикое шаманство с матрицами за куб...

→ Ответить

CherryTree

13 лет назад, # ^ |

← Rev. 4 →

На самом деле достаточно просто. Надо найти количество полных подграфов величины 1, 2, 3 и 4 в почти полном графе. Количество полных подграфов величины 1, 2 и 3 ищется понятно как. Для того чтобы искать количество подграфов величины 4 будем перебирать две первые вершины (назовем их i1 и i2, и конечно они должны быть совместимы). Добавим к ответу для каждой такой пары количество таких пар i3 и i4, что i1<i2<i3<i4 а также i1 совместима с i3 и i4 и i2 тоже совместима с i3 и i4. Мы получим ответ, в котором не учтен случай, когда четверка подходит под условие выше, однако i3 и i4 несовместимы. Понятно, что в таком случае будет K таких "плохих" пар (i3, i4), т.е. это будут ребра данные во вводе. Переберем каждое ребро и для него посчитаем количество таких пар (i1, i2), которые будут совместимы с (i3, i4), причем (i1, i2) не является ребром и отнимем это количество от ответа. Ну, вообще это сложно нормально объяснить. Код.

→ Ответить

tunyash

13 лет назад, # ^ |

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

Понятно, что множества величины 1 и 2 перебираются банально, а плохие мн-ва величины 3 фиксируются ребром и вершиной. Надо посмотреть, что сколько раз мы посчитали, но это не слишком сложно.

Плохие множества, размера 4 всегда подходят под один из следующих видов.

1) Ребро и две независимых вершины
2) Три ребра, имеющие общую вершину

3) Цепь, длины 3

4) Два независимых ребра

5) Цепь, длины 2 и независимая вершина.

Черт, я не знаю, как я вообще это сдал. У кого-нибудь есть решение без темного шаманства со случаями?

→ Ответить

map

13 лет назад, # ^ |

Я думаю, что нет :) По крайней мере все остальные решения (онлайн и матрицы) требовали гораздо большей техники.

В идеале на 100 должно было заходить O(NM).

→ Ответить

yeputons

13 лет назад, # ^ |

В какой-то мере у меня есть. Все случаи там разбираются при помощи for'ов.

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

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

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Есть онлайновое решение. Последовательно добавляя ребра (u, v), будем на каждое ребро будем считать, сколько сочетаний, которые могли пойти в ответ, исключаются текущим ребром. При этом поддерживаем граф списками смежности и компоненты смежности графа в DSU, считая для каждой компоненты колличество её вершин и рёбер.

Для сочетаний длиной 1 и 2, решение, понятно, за константу. Для сочетаний длиной 3 ответом будет n - 2 - (g[u].size() + g[v].size()) + пересечение g[u] и g[v].

Для 4 нужно подсчитать все пары вершин, которые не содержат u, v, и их соседей, между которыми нет ребра.

Но это решение скорее нужно отнести к шаманству, наверняка есть более простое решение.

UPD: реализация.

→ Ответить

13 лет назад, # |

я писал на J нечто такое:

Построим в самом начале остов. Сохраним для каждой пары вершин наибольшее ребро - W[i][j]

Теперь перебираем тройки. Строим для них точку Ферма. Выбираем теперь 2 ребра, которые потом выкинем из начального остова, поставив вместо них 3 ребра из точки Ферма текущего треугольника, с помощью сохраненных наибольших ребер для пар вершин. Делаем это, используя LCA (построенное в начале дерево, разумеется, подвесили): пусть текущая тройка a, b, c. Берем d=LCA(A, B, C) и выкидываем два максимальных ребра из W[a][d], W[b][d], W[c][d]

Итого асимптотика O(n³ * logn).

Доказывать правильность алгоритма строго не умею :)

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

Мне ifsmirnov долго не верил когда я ему такую 4-ую степень рассказывал. В принципе там доказательство не сложное. Надо последить за тем что делает алгоритм Краскала. Правда со сведение к кубу уже есть какие-то эффекты. Там какие-то случаи какие-то дурацкие вроде бывают расположения точек.

→ Ответить

goo.gl_SsAhv

13 лет назад, # ^ |

LCA можно предпосчитать, чтобы избавиться от Log(n)

→ Ответить

13 лет назад, # ^ |

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

→ Ответить

13 лет назад, # ^ |

← Rev. 5 →

Можно вообще без LCA почти также. См ниже

→ Ответить

13 лет назад, # |

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

→ Ответить

BelovP

13 лет назад, # ^ |

Сделаем события вида дуга открывается\дуга закрывается. Отсортируем по полярному углу. Будем идти по окружности и считать, сколько дуг открыто. Если открыто n - прибавляем дугу к ответу. Потом точно также ищем пересечение всех окружностей. Считаем ответ

→ Ответить

sdryapko

13 лет назад, # ^ |

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

→ Ответить

evg-zhabotinsky

13 лет назад, # ^ |

Более того, оказалось, что пересечение окружностей всегда непусто. (Хотя в условии это не написано)

→ Ответить

13 лет назад, # |

← Rev. 2 →

Не уверен, что правильно но 60 получает.
Очевидно, искомая точка находится в т. Торричелли какого-то треугольника или ее вообще быть не должно. Докажем, что ребра, не входящие в минимально остовное дерево для начального графа(без добавленной точки), никогда не войдут в ответ.
Возьмем простой цикл. Самое большое ребро этого цикла никогда не будет ребром никакого остовного дерева, выкинем его. В конце концов, останется дерево. Других ребер быть не должно.

Пусть d[i][j] - max ребро на пути из i в j. Это легко насчитывается за куб. Теперь переберем все треугольники. У нас есть n + 2 ребра, нужно научиться выкидывать 2 ребра за константу. Рассмотрим этот треугольник (i, j, w). Есть всего 3 кандидата: d[i][j], d[i][w], d[j][w]. Если аккуратно посмотреть на эту конструкцию, легко доказать, что среди этих трех присутствуют 2 одинаковых ребра. Их и выкинем. В итоге О(N^3).

→ Ответить

13 лет назад, # ^ |

хм, может, 2 разных?

ну у меня примерно то же самое не проходило сначала на 60, 1 тест WA был. добавил LCA - зашло

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Из трех ребер d[i][j], d[i][w], d[j][w] есть 2 одинаковых. То, что они все не равны тоже доказывается.

→ Ответить

13 лет назад, # ^ |

так, я ничего не понял. с одной стороны, ты говоришь "есть 2 одинаковых", а с другой - "что они все не равны"

→ Ответить

13 лет назад, # ^ |

Не так выразился. Имелось ввиду, что все три ребра одновременно не равны одному.
Короче, если их положить в сет, размера сета равен 2.

→ Ответить

13 лет назад, # ^ |

а, ну да, тогда вроде согласен)

→ Ответить

ilona

13 лет назад, # |

← Rev. 4 →

Интересно, можно было делать так?

Строим в самом начале минимальное остовное дерево. Теперь за куб перебираем тройки (A, B, C), для них находим точку ферма, и теперь дфсом пытаемся найти два таких ребра(наибольшего веса, и не ребра, соединяющие точку ферма с точками A, B, C), чтобы граф сохранял связность и был деревом. Очевидно, что эти ребра будут лежать на путях между вершинами(A, B, C). Сложность O(n^4 / 6).

К сожалению идея пришла в последний день, закодить так и не получилось =(

→ Ответить

13 лет назад, # ^ |

← Rev. 4 →

Пробовал, у меня WA на 5-ти тестах.

→ Ответить

13 лет назад, # |

← Rev. 11 →

а я нагуглил барицентрические координаты точки Ферма :)

а именно: BC/sin( $\text{[math]}$ + pi / 3) ...

→ Ответить

13 лет назад, # |

интересно, много ли народу из тех, кто сдал J, сдавало ее на 100

→ Ответить

13 лет назад, # ^ |

Статистика в самом низу таблицы.

→ Ответить

13 лет назад, # ^ |

о чем речь? какая статистика? вы точно правильно поняли мой (риторический) вопрос?

→ Ответить

13 лет назад, # ^ |

Я буду читать номер задачи, перед тем как отвечать.

→ Ответить

13 лет назад, # ^ |

и вообще, разве есть статистика, это вроде страницы, а не количество сдавших?

→ Ответить

http://paste.org.ru/?m8gudl

13 лет назад, # ^ |

Статистика-то есть, но эта задача еще не протестирована на оффлайн-тестах.

→ Ответить

Romchela

13 лет назад, # |

← Rev. 4 →

Скажите, пожалуйста, почему у меня вылетало 6 тестов. Задача E количество кратчайших путей.

→ Ответить

13 лет назад, # ^ |

На правах кэпа: неправильный алгоритм / реализация.

Расскажи сначала свой алгоритм, если он правильный, то посмотрим реализацию.

→ Ответить

kostya_by

13 лет назад, # ^ |

+10

у тебя как минимум нету длинной арифметики. в этой задаче она была нужна.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Кстати, решение без длинной арифметики падало на пяти последних тестах.

→ Ответить

Mazeev

13 лет назад, # |

Я решал так: сначала построим мин. покрывающее дерево. Потом переберем все тройки вершин, и если сумма ребер между тремя вершинами положительная(т.е. если есть хотя бы одно ребро), то ставим точку Ферма, кидаем три вершины в одно множество и опять строим мин. остов. Строим его из тех ребер, которые были в изначальном мин. остове. Берем наилучший ответ.

Когда отправлял, получил WA на одном тесте. Но сам я сделал штук 15 рандомных макс. тестов, и это решение выдавало такой же ответ, что и брутфорс. В итоге такая эвристика: если n <= 80, то решаем брутфорсом, иначе решаем так :)

→ Ответить

13 лет назад, # ^ |

случайно не на 19м тесте WA было?

→ Ответить

Mazeev

13 лет назад, # ^ |

Глянул. На 23.

→ Ответить

Aganov

13 лет назад, # ^ |

у меня тоже WA23, правда решение другое, и я не стал писать брутфорс на случай маленького N, а забил на задачу.

таки интересно узнать, что за тест

→ Ответить

13 лет назад, # |

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

→ Ответить

13 лет назад, # |

+19

а скоро запустят проверку на оффлайне?

→ Ответить

Aganov

13 лет назад, # ^ |

уже

→ Ответить

kuzmichev_dima

13 лет назад, # ^ |

Я чего-то не понимаю, но зачем запустили реджадж F?

→ Ответить

13 лет назад, # ^ |

Ну там же можно было получить максимум 70 баллов за отправку, в условии сказано, что остальные 30 дают за offline-тесты. Все нормально.

→ Ответить

13 лет назад, # ^ |

Скорее всего имелось в виду то, что на офф тестах вроде проверили уже всех, а сейчас снова заново запустили проверку

→ Ответить

13 лет назад, # ^ |

А, извините, этого не знал.

→ Ответить

13 лет назад, # |

← Rev. 2 →

Решение за константу для задачи про фибоначчи, когда k < i?

→ Ответить

BelovP

13 лет назад, # ^ |

← Rev. 2 →

Используя формулу a[j] = fib(j - i - 1) * a[i] + fib(j - i) * a[i + 1],где fib(x) - х-тое число фиббоначи, находим i + 1 элемент последовательности. Потом считаем назад числа в порядке уменьшения, пока не получим число под номером k.

→ Ответить

13 лет назад, # ^ |

Это же не за константу :)

→ Ответить

kuzmichev_dima

13 лет назад, # |

Вот как можно было в 70-бальном решении F (при финальном сабмите) забыть поменять константу с 30 на 10^6 только в 1 месте, и получить на off-line тестах RE...sad

→ Ответить

13 лет назад, # ^ |

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

→ Ответить

13 лет назад, # |

В F нужна была длинка?

→ Ответить

13 лет назад, # ^ |

Вроде, нет. Хотя почему-то очень много решений, набравших 94 балла. Неужели почти у всех одна и та же ошибка?

→ Ответить

pva701

13 лет назад, # ^ |

перетестируют, у меня по ней было 94, стало 100

→ Ответить

13 лет назад, # ^ |

вот блин, а у меня не стало

→ Ответить