Периодически сталкиваюсь с ошибкой 403 Forbidden, отдаваемой CF, при попытке авторизоваться через Gmail. У кого еще проявляется та же проблема?

P.S. MikeMirzayanov не читает личку, хотя я ему туда прислал кое-что из сетевого лога браузера.

Всем привет!

Есть люди, такие, как Petr, которые остаются в спортивном программировании даже спустя много лет после окончания вуза и продолжают что-то выигрывать. Многие другие уходят из СП практически сразу после того, как теряют возможность участвовать в ACM ICPC (как, например, я сам или многие мои друзья/знакомые).

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

Мне вспомнилось видео, на котором Sereja и кто-то из братьев Соболевых в поединке по армрестлингу выясняли, кто же тут самый сильный спортивный программист. Кстати, может кто скинуть ссылку на то видео?

А я предлагаю другое соревнование: зайти на сайт ifastest.ru, записать свой лучший подход и выложить сюда скриншот. Материального приза не будет, только респект и уважуха от сообщества.

P.S. Рекомендую использовать Chrome, потому что Firefox реагирует на клик со значительной задержкой.

Я недавно решил закодить одну задачу, а т.к. я уже отучился от привычки использовать глобальные массивы с фиксированным размером, пришлось нагородить вот такую некрасивую штуку: vector<vector<vector<char>>> visited(n, vector<vector<char>>(n, vector<char>(n, false)));. Потом я вспомнил, что в современном C++ ничто не мешает сделать создание подобных векторов заметно более удобным, поэтому я реализовал вот это:

#include <vector>
#include <iostream>

template<typename T, size_t nDimensions>
struct VectorType
{
	typedef std::vector<typename VectorType<T, nDimensions - 1>::Type> Type;
};

template<typename T>
struct VectorType<T, 0>
{
	typedef T Type;
};

template<typename T>
struct MVector
{
	static typename VectorType<T, 0>::Type create();

	template<typename SizeType, typename... SizeTypes>
	static typename VectorType<T, 1 + sizeof...(SizeTypes)>::Type create(SizeType sz, SizeTypes... sizes);
};

template<typename T>
typename VectorType<T, 0>::Type MVector<T>::create()
{
	return typename VectorType<T, 0>::Type();
}


template<typename T>
template<typename SizeType, typename... SizeTypes>
typename VectorType<T, 1 + sizeof...(SizeTypes)>::Type MVector<T>::create(SizeType sz, SizeTypes... sizes)
{
	return typename VectorType<T, 1 + sizeof...(SizeTypes)>::Type(sz, create(sizes...));
}


int main()
{
	int n, m;
	std::cin >> n >> m;

	auto matrix = MVector<int>::create(n, m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cin >> matrix[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cout << matrix[i][j] << " ";
		}
		std::cout << std::endl;
	}
}

Всем добрый день!

Примерно полтора месяца назад я откликнулся на вакансию в одной московской компании. Мне дали "небольшое тестовое задание", в котором требовалось сбрутить пароль от небольшого (2 килобайта) зашифрованного файла. Файл состоит из шифртекста и хеша от открытого текста. Идея была такая: пароль может состоять из не более, чем 7 латинских букв различного регистра и цифр. Пароль хешируется, и его хеш используется в качестве ключа для расшифровки. Правильность расшифровки можно проверить, прогнав полученный plaintext через хеш-функцию и сравнив результат с хешом в зашифрованном файле.

В чем проблема? 62^7 — это примерно 3.5 триллиона различных паролей. Если перебирать миллион паролей в секунду, то понадобится потратить на это порядка тысячи машинных часов, что абсолютно неприемлемо делать ни на своей машине (слишком долго), ни на амазоновском инстансе (слишком дорого).

Собственно говоря, на тестовое задание я забил (хоть там и было сказано, что если вы не сможете подобрать пароль, то всё равно стоит прислать код). Однако, бугурт до сих пор остался. Теперь мне хочется таки написать брутфорс, чтобы узнать: что же господа спрятали внутрь файла?

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

Во-вторых, а много ли желающих погонять свою машинку в течение нескольких суток ради шанса получить, к примеру, гифты в Стиме в пределах 1-2 тысяч рублей? Плюсаните, пожалуйста, первый комментарий (и, для баланса, минусаните второй).

P.S. Если кто готов использовать для такой цели что-то ну совсем мощное (например, стоечный сервер с десятками ядер) — напишите, пожалуйста, в комментариях.

Пару месяцев назад я придумал одну задачу. Рассказал ее коллеге, и мы вместе нашли некое подобие решения. Теперь мне бы хотелось услышать какие-либо новые идеи.

