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

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

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

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

Не думаю что эти меры сложны в реализации. Нужно уделить этому моменту некоторое внимание, спам уже достал.

PS: еще неплохо бы сделать свой хостинг изображений, ибо записи создаваемые пользователями будут постепенно терять свои изображенияиз-за недобросовестных хостингов.

Добрый день. 10 дней назад возникла нехорошая ситуация, когда некоторые решения участников были отклонены в связи с тем, что некоторая их часть является копипастой с e-maxx.ru. Ситуация, на мой взгляд, плоха тем, что проверены и отклонены по этой причине лишь некоторые решения, а также нет явных критериев отбора, и, опять же, как мне видится, таких критериев не может существовать в принципе. Это вызвало негодование и обсуждений правил, в ответ даже появился пост, который помимо указанной проблемы затрагивает и некоторые другие.

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

В продолжение, в новом посте я предложил, по словам MikeMirzayanov «взломать систему», и даже обещал за это вознаграждение, но пост был забанен, и я получил предупреждение. Суть поста заключалась в том, что я объявил конкурс на программное обеспечение, которое может снимать с экрана нарисованный на нем код (с учетом того что код на экран не помещается, и нужна прокрутка) а затем преобразует его в текстовый вид и позволят легко запустить как Java или C++. Дата окончания конкурса подошла, и победителя не выявлено, поскольку участников кроме меня самого и небыло. В связи с этим объявляю о завершении конкурса, и отзываю обещанное мною вознаграждение в 5 тыс. рублей. У меня есть некоторые зайчатки ПО, которое выполняет необходимые действия.

Этот пост написан с целью объявления официального окончания конкурса, а также с тем, чтобы мы вместе обсудили текущие правила и ваше к ним отношение. Считаете ли вы, что копипаст неприемлем,? Если да, то по каким критериям администрация должна это определять? Как автоматизированно проверять на это код всех решений? Где грань между копипастой, и стандартным написанием боянистых вещей в СП?

Как вы относитесь к тому, что исходный код взламываемого решения печатается у вас на экране, а скопировать вы его не можете? Я, например, могу. Также я могу его легко запустить в три клика мышкой. Вы не считаете, что находитесь в невыгодном положении? Будете каждый писать своё ПО, которое обходит данное ограничение системы, или согласитесь с требованиями, несмотря на то, что иные участники легко их обходят? Интересны любые мнения, подливайте масла в огонь.

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

Читал немного про perfect hashing, но то что следует ниже придумал час назад.

Итак, мы хотим положить в хеш таблицу n заранее известных объектов. А потом спрашивать её, содержит ли она такой объект. Предлагается завести массив размера n значениями которого могут быть объекты или null. И второй массив, где i-тый элемент равен true, если в этой ячейке есть коллизия, либо false в противном случае. Без особого матана, я численно прикинул, что порядка 1 / exp(1.0) (1/2.71828…) объектов должны с кем-то образовать коллизию. Для этой части объектов заведем подобную хеш-таблицу рекурсивно. Когда у нас осталось n < K объектов, для построения хеш-таблицы, мы просто применяем линейный поиск по списку. Ну или бинарный поиск, значение K фиксированное, и может быть выбрано оптимально исходя из практики тестирования.

Понятно, что если в первом массиве мы нашли null по хешу, то такого объекта нет, если там какой-то объект есть, то смотрим совпали ли мы с ним, если нет, продолжаем искать в хеш-таблице следующего уровня, которая в 1 / exp(1.0) раз меньше исходной.

Хеш-функции на разных уровнях могут отличаться.

Худшая оценка сложности Ln(n), где Ln – это натуральный логарифм, логарифм по основанию числа e = exp(1.0) ~ 2.71828…, число эйлера. Средняя оценка сложности 1 / (1 – 1 / e) = 1.5819
Прерасход памяти, составит те же 1.5819 (указателей), если мы считаем что в первом массиве хранятся указатели, плюс битовый массив для второго массива, но это проценты. В обычной хеш-таблице с разрешающими цепочками мы используем по одному указателю для самой таблицы, плюс по одному указателю для каждого находящегося в ней объекта (для поля next) т.е в общей сложности примерно 2 указателя на объект.

