Задачи A(div2), B(div2)

Задача C(div2), A(div1)

Другая оптимизация подразумевала хранение 26-и сбалансированных деревьев или отсортированных списков (по одному для каждого символа) состоящих из позиций вхождения того или иного символа. С помощью них, используя lower_bound, можно было искать самый левый нужный нам символ справа от текущей позиции. Такое решение имеет асимптотику O(|s1| + |s2| * log(|s1|).

Задача D(div2), B(div1)

Авторское решение подразумевает следующее. Предпосчитаем все минимумы на отрезках вида [i, n]. Это можно выполнить за O(n) также идя справа налево. Обозначим минимум на отрезке [i, n] за Min_i. Очевидно, что Min_i <  = Min_i + 1. Теперь для каждой позиции i с помощью бинарного поиска найдем такое число j > i, что Min_j < a_i и Min_j + 1 >  = a{i}. Для такого числа j утверждается, что среди моржей с номером j и более нету моржей младше моржа i. Это очевидно так, как Min_j принимает значение минимального возраста моржа на отрезке [j, n]. Если такого j не нашлось то следует вывести  - 1 иначе j - i - 1.

Задача E(div2), C(div1)

Будем считать количество лыжных баз включая базу из пустого подмножества ребер (при выводе просто отнимем единицу). Изначально количество лыжных баз равно 1. Если мы соединяем вершины которые были в одной компоненте связности, то результат умножим на два, в противном случае ничего делать не надо. Для того, чтобы быстро узнавать лежат ли две вершины в одной компоненте связности и быстро объединять компоненты можно было использовать DJS.

Теперь самый смак. Почему же это верно?
Для доказательства используем матрицу инцидентности I, строками будут являть ребра, столбцами --- вершины. Определим xor двух строк. Xor'ом двух строк a и b является строка c такая, что c_i = a_i xor b_i. Заметим, что если xor нескольких строк равен строке содержащей только нули, то ребра соответствующие взятым строкам образуют лыжную базу. Действительно, степень смежности каждой вершины четна, а значит в каждой компоненте из взятых можно построить эйлеров цикл (Необходимые и достаточное условие существования эйлерова цикла: четность степени смежности каждой вершины и связность графа). Ответом будет являться 2(m - rank(I)). 

Почему это так? Если справа от каждой строки в матрице приписать индекс соответствующего ребра и искать ранг матрицы с помощью метода Гаусса и при xor'e строк выполнять xor наборов ребер записанных справа, то в итоге наборы ребер которые будут записаны справа от нулевых строк будут образовывать базис линейного пространства. В доказательство корректности этого я приведу алгоритм поиска ранга матрицы из которого это будет очевидно.

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

Пример:
1 1 0 a*
0 1 1 b*
1 0 1 c
1 0 1 d

1 1 0 a*
0 1 1 b*
0 0 0 c + a +b
0 0 0 d + a +b

Так как наборы ребер записанные справа образуют базис, то ни один набор записанный справа от нулевой строки не должен получаться путем комбинации (xor'а) других наборов записанных справа от нулевых строк. Действительно это так потому, что справа от нулевой строки будет находиться ребро соответствующее ей изначально и ни в каком наборе записанном справа от нулевой строки оно не встретится т.к. мы выполняли xor только с помеченными строками.

Осталось заметить, что строка, соответствующая ребру, соединяющему вершины a и b, в матрице инцидентности является линейно зависимой, если до добавления ребра существует путь из a в b (мы можем проxorить ее со всеми строками соответствующими ребрам на пути из a в b).

Задача D(div1)
Выделим все циклы в подстановке вида:
1 2 3 4 5 ...
a₁ a₂ a₃ a₄ a₅ ...
Например, в последовательности a = {2, 1, 4, 5, 3} есть 2 цикла длины 2 и 3 на позициях 1 2 и 3 4 5 соответственно. Если длина цикла больше 5, то взяв 5 последовательных элементов можно их переставить так, что 4 из них встанут на свои места. Так же можно взять 4 элемента и получить 3 элемента на своих местах. В общем виде: если мы берем p элементов в цикле длины больше p, то можно переставить их так, чтобы p - 1 встали на свои места. Если длина цикла равна p, то можно взять p элементов и поставить все из них на свои места. Поэтому для общность далее я буду говорить о длине цикла, как о его длине - 1 (теперь можно всегда говорить, что если взять p элементов, то p-1 встанут на свои места).
Не всегда все элементы выгодно брать в одном цикле, можно брать несколько в одном и несколько в другом. Таким образом можно получить разбиения чисел до 5 на их сумму: 5, 4, 3, 2, 2 + 3, 2 + 2. Можно взять, например, три элемента в первом цикле и два во втором, их длины уменьшатся на 2 и 1 соответственно.
Задача заключается в том, чтобы довести все длины циклов до нуля. Предположим в что в оптимальном решении нам следовало бы четыре раза уменьшать один и тот же цикл (a) на единицу. Будем считать, что выполнялись операции где берется ровно по 5 элементов и они не применялись к одним и тем же циклам, за исключением a. Такое условие является более строгим так как при пересечении операций в других циклах или при выборе меньшего количества элементов можно использовать менее продуктивные операции.
Схематично это можно представить в виде таблицы: строки --- это операции, столбцы --- циклы, а в клетках записаны значения на которые уменьшается тот или иной цикл.
a    b   c    d    e
1    2
1        2
1              2
1                   2 
Заменим операции на следующие:
a    b    c    d    e
4
      2   1
           1    2
                       2
Количество операций не изменилось, но теперь стало видно, что если существует оптимальное решение, где встречается четырежды уменьшение цикла на единицу, то существует оптимальное решение где не встречается четырежды уменьшение цикла на единицу. Приведем еще несколько замен подобной выше:
a    b    c
2    1
2          1
Заменим на:
a    b    c
4
      1    1

и

a    b    c    d
2    1
1         2
1               2
Заменим на:
a    b    c    d
4
      1   2
                 2
Из этих замен вытекает то, что существует оптимальное решение в котором один и тот же цикл не уменьшался на 1 + 1 + 1 + 1, 2 + 2, 1 + 1 + 2. Отсюда следует, что каждый цикл следует уменьшать жадно на 4 элемента пока его размер  >  = 4. Таким же методом докажем, что если остались после жадного набора циклы длины 3, то их следует уменьшать сразу на 3.

a    b    c  
2    1
1          2
Заменим на:
a    b    c    d
3
      1    2

a    b    c    d
1    2
1         2
1               2
Заменим на:
a    b    c    d
3
      2   1
           1    2

Теперь остались только циклы длины 2 и 1. Будем перебирать количество операций вида {2, 2} -  > {0, 1} (один цикл длины два уменьшается на два, другой цикл длины два уменьшается на единицу), которые следует выполнить. Пусть мы зафиксировали некоторое количество таких операций. Теперь выполним максимальное количество операций вида {2, 1} -  > {0, 0}. После их выполнения у нас либо не останется циклов положительной длины, либо останутся циклы только длины 1, либо останутся циклы только длины 2. Во втором случае следует выполнять операции вида {1, 1} -  > {0, 0} и если останется один цикл, то следует применить операцию {1} -  > {0}. В третьем случае следует выполнять операции {2} -  > {0}. Перебирая количество операций {2, 2} -  > {0, 1} и выполняя описанные выше действия мы найдем оптимальное решение. Разбивать цикл не несколько циклов меньшего размера не имеет смысла. Стресс тест показал, что объединение циклов тоже не ведет к улучшению.

Задача E(div1)

Формально нам задан массив значение в ячейке которого описывается функцией зависящей от времени T val_i = a_i + b_i * T (в геометрическом смысле это уравнения прямых). Разобьем массив на блоки величины d ~ sqrt(n): [0;d), [d, d * 2), [d * 2, d * 3), ..., [d * k, n). Теперь предпросчитаем моменты времени, когда меняется лидер на блоке. Так как у нас есть уравнения прямых, то можно воспользоваться алгоритмом пересечения полуплоскостей образованных разрезанием плоскости уравнениями прямых из обрабатываемого блока. На оси Oy отмечаются высоты, на оси Ox --- время. Нас будет интересовать только координаты x точек пересечения полуплоскостей и номера прямых которые пересекаются в этой точке. Будем считать, что для каждого блока мы нашли моменты времени, когда меняется лидер и номер лидирующего после этого момента. Для каждого блока это займет O(d * log(d)) времени. так как блоков (k) у нас примерно n / d ~ n / sqrt(n) ~ sqrt(n), то весь препроцессинг займет O(n * log(n)) времени.

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

Всего удалений моментов времени смены лидера будет не больше O(n), а не считая удаление моментов времени смены лидера, каждый запрос обрабатывается за O(sqrt(n)). Итоговая асимптотика равна O(n * log(n) + m * sqrt(n)). 

Для решения этой задачи можно было воспользоваться деревом отрезков и получить асимптотику O(n * log(n)), но использование O(n * log(n)) памяти.

Всем привет.

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

По традиции выражаю огромную благодарность команде Codeforces и Alias за помощь в подготовке контеста.

Желаю всем успеха и пусть победит сильнейший!

UPD1:

Разбаловка задач для div1: 500-1000-1500-2500-2500

Разбаловка задач для div2: 500-1000-1500-2000-2500

UPD2:

Победитель в div1: SergeiRogulenko
Победитель в div2: piotr.mikulski
Мои поздравления!

Разбор

http://www.icfpcontest.org/

ICFP -- ежегодный контест, который длится 3 дня с одной творческой задачей. Отчеты команд прошлого года можно посмотреть тут.

А у меня технический вопрос по соревнованию к тем, кто участвовал в прошлом году. Как происходит отправка/проверка решений? На сайте написано что нужно иметь машину с Debian, с какой целью?

Заметим, что, если добавить в полупустой квадрат размера 2ⁿ × 2ⁿ печеньку максимального размера (она будет иметь размер 2(n - 1)), то наш квадрат разобьется на 4 квадрата величины 2^n - 1 × 2^n - 1, три из которых будут полупустыми квадратами, а один будет полностью заполнен. Отсюда следует формула f(n) = 3 * f(n - 1), f(0) = f(1) = 1. Переходя к замкнутой форме, получим ответ 3^n - 1 (при n > 0) и 1 (при n = 0).

Задача B.

Очевидно, что предложения следует помещать в SMS жадно. Действительно, если мы можем поместить предложение в текущее сообщение, то нету смысла начинать новое, т.к. при этом количество сообщений может увеличиться. Единственным подводным камнем в задаче была необходимость аккуратно обрабатывать пробелы между предложениями.

Задача C.

Для начала научимся решать более простую задачу: требуется подсчитать количество счастливых билетиков, в которых 1 ≤ a ≤ x и 1 ≤ b ≤ y. Преобразуем выражение a * b = rev(a) * rev(b) к выражению вида a / rev(a) = rev(b) / b. Переберем все возможные a и подсчитаем кол-во обычных несократимых дробей вида a / rev(a) (double, кстати, тоже работает =) ) с помощью какой-нибудь структуры, например, map из STL. Остается для каждого значения b найти количество совпадающих дробей a / rev(a) с rev(b) / b и добавить к ответу.

Теперь перейдем к нашей задаче.

Если счастливых билетов с ограничениями 1 ≤ a ≤ max_x и 1 ≤ b ≤ max_y меньше w, то x и y, удовлетворяющих условию задачи, не существует и следует вывести  - 1. 
Если решение существует, то воспользуемся методом двух указателей. 

Нам потребуется поддерживать количество счастливых билетов 1 ≤ a ≤ x и 1 ≤ b ≤ y. Для этого заведем две структуры типа map (назовем их m1 и m2). Научимся переходить из состояния (x,y) в состояния (x,y+1), (x+1,y), (x,y-1), (x-1,y). Если мы хотим увеличить (уменьшить) значение x, то к значению количества счастливых билетиков мы прибавим (отнимем) m2[x/rev(x)] и увеличим (уменьшим) значение m1[x/rev(x)] на единицу. В случае с изменением y следует выполнить аналогичные действия.

Зафиксируем некоторое состояние (x,y), где x = max_x, а y = 1 и подсчитаем для него количество счастливых билетиков. Будем увеличивать y, пока баланс счастливых билетиков не станет больше или равен w. Очевидно, что это будет такое наименьшее y для x, что в соответствующем диапазоне найдется достаточное количество счастливых билетов. Важно отметить, что в дальнейшем уменьшать y не будет иметь смысла. Прорелаксируем ответ и уменьшим x на единицу. Будем повторять действия, описанные в этом абзаце, пока x больше нуля. 

Так как x из ответа лежит в пределах от 1 до max_x и для кадого значения x из этого же диапазона мы нашли оптимальное значение y, то в результате работы алгоритма был просмотрен ответ с наименьшим значением x * y.

Так как каждый указатель не принимает одно значение дважды, и время, затрачиваемое на поддержку баланса, порядка логарифма, то общее время работы программы имеет асимптотику O(max_x * log(max_y) + max_y * log(max_x)).

Задача D.

Заметим что любая точка, лежащая внитри треугольника из первых трех точек, будет всегда содержаться внутри выпуклой оболочки в дальнейшем. Зафиксируем одну из таких точек и перенесем центр координат в нее. Будем хранить точки выпуклой оболочки в структуре типа map, где ключом будет угол для вектора из начала координат к какой-либо точке. Каждому углу будет соответствовать одна точка.

Научимся отвечать на запросы второго типа. Для точки в запросе (A) найдем ближайшую точку к ней по часовой (B) и ближайшую против часовой (C) стрелки. Если угол, образованный векторами AB и AC отрицательный, то точка лежит вне выпуклой оболочки, в противном случае точка лежит внутри или на границе. 

Теперь научимся обрабатывать запросы первого типа. Если точка из запроса (C) лежит внутри выпуклой оболочки, то ничего делать не надо. Найдем две ближайшие точки по часовой стрелке (ближнюю из них обозначим A, другую B). Если поворот от вектора AB к вектору AC положительный, то закончим обработку точек по часовой стрелке, иначе удалим из структуры точку A и повторим эти же действия. Подобным образом следует обработать точки, лежащие против часовой стрелки относительно C. 

Каждая точка добавляется максимум один раз и удаляется максимум один раз. Каждая из этих операций выполняется за O(log(h)), где h — количество точек в выпуклой оболочке. Итоговая асимптотика O(q * log(h)).

Задача E.

Заметим следующие факты. Пусть у нас есть зафиксированное состояние некоторого количества областных центров, тогда для каждой вершины не являющейся, областным центром следует выбрать ближайший к ней областной центр, т.к. d[i] <  = d[i + 1]. Утверждается что все вершины лежащие между некоторой вершиной x и ее центром g будут принадлежать этому центру g. Предположим что это не так, тогда g является не самым ближайшим центром для некоторой вершины между x и g, и для нее существует более ближайший центр u, но тогда должно быть dist[x][u] < dist[x][g], что приводит нас к противоречию. Таким образом получаем, что наше дерево должно быть разбито на некоторое количество поддеревьев и в каждом поддереве будет один областной центр. Для общности так же положим d[0] = 0.

Будем решать задачу используя "перекрестное" ДП.

Первая функция DP. D1(T, g, x, s) будет отвечать за формирование поддерева с областным центром g. T -- некоторое поддерево исходного дерева определяемое направленным ребром uv. областной центр g должен содержаться в T. Будем считать что городу v назначен областной центр g. Так я упомянул выше эта функция будет отвечать за формирование дерева с цетром g. Вся задача будет заключаться в выборе тех ребер которые будут ограничивать наше поддерево. Рисунок:

Зеленые и красные ребра соединяют вершины, которым назначен областной центр g. Фиолетовое ребро ограничивает множество вершин, которым назначен центр g. Стоит отметить, что вершины лежащие на пути из красных ребер нельзя использовать как ограницивающие т.к. вершине v уже назначен центр g.

Пусть ребро xs является ограничивающим, тогда для поддерева T' (Вершины этого поддерева обведены в круг) вызовем функцию функцию ДП D2(T').

