SNSS'11 - Round 4 - Разбор и обсуждение

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Задача А

Как решал я. Для каждого слова посчитал хэш, запихал все в сет. Потом для каждого префикса каждого слова считал его хэш, и хэш оставшейся части (амортизационно - за О(1) ), и проверял, есть ли хэши обеих частей в сете. Почему-то упорно получал ВА(5). Кто сдавал так же - в чем может быть проблема, и заходило ли такое решение?

Задача B

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

Задача С

Буду благодарен за разбор

UPD: разбор от Jokser'а см. ниже в комментариях

Задача D

Противная задача с нечеткими ограничениями, но все, что нужно - как-то написать то, что описано в условии. Для быстрой проверки того, выбрал ли пользователь i приложение j я завел битовую матрицу 10000 x 10000, проверку для каждого пользователя делал фактически в лоб (даже без всяких бинпоисков), логично предполагая, что хитрых тестов с такими раздолбайскими ограничениями не будет. Задача зашла мгновенно.

Задача E

Почему-то относительно мало участников сдавали, хотя задача, имхо, проще той же D. Выполняем бинпоиск по ответу, для каждой длины в лоб за O(N²) проверяем, подходит ли эта длина. При заданных ограничениях без всяких оптимизаций просто летает.

UPD: как указал jte ниже, задачу можно решать даже целочисленно (если умножить все длины на 2 и потом не забыть разделить ответ на 2), что еще более ускоряет поиск ответа.

Задача F

Посидев несколько минут с карандашиком, можно было вывести нехитрую формулу $\text{[math]}$ при A <= B;

Комментарии (27)

Написать комментарий?

_jte_

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

← Rev. 2 →

В А ВА5 у меня получало, пока проверял текущую строку лишь с теми, что были ранее. После этого - АС.

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

→ Ответить

goryinyich

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

Но я сравнивал со всеми... Может быть, первый большой тест

golyj_na_stole

В А у меня зашло решение(~~один в один~~), которое Вы описали выше.

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

В F можно было не выводить формулу, а каждый раз вычислять длины высот и пересчитывать A и B(это можно сделать, например, через синусы и косинусы углов(синус и косинус считать по определению)). Потом сумму длин высот добавлять к ответу. Остановиться, когда сумма длин высот станет меньше эпсилона.

Да, но точное решение почти всегда лучше численного, вот я и привел его.

А ваше численное очень уж сложно =) Можно было заметить, что если в исходном треугольнике гипотенуза равна $\text{[math]}$ , то затем она становится равной B, а высоту в прямоугольном треугольнике можно найти по формуле $\text{[math]}$ . Собственно, применением формулы геометрической прогрессии к данному выражению мы и получаем формулу выше.

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

в А проходит HashSet на Java.

UPD. Забыл, что там сравнивается на равенство в случае одинаковых хешей.

Sereja

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

ilyakor

Интересно, как все решали B до клара (который был разослан только вчера, после того, как я промучавшись с ней полчаса решил спросить у Снарка, что за ботва с условием). Неужели все догадались, что автор имел в виду связную внешнюю область (в таком случае поражаюсь навыкам телепатии участников)? Или есть какая-то более адекватная интерпретация, в которой задача в начальной постановке решается без дополнительных ограничений?

Честно говоря, когда я прочитал, сразу стал решать для связной области. Только сейчас после вашего комментария понял, что по условию она могла быть не связная =) Ну, после задачи D на это сложно обижаться.

Да на SNS вообще сложно обижаться =)

В задаче D забавно, что проходит решение с 10000 * 10000 булевой матрицей, т.е. 93 метра памяти.

У вас прошло? Я использовал битовую матрицу, то есть размера порядка 12 Мб

Да, в этом весь и прикол, что прошло 95 метров памяти. Я после отсылки понял, что сморозил, но увидев АС увидился. После контеста еще раз выделил память по максимуму - все прошло.

Ну, что взять со снарка? =)

Я ему про это написал, но до сих пор без ответа =).

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

Ну просто ответить можно было бы имхо

Наверное, вы нечасто пишете Снарку. Прикинуться деревом - его любимый трюк, особенно если вы пишете про косяки =)

Скорее всего, Вы правы, ибо это было мое первое ему письмо после регистрации)

Jokser

Задача C решается следующим образом:
Будем последовательно рассматривать все N вертикальных рядов. Для текущего ряда будем перебирать все интернет-кафе и для каждого кафе найдем точки пересечения с данным вертикальным рядом - некий отрезок [L;R]. Я это делал 2-мя бинпоисками: фиксировал некую центральную точку X - точка пересечения горизонтального отрезка, проведенного из центра кафе с вертикальным рядом. А дальше одним бинпоиском увеличивал верхнюю границу, вторым нижнюю. Запихиваем отрезки в массив и сортируем по левой границе, также дублируем и сортируем по правой. А дальше в лоб перебираем текущую точку Y на вертикальном отрезке. Заводим 2 указателя, первый проверяет левые границы и включает отрезок в текущие, которые покрывают Y, второй проверяет правые границы и отрезки исключает. Тогда для каждого Y можно несложно найти ответ. Итого сложность получается O(N*K*logM + N*M)
Код: http://pastebin.com/K9dMLZBF

Zhukov_Dmitry

← Rev. 3 →

Можно же вместо бинпоисков воспользоваться теоремой Пифагора :)

Да и от M во времени работы алгоритма можно избавиться.

Например, добавляем L_i - начало отрезка с пометкой о том, что это начало, и R_i + 1 - следующую за концом отрезка точку с пометкой о том, что это конец.

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

И самое главное - перебирать номера столбцов от 1 до N, а не от 0 до N - 1. :)

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

KADR	13 лет назад, # \| 0 Кстати, в F можно было просто много раз проделать то, что написано в условии и просуммировать. Кода чуть больше чем с формулой, зато даже думать не надо :) → Ответить

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

Кстати, а как в D проверять ответ в лоб? Я придумал только динамику по сл. параметрам - [последняя проверенная развязка][рядом с какой развязкой был поставлен последний пост][он был поставлен по часовой на расстоянии d, против часовой на d и или же пост был поставлен в самой развязке] - храним минимальное кол-во постов. Она еле зашла на C++.

Будем жадно.

Переберем точку, от которой начинаем строить. Далее, отложим первую метку на расстоянии currentAnswer от нее. И далее будем идти по точкам, и если они еще покрываются текущей меткой - то пропускаем их. Иначе, ставим новую метку на расстоянии currentAnswer. Если таким образом мы использовали не более K меток - то этот ответ достижим.

Предположим, что развязка - первая по часовой стрелке, "накрываемая" каким-то постом при заданном расстоянии d. Тогда за O(N) вы можете найти минимальное количество постов для накрытия всех развязок при фиксированной первой, а с учетом того, что нужно перебрать все развязки на предмет "первой накрываемой", то и получается искомая оценка O(N²). Если непонятно - пишите, выложу код.

Gassa

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

Блог пользователя goryinyich