Ребята просто предложили написать вместе с ними. Для меня это, безусловно, позитивный опыт, поэтому глупо было бы не согласиться.

Зашло такое: Найдём самый заполненный квадрат 15х15 и будем его во все стороны поочередно расширять, пока в том, что мы добавляем 60% черного. Ну и на всякий пожарный после этого пытаемся его чуть чуть сжать, вдруг скор от этого улучшится

Мы для каждой клетки брали квадрат 15x15 с центром в ней и считали количество черных клеток в нем. Среди таких квадратов выбирали те, у которых черных > 2/3, строили bounding box для их центров. Потом отступали на небольшие dx, dy от границ и выбирали оптимальный вариант, считая по формуле.

У нас бинарная морфология зашла — возьмём структурным элементом квадрат 3х3, сделаем подряд эрозию, два наращивания и эрозию. Найдём прямоугольник описывающий оставшиеся точки. Если его в качестве ответа посылать было ВА 107, поварьировали на единички все координаты и нашли лучшый, зашло.

На GCJ была задача дано множество чисел надо найти 2 подмножества одинаковой суммы. Здесь делаем также будем искать 2 строки из 0 и 1. Выпишем хеш это получится просто сумма некоторых степеней p. Теперь решаем задачу также как на GCJ сдал ее eatmore.

Я сдал такое.

Давайте посмотрим на два полинома. Будем для простоты считать, что они оба имеют длину N = 10⁵. Тогда их разность, которая должна оказаться нулём по модулю q, имеет вид

c₀·p^N - 1 + ... + c_n - 2·p + c_n - 1, где .

Будем искать небольшие суммы из какого-то количества степеней p, которые дают ноль в результате. Во-первых, давайте возьмём, посчитаем все степени p до (N - 1)-ой, отсортируем, и возьмём разности соседних. Так как степени p по модулю q ведут себя достаточно случайно, эти разности будут более-менее равные числа около . Это самое имеет порядок .

Отсортируем эти разности, возьмём снова разности соседних, получив тем самым какие-то выражения вида (p^a - p^b) - (p^c - p^d). Они будут ещё на несколько порядков меньше. И так далее. На k-ом шагу мы будем фактически оперировать суммами из 2^k степеней p с коэффициентами  ± 1.

Вот оказывается, что к третьему-четвёртому шагу гарантированно находится ноль среди таких разностей. А значит, что можно найти вот эти использованные 8 – 16 степеней p, и построить соответствующие строки, состоящие из множества букв a, перемежаемых чем-то другим в этих степенях.

Как-то так. I like it :-)

Я думаю, если выбирать основание и модуль случайные, то вполне безопасно.

Я сдал полнейший рандом. брал мапу, ключи — хеши, зачения — строки. генерил на каждой итерации рандомную строку рандомной длины, длиной не более 10 символом. смотрел, есть ли такой хеш в мапе. если есть — то профит!

Нужно умножить координаты на 2. Иначе часть внешности, может быть недоступна скраю.

У нас было ВА 5, когда не проходило такой тест: http://pastebin.com/GTurg3vZ

Построили ДНФ. Выразили через штрих отрицание,и, или

Вариант 1. Выразили так, что A, B входят 2 раза в A^B,AvB . Тут чтобы посчитать A_1 v A_2 v ... v A_N нужно не по очереди, а деля на 2 равные половины
Пример выражения

Вариант 2. Выразили сперва истину и ложь, через них то же ^, v, теперь уже A, B входят по 1 разу и все получается линейно

1. Выразим все четыре функции от одной переменной через штрих.
2. Заметим, что , так что можно решить для масок m₁ и m₂ рекурсивно, а потом добавить к ним бит a.

Получается вот такое решение, которое укладывается в 600 символов (а не в 500000, как предлагалось).