Codesprint - Codeforces

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Codesprint закончился, можно обсудить задачи. Лично я полностью решила четыре штуки:

Picking Cards - произведение ((количество карт номиналом < i) - i + 1) по i от 1 до N.
Coin Tosses - рекурсия по количеству орлов, которые осталось выбросить с текущего момента; за один шаг рекурсии рассматриваю один бросок монеты, и получаю либо орла (переход к "осталось выбросить на одного орла меньше"), либо решку (переход к известному матожиданию числа бросков, нужных для того, чтобы выбросить N орлов подряд - 2^N+1-2). Немного начудила - считала не в целых, а в Decimal (Python), так что преобразование в строку получилось страшноватое, но прошло.
Fraud Prevention - много-много парсинга и строковых манипуляций, в итоге я хранила все полученные строки в map тройной вложенности, с ключами deal id, email id, card info и последним значением - множеством order_id, соответствующих данному набору ключей. Обманными считались те пары deal id + email id, у которых было больше одной записи card info. Так получилось удобнее, чем сверять с предыдущими записями на ходу.
Quora Classifier - задача, которая меня порадовала больше всего: она оказалась в точности тем, чему учил профессор Ng! Первый шаг - нормализация данных (интервалы значений не заданы, так что просто на максимум). Второй - логистическая регрессия + лекция Large Scale Machine Learning, т.е. параметры подстраиваются под один (случайно выбранный) образец, а не под все сразу. 100 000 итераций для качественного обучения хватило с запасом, прошло с первого сабмита.

Остальные баллы набрались на частичных решениях, но это неинтересно, интересно, как эти задачи сдать полностью. Кто-нибудь поделится?

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

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

dalex

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

+165

Жаль, никто не написал сюда, когда этот Codesprint начался...

→ Ответить

gojira

В Coin Tosses выводится общая формула для ответа. У меня она такая: 2^(M+1) * (2^(N-M) - 1).

Subsequence Weighting - немного динамики и структур данных. Так как подпоследовательность с максимальной суммой, заканчивающаяся в элементе i, обязательно продолжает одну из подпоследовательностей с максимальной суммой, заканчивающихся до i, ANS(i) = максимум из ANS(j), j < i таких, что Bj < Bi. Если предварительно сжать числа B (то есть минимальному сопоставить 0, следующему - 1, и так далее), то можно завести дерево Фенвика или дерево отрезков, где в процессе подсчета значений на i-ой позиции будем хранить максимальную сумму среди всех подпоследовательностей, оканчивающихся в элементе со сжатым B равным i. Будем слева направо проходить индексы и query-ить нашу структуру, а потом обновлять её значением суммы в пройденном индексе. Запрос получится такой: найти максимум среди значений в интервале [0, Bi - 1].

+11

Polygon.

Я наверное решал слишком сложно, но всё же. Сохраним данные N точек таким образом, чтобы потом быстро отвечать на запрос "сколько точек в данном прямоугольнике?". Делать это видимо можно с помощью сжатого двумерного дерева отрезков (на e-maxx.ru в соответствующей статье описано), но я сжал координаты и сохранил частичные суммы по квадратам 4x4 (матрицу 5000x5000 то бишь завёл, в которой в элементе (i,j) записано, сколько точек лежит слева и сверху от точки (i,j)) и отсортированные списки значений Y-координат для каждого X и X-координат для каждого Y. С их помощью для данного прямоугольника можно за (1+4*3*logN) посчитать количество точек внутри его.

