Участников в Radisson, организаторов в Mariott. Mariott гораздо круче

http://lmgtfy.com/?q=acm+icpc+world+finals+2012+schedule

а почему это именно подотрезок?

я почелленжил экспоненциальное решение в своей комнате, но это было тривиал =)

В моем письме все это написано :) а именно: кому, что, когда — все есть это.

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

Не вижу никаких проблем

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

на самом деле цель благая, я помню прекрасно холивары в ПЗ, но тогда и ограничения нужно давать 10⁹?

у нас прошло в даблах путем стопицотзапихивания

Кроме выше сказанного в ряде задач какие-то моменты были написаны в разделе Input/Output. Я все-таки считаю, что этот раздел неспроста часто называется “формат входных-выходных данных”, что бы писать там именно формат, а не ключевые моменты условия.

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

Кроме того, если красивая сказочка засталяет участников очень сильно напрягаться при прочтении, то нафиг такую сказку?

P.S. ладно мы, у нас была просто тренировка, но мне жалко те команды, для которых это было официальное соревнование.

а зачем так делать?

У нас было много wa82, прошло в даблах, только один момент в длинке на c++

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

примерно какое количество участников вы приглашаете?

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

все перенумеровал, тогда искомое — это разность в индексах куда хотели встать и куда встали в итоге

эээ… зачем это все?

задача очень просто решается стандартным сетом в пару строчек

интересно, на финал поедут только те, кому ехать на метро? =)

а есть правило, что участник, занявший первое место во внеконкурса, все равно приглашается на онсайт? :(

[rng_58]> if no one can solve 550 in 24 hours we will unrate the match

Круто сделали :) sarcasm

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

жадность верна или нет — пока сказать сложно, но мне кажется, что нет. Хотя в этой задаче может быть граф очень специфического вида… Например, он транзитивен, это что-нибудь дает?

у меня 5-мерная динамика =) может, есть проще. если пройдет — расскажу

UPD: не прошла, жаль, будем искать косяк

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

а теперь я раздваивал вершины и строил паросочетание

посмотри мое решение выше

меня как раз зачелленжили на этом случае… обидно

попробую объяснить, у меня как-то сложно и запутанно.

сделаем записи такого вида для пар переключателей “x имеет такой же тип, как и y” или “x имеет противоположный тип, чем y”. Это можно сделать, потому что степени лампочек не более чем 2. Тип — это нажмем мы переключатель или нет.

Далее разбиваем граф переключателей на компоненты связанности, каждую компоненту пытаемся сделать двудольной по отношению “x имеет противоположный тип, чем y”.

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

На каждом этапе — проверка, получилось ли сделать его. Например, если одна из компонент не двудольна, то ответ сразу  - 1, если есть включенная лампочка, а переключателя для нее нет — тоже, и т.д. Много проверок…

Объяснил плохо, посмотри мой код.

P.S. Систестов не было, не знаю, пройдет или нет. Идейно вроде правильно

P.S.S. Прошло. FUCK YEAH.

2SAT не будет работать, он не минимизирует ответ

Однако вспоминается история http://codeforces.ru/blog/entry/1067 , бывает же точно наоборот)

видимо, на этот тест ответ все равно CANNOT, не?

у меня в комнате очень быстро сломали такое

wantedParity = 1

x = -1, y = 0

тогда (x + y) % 2 == -1, а не 1

меня одного во время челленж-фазы постоянно выкидывало с сообщение “connection is lost”? +50 я так и пролюбил… :(

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

Мне в целом пофиг, я уже прошел

Но я разочаровался, да и вообще я вижу большую разницу между “соревнование по необычным правилам” и “соревнование на необычном языке”

каким образом достигается связность полученного эйлерового графа? почему ответ у тебя не получится состоящим из нескольких компонент?

мы просим о любых случаях читерства сообщать любому из авторов в ЛС, вы можете найти ссылки на профили в тексте поста.

на самом деле достаточно давно уже изменили, я где-то с месяц назад заглядывал в расписание — уже был Нью-Йорк

я чуть выше написал свое решение, которое сдал в дорешку. тынц

я не жюри, но мне кажется мое эстетичным

Очень простое решение, состоит из некоторых очевидных фактов:

1. пусть в ответе есть num кубиков цвета c (ну и еще какой-нибудь цвет). Утверждение: эти самые num кубиков максимальные из всех с цветом c.

2. выпишем тройки следующего вида (sum, num, c), означающие, что если мы возьмем num кубиков цвета c, то максимальная сумма равна sum. Утверждение: количество таких троек равно O(n), а даже ровно n.

3. Сгруппируем все эти тройки по величине num. Утверждение: для фиксированного num из всего множества троек с этим num нам нужно лишь не более двух троек с максимальными sum, то есть два максимума, все остальные бесполезны и мы их выкинем.

4. Переберем k — сколько мы возьмем кубиков некоторого цвета, тогда другого цвета (не теряя общности) мы должны взять или k или k - 1 штук. Утверждение: раз мы для каждого k оставили не более двух максимумов, то можно перебирать втупую.

Очень простое и короткое решение, реализовать можно за O(n·log(n)).

http://codeforces.ru/contest/159/submission/1337673

мне кажется, что у вас num — это количество элементов меньше или равных a[k / n], а должно быть просто равных.

Потому что писалось в темпе и не очень внимательно. Я поправил, спасибо

http://codeforces.ru/blog/entry/4012#comment-81960

как раз речь о том, что использовать астрономическое время не совсем точно, оно сильно зависит от текущей загрузки системы. Процессорное — не зависит от того, что вы еще параллельно делаете

под линухой можно запускать через time :)

Не очень точно, потому что clock() возвращает астрономическое время. При тестировании используется процессорное, а его изнутри программы я не знаю, как считать.

А, простите, я уточню — я использую Google Calender, и вот там нет этого. И мой bug issue относился именно к нему.

Где взять ссылку показанную страницу?

я не имел ввиду ничего плохого :) я полностью за развитие этого проекта, и использую его очень активно

на http://clist.x10.mx/ нет контестов CF, ни одного раунда из VK cup, даже квалов.

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

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

В конце концов генерите макстест и тестируйте на стороне сервера.

чуть впереди)

забавно, что многие в 500 ловятся на тесте:

##.. ##.. ..## ..##

круто. жуткое извращение, конечно… но красиво

Ну да, я придумал именно решение с 2-sat, но граф огромный…

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

а это в каком формате написано?

Спать наверно пошли =) а Америке уже ночь… вообще печально, потому что сидишь тут, ждешь…

Я вообще не очень понимаю, чем вызвана такая задержка в тестировании каждого раунда, GCJ давным-давно научился сразу результаты показывать

а у кого можно узнать, когда будут результаты?

Очень интересно, как решать Unfriending, Придумал только за O(n²·log(p) + n·SumSizesOfGroups).

You can run your code on the server-side. Use “custom test” tab in the contest dashboard.

You must normalize pref array like this way: for(int i = pref.length - 2; i >= 0; i--) pref[i] = min(pref[i], pref[i + 1]);

You must do the same for suff array.

VS2010 особенно тупая IDE, и прога на зависла, она просто очень мееееееееееееееееееееееееееееееееееееееееееееееееееееееедленно работала. Видимо, VS пихает в конструкторы исключительно много debug-кода. Это легко заметить, запустив свою программу комбинацией ctrl-f5, должно быть принципиально быстрее.

в моей комнате многие ломались на тестах из одной строчки — «.9.», «9.9» и «999»

Не вижу причин отказываться от такого предложения ☺ более того, такие «предложения» стоит выполнять, а не обсуждать ☺

12. +1