Вопрос: известен ли вам этот велосипед или ему подобный?

Знаете ли вы принципиально иные способы разрешения коллизий, чем два предложенные в кормене?

Если я не ошибаюсь, когда-то давно видел код c темплейтами, который во время компиляции выполнял алгоритм решета эратосфена на массиве константной длины. Можете подсказать как подобное делается или поделиться ссылкой? Было бы еще лучше инициализировать константный массив подобным образом, типа statiс const int arr[42]; на самом деле задача проще, нужно проинциализировать счетчик числа битов a[i] = a[i >> 1] + (i & 1)

Чуть более суток назад появился пост, с ужасно оформленным вопросом о казалось бы простой задаче. Пост был заминусован, но я попытался решить задачу, и не смог этого сделать
Условие в человеческом виде выглядит примерно так:
На входе дано число n <= 200. Предположим мы выписали все n*2 значные номера(с ведущими нулями) счастливых билетов. Билет считается счастливым, если сумма первых n цифр равна сумме последних n цифр. В выходной файл нужно вывести 10 чисел — сколько раз мы написали цифру 0, цифру 1, и т.д.

В голове вроде сразу появилось ДП, но оно оказалось медленным, я уже по-разному его попереписывал, но все равно получется слишком медленно для указаных ограничений.
Может кто-нибудь из 43 человек заминусовавших автора знает как решать эту задачу?

Вот мой код

Основные тормоза здесь в строках 63-67. Может можно здесь применить быстрое умножение? Хотя для массива в 200 элементов имхо это не даст сильного ускорения, может можно придумать простую свёртку, чтобы считать это дело? Нам ведь не нужен сам результат умножения, нам нужна сумма a[i] * i, где a это многочлен dcnt в квадрате. Сейчас код работает 13 секунд, но комп у меня довольно мощный, и это многовато. Асимптотика выходит B^2 * N^3 B = 10 (основание СС).
UPD: забыл указать, что ответ нужно вывести по модулю 10^9 + 7

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

1. Даны два списка цифр (от 0 до 9) которые представляют собой запись длинных чисел, например список 3 -> 2 -> 6 -> 7 -> 8 это число 32678. Требуется сложить два этих числа используя O(1) дополнительной памяти. По спискам мы можем перемещаться только вперед, по спискам можно проходить несколько раз.
   Заметим что никакие хаки не позволяют нам двигаться по спискам в обратном направлении, по условию задачи.
   

2. Дан однонаправленный список, где следующий элемент задается его адресом — переменной фиксированной длины, например 8 байтовой. Придумать хак, позволяющий двигаться по списку в обратном направлении. Использовать O(1) памяти. Более подробно опишу что представляет из себя элемент списка на конкретном примере кода
   

struct TListElement {
    int Val;
    TListElement* Next;
};

PS: Ответы прятать под спойлер (в предыдущую правку)

Долгое время задачи на ДП ставили меня в тупик. Во время соревнования не понимаешь, как это решать, кроме полного перебора.

Во время разбора говорят: «давайте заведем массив d[i][j], где i это количество ёжиков, а j количество белочек, а в самом массиве d[i][j] будем хранить чего-то там». Думаешь «ЩИТО? WTF, как бы я на контесте догадался, что мне надо завести двумерный массив, а не трехмерный, например? Почему индексы это ежики и белочки, а не стоимость белочек и оставшиеся у зайчика деньги?» потом говорят «понятно, что d[i][j] = d[i – 1][j] + 100500 * d[i – 1][j + 13] + 42» Смотришь, ну вроде да, логично, но как блин к этому прийти-то? Как бы я понял, что использовать в качестве индексов? В каком порядке эти индексы перебирать? Как понять КАК рассчитывать значение d[i][j] из таких-то предыдущих вычисленных значений?

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