Вторая функция ДП будет перебирать каждую вершину в поддерве T' в качестве областного центра и вызывать D1.

В первой функции ДП имеется порядка O(n³) состояний т.к. поддеревьев T порядка O(n), вариантов выбора g столько же и пара (x;s) образует ребро, а ребер всего 2*n-2. Вторая функция ДП имеет O(v) состояний и переход выполняется за O(v). Таким образом решение требует O(n³) памяти и имеет асимптотику O(n³).

Желаю всем удачи и пусть победит сильнейший!

Поздравляем Petr'а с победой, единственного участника, сдавшего все пять задач!

Разбор

Вот уже спал ажиотаж вокруг CodeForces и стали видны основные недостатки в системе. Старые идеи уже не так хороши, как казалось раньше, а новых пока не придумали.

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

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

Сокращения используемые далее:

CF = CodeForces

TC = TopCoder

"В начале было Слово..."

Предлагаю обратиться к тому, для чего вообще проводятся контесты. Можно выделить 3 основных направления:

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

2. С целью отразить навыки решающего. Большинство контестов проводятся с этой целью, за примерами далеко ходить не надо: NEERC, Чемпионат Урала, TC и т.д. В таких контестах ценится оригинальность задач, оценивается умение участников хитро соображать / качественно и быстро  реализовывать. Другими словами, кто "Быстрее, выше, сильнее", тот и молодец.

