Столкнулся с неожиданной проблемой: разборы задач из мешапа, добавленные с помощью тега [tutorial:] в блог группы, не доступны для просмотра участникам группы.

В режиме предпросмотра разбор виден, но отображается красная надпись "не доступно публично".

Это известная проблема? Кто-нибудь уже сталкивался с таким? Есть ли какой-то способ починить видимость, кроме копипасты всего разбора из полигона напрямую в блог?

Недавно прошел отборочный этап на интенсивы в рамках фестиваля RuCode 2020: https://www.rucode.net/

Я попробовал прорешать все задачи отбора (ссылка на условия) и у меня возник затык на задаче L.

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

Сегодня ночью закончился квалификационный раунд YTCF 2018. Хотелось бы обсудить задачи.

A: в задаче требовалось выбрать минимальное по размеру множество точек на прямой, от которых расстояние до остальных было бы не более R (от какой-либо из выбранных). В одномерном случае эта задача тривиальна, но мне интересно, существует ли какой-то эффективный алгоритм для двумерного случая?

B: стандартная одномерная динамика, нет особого смысла что-то по ней писать.

C: по условию вам даны две карты города — новая и старая — в следующем формате:

• множество ключевых точек, заданные двумя вещественными числами;
• улицы, являющиеся ломаными, построенными на ключевых точках.

Количество ключевых точек на карте N, количество улиц M и суммарное количество отрезков во всех улицах L₁ + L₂ + ... + L_m не превосходят 10⁴.

Целью задачи было определить, какие старые улицы находятся близко к каждой из новой. Старая улица располагалась близко к новой, если все её точки находились на расстоянии не более D от какой-либо точки ломаной, образующей новую улицу. (D также дано во входных данных).

Я не придумал ничего оптимальнее, чем решение за — для каждой новой улицы проверить, находится ли к ней достаточно близко каждая из ключевых точек старой карты, а затем проверить условие для старой улицы как побитовое И всех ее ключевых точек. Грубая оценка подстановкой максимальных значений — 10⁸· константа · операции с вещественными числами, что ожидаемо не влезло в 1 секунду на Java 8.

Для этой задачи существует оптимальнее асимптотически решение? Или подобное можно было упихать на C++ (я не стал переписывать, хотя время было, так как оценка выше навевала уж слишком плохие мысли)?

D: дано N (1 ≤ N ≤ 300) точек на плоскости D_i — водители такси. Также дано N маршрутов, заданных точкой отправления P_j^start и точкой прибытия P_j^end. Расстояния в задаче считаются по манхэттенской метрике (|X₁ - X₂| + |Y₁ - Y₂|), длиной маршрута считалась сумма расстояний (D_i, P_j^start) и (P_j^start, P_j^end). Требовалось распределить водителей по маршрутам, чтобы минимизировать максимальную длину маршрута.

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

При заполнении заявления DS-160 на визу США у нас возникло несколько вопросов, которые не особо понятно где прописаны или как интерпретировать. Мы прочитали, что иммиграционное законодательство США довольно жесткое, поэтому могут возникнуть проблемы из-за любого не совсем корректного ответа на вопрос заявления. Поэтому если вы уже получили визу на финал в США, то мы будем очень признательны, если вы поможете ответить на следующие вопросы:

• В пункте "Кто оплачивает вашу поездку?" непонятно, что писать. С одной стороны, перелет оплачиваем мы сами, с другой — проживание и питание оплачивают нам организаторы финала. И полет, и проживание являются важными составляющими поездки, поэтому просто опустить их кажется немного странным. Что вы указывали в этом пункте?

• В пункте "Кто с вами летит?" указывали ли вы кого-нибудь из членов команды и/или тренера? Если да, то в качестве кого: друг, бизнес-партнер, другой тип отношений? Если нет, то стоит ли на собеседовании говорить о них — соревнование-то командное все-таки?

• В пункте "Кто может подтвердить о вас информацию в США?" единственное, что приходит на ум — указать организаторов финала. Но какую именно информацию о них писать? На данный момент мы смогли собрать вот такую информацию, но возможно мы что-то не так поняли или не так интерпретировали:

1. Organization name: THE ACM-ICPC PROGRAMMING CONTEST
2. Relationship to You: OTHER
3. U.S. Street Address (Line 1): ONE BEAR PLACE
4. City: WACO
5. State: TEXAS
6. ZIP Code (if known): 97356
7. Phone Number: 12542991410
8. Email Address: [email protected]