Условие: Алиса и Боб загадали по однобайтовому числу (пусть эти числа будут называться a и b соответственно). Требуется придумать протокол общения между Алисой и Бобом, позволяющий им понять: равны ли a и b? При этом хочется, чтобы Алиса и Боб выдали друг другу как можно меньше информации о своих числах (в идеале — только сам факт равенства/неравенства). Предполагается, что Алиса и Боб будут строго следовать протоколу. Предполагается, что посторонних участников в задаче нет.

Прошу писать идеи решения в комментариях и прятать их под спойлеры.

UPD. hellman_ предложил решение, которое на первый взгляд удовлетворяет вышеописанному требованию к идеальному решению.

UPD2. OWNAGE от eatmore.

UPD3. Опубликовал неидеальное авторское решение.

Уважаемый Михаил Расихович!

Вы долго и весьма успешно боретесь с накруткой вклада, но почему ничего не было сделано против его целенаправленного слива организованной группой людей и/или ботов?

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

Пример явно слитого комментария. Еще пример, хоть там и не -25.

Решил-таки написать этот развлекательный пост, источник идеи, думаю, очевиден.

Знает ли кто обладателей соло-рейтинга 5k+ среди спортивных программистов? А, может быть, у кого-то есть и 6k?

P.S. Сам на данный момент нахожусь в районе 3k и постепенно поднимаюсь.

Несколько минут назад я, как и много раз до этого, выполнил стандартную процедуру входа по Gmail. Но тут выяснилось, что разрешение, которое я дал 3 с лишним года назад, куда-то исчезло. Подозрительных записей в логе Gmail я не увидел.

Это массовое явление, или у меня все-таки проблемы с безопасностью?

P.S. Не исключаю, что доступ когда-то уже отзывался, но я про это забыл.

Буквально несколько часов назад на Хабре была опубликована очень интересная статья.

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

Чем руководствуется администрация, не удаляя аккаунты, очевидно являющиеся фейками?

P.S. Спрашиваю не в ПМ, т.к. ответ интересен явно не мне одному.

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

Высказывалась идея, что КФ с его вкладом — саморегулирующаяся система. В случае со спамом это предполагает возможность заминусовывать спам-посты до их выпадения из прямого эфира.

Вот про это я и хотел поговорить. Прямо сейчас (на момент написания текста — прим.) прямой эфир замусорен спамом (извиняюсь за тавтологию). Я, как пользователь, которому не все равно, поставил на каждый пост по минусу. Перечислю последовательность действий для каждого поста:

1. Открыть пост по ссылке.
2. Прокрутить страницу вниз, чтобы добраться до кнопки "не нравится".
3. Перевести курсор в левую часть окна браузера и поставить минус.
4. Перевести курсор в правую часть окна (опционально: прокрутить страницу вниз).
5. Перейти к пункту 1.

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

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

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

Задача: у нас есть N точек на плоскости, и нам нужно для каждой точки отсортировать все остальные по полярному углу.

Вчера мной была косвенно высказана гипотеза, что эта задача может быть разрешима за O(n²). Гипотеза возникла в тот момент, когда я доказал, что различных сортировок существует O(cⁿ²), где c — небольшая константа.

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

Второе предложение из комментария напомнило мне одну весьма больную (по крайней мере, для меня) тему.

Кого мы подразумеваем под словом "новичок"? Того, кто недавно начал заниматься спортивным программированием, или того, у кого плохой навык решения задач? Сложный вопрос. Да, да, первое по идее автоматически предполагает второе (человек не может с рождения быть хорошим СПшником, чтобы хорошо решать задачи, нужно учиться). Но личные наблюдения показывают, что есть много людей, не относящихся к первой категории, но относящихся ко второй.

Так что же заставляет т.н. новичков укореняться в своем статусе? По-другому: что обеспечивает низкий порог вхождения в СП и одновременно с этим возможность застрять на серо-зеленых ступенях развития? Не те самые легкие задачи, про которые я упомянул в заголовке темы? Почему я вообще качу на них бочку? Что в них плохого? Разве Petr и tourist никогда не решали их, разве они начали с ходу с гробов, и у них все сразу получилось? Да не в самих задачах дело, а в отношении к ним...