3. "For fun". Название говорит само за себя.

Конечно ни один контест не проходит без fun'a и получения каких-либо новых навыков, но в контесте одна из составляющих цели выражена сильнее.

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

1. "Обучение. Отражение навыков. Fun". Участники с такими приоритетами по большей части находятся в div2. По мнению администрации это действительно так, и я с этим мнением согласен.

2."Отражение навыков. Обучение/ Fun". Эти люди перед каждым контестм обычно думают: "Вот бы мне щас +75 сделать я бы желтым/фиолетовым/красным. Навыков для у меня достаточно и тот рейтинг, который я сейчас хочу получить соответствует моему уровню". Таких участников можно встретить в div1.

Существуют, конечно, люди которые решают for fun, но их гораздо меньше.

С div2 only контестами все хорошо и они действительно справляются со своей основной целью --- обучением.

Посмотрим на div1 (общие) контесты. Из чего они состоят и чем достигается основная цель (отражение навыков). Далее речь будет идти только о них, если не обговорено обратное.

"Яйцо взбить с сахором, добавить два стакана муки, щепотку соли и все перемешать"

Контесты в АСМ формате состоят из некоторого набора задач. Так, как контесты стараются делать сбалансированными, то можно говорить, что проверяются навыки участника/команды решать задачи широкого круга тематики. Контесты на CF состоят как минимум из двух составляющих: решение задач и взломы. Ко взломам я еще вернусь. Для начала поговорим о главной составляющей контеста -- о задачах.

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