Вся нужная информация есть в условии, иногда на неё нужно посмотреть с обратной стороны, изменить направление перебора в какую-то другую сторону. Давным-давно я столкнулся с некоторыми сложностями при решении задачи Folding и AlexSkidanov провел для меня её разбор по ICQ. Как мне кажется, примерно с этого времени я начал решать ДП лучше и чаще. Давайте разберем её.
Условие вкратце: есть строка из заглавных латинских букв, и правила по которым мы можем её сжимать, нужно сжать строку так, чтобы её сжатая версия была как можно короче. Сжатие описывается как то, что есть из себя сжатая строка и во что она разжимается:

1) Стока состоящая только из букв есть сжатая стока, и разжимается она в саму себя.
2) Строка, являющаяся конкатенацией двух сжатых строк A и B, и разжимается она в конкатенацию строк U(A) и U(B), где U(X) – то, во что разжимается строка X
3) Строка D(X) где D целое число большее 1, а X сжатая строка, разжимается в конкатенацию D строк U(X)
Примеры U(“A2(B)”) = “ABB”, U(“3(2(A)2(B))”) = “AABBAABBAABB”.

Ок, давайте подумаем, что мы можем делать со строками? Мы можем либо склеивать две различные строки в одну, либо склеивать N одинаковых строк X в одну вида N(X). Или можно посмотреть на задачу с другой стороны, и наоборот, разделять строку на две произвольных подстроки, или на несколько одинаковых. Оба варианта имеют право на существование, но давайте используем второй вариант, потому как его удобно реализовать рекурсивно, и моему мозгу он как-то более понятен. Т.е. пытаемся применить рекурсивный подход. Вот дали нам строку S которую надо сжать, мы можем разбить её на две, сжать их (рекурсивно) и склеить результат, либо разбить строку на N одинаковых подстрок, сжать эту подстроку в Z и вернуть строку N(Z).

string D(int L, int R) // результат сжатия для подстроки состоящей из символов i, L <= i < R
{
	if (L + 1 == R) // осталась одна буква, вернем её
		return string(s + L, s + R);
	if (d[L][R].size()) // мы уже считали результат для этой подстроки, вернём то что ранее насчитали
		return d[L][R];
	string res = string(s + L, s + R);// изначальный результат это сама подстрока
	int n = R - L;
	for (int i = 1; i <= n; i++) // пытаемя разбить на n / i одинаковых
		if (n / i >= 2 && n % i == 0 && ok(s + L, n, i)) //
		{
			string zip = Str(n / i) + "(" + D(L, L + i) + ")";
			if (res.size() > zip.size())
				res = zip;
		}
	for (int i = L + 1; i < R; i++) { // пытаемся разбить на две любые
		string zip = D(L, i) + D(i, R);
		if (res.size() > zip.size())
			res = zip;
	}
	d[L][R] = res;
	return res;
}

Int main() {
	cin >> s;
	cout << D(0, s.size()) << endl;
}

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

Динамическое программирование.

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

Основная идея ДП это оптимизация перебора. Сводим задачу к полному перебору всех вариантов, а затем отсекаем те варианты, которые в ходе этого перебора решаются повторно. Статью я решил по-быстрому запилить после ответа на вопрос в теме. Рассмотрим задачу которую пытается решить автор сего поста. Ответьте на вопрос какова сумма цифр всех чисел в интервале от A до B, обозначим это как Q(A, B). (A, B <= 10^9) В таких задачах часто используется такой прием: научимся отвечать на Q(0, X) а затем вычислим Q(A, B) как Q(0, B) — Q(0, A — 1). Ок, обозначим Q(0, X) как F(X). a[i] — i-тая цифра числа X, т.е. X = a[0] + a[1] * 10 + a[2] * 100 и т.д.

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

int a[MaxDigits];
int x[MaxDigits];

int BuildNumberFromDigits(int* a); // собрать число из цикверок, описана где-то в другом месте программы