Решил вот человек заниматься СП, привели его на ресурс, подобный acmp.ru. Там сабжевых легких задач — больше половины. Начал наш новичок их решать, вначале было трудно, потом стало легче, потом вообще все пошло как по маслу, и он нарешал их пару сотен. Натыкается наш "новичок" на что-то уровня этой самой А-шки с сегодняшнего дня и застревает. К сожалению для "новичка", легкие задачи не подняли его уровень алгоритмического и математического мышления на приемлемый уровень. Тут "новичок" встает перед выбором: решать что-то более сложное и развивать себя в ходе этого дела, застрять на месте или тупо на все забить. Проще всего пойти по второму пути, ну многие так и делают, попутно пополняя собой ряды вечнозеленых участников на CF и TC ("Узнал я про CF. Поучаствую, ведь главное именно это, а не победа."). Кстати, и тут легких задач достаточно.

Вспоминаю свой опыт решения задачи Ancient Messages с финала ACM ICPC 2011, кажущейся халявкой по меркам остальных задач оттуда же, но занявшей у меня (тогда совсем новичка) несколько часов. Какая же была радость после получения АС! Кроме этого, я научился пользоваться DFS-ом и получил серьезный подъем мотивации на развитие.

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

Написал все почти на одном дыхании.

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

Ссылка на скриншот.

Столкнулся я вчера вечером с одной непонятной штукой.

В-общем, я пару-тройку дней назад написал решение на задачу C с Северного четвертьфинала этого года. Запустил на макстесте на универовском компе — в TL = 2с на глаз явно укладывалось. Вчера вечером, наконец, был опубликован официальный архив, я, радостный, его скачал и запустил свое решение тестером с Тимуса на своем ноуте, предварительно выставив TL и ML как в условии. TLE 55! Ну, думаю, дело в том, что универовский комп чуть быстрее — ставлю с запасом ТL = 4с. TLE 62! Ставлю 10с — AC с максимальным временем работы на 67 тесте = 8.674с. Запускаю вручную на 67 тесте — получаю время работы порядка 2.1с. Сегодня запускаю с использованием run.exe на том же 67 тесте — получаю время 8.7с.

Вопрос: почему так может происходить?

P.S. Вот код (тупое решение за ). Компилировал с помощью VS 2010 SP1.

P.P.S. Заслал в тренировку на CF — получил честный TLE67.

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

Гипотеза:
Пусть у нас есть бор, состоящий из не более, чем N вершин. Возьмем все строки, соответствующие листьям этого бора. Я утверждаю, что в сумме у этих строк будет не более, чем N * K различных суффиксов, где K — размер алфавита.

Я выдвинул эту гипотезу из того соображения, что по такому бору можно построить суфавтомат, и в нем будет не более N * K переходов. Где логическая связь между этим высказыванием и моей гипотезой — именно это мне и хочется узнать.

UPD. Своеобразный feature-request: неплохо было бы иметь возможность убирать свои топики из прямого эфира, не переводя их в черновики.

Люди добрые, помогите чем можете... Читаю задачу, четко вижу в ней пересечение матроидов, а как его находить — не знаю...

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

P.S. Кормена я уже читал.

Недавно я заметил, что на данном ресурсе бОльшая часть виртуальных контестов была удалена (список оставшихся). Может ли кто-нибудь объяснить причину?

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

Боян? Добавим в условие дополнительное ограничение: на каждой стадии турнира каждый из игроков обязан сыграть с другим игроком (кроме игрока, для которого пара не нашлась — он автоматически проходит в следующую стадию).

Задачу в таком виде мне подкинул Jokser, вот источник (условия, задача D, тесты). К сожалению, авторское решение задачи соответствует решению оригинальной задачи без введения дополнительного ограничения (я так утверждаю, потому что разобрал тесты).

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

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

Перейдя на страницу с попытками пользователя Algiz, я внезапно превратился в другого человека! (ссылка на скриншот) Как такое вообще возможно?

Относительно недавно на Codeforces появилась функция "Черновики", позволяющая восстанавливать набранные, но не отправленные посты, комментарии и личные сообщения.

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

Прошу пользователей Codeforces принять это к сведению, а Михаила Расиховича сделать что-то с вышеописанной ситуацией (к примеру, сделать возможным отключить сохранение черновиков и позволить удалять их вручную, ну или реализовать сохранение черновиков в Cookies).

Рассмотрим такую абстрактную задачу: дано корневое дерево, и у нас есть три вида запросов:

1. Удалить какое-либо поддерево
2. Добавить в дерево одиночную вершину, подвесив ее за произвольного предка
3. Для двух вершин А и В сказать: является ли А предком В? (В оригинале нужно было искать LCA двух вершин)

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

Задача отсюда (B). Решения с ответом на запрос за очевидны. Вопрос: как отвечать на запрос за линию?

Для тех, кто не в курсе: речь про вот этот гроб.

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