Всем привет!

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

UPD: Спасибо за ответы

Всем привет! В последнее время интерактивные задачи стали очень модными (сегодня даже все задачи оказались такими), поэтому хотелось бы узнать мнение сообщества по поводу хитрого вопроса. Сегодня на контесте были такие задачи, что интерактор просто читал тест из инпута и честно отвечал нам на наши запросы. Но бывают и другие интеракторы у которых ровно один тест, они ничего не читают из инпута и играют против нас оптимально (т.е. если мы хоть раз ошибемся то интерактор точно выиграет). Задача последнего типа например была на позапрошлом полуфинале NEERC. Эти два типа сильно отличаются поскольку в первом типе можно запихать всякую рандомизированную фигню, в то время как во втором типе нельзя. С другой стороны в сегодняшней задаче А (мне так кажется) и не только можно было написать интерактор который играет против нас оптимально, а если я правильно понял там были тупо тесты. Поэтому хотелось бы знать не правильнее было бы участникам давать информацию по поводу того какого типа интерактор в задаче, поскольку в противном случае команда сразу пихающая хрень получает преимущество (хотя это не логично).

Hi everybody. Now I can't open SRM #390 for practice. Does anyone know how I can write to the Topcoder administration about this?

Всем привет. У меня одного в архиве текстов нет первого теста по задаче D1. В условии написано, что в D1 и D2 тексты взяты их архива и изменен только id. Первый тест выглядит так:

0

OFFICIAL WANTS ARAB FUND TO HELP LEBANESE POUND

ABU DHABI, March 28 — Lebanese central bank Vice Governor

Meguerditch Bouldikian called for the establishment of an Arab

fund to assist the Lebanese pound, which has lost more than 80

pct of its value...

1869890 В архиве есть только более полная версия этого текста.

Всем привет. Хочу написать функцию которой передается количество аргументов и аргументы возможно разного типа. Например, чтобы можно было вызвать функцию примерно так print(3, 1, 1.9, "abc"). Погуглил немного ничего для определения типа не нашел может кто знает как это сделать? Если для параметров тип заранее известен то можно так:

// ...
#include <cstdarg>
// ...
inline void print(int n, ...)
{
	va_list params;
	va_start(params, n);
	
	if (n == 1)
	{
		int x = va_arg(params, int);
		cerr << "int " << x << endl;
	}
	else
	{
		char* x = va_arg(params, char*);
		cerr << "string " << x << endl;
	}
	
	va_end(params);
}
// ...

UPD: Всем спасибо за ответы. Результат видимо такой: в обычном стандарте С++ нормально это не делается, а в С++11 есть свои фишки о которых написал cmd

Всем привет. Сейчас решал задачку на ТЦ и получил такую ошибку. Пробовал и с плагином (moj) и без него. Арену перезагружал ничего не помогает. Кто-нибудь сталкивался с этим?

Уже прошел первый квалификационный раунд Russian Code Cup 2012. Для тех кто хочет подготовиться к следующим квалам, отбору, финалу или еще чему-нибудь добавил все туры прошлого года. Чем больше номер квала тем он видимо попроще. Финал не рекомендую решать тем кто нему не готов, задачи там достаточно сложные. Его стоит прорешать тем кто уверен в своих силах. Первый квал к сожалению без ранклиста, потому что на официальном сайте в нем не указаны времена посылок. Условия доступны в переделанном виде в pdf, а также на официальном сайте. Все ссылки можете увидеть в боковой панели ресурсов тренировки. Удачи на тренировках!!!

Upd: Добавлен второй квал 2012 года.

Добавил в тренировки все ВКОШПы.

Таймлимиты отличаются от тех, что написаны в условии, но поставлены с кратным запасом от авторских решений. Память во всех задачах выставил 256Мб. К сожалению для первых трех ВКОШПов не нашел монитора со временами посылок, поэтому в них ранклисты пока пустые. До 2002 года включительно условия есть только в doc, поэтому стоит вооружиться чем-то что читает docи (на крайний случай можно читать в google docах).

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

Желаю всем удачи на тренировках!

P.S.: Не обращайте внимания на странный порядок тренировок.

UPD: Условия задач до 2002 года теперь доступны в pdf. Спасибо zurg

A. Открытки и фотографии

Будем идти по строке слева направо. Если мы прошли всю строку, либо в руках у нас уже 5 предметов, либо очередной предмет отличается от тех, что мы держим в руках, то относим все предметы в кладовку. Ответом на задачу будет количество посещений кладовки.

Сложность решения O(n).

B. Перестановка

Посчитаем количество чисел от 1 до n, которые встречаются в последовательности хотя бы один раз. Тогда ответ есть n минус это количество.

Сложность решения в зависимости от реализации O(n) или O(n logn).

C. История

Отсортируем пары, заданные в условии по году начала события. Будем идти по массиву этих пар и поддерживать значение rg - самый поздний год окончания какого-либо из уже обработанных событий. Тогда если для текущего года окончания события - year, верно что year < rg, то нужно прибавить к ответу единицу, поскольку данное событие покрыто каким-то из ранее обработанных (поскольку все обработанные события имеют левую границу меньше нашей и какое-то из них имеет правую границу rg большую year). После этого пересчитываем rg следующим образом: rg = max(rg, year).

Сложность решения: O(n logn) - на сортировку и O(n) - на решение.

D. Палиндромы