int Ans(int pos, int sumOfDigits) {
    if (pos == MaxDigits) {
        if (BuildNumberFromDigits(x) <= BuildNumberFromDigits(a))
            return sumOfDigits;
        else
            return 0;
    }
    int res = 0;
    for (int digit = 0; digit < 10; ++digit) {
        x[pos] = digit;
        res += Ans(pos + 1, sumOfDigits + digit);
    }
    return res;
}

тупейший перебор всех вариантов чисел из MaxDigits цифр. ну не совсем тупейший, сумму цифр я считаю на ходу, а не в конце рекурсии, но думаю эту незначительную оптимизацию может сделать и ваша бабушка.

Помедитируем на этот код и подумаем как можно сократить перебор вариантов, какие подзадачи решаются по многу раз, что еще можно соптимизировать? ну первое что бросается мне в глаза это то, что сравнение итоговых чисел if (BuildNumberFromDigits(x) <= BuildNumberFromDigits(a)) можно делать также по ходу рекурсии. давайте заведем некоторый сравнятор чисел, который выполняет сравнение чисел узнавая цифры по одной начиная со младших разрядов. удобнее конечно написать такой онлайн сравнятор, который узнаёт циферки в порядке от старших к младшим, и здесь можно изменить порядок перебора, но это не принципиально. Главное у нас есть некоторая фиговина, которой одна за одной даются циферки числа x а затем мы можем узнать результат сравнения числа X и того числа чьи циферки мы давали.

пример:

TComparer cmp(X);
cmp.AddDigit(1);
cmp.AddDigit(2);
cmp.AddDigit(3);

bool LessOrEqual = cnt.IsLessOrEqual(); // bool LessOrEqual = (123 <= X);

после внедрения этой штуки в рекурсию она примет вид:

int Ans(int pos, int sumOfDigits, TComparer cmp) {
    if (pos == MaxDigits) {
        return cmp.IsLessOrEqual();
    }
    int res = 0;
    for (int digit = 0; digit < 10; ++digit) {
        TComparer cmp2 = cmp;
        cmp2.AddDigit(digit);
		res += Ans(pos + 1, sumOfDigits + digit, cmp2);
    }
    return res;
}

TComparer cmp;
cmp.Init(a);

int ans = Ans(0, 0, cmp);

Давайте я покажу вам немного уличной магии. Заметим, что сравнятор имеет довольно небольшое число состояний. Это позволяет нам применить запоминание. (англ Memoisation, а не MemoRisation, как часто ошибочно пишут русскоязычные программисты.) Запоминание работает так: заходим в рекурсию, проверяем не вызывали ли мы ранее функцию с такими же точно параметрами? Если вызывали, то возвращаем запомненный ранее результат, иначе вычисляем его, и перед возвратом запоминаем то, что мы посчитали.

map<TComparer, int> dp[10][100];

int Ans(int pos, int sumOfDigits, TComparer cmp) {
    if (dp[pos][sumOfDigits].find(cmp) != dp[pos][sumOfDigits].end())
        return dp[pos][sumOfDigits][cmp];
    int res = 0;
    if (pos == MaxDigits) {
        res = cmp.IsLessOrEqual();
        dp[pos][sumOfDigits][cmp] = res;
        return res;
    }
    for (int digit = 0; digit < 10; ++digit) {
        TComparer cmp2 = cmp;
        cmp2.AddDigit(digit);
		res += Ans(pos + 1, sumOfDigits + digit, cmp2);
    }
    dp[pos][sumOfDigits][cmp] = res;
    return res;
}

В такой манере можно написать любую задачу на ДП.

Общий вид решения такой:
1) перебираем все варианты рекурсивно
2) в качестве одного из аргументов рекурсивной функции передаем состояние перебираемого объекта
3) применяем запоминание.
4) ???????
5) PROFIT!

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

заметим, что изначальную оптимизацию Q(A, B) == Q(0, B) — Q(0, A — 1) можно было не придумывать, просто состоянием перебора была бы пара "сравняторов".

