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

Я общался с одним человеком, который за несколько лет самостоятельно написал компилятор C++. Когда я последний раз с ним разговаривал (это было лет 5 назад), он уже приближался к поддержке всех основных фич C++ ISO 2003, и потихоньку начал копать в сторону оптимизации кода.

Нужен ли миру его компилятор C++? Вряд ли. Но это нисколько не волновало его: и это-то, на мой взгляд, и восхитительно :) Это замечательный пример уверенности в себе, упорства, и желания творить. Чего я и желаю автору данного топика.

Помнится, я тоже начинал писать свой клон Visual Studio… Понятно, чем это закончилось: как и у тысяч других начинающих программистов, проект завяз где-то в стадии ver. 1E-12 (для меня самыми убийственными оказались вопросы отладки: сделать “на коленке” хороший отладчик, который может тягаться с возможностями Visual Studio, ни за что не получится).

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

Ну да, а перед этим долго и упорно искал Формулу :)

Кто ещё решал B div 1 с ограничениями K <= 10^9? :)

Сам Facebook, очевидно, и оплачивал. Билеты на самолёт + 40$ “суточные” (например, на еду, или любые другие расходы — но потом всё подтверждать чеками надо будет).

Угу.

Я вечером перед контестом подготовил всё для распараллеливания решений: оставил в номере работающий ноут с VPN’ом к 24-ядерному сервачку, написал скриптики для запуска на всех тестах и склеивания их ответов, для доступа к этому ноуту поставил TeamView…

Только вот на контесте параллелить оказалось нечего.

Да, у меня примерно то же самое.

А я не понял, что, пригласительные e-mail’ы рассылались всем пользователям ВКонтакте? Тогда даже странно, что всего 4000 тысячи человек пришли.

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

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

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

В любом случае, я-то, наивный, полагал, что она стоит 500-1000 рублей, ну может 1500, но такие деньги… Даже 120$+доставка = немаленькая сумма.

Все мои материалы (статьи, код) — под Public Domain.

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

Другой характерный пример — несколько лет назад я активно искал книгу Ahuja “Network flows”, и т.к. никак не мог найти в электронном виде, то решил немного раскошелиться и купить.

Гугление сразу выдаёт ссылку в озоне:

http://www.ozon.ru/context/detail/id/1790165/

цена: 13 320 руб.

подняв челюсть с пола, я отказался от своей затеи, и таки нашёл пиратку (вернее, добрые люди прислали)

нет, я не выкладывал под другой ссылкой. сейчас вообще стёр все упоминания.

ок:)

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

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

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

UPD: стёр совсем

Есть ещё один интересный факт. Когда-то я разговаривал со своим научным руководителем — у него издано несколько книг по достаточно узкой тематике, где мало книг вообще, а русских — тем более. Так вот, я был поражен, когда узнал, что он не получает от продаж этих книг ни копейки!

Точнее, какие-то копейки ему положены, но суммы настолько смешные, что, по его словам, “приходить за ними в издательство просто стыдно”.

Так что и по “ту сторону баррикад” люди тоже мало что выигрывают от копирастии.

Да, доказательство по индукции трудно назвать решением — надо же сначала как-то придумать эту формулу.

Я выводил так. Есть известный код Прюфера: это последовательность из n-2 чисел, где каждое число от 1 до n. Любая такая последовательность взаимно однозначно соответствует некоторому дереву. Отсюда, в частности, уже следует формула Кэли, что число остовных деревьев в полном графе равно n^n - 2.

Ещё одно замечание — если степень вершины в дереве равна d[i], то в коде Прюфера она будет встречаться d[i]-1 раз.

Чтобы решать задачу D, надо заметить, что фактически мы должны найти количество остовов в графе из CC вершин (где CC — количество компонент связности), но где каждая вершина имеет “вес” S[i] (где S[i] — размер i-ой компоненты связности). Этот “вес” означает, что когда мы подводим к i-ой вершине ребро, на самом деле это ребро можно подвести не одним, а S[i] способами (к любой вершине этой компоненты связности).

Связывая два предыдущих абзаца, задача сводится к тому, чтобы свернуть такую формулу: сумма по всевозможным d[i]>=1 (где сумма всех d[i] = 2*CC-2) таких величин:

s[1]^d[1] * s[2]^d[2] * … * s[CC]^d[CC] * multinom(CC-2,d[1]-1,d[2]-1,…,d[CC]-1),