Теперь надо как-то поделить заданный многоугольник на прямоугольники. Я поделил его на (M/2-1) x (M/2-1) прямоугольных частей (если взять все различные X-координаты вершин в порядке возрастания и то же самое для Y, то часть (i, j) занимает прямоугольник (Xi, Yj)-(X(i+1), Y(j+1)), определил для каждой, внутри она или нет, потом горизонтально смежные части, находящиеся внутри многоугольника, объединил в полоски и для каждой (а всего их не более M вроде бы) делал запросы в свою структуру.

cmd

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

Я так делал:

На прямоугольники разбивал следующим образом:

Рассмотрим вертикальный отрезки, некоторые из них идут снизу вверх, некоторые сверху вниз. Тогда можно брать прямоугольники от x = 0 до этого отрезка и в первом случае отнимать от ответа количества точек в прямоугольнике, а во втором прибавлять (что-то типа как ориентированную площадь считают). Единственно надо быть аккуратным с +-1 на границах - они будут зависеть от того как повернуты горизонтальные отрезки относительного текущего вертикального.

Сумму в прямоугольнике искал так:

2d-дерево у меня не хотело проходить по времени (может как-то криво закодил). В итоге сдал с помощью персистентного дерева отрезков:

Разобьем по слоям (по y координате) все точки. И в каждую новую версию дерева отрезков будем добавлять все точки с равной y координате. Пусть tree[y] - версия дерева отрезков со всеми точками с координатой не больше y. Тогда легко затем посчитать ответ за O(log(n)) для запроса ax, ay, bx, by (прямоугольник) - tree[by].sum(ax, bx) - tree[ay - 1].sum(ax, bx).

← Rev. 3 →

Direct Connections:

Посортим все города по координате x и будем идти от меньшей к большей.

(далее количество жителей == вес == weight)

В таком случае нам надо суммировать для i-го города так:

sum = 0;
for(int j = 0; j < i; ++j)
        sum += max(weight[j], weight[i]) * (x[i] - x[j]);

В этом варианте не нужны модули для нахождения расстония, но остается проблема с max.

У нас получается, что для всех weight[j] < weight[i] надо использовать вес weight[i], а для остальных их собственный вес weight[j]. Нам нужны будут запросы:

1) cnt(weight) - сколько элементов имеют вес меньше weight,

2) sum_x - сумма всех координат городов имеющих вес меньше weight

3) sum_weigth(weight) - суммарный вес элементов имеющих вес не меньше weight

4) sum_weight_x(weight) - сумма вес * координата для всех городов имеющих вес не меньше weight.

И операции добавления элемента в каждую из структур: upd_cnt(weight, 1), upd_sum_x(weight, x), upd_sum_weight(weight, weight), upd_sum_weight_x(weight, weight * x);

Если такие операции есть, то можно посчитать длину кабеля из данного города в города с координатой меньше так:

notless_sum = sum_weight(weight[i]) * x[i] - sum_weight_x(weight[i]) - сумма ответов для тех у кого вес не меньше weight[i]

less_sum = cnt(weight[i]) * weigth[i] * x[i] - sum_x(weigth[i]) * weigth[i] - сумма ответов для тех у кого вес меньше weigth[i]

и результирующее sum = less_sum + notless_sum

Все операции можно реализовать с помощью дерева Фенвика или любой другой аналогичной структуры. У меня было 4 Фенвика на каждый из запросов.

Ассимптотика O(n * log(max(n, maxW))).

O(n * max(n, log(maxW))).

Видимо, O(n * log(max(n, maxW)))?

Да, спасибо. Сейчас поправлю.

Direct Connections.

Понятно, что если рассматривать города в порядке возрастания населения, то рассматривая город i с населением Pi и координатой Xi, ровно Pi кабелями его надо соединить лишь с рассмотренными до него городами. Если мы сможем быстро найти сумму координат S и количество C ранее рассмотренных городов слева от i и справа от i, то итоговая сумма расстояний от города i до всех предыдущих равна (Cleft * Xi - Sleft) + (Sright - Cright * Xi). Искать же эти суммы и количества можно с помощью дерева Фенвика или дерева отрезков, только предварительно надо найти для каждого города его порядок слева направо и запомнить его, чтобы в дереве в нужном месте делать обновления и запросы.

Count Strings.

Её я не написал, но похоже что решается она так. Преобразуем данное Regular Expression в недетерминированный конечный автомат, а его в конечный. Количество состояний, видимо, будет небольшим из-за небольшого размера алфавита. Возводим матрицу переходов автомата в степень L. Ответом будет элемент матрицы, соответствующей переходу из начального состояния в конечное.

MBabin

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