В качестве примера из жизни вспоминается случай, когда применение этого подхода стало единственным моим шансом на то чтобы сдать задачу. Задача была из этой же области — "теории цифр" — задачи на подсчет количества чисел (и/или сумму цифр), у которых на цифры наложены некоторые условия. Не помню формулировки, но в ограничениях на цифры были использованы массивы цифр чисел, и перевёрнутые массивы цифр. перебираемых чисел было два, и перебор приходилось осуществлять двигаясь сразу с обеих сторон. т.е. я перебирал четыре циферки ставил одну слева и одну справа у каждого из чисел и шел вглубь перебора, ближе к середине чисел. Подумав над задачей, я увидел что как-то так можно решить задачу, но написать такой вот "сравнятор", или точнее конечный автомат который что-то вычисляет, оказалось самой сложной подзадачей. Конечный автомат оказался невероятной извращенности штуковиной. Он вроде бы складывал эти два числа онлайн, цифра за цифрой в этом тупом порядке. Там были какие-то флаги переноса и займа, позиции, и вообще не пойми что. Когда я наконец получил плюс по этой задаче мне вспомнился тот самый негр в фуражке. Потому что это одно из самых извращенных решений мною написанных, при этом сама рекурсия заняла всего десяток строк, менее пяти процентов кода.

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

PS: "Остерегайтесь багов в коде выше, я только доказал что он корректен, но не тестировал его"(c) Дональд Кнут

Today date is 25 Dec. Merry Christmas Everyone!

Решая задачку D монеты с отборочного russiancodecup мне понадобилась операция "битового умножения". Т.е. по сути перемножения многочленов над полем чисел где умножение это "И" а сложение это "ИЛИ". представить себе это можно так: перемножаем числа в столбик как учили в школе, а числа между двумя прямыми линиями вместо складывания "сИЛИваем". нет ли такой операции для 32-х битовых чисел в assembler? она была бы очень полезна для олимпиадок :)

(перепост)
Отстоим права человека!

Нам кажется, что вопрос участия в столь важном мероприятии спортивного программирования, как VK Cup, не должен зависеть от решений кого-либо в ситуациях, где эмоции явно превалировали и не было проведено ни достаточного анализа, ни попыток решить конфликт путем договоренности.
(конец перепоста)

Я считаю, что вопреки разногласиям в оценках его действий, действий администрации данного ресурса, Константин Дроздов должен получить право на участие в турнире VK Cup.

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

В общем вопрос к людям делали вы такое когда-нибудь? И может посоветуете программку какую?

Может есть программки для "текстового" скринкаста, ну чтобы писалось не обычное видео в плохом качестве, а хитро как-нить, учитывая специфику (куча кадров одинаковые, на экране в основном текст и т.п.)

После такого числа стихов уж не знаю оффтопная ли тема :)

Ответ на ответы поэтам и поэтессам:

Я не знатного рода и племени
И нещадно по свету гоним.
Жизнь плясала, хлестала по темени.
По суставам и почкам моим.

И ведь надо ж – не думал, не грезил я
Вот такую судьбину сыскать:
Привязалась к печенке поэзия.
Растудыт-перетак ее мать!

UPD: Выдержав паузу сообщаю, что автор стихотворения Борис Николаевич Прудаев, мой  покойный  дед. Недавно день рождения был, вспоминал.

вслед за этим стихотворением вспомнился забавный ответ веб-сервера на ошибку 404.

Это тоже из времен пиликающего модема, 32-56 кбит/c, и ночей за чтением киберпанка.

Итак, творческий, псевдо-интерактивный, ответ веб-сервера на запрос, вместо 404 и 403: ссылка

UPD: Народ, а может кто еще че-нить из тех времен вспомнит? Меня че-то на ностальгию пропёрло :) Приветствуются всякие ответы, хоть с сылками хоть просто, описательные, или истории может какие...

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

Мне давно известно, что ответ равен (число вершин в графе) - (размер максимального паросочетания). Ограничения на n <= 1000 * 1000, рёбер O(n) время 2 секунды. Я знаю что в таких условиях алгоритм Динница легко найдет поток.

Моё решение, посланное под GNU C++ получило MLE, однако перепослав его в MSVC я получил AC, прога отъела 245 мб памяти.