Сначала сделаем небольшой предподсчёт: cnt[lf][rg] - наименьшее количество символов, которое мы должны изменить, чтобы подстрока [lf, rg] стала палиндромом. Это легко сделать за O(n^3) времени и O(n^2) памяти. Теперь будем считать динамику z[i][j] - наименьшее число изменений, которое мы должны сделать, чтобы разбить префикс длины i на ровно j палиндромов. Сначала весь массив заполним бесконечностями, а z[0][0] присвоим 0. Теперь будем делать переходы вперёд: переберём длину len очередного (j-го) палиндрома и сделаем обновление состояния z[i + len][j + 1] значением z[i][j] + cnt[i][i + len - 1]. Ответ есть минимум z[n][i], где n - длина строки из входного файла, а i отрезка [1, k]. Чтобы вывести ответ необходимо в дополнительном массиве сохранить предка для каждого состояния.

Сложность решения: O(n^3) по времени и O(n^2) по памяти.

E. Последний шанс

В этой задаче можно было подумать, что при фиксированном начале строки функция "хорошести" от конца строки монотонная, но это не так (хотя бы на примере строки baaab). Заменим все гласные из строки на число -1, а все согласные на число 2. Теперь легко понять, что подстрока [i, j] будет хорошей, если сумма в подотрезке [i, j] неотрицательна. Обозначим эту сумму sum[i][j]. Очевидно sum[i][j] = p[j + 1] - p[i]. Где p[i] - сумма первых i элементов. Теперь решение становится достаточно понятным. Одним из решений было следующее: отсортируем все частичные суммы вместе с индексом частичной суммы и заведём структуру данных над массивом индесов частичных сумм, позволяющую извлекать максимум на суффиксе, а также изменять значение в точке (в качестве такой структуры подойдёт дерево отрезков). Теперь будем пробегаться по массиву частичных сумм (отсортированных) и для текущего индекса частичной суммы (начала хорошей строки) найдём самую правую частичную сумму больше либо равную нашей. Пусть величина текущей частичной суммы равна s, а её номер - i. Найдём в массиве частичных сумм первую частичную сумму с величиной больше либо равной s. Найдём максимум на суффиксе найденной частичной суммы - это и будет позиция самой правой хорошей границы для i (если эта граница больше i). Для удаления нашей суммы из массива обновим значение в ней величиной отрицательной бесконечности. Таким образом легко найти не только максимальную длину хорошей подстроки, но и количество таких подстрок.

Сложность решения: O(n logn) по времени и O(n) по памяти.

Всем привет!!!

Осталось меньше 11 часов до начала Codeforces Beta Round #98 (Div. 2). Этот раунд для вас подготовил я, идеи задач мне подкинул MikeMirzayanov. По традиции RAD проследил за тем, чтобы я не посадил багов и написал нормальные условия, а Delinur перевела условия на английский язык. За что им всем спасибо!

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

Надеюсь задачи окажутся интересными не только участникам из Div. 2, но и участникам с рейтингом больше 1699.

Продолжу небольшое повествование о себе (начало в предыдущей записи в блоге). Кроме программирования я очень люблю спорт. В течении нескольких лет до того как я начал писать код, я достаточно серьёзно занимался академической греблей. А до этого я занимался практически всеми видами спорта :-): каратэ, футбол, хоккей, борьба самбо и ещё много всего интересного. Сейчас очень люблю (особенно на сборах) играть в волейбол и настольный теннис. Я решил подготовить этот раунд несмотря на то, что в течении последних двух недель Codeforces заметно менялся внутри и я принимал в этом участие.

Следуя модным тенденциям скоро поменяю аватарку.

Всем удачи на раунде и высокого рейтинга!

UPD:

Соревнование закончено, результаты окончательные, рейтинги пересчитаны.

Top 10 (Div. 2)

Поздравляем победителей!!!

Всем доброго утра/дня/вечера/ночи!!!

В начале этого месяца я присоединился к команде Codeforces. Сейчас я занимаюсь небольшими улучшениями на проекте, а также добавлением некоторой функциональности. К примеру, вы могли заметить, что сегодня на вашей личной странице появилась новая вкладка с результатами ваших выступлений. Также я принял участие при внедрении некоторых улучшений, о которых ранее писал MikeMirzayanov. Надеюсь, что моё участие в проекте принесет много пользы.

И немного расскажу о себе. Я учусь на 4 курсе мех-мата СГУ. Программированием начал заниматься на первом курсе, когда прошел (с последнего места среди прошедших :-) ) отбор в Центр олимпиадной подготовки программистов. До последнего месяца я писал только олимпиадный код и никакого опыта промышленного программирования у меня не было. Надеюсь это не помешает мне достичь высот в этом очень интересном деле.

Довольный и немного уставший Давтян Эдвард

UPD: 1. Изменена страница с соревнованиями. Добавлен столбец для просмотра рейтинга после контеста 2. Добавлена возможность просмотра всех комментариев любого пользователя со страницы этого пользователя

UPD2: 3. Добавлена страница со всеми задачами (на неё можно зайти со страницы контеста). На ней можно увидеть весь комплект задач, а также распечатать его (каждая страница будет распечатана на отдельной странице).

Завтра на CodeChef короткий 2.5 часовой контест. Здесь можно его обсудить, а мне интересно как переводится индийское время в московское (т.е. во сколько по Москве начинается контест).

UPD: Информация для тех кто ни разу не участвовал в Codechef (я сам участвовал один раз). Формат там очень похож на ACM, полное онлайн-тестирование (на всех тестах). В марте было 5 задач, думаю там обычно всегда так. Вместо вердиктов AC, WA, TL и прочих приходят прикольные картинки (если навести мышкой на картинку, то всплывает письменный вердикт). Ввод/вывод стандартный, скорее всего будут multitestы в хорошем формате, т.е. сначала дано количество тестов потом сами тесты. Вообще у них достаточно удобный интерфейс.