где multinom(n,k1,k2,..,ki) — это мультиномиальный коэффициент, аналог биномиального, только когда надо выбирать сразу несколько видов объектов (выражается через факториалы очень просто, по аналогии с биномиальным).

Всё, последний шаг — заметить, что “мультиномиальные коэффициенты” + “степени переменных” = любовь :)

В том смысле, что мультиномиальные коэффициенты появляются, когда раскрывают выражение вида:

(x1+x2+..+xi)^j

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

s[1] * s[2] * … * s[CC] * (s[1]+s[2]+…+s[CC])^(CC-2) = = s[1] * s[2] * … * s[CC] * n^(CC-2)

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

(Из этой же серии у меня вот под VMWare недавно получилось, что на языке D map работает якобы в 3 раза быстрее, чем в C++ — что выглядит весьма подозрительно)

Who will read this at LightOJ? One can’t read anything here without registration, and this is really weird.

В E на контесте мне не показалось понятным, что искомый ответ можно представить в виде подмножества выпуклой оболочки. Иными словами, почему не может так получиться, что есть один критический круг, упирающийся в точки P[1] и P[3], и другой — в точки P[2] и P[4]? Хотя сейчас это как-то смутно осознаётся, но чётко пока не могу понять.

Дело тут не столько в C++, сколько в том, что в процессорах Intel давным-давно было принято такое решение: SHL на >31 работает неожиданно — берёт аргумент по модулю 32. Мотивы этого мне неизвестны — может быть, это бывает полезно при оптимизации.

По-моему, уж кто надменен, так это те пара личностей, недавно [недо]покинувших кодефорсес, которые почему-то решили, что это они здесь хозяева-баре…

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

Вспоминая тему примерно полугодичной давности “контесты <=> алкоголь”, я готов поверить, что в не самом адекватном состоянии человек может прекрасно решать контесты :)

Я не большой специалист, но примерно — месяц. Но мне лично 2 года назад сделали за 5 или 6 недель, в общем, тогда я получил визу на руки за несколько часов до вылета :)

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

А кто-нибудь видит какой-нибудь официальный e-mail HackerCup (или другой способ связаться с ними)? Просто хотелось бы побыстрей получить Invitation Letter, ибо сроки для визы поджимают…

Весьма неожиданный способ выстрелить верёвкой.

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

Надо признать, что мне писали об этом на почту, но я всё не находил времени сесть разобраться… Да и во всяких научных статьях конкретно того “Левита”, что у меня, я не находил, поэтому оставалась надежда, что он всё же полиномиальный.

Эх, жалко, такой ведь забавный алгоритм был :)

P.S. Да и всё равно не отнять у него скорости работы на случайных тестах или некоторых графах особого вида (например, граф переходов по клеткам клетчатого поля) — обычное дело, когда на тестах жюри он отрабатывает быстрее Дейкстры :)

А можно не создавать шаблон, а отредактировать стандартные настройки.

Поскольку проекты в VS генерятся javascript-скриптами, придётся залезть в них.

Вариант 1.

Открываем %VS_DIR%\VC\VCWizards\1033\common.js, там находим функцию AddCommonConfig(), в ней исправляем WarningLevel_3 на WarningLevel_4 (в двух местах: для Debug и Release).

Вариант 2 (если хочется менять только для Win32-проектов).

Открываем %VS_DIR%\VC\VCWizards\AppWiz\Generic\Application\scripts\1033\default.js, находим функцию AddSpecificConfig(), и там в двух местах дописываем строки:

CLTool.WarningLevel = WarningLevel_4;

(дописываем их куда-нибудь в подходящее место, например, после строки "var CLTool = config.Tools("VCCLCompilerTool");")

Maybe by O(N^2)-solution a hash-map solution was meant?

If you fix one point, you have to find maximum number of another points that have the same polar angle. So the problem transforms into finding the number that encountered maximum number of times among given N-1 double numbers - this can be done with hash-map (also you can try to replace double angles with pairs of integers - reduced fractions).

У нас в команде (Саратов СУ 2) мы заметили, что прошли через две ступени:

1) узнали про понятие "асимптотика" - т.е. то, как заранее отличать "чёткие" решения от слишком медленных;