Автор контеста считает, что все впорядке.

Ок, полагаю у автора есть решение O(1) времени и памяти, поэтому типа все ок.

Но давайте обратим внимание на ограничения еще раз.

Если бы n и m были до 5000 стал бы я писать поток? - Нет.

Если памяти было 64 мб? - Тоже нет.

И что, я должен был воспользоваться экстрасенсорными способностями, чтобы понять хитроумный замысел автора?

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

Если вы не предполагаете таких решений, так ставьте человеческие ограничения, которые их исключают.

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

Доколе?

UPD: Кроме того, получилась задача на тупую формулу, которую придумывали всяко-разно, а другие ломали. Контест, где 20+ взломов у одного участника, ИМХО не очень правильно подготовлен.

В пример можно взять SRM'ы, вы видели, где у участников 19 челенжей по одной задаче? как правило такие ситуации связаны с кривыми чекерами, или неточностью условия, и большинство таких контестов стали нерейтинговыми, из-за факапа, который авторы признали, не прикрываясь тупыми отмазками.

Как можно понять из названия поста, далее пойдет критика модерации на ресурсе.

Данная тема только в этом году подымалась уже несколько раз.

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

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

типа: "Ага, Венера в зените, Юпитер убывает - удалю-ка я к чертям коммент goo.gl_SsAhv'a"

или "Опа, опять этот назойливый чел, он мне всегда не нравился, снова в коментах ругается - удалю-ка я комент" (BTW, IMHO слово "муди" - не мат прим. ред)

[коментарии кэпа опущены]

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

WTF? Что происходит? Какого ХРЕНА?

UPD: ГСЧ и планеты более справедливы, чем личные предпочтения модераторов, и их отношение к модерируемому - это очень неправильно так поступать.

Что-то мне не пришло письмо о том, что скоро будет СРМ, уже через 5.5 часов он состоится в 6:00 по московскому времени. Тут можно уточнить время начала в других часовых поясах.

Предлагаю как всегда обсудить здесь задачи по окончании тура.

по информации snarknews.info

Анонс: 24.12.2011 (сб), 06:00 на сайте www.topcoder.com состоится Single Round Match 526.5, назначенный в качестве "компенсационного" из-за проблем с регистрацией перед началом SRM 526.

UPD: Я ошибся на 24 часа,  матч будет только через сутки. Прошу прощения, заработался.

Что за фигня с этим Maximal Depth ?

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

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

Нравится ли вам данное нововведение? Давайте здесь пообсуждаем этот момент.

UPD: И зачем вообще велосипедостроением заниматься? посмотрите на ЖЖ например, у них на моем мониторе около сантиметра отступ, а здесь три.

Люди, объсните мне кто-нибудь чем неверно мое решение 500-ки.

Решение:

Считаем хеши для всех подстрок, в мапе отмечаем сколько раз каждая подстрока встречается.

Затем все количества кидаем в отдельный массив и строим дерево хаффмана стандартным алгоритмом с кучей - достаем из кучи два элемента(самых маленьких), объединяем их, и кладём этот элемент снова в кучу. моё решение для теста "abbac" даёт ответ 3.4, авторское решение даёт ответ 3.6666

либо мое решение лучше чем авторское, либо оно неверно.

где ошибка?

UPD: Естественно хеши не прямо для подстрок считаю, а так чтобы строки-анаграммы имели одинаковый хеш.  

UPD2: Ага, понял за что минуса, в посте скиданова спойлится хаффман, но я только сейчас дорешивал, и пост прочел только сейчас. Кстати, мне хаффман почти сразу вспомнился.

Хочу писать TCO Round 3 с дачи, с чужого ноута, и никак не могу поставить MinGW, на соурсфордж инсталлер ставит, но потом при компиляции прога причит "не найдем libgmp-10.dll" нету ли у вас инсталлера любого компилера C++ который ставится оффлайн? у меня раньше на флешке такая штука всегда была, пока не потерял флешку.
Простите за тупую тему в прямом эфире, но я хотя бы не про браки среди гомиков спрашиваю.