• В пункте "Текущее место работы" лучше указать университет или все же работу, как наиболее "прибыльный" вариант? Кое-где пишут, что чем больше заработок, тем проще доказать, что ты захочешь вернуться, но с другой стороны в данный момент мы едем на студенческие соревнования, так что указать университет кажется логичнее.

P.S. Если у вас возникали проблемы с чем-то другим при подаче заявления/собеседовании на визу, то мы будем признательны, если вы поделитесь с нами этим опытом.

Пару месяцев назад мы провели очередную межвузовскую командную олимпиаду. Тренировка по задачам этого контеста состоится в воскресенье, 7 июня, в 13.00 по Московскому времени.

Авторами задач данного соревнования являлись Sinner, dalex, Slamur, также неоценимую помощь в подготовке оказали craus, Shlakoblock и I_love_natalia.

Зайти в контест вы сможете на этой странице: Тренировки Codeforces

Список предыдущих наших контестов:

• 2012, Отборочный контест СГАУ на четвертьфинал ACM ICPC
• 2013, VI Самарская областная межвузовская олимпиада по программированию
• 2013, Отборочный контест СГАУ на четвертьфинал ACM ICPC
• 2014, VII Самарская областная межвузовская олимпиада по программированию
• 2014, Отборочный контест СГАУ на четвертьфинал ACM ICPC

Два вопроса:

1) разрешалось ли делать посылки и в yandex.contest, и в еджадж? А то на еджадже посылки из yamndex.contest не показаны.

2) почему нигде в условии Е не определили произведение нуля перестановок?

И как решать A, B, C, F?

Только закончился 1 раунд Opencup для Div2. Как решать задачи D, E, H, K?

10 — 11 ноября прошел отборочный этап олимпиады "Волга-ИТ" в номинации "Алгоритмическое программирование".

Вот ссылка на олимпиаду: http://volga-it.org.

А вот ссылка на тур: http://vtcloud0.ulstu.ru/ru/contest-cid-138d-sh-1?ps=1&smt=1

Участникам предлагалось за 1,5 дня решить 13 задач. Влияло только количество решенных задач, штраф не учитывался. Мне довелось решить все задачи, поэтому проведу здесь разбор.

Задача А.

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

Для этого пройдемся последовательно по массиву героев и будем на каждой итерации сравнивать текущего героя и лучшего на данный момент. Если текущий герой побеждает, то он занимает место лучшего. Заметим, что в этом случае все проигравшие уже точно не являются кандидатами на сильнейшего.

Осталось проверить нашего "лучшего". Для этого второй раз переберем всех героев и сравним кандидата с каждым. Если найдется герой, который не дает победить кандидату (помните о ничьей, где никто не побеждает), то игра сбалансирована, и мы выводим Yes. Иначе — No.

Задача B.

Для начала увеличим все получаемые очки в 2 раза, чтобы иметь дело лишь с целыми числами.

Посчитаем динамику dp[i][j] — вероятность набрать j очков за i игр. Ответ в таком случае — .

Переходы очень просты: dp[i][j] = dp[i - 1][j]·pLose + dp[i - 1][j - 1]·pDraw + dp[i - 1][j - 2]·pWin, где pLose, pDraw, pWin — вероятности проиграть, сыграть в ничью и выиграть соответственно.

Задача С.

Посмотрев на примеры, к тому же с рисунком, можно заметить, что если n·m — число перекрестков — четное, то каждый перекресток можно пройти лишь 1 раз. (точного доказательства, увы, не приведу). В этом случае в каждый перекресток входит ровно одна улица из маршрута, а значит ответ равен 20·n·m.

Если же количество перекрестков нечетное, то, как ни старайся, один перекресток придется пройти дважды (опять же, основано чисто на моей интуиции и на неспособности построить контрпример). В этом случае ответ — 20·(n·m + 1).

Задача D.

В этой задаче достаточно записать все цифры из запросов на соответствующие им места. Если после этого какая-то позиция в пароле осталась незаполненной, то ответ 0, иначе — выводим наш пароль.

Задача E.

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

Запишем задачу более формально:

Дана матрица a[][], найти количество различных линейных комбинаций ее строк по модулю 101. Заметим, что мы можем рассматривать лишь линейно независимые строки.

