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

Если вспомнить что с обычной метрикой мы можем построить выпуклую оболочку как набор внешних точек на линиях аля x cos(a) + y sin(a), т.е. мы этими линиями облепляем нашу фигуру.

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

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

Не уверен, что понял, в чем суть вопроса.

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

Функция расстояний — это такая дискретная штука, описывающая расстояния от текущей вершины до остальных в порядке обхода? Она и в Евклидовой не обязана быть выпуклой. Возьми правильный 2*N-угольник (вписанный в окружность), разрежь его пополам, добавь еще одну вершину в центре этой описанной окружности и по одной в каждом круговом сегменте. Расстояние от "центральной" вершины к каждой из старых вершин будет равно R, а расстояние от нее к новым вершинам будет меньше R (потому что они внутри круга). Получается настолько немонотонная и невыпуклая функция, насколько это вообще возможно — последовательность расстояний будет пилообразной :)

Ну или даже на твоем примере — подтяни точку В ближе (напр., в 5.5 вместо 6) и в Евклидовой метрике все перестанет быть выпуклым.

При умножении на эти вектора получается ровно та формула, которую я написал.

UPD. Только там, похоже, должно быть не , а .

Сначала нужно показать, что расстояние между двумя точками — это всегда максимум из скалярных произведений описанных выше векторов на (dx; dy).

Дальше как в манхэттенском расстоянии. Зафиксируем точку j, и найдем точку i с максимальным (xi — xj) * mulx + (yi — yj) * muly по всем парам (mulx; muly). Для этого можно найти максимум по каждой паре в отдельности, а потом взять максимум из найденных 12 точек. Но при поиске максимума по каждой паре в отдельности -xj * mulx и -yj * muly можно выкинуть как константы.

UPD: произведений на самом деле 8, потому что пары с двумя единицами нам не нужны, как и пары с двумя корнями.

Попробую еще раз. Если ты взял k чисел, то i-е из них -- (i ^ coef_i), где coef_i < 256. Так как xor с числом, меньшим 256, не меняет ничего, кроме последних 8 бит, то появляется неравенство: |i — (i xor coef_i)|<256. Комбинируя дважды эти неравенства с разными знаками, мы получим то, что я написал выше.

Глубинный смысл в том, что |(10^5 xor a) — 10^5| очень мало по сравнению с 10^5 (для любого маленького a).

Снизу я написал более точную версию своего решения и даже код приложил. Все с ним в порядке. А что касается "догадаться", то я в шоке, что многие участники моего уровня догадались, а такие топы не смогли. Может, действительно, слишком сложно думают. Грибоедов, помнится, что-то о подобном писал.

А известно авторское решение?

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

Эм... Я конечно рад, что мной восхищаются. Но я сдал свое решение. Может быть его неправильно поняли по текстовому объяснению. Попробую лаконичнее.

Действуем так: Ищем самое маленькое неустановленное число v. Запускаем дфс из v, чтобы определить всех, кто еще не установлен и требуется для установки v. В ходе дфса для каждой такой вершины посчитаем, сколько вершин требуют ее установки, чтобы их можно было установить. Теперь будем строить обратный порядок для текущего множества вершин. Сама вершина v, очевидно, в нем будет первой. Далее выгодно выбрать наибольшую из тех, у кого количество ссылок равно нулю. Это можно сделать с помощью обычной кучи.

Дабы пояснить за свой "гнилой базар", выложу свой код.

+1 мы прорешивали этот контест. Придумали это, не доказали и забили. И кстати там вроде не совсем лексикографически минимальный, там немного другое надо было искать.

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

Thanks,I have found the reason(I didn't receive the first answer)

Ну, похоже авторы как раз и придумали эту задачу, увидев задачу с IMC. Вообще, кажется, они не особо запаривались новые задачи придумывать в этот раз.