Думаю не одному мне нынешние квоты на финал ACM кажутся несправедливыми, вот и решил
поговорить на эту тему. С одной стороны понятно, что нельзя на финал пригласить только
самые лучшие команды, ибо тогда это будет не тот финал который мы знаем. От России было бы
довольно много сильных команд, также как и от Китая и других "сильных" стран, но количество
стран участников бы сильно сократилось, а представительство Южной Америки или Африки было бы
минимальным. Такой вариант я думаю никому бы не понравился, считаю ограничения квот разумной мерой.
А вот величины этих квот не считаю справедливыми. От США 20 участников, от России всего 12, Китай 14.
По населению США превосходит нас, но ведь китай превосходит и США и Россию в разы :)
Самое обидное, это видеть внизу турнирной таблицы финала 5 команд из США с нулём решеных задач,
в то время как команде с 50-ого места на полуфинале NEERC по силам решить 3-4 задачи финала.

Я говорю об этом ещё и потому, что меня это реально каснулось. Мы заняли 25-ое место с 7 задачами,
и были второй невыходящей командой. не прошли в финал по штрафу. Если бы обрезать команды по семи задачам,
от NEERC было бы 15 команд. И эта ситуация кажется ещё более не справедливой в связи с тем, что
половину наград завоевывают в итоге команды от NEERC. Я конечно понимаю, что США организаторы, и квоту
себе не порежут, но разве им самим не стыдно видеть внизу турнирной таблицы этот столбик позора?

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

Странно, что я ещё не видел подобных обсуждений на этом сайте.

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

Может быть где-то эта тема уже подымалась? на форумах и прочее. ссылки в каментах приветсвуются.

Одному очень хорошему человеку требуется написать задание для зачета, которое проверит автоматическая проверяющая система.

задание банальное, тупо дейкстра, но тесты кривые, есть идеи КАК нужно написать программу, чтобы вывод совпал с сэмплом?

В графстве Алгоритмия построено несколько городов. Между некоторыми городами проложены дороги.

Стоимость проезда по разным дорогам разная. Известный путешественник Эдсгер Дейкстра стоит в городе X.

Он хочет узнать какое минимальное количество местных денежков придётся потратить, чтобы доехать из города X

до любого другого города.

Формат входных данных
В первой строке дано имя города, где находится Эдсгер Дейкстра (город X).
Во второй строке дано число N - количество городов в графстве
В последующих N строках описано с какими городами связан дорогами каждый из N городов графства. Каждая такая строка имеет вид:
Gi CNTi N1 S1 N2 S2 ... N CNTi SCNTi где
Gi - город, для которого даны имена городов, связанных с ним дорогами
CNTi - количество таких [соседних] городов
N1, N2, .. - их имена
S1, S2, .. - соответственно стоимость проезда по дороге из города Gi в эти города

Формат выходных данных
В единственной строке выходного файла должно быть перечислено через пробел N пар вида город стоимость_проезда_до_него. Города в строке должны быть отсортированы в порядке возрастания. Если до какого-то города нет возможности доехать, то вместо стоимости вывести inf

[input]

saratov
4
tomsk 2 saratov 5 perm 7
omsk 2 saratov 4 perm 1
saratov 3 tomsk 5 perm 12 omsk 4
perm 3 tomsk 7 saratov 12 omsk 1

[output]

tomsk 5 omsk 4 perm 5 saratov 0

50 тестов, нормальное решение проходит 0 из низ, если вывести строку "tomsk 5 omsk 4 perm 5 saratov 0",

то первый тест проходится и мы имеем 2% 

кто мне объяснит почему этот код получает AC на acm.timus.ru?

баг? я сначала парился с другой задачей, и мой ассерт не срабатывал,

поставил другое условие - отрицание предыдущего - всё равно не срабатывает. 

поставил ASS(0); перед считыванием данных - всё равно нету ожидаемого ТЛ.

вот решение 1000 на тимусе, почему оно заходит?

http://www.everfall.com/paste/id.php?wvxb294mu9qt