Каждая независимая строка может быть взята в ответ от 0 до 100 раз (на 101 раз ее вклад будет аналогичен 0). Всего таких строк count, значит полное количество их комбинаций равно 101^count.

Как известно, count = rg(a). Ранг матрицы можно найти, например, с помощью алгоритма Гаусса за O(n²·m), что укладывалось в ограничения. Заметим, что искать ранг надо не в вещественных числах, а в целых по модулю 101.

Задача F.

Сначала решим задачу лишь для пути с первой стоянки на вторую.

Посчитаем динамику dp[i][j] — сколькими способами можно добраться из начального положения в клеткку (i, j). Так как двигаться можно лишь вправо и вниз, то dp[i][j] = dp[i - 1][j] + dp[i][j - 1].

Заметим, что количество способов добраться из (1, 1) в (n, m) равно количеству способов добраться из (n, m) в (1, 1). Пути "туда" и "обратно" независимы, поэтому ответ на задачу равен dp[n][m]·dp[n][m].

Задача G.

В этой задаче требовалось сделать ровно то, о чем говорилось в условии: перевернуть битовые записи чисел a и b, сложить полученные числа, перевернуть обратно сумму.

Задача H.

Отношения "i ненавидит j" задают нам ориентированный граф. Заметим, что если в этом графе есть цикл, даже вырожденный (есть ребра (i, j) и (j, i)), то способов рассадить детей нет.

Иначе для существования ответа требуется, чтобы максимальный путь в графе не превышал r. Максимальный путь можно было найти запуском "поиска в ширину" из каждой вершины, благо ограничения позволяли.

Также можно было провести топологическую сортировку графа. Пройдем по вершинам в порядке сортировки и посчитаем динамику . В таком случае максимальный путь в графе — .

Задача I.

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

Задача J.

Подобная задача была на SNSS 2012 Round 1, только там надо было найти количество двоичных строк длины N, содержащих данную подстроку. Заметим, во-первых, что от размера алфавита ничего не зависит. Также очевидно, что ответ на нашу задачу = (26^N - ans), где ans — ответ на задачу из SNSS.

Подробный разбор содержится в обсуждении того раунда: http://codeforces.com/blog/entry/4936#comment-100728.

Также на досуге можете почитать вот этот тред: http://www.cyberforum.ru/cpp-beginners/thread694502.html.

Задача K.

Отсортируем все отрезки по a[i], чтобы a[i] < a[i] + 1 или a[i] = a[i + 1] и b[i] > b[i + 1]. Теперь наша задача свелась к нахождению длины максимальной невозрастающей последовательности в массиве b. В самом деле, если b[i] ≥ b[i + 1], то это означает, что i + 1 отрезок вложен в i-ый по условию сортировки, что нам и требуется по задаче.

Решение этой задачи тоже недавно обсуждалось на КФ: http://codeforces.com/blog/entry/5541.

Задача L.

Так как N ≤ 1000, то возможно решение за O(N²): переберем возможную высоту буквы и возможную длину крайних горизонтальных линий, не забыв о проверке условия о длине средней черты. Каждая пара прибавляет к ответу (h + 3) / 2 - 3, где h — текущая высота буквы (деление целочисленное). Эту формулу можно получить, если внимательно посчитать количество доступных для рисования средней черты линий.

Задача M.

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

Будем хранить две переменные: sumX = x_c·count и sumY = y_c·count, где count — количество уже подвешенных грузиков. Зная sumX и sumY, мы быстро сможем находить x_c = sumX / count и y_c = sumY / count.

Разберем пересчет sumX: допустим, нам дан прямоугольник (x₁, y₁) — (x₂, y₂). Без потери общности будем считать, что x₁ ≤ x₂. В этом случае к sumX прибавится величина , так как в каждом столбце от y₁ до y₂ мы прибавляем одинаковую сумму по x.

Для быстрого подсчета можно было использовать, например, префиксные суммы, посчитанные заранее: sum[i] = sum[i - 1] + i. В таком случае изменение приняло бы вид: |y₂ - y₁ + 1|·(sum[x₂] - sum[x₁ - 1]).

Аналогично пересчитываем sumY. Общее количество грузиков count увеличивается на |x₂ - x₁ + 1|·|y₂ - y₁ + 1|.