Каждая задача дается в контесте с определенной целью. Ну вот хоть кто-нибудь мне скажите: какой смысл несет задача А для участников с рейтингом 1650+ или задача Е для участников с рейтингом 1300-? Найдутся люди которые скажут задача А для того, чтобы все сдали и порадовались, а задача Е для тех, кто по глупости слил первый контест или для unrated. Ну неужели люди с 1650+ не сдадут задачу B в своем большенстве? На то у них и рейтинг 1650+. А unrated станут красными / жетыми не через один контест, а через два, если задача уровня E будет для них недоступна. 

По этой подтеме я полностью согласен с Alex_KPR. Стоит давать часть общих задач и часть различных. Такой подход ведет к четкому разделению на дивизионы во время контеса. Консервативное мнение администрации по поводу четкого разделения на дивизионы, на мой взгляд, обусловлина от части тем, что "Это же похоже на TopCoder, а мы не хотим сделать второй TopCoder". На самом деле идея деления на 2 дивизиона во время контеста не нова и заметить ее можно не только на TC. В качестве примера приведу Open Cup.

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

"Давай свой исходник, я тебя похачу"

Да, да, да. Речь пойдет о взомах. Им было посвящено больше всего постов о системе CodeForces за последнее время. Предлагались идеи косметического характера: изменять очки за взломы, как-то их ограничивать, что в итого приводило бы к потере интереса участника к взломам на i-ой минуте контеста %)