2) забыли про понятие "асимптотика" - т.е. стали сдаваться задачи не только с миллиардной асимптотикой, а даже с какими-нибудь 2¹⁰⁰ операций: весь вопрос лишь в качестве отсечений :)

А там достаточно тупое решение.

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

Поэтому решаем так: перебираем, сколько цифр на суффиксе входного числа мы будем менять, и запускаем динамику с двумя состояниями (количество_цифр, сумма_цифр), которая возвращает нам количество таких чисел - и если это количество стало >= T, то мы останавливаемся и выводим ответ, восстанавливая его по динамике.

Точно асимптотику сложно оценить, но работает быстро.

Ну да, хорошое сравнение - Borland Pascal и Eclipse ;)

Вообще вспоминаю время, когда мы во время подготовки к Финалу всё писали на Eclipse, как садо-мазо-развлечения :-D

G (Midsummer Fires):

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

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

Учитывая, что все эти полоски ориентированы по направлению от одной и той же точки - от точки источника света, можно сделать такое решение: отсортировать всё (и полоски, и точки) по расстоянию от источника света и обрабатывать в этом порядке. Мы поддерживаем все текущие полоски в отсортированном по углу порядке (в виде set, например), и тогда для ответа на запрос нам надо просто взять две полоски, соседние по полярному углу с текущей точкой-запросом (можно понять, что другие полоски, чем ближайшие по углу, нет смысла брать).

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

P.S. Задача B тоже интересует, мы не сдали.

AFAIK на наших контестерах пробовали внедрить 2008-й вижак, но в итоге оказалось, что в нём всё только гораздо медленнее - видимо, т.к. STL стала тормознее. И в итоге откатились обратно к 2005-й. Не знаю, возможно, с этой тормознутостью можно бороться какими-то флагами компилятора...

(Правда, есть вариант сделать доступными обе версии на выбор - как с G++ поступили)

Codeforces has become a great stress-test for C++ compilers, and it looks like GNU C++ definetily fails it :)

(there have been about 10 topics here about the code that is wrongly compiled by G++ with -O2 option enabled)

Yes, the running time is O(X (|V|+|E|)), where X is the number of vertices on the left. So if we choose left side as smaller side and right side as larger - it will be much faster that vice versa.

Also it's widely known that in reality this upper bound is never reached.

Additionally, there exists a trick, when before executing the DFS you try to find an straight edge to a non-saturated vertex. This trick greatly improves the running time, and makes the algorithm applicable even for thousands of vertices.

Для суффиксного автомата это решается следующим образом.

Заметим, что одному состоянию автомата может соответствовать несколько строк (причём разной длины). Однако известно, что все строки, соответствующие одному состоянию - их длины образуют некоторый сплошной отрезок [a;b], причём никакая длина не повторяется дважды.

Более того, стандартный алгоритм подсчитывает это число b - оно там называется length. Число a можно найти так: перейдём из текущего состояния по суффиксной ссылке и возьмём его length + 1.

Ну и всё, мы научились узнавать для каждого состояния этот отрезок длин [a;b], теперь надо просто к ответу прибавить длину пересечения этого отрезка с отрезком [l;r].

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

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

Например, Takaoka в 2002 г. предложил алгоритм с асимптотикой O (n^3 * sqrt{ log log n / log n }) ("Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication").

[offtop]

Кстати, меня всегда удивляло - почему нельзя избавиться от рекламы на бесплатных хостингах, просто повесив обработчик сразу после открытия страницы, который кликает куда надо или просто убивает DOM-элемент с баннером? По крайней мере, когда e-maxx.ru ещё жил на бесплатном хостинге, я так и делал :)

Например, у вас это бы выглядело как-то так (на jQuery) :

jQuery(function(){   jQuery('div:eq(1)').remove();   });

Ну, видимо - не боян, но теперь стал им :)

Проблема этой задачи, наверное, в том, что не так-то просто отделить быстрый N^3 Флойда от NM достаточно навороченного алгоритма.

Visual Assist X

А в "голой" студии вряд ли возможно.

Спасибо!

Да, мы на 4:57 поняли, где была допущена маленькая ошибка, на 4:58:30 сдали :)

Я думаю, просто компы сейчас нормальные :) Не всегда было так быстро...

И, кстати, по моим ощущениям g++ всегда ещё дольше, чем cl, компилил. Хотя не замерял - возможно, я не прав.

А что именно непонятно? Само условие или почему это так?

Ещё раз, само условие выглядит так:

если существует такая t, что

d[i][t]<INF && d[t][t]<0 && d[t][j]<INF,

то кратчайший путь (i,j) - бесконечно маленький.

AFAIK, правильно так:

"между вершинами i и j не существует кратчайшего пути тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется d[t][t]<0"

http://e-maxx.ru/algo/floyd_warshall_algorithm

You mean O(K*MlogN)? This is about 10^10 :)

I solved this problem several years ago, my solution was according to the Eppstein's article. And I viewed other solutions - they were in fact the same too.

Кстати, файлы-проекты .sln, .suo, .vcproj, .vcxproj.* и подобные точно не стоило удалять - это же и есть сами проекты :) Они и занимают совсем уж мало места.

Казалось бы, меню Project -> Clean project (или как-то примерно так) как раз и очищает всё это?

А вообще когда-то давно я тоже делал подобную утилиту :) Основное место занимают файлы IntelliSense и .obj-файлы, остающиеся от компиляции каждого .cpp файла.

Да, Кормен ссылается на Тарьяна.

Я пока ещё только приступаю к попытке изучения доказательств (в особенности в свете "ошибок", указанных Zhang), поэтому особо нового мне сказать пока нечего. Но в целом, по ощущениям, скорее китайцы не правы, а Tarjan и соавторы - вряд ли могли допустить настолько серьёзный промах.

Я планирую начать с более современного анализа, проведённого в 2005 г. Seidel и Sharir ("Top-down analysis of path compression"), который, как утверждается, значительно проще доказательств Tarjan.

В википедии пишут, что статья Zhang не прошла peer-reviewing на конференции STOC 2008, после чего была удалена с сайта автора...

Всё же, с вероятностью 99%, доказательство в ней неверно (хотя я проглядел его - доказывалось там как раз для худшего теста, не для случайного).

Я боюсь, таких тестов просто не может существовать - потому что невозможно отделить на практике константу от обратной функции Аккермана (которая <=4 для всех разумных ограничений).

Это скорее теоретический вопрос - является ли время работы DSU настоящей константой, или всё же чрезвычайно медленно растущей функцией.

Как отмечал в своей статье Тарьян, "DSU - это первый (и, возможно, последний) элементарный алгоритм, который имеет настолько сложную доказанную асимптотику". Будет символично, если и у этого уникума DSU асимптотика окажется "простой".

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

Как временное решение можно взять любую вики, хоть мою - проблем никаких нет. Только будет выглядеть это немножко странно - разборы к контестам публиковать на стороннем ресурсе (хотя, если получится оформлять их качественно - почему нет?). Ну и ещё не надо забывать про нерусскоговорящих пользователей - для них e-maxx.ru фактически недоступен, и ссылки на алгоритмы давать не получится.

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

Полезность дорешивания, наверное, трудно отрицать, но если быть честным, мы не часто им занимались :)

Я на всякий случай написал письмо Marsha Poucher, она подтвердила, что сроки действительно такие:

Yes, 13 - 18 May 2012 are the dates of the 2012 World Finals in Warsaw. We realize these dates may not be ideal for all but hope knowing the dates a year ahead will give time for all to make plans accordingly.

Угу, только что.

ОК, понятно, в следующий раз клары к жюри надо писать сюда :-D

Кстати, в D палево в 10 тесте (если, конечно, это не какая-то магия у меня).

Там как будто бы после самого теста идёт какой-то мусор - поэтому у меня был RE на 10 тесте (я обычно с мультитестом пишу решения).

Жюри я писал об этом давно, они никак не отреагировали.

Да, с информацией по целочисленному ФФТ напряжёнка, но когда-то я находил это в одной книге. Сейчас попытался снова откопать - не смог :(

Но, видимо, ответы на все вопросы и так уже получены

===============

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

Или ещё проще - просто сделаем числовой used.

Только хотелось, видимо, совсем арифметического решения без массивов - имхо, маловероятно, что такое решение есть.

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

а с материалом по этой теме вообще проблемы, и именно анализа задач я нигде не видел - сам рад бы был почитать

ну вот есть небольшая подборка (если что-то получится понять из этого конспекта):

http://e-maxx.ru/upload/lections/lection_games.pdf

Спасибо!

Мы тоже почти сразу поняли, как решать так, но посчитали и не стали писать :) Говорят, там есть решение за квадрат, но я не понял, какое