Разве? Я не очень разбираюсь в автоматах, но вроде бы для одного символа нужен НКА из трех состояний (начальное, терминальное, мусор), для * от любого выражения - НКА с парой лишних переходов, для последовательного соединения двух НКА с NA и NB состояниями - НКА с N=NA+NB-2 состояними (начальное B объединится с конечным A, а мусор общий), для НКА(A|B) - N=NA+NB-3 состояния (начальные объединятся, конечные объединятся, мусор объединится). Таким образом вроде ~50 состояний должно быть в итоге.

Я тоже не очень в них разбираюсь). Для 1 символа достаточно 2х состояний начальное и терминальное. Для * и объединения нужно, имхо, пара новых состояний -- новое начальное и новое терминальное + несколько eps переходов (интересно как обойтись только 1 или 0 новыми состояниями?). Более того даже если в итоге получится только 50 состояний то при переходе к ДКА теоретически может получиться порядка 2^50 состояний, а у них мультитесты из 40 тестов и уже 100 состояний дают ТЛ.

UPD: Для конкатенации можно обойтись 0 новыми состояниями.

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

Xazker

Решал, как описывали выше. Автомат строил как в статье.

http://lambda.uta.edu/cse5317/notes/node9.html

Так в статье же строится НКА. Неужели у них были на столько слабые тесты, что не было примеров типа ((a)|(a))? А то просто не верится что можно пройти 40 тестов за 2 секунды, когда в каждом тесте НКА у которого пусть даже 50 состояний переводится в ДКА а потом его матрица возводится в степень.

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

Alex_KPR

опять делаю вывод, что лишние знания приводят к худшему результату :)

Crab Graph:

Решал так (не знаю насколько оно верное, но вроде правдоподобное):

Найдем в графе максимальное паросочетание и преимущество будем отдавать вершинам со степенью 1, если можно включить в паросочетание, то будем их включать. Найти можно с помощью алгоритм Эдмондса.

Каждое ребро из паросочетания это будет какой-то краб. Притом можно заметить, что свободные вершины будут либо строго подсоединены только к одной из вершин ребра из паросочетания (иначе мы можем его увеличить), либо это будет один треугольник (1-2, 2-3, 3-1 и 1-2 из паросочетания например, присоединение любых других ребер будет приводить к увеличению паросочетания). Из этого можно увидеть, что если бы у нас ограничений на T (на количество ребер у краба) не было бы, то мы бы могли без разбора жадно набирать вершины дополнительные к крабу. Но есть ограничение на T. С этим можно бороться с помощью максимального паросочетания. Сделаем граф из двух долей: первая доля это ребра из паросочетания, вторая - вершины которые не входят в паросочетание. Из истока в первую долю ребра с пропускной способностью T-1 (минус 1, потому что одно ребро уже есть - из паросочетания), из второй доли в сток с пропускной способностью 1 и между долями ребро с пропускной способностью 1, если ребро и вершина соответствующие инцидентны.

Тогда ответ это: 2 * размер максимального паросочетания + величина максимального потока в выше описанном графе.

в крабах существует очень красивое и простое жадное решение :)

Расскажи =)

Вообще если например рассматривать случай T = 1, то задача в точности - найти максимальное паросочетание в произвольном графе, что меня собственно и натолкнуло на решение.

+31

ну как раз идея в том, что, согласно условию задачи, T > 1 :)

возьмём все вершины степени один и скажем, что они - ноги

ну те вершины степени один, которые уже нельзя взять из-за "насыщенности" голов, просто удалим

удалим все "насыщенные" головы, то есть головы, к которым уже присобачено T ног

будем повторять описанные выше операции до посинения

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

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

пишется быстро и легко акцептится :)

Quora Nearby - у меня прошел алгоритм, отвечающий на каждый запрос про question за O(суммарное количество топиков для всех вопросов), то есть просто находил расстояние от данной точки до каждого топика, а потом выбирал для каждого вопроса относящийся к нему топик с наименьшим расстоянием. То есть без дополнительных ограничений это O(NMQ) вообще. А асимптотически быстрее это решается?

AlexSkidanov

-7

Мне нравится блок над блоком Participating Companies на странице CodeSprint :о)

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