Хочу отметить, что это единственный способ "коммуникации" между участниками во время контеста, кроме монитора. Почему я сказал "коммуникации"? Потому, что таким путем один человек передает информацию / влияет на другого. В случае монитора участник видит, что вот эта задача легче, ее много уже решило, а эта труднее. В случае взлома, он получает помощь в виде "Твое решение не верно, я тебя похачил. Ищи багу.". Так, как монитор уже давно устоявшаяся часть контестов, на эту тему я дискуссировать не буду. Взломы же могут иметь гораздо более сильное влияние на положение дел, чем монитор. Монитор для всех един. Во взломе участвуют только 2 человека. Лично я выступаю за отсутствие таких "коммуникаций" во время контеста вообще. Формат РОИ мне как раз этим и нравится. Далее я предложу идею, где влияние хаков будет гораздо меньше чем сейчас.

Начнем и к этой теме подходить не со стороны проблем, которые проявились в последние контесты, а со стороны цели.

Хорошо. Пусть во время контестов требуется оценивать не только уменее решать задачи, а еще и находить баги в чужих решениях. Изначально идея взломов была взята от TC (поэтому мне невольно придется проводить аналогию с ТС) с единственным изменением: решения можно взламывать во время контеста. Именно из-за противоречивости последней идеи и идей TC возникают неприятные моменты . А что будет если начнем "рисовать" с чистого листа?

Пусть мы хотим оценивать умение находить баги в чужих решениях. Что для этого нам нужно? Во-первых нам нужны эти самые решения, во-вторых люди, которые будут взламывать. Решения у нас есть (т.к. это основная часть контеста), а для хакеров еще нужно мотивировать дополнительными баллами. Кроме того нужно выполнение некоторых ограничений и избежание читов.

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

Сколько задач выдается системой? 1, 2, 3? какие задачи выдаются? Только багнутые или любые? Если выдавать 3 задачи то в какой комбинации их выдавать? все 3 багнутые? 1 багнутое и 2 хороших? Как часто выдавать код для взлома? Все эти вопросы достаточно важны и так, как идея выдавать код новая, требуется их обильное обсуждение. Я осмелюсь предложить некоторый вариант, который может выступать в качестве показательного примера качественно-нового подхода.

Выдаем по 3 задачи: 2 из них проходящие все тесты и 1 из них багнутое. С технической точки зрения можно проверять задачи на финальных тестах по ходу их субмита, но результат не сообщать участнику, а использовать только для формирования хак-сетов. Участнику дается 10-15 минут на то, чтобы найти багнутое решение и взломать его. По истечению этого времени хак-сет закрывается и участник больше не может взламывать его. По частоте выдачи хак-сетов есть два предложения. Первое: выдвать хак-сет не чаще чем раз в 7-15 минут. Второе: каждые 7-15 минут у участника увеличивается счетчик неиспользованных хаков, после взятия хак-сета этот счетчик уменьшается, разрешается брать хак сет не чаще чем раз в 0-7 минут. После успешного взлома задачи участнику, чье решение взломали, об этом не сообщается. Задача больше не всключается в хак-сеты если появилялась (либо ломалась) в сете более более 5-20 раз. Хак-сет формируется из решений по одной конкретной задаче. Чтобы участник мог брать хак-сеты по этой задаче, задача должна быть заблокирована. Если всего решений по данной задаче < 5-10, то участнику предлагается просматривать все решения и проводить взломы по старой схеме (на это тоже дается 10-15 минут после чего происходит повторная проверка на кол-во решений).

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

Буду рад увидеть бурное обсуждение по теме абзацев выше.

Я обещал, что буду ссылаться на ТС. Собственно вот. Думается мне, что на ТС задача организации взломов, когда она решалась с нуля, выглядела примерно так. "Хорошо. Будем давать баллы за челенджи. А чтобы люди не тырили чужие решения, пусть они не смогут их видеть до некоторого момента. Чтобы решить проблему 'думать задачи или челить', выделим под взломы вобще отдельную фазу. Этим убъем сразу двух зайцев: дополнительные балы никому не лишние, учитывая что субмитить уже нельзя, к тому же решения никто не будет копипастить. Хм... А не будет ли появлять такой человек который будет челить по 30-40 человек за контест? А разобьем людей по комнатам и все будет ОК."

Там разбиение на комнаты решает свою задачу --- ограничение взломов. А на CF этого ограничения, как мы видим, не достаточно. Тут-то и начинают появляться проблемы, если на уже готовую идею пытаться навешать другие. (На фундаменте 5-этажки не построить небоскреб )) )

Способ ранжирования/оценки в контестах.

Основные стороны этой проблемы можно посмотреть в посте natalia.

Один контест в год -- мало, 20 контестов в месяц -- много. Ищем золотую середину.

PS Пост не закончен, добавлю в скором времени еще 2 подраздела.

Помню кем-то поднималась уже такая тема в блоге, но к сожалению с помощью гугла я ее найти не смог.

Кому-нибудь уже пришла футболка? В прошлом году приходили перед новым годом.

Недавно заметил, что на codeforces.ru пути до всех картинок и css файлов начинаются с http://codeforces.ru:88. Это вызывает трудности при просмотре сайта через проки сервера, где запрещены запросы на этот порт.

Возможно ли выложить хотябы css и скрипты на стандартный порт?

Толчком к написанию этого сообщения послужил пост пользователя gasya о сайте CodeChef.com. Последнее время стал замечать, что становится все больше сайтов, где проводятся регулярные контесты. Вследствие этого начинают перекрываться времена контестов.

Например, в субботу будет:

• Школьная командная олимпиада #3 (ЗКШ 201011) в 14:00
• Тренировка ИТМО в 16:30
• 487-й Single Round Match на ТС в 20:00

Назрели следующие вопросы:

Такое было всегда и я это заметил только сейчас (: или же такая тенденция действительно существует?

Контесты на каких сайтах Вы предпочитаете? Какие решаете регулярно, какие "как получится", а какими пренебрегаете?

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

Идея следующая:

Участникам каждый день предлагается по 1 задаче, которую можно засубмитить в течение дня. В конце недели подводится итог (рейтинговая таблица/очки/медальки/отдельный рейтинг) по решенным задачам.

О субмитах:

Время, через которое сдана задача, предлагаю учитывать. У всех свои часовые пояса, просыпаться в 3 часа, чтобы сразу сдать задачу, не вызовет восторга. Но критери для оценки задач, кроме АС, безусловно нужны (пища для размышления)

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

Об итогах:

Отдельный рейтинг (?) по DPWC контестам. (Пока на ум других идей не приходит)

Предагайте свои идеии по этому поводу. =)

Update 1: Идея с отдельным рейтингом не очень хороша в силу того, что требует либо решения максимального кол-ва задач, либо отсутствия решений по 7 задачам вобще (дабы не портить рейтинг)

Немного нелепо ))