(с) SnarkNews
В кратце описание системы - когда вы посылаете задачу, вы можете ее послать по нормальному, по ACM-овски, либо вы можете послать ее в темную. Во втором случае она останется в монике до конца как знак вопроса, и перепослать или что-то еще сделать по ней нельзя.
В конце соревнования все темные проверяются, и за успешные дают 1.5 балла.
Мне одному кажется, что в этом соревновании будет просто невероятно заруливать удача? По-моему совершенно любой человек может накосячить на любой задаче с каким-то шансом. Очевидно, что по простой задаче никто никогда в такой системе не отправит в светлую - это тупо. Значит все почти участники поощрительные задачи будут сабмитить в темную.
У трети из них она не пройдет, и это сразу совершенно случайным образом даст кому-то фору в 1.5 поинта :о Если простых задач парочка, то это еще круче раскидает людей.
Было бы еще разумно, если бы у задач были какие-то назначенные им поинты, и падение простой задачи не равнялось бы по поинтам падению гроба, а в таком виде это будет полюбому лотерея.
Вообще возникает устойчивое ощущение, что снарк не любит штрафы. Те, кто писал в его системе АСМ+ думаю помнят, что там штраф полностью лишает вас возможности бороться за призовые места с теми, кто штраф не сделал :о
А еще интересно, что же вообще значит TCM. Это типа TC и ACM вместе? От TC получается взяли только проверку в конце? Или это как-то по умному еще расшифровывается?
Простые я многие не решал, так как во время тура не мог писать нормально, а на дорешивании это не очень интересно, но общая идея такая:
C кажется просто надо сделать что написано
F видимо дийкстра
G это поощрительная задача
и J - есть острое сомнение, что на Java и BigDecimal сдается моментально.
Задача B.
Решать будем для каждой отдельной компоненты связности.
Сначала избавимся от очень дурацкой вещи - вершин со степенью один. Легко доказать, что если степерь вершины равна единице, то и степень смежной ей вершины тоже единица. Отлично :о) Это мы покрасить можем.
Теперь полагаем, что степень всех вершин не единица.
Возьмем произвольную вершину, и покрасим ее в первый цвет. Возьмем любую смежную с ней вершину, и покрасим во второй. Теперь будем до победного делать очевидную вещь - если у вершины есть смежные ей двух разных цветов, красить ее в третий.
Теперь легко доказать, что это покрасит всю компоненту связности. Пусть это не так. То есть в какой-то момент времени мы остановились, и осталась хотя бы одна вершина, не покрашенная. Очевидно, что тогда есть ребро, связывающее покрашенную и не покрашенную вершину. Пусть покрашенная вершина - А, а непокрашенная - Б. Так как А покрашена, у нее есть две смежных вершины ей двух других цветов (иначе почему бы мы покрасили А?), возьмем только одну из них, другая нас не интересует. Пусть эта вершина - В. То есть мы имеем вершину А одного цвета, смежную ей вершину В другого цвета и смежную вершине А вершину Б не покрашенную. В и Б не обязательно смежны, но! между В и Б есть путь, пролегающий через вершины, смежные А (по условию того, что все вершины, смежные с А, образуют связный граф). Пусть эта цепочка В-Х1-Х2-Х3-Б. Обратите внимание, что мы можем ее покрасить. Х1 смежна с В и А, которые разных цветов, и потом красится в оставишйся, аналогично красится Х2, далее Х3, и наконец, Б. То есть Б не могла остаться не покрашенной.
В общем задача требует от нас покраски в лоб по большому счету.
Задача D
Первое наблюдение - оба дуэлянта никогда не зайдут в одну боковую аллею, так как это pointless. Если дуэлянт входит в аллею, где сейчас другой дуэлянт, это странно - они тогда точно столкнуться, в тоже время не войдя в нее мы гарантированно избежим столкновения.
Если дуэлянт входит в аллею, где был другой дуэлянт прежде, то значит они уже разошлись - это вообще не имеет смысла рассматривать :о)
То есть до момента, когда дуэлянты столкнутся или разойдутся, каждая боковая аллея будет посещена максимум одним из них. А значит решать можно так:
1. Закрепим за 2^20 в какие из боковых аллей хотя бы один дуэлянт войдет
2. Создадим четыре типа событий (первый дуэлянт вошел в аллею, второй дуэлянт вошел в аллею, первый вышел ,второй вышел) и пойдем по событиям, пока либо второй не окажется выше первого без столкновения, либо пока они не столкнутся.
Задача E.
Для каждого отрезка АВ построим прямую, перпендикулярную ему и проходящую через точку А, и другой, проходящий через точку В. Для каждой такой прямой будем хранить два списка перпендикулярных ей отрезков - те, у которых левый конец лежит на этой прямой, и те, у которых правый конец лежит на этой прямой. Для вертикальных отрезков, у которых нет левых и правых концов, соответственно будем брать нижний и верхний.
Для каждой прямой оба списка должны быть отсортированы по удалению лежащего на этой прямой конца отрезка до какой-то очень далекой точки на этой прямой.
Теперь рассматриваем каждый отрезок СД. Для скольких букв Ш, у которых торчалки идут вправо (или если лежачая палочка строго горизонтальная, то идущих вверх) она будет лежачей палочкой? Очевидно, чтобы посчитать это, надо понять
а) У скольких отрезков левый конец лежит на этой прямой, в точности в точке С
б) У скольких отрезков левый конец лежит на этой прямой в точности в точке Д
в) У скольких отрезков левый конец лежит на этой прямой между точками С и Д.
И перемножить эти три числа.
Так как мы знаем все отрезки, у которых левый конец лежит на прямой, содержащей СД, и они у нас отсортированы, ответить на все три вопроса кажется не очень сложным.
Аналогично считаем, сколько букв Ш идут в обратную сторону от закрпленного отрезка. Рассматриваем так каждый отрезок в роли лежачей палочки, суммируем ответ. Получается что-то вроде N log N.
Задача I (разбор предоставлен Сергеем Штейнером)
Нам нужно вычислить сумму весов остовных деревьев, делённую на их количество. Вычислим для каждого ребра, какой вклад оно даст туда. Понятно, что i-е ребро появится в сумме N - N_i раз, где N - количество остовных деревьев вообще, а N_i - количество остовных деревьев, не содержащих i-е ребро, то есть количество остовных деревьев в графе с удалённым i-м ребром. Заметим, что для всех рёбер, инцидентных одной и той же паре вершин N - N_i одно и то же. Итак, осталось научиться вычислять количество остовных деревьев в мультиграфе. Тут нам на помощь приходит матричная теорема Кирхгофа:
http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%8...
Теперь мы перебираем все пары вершин и за O(n^3) считаем ответ для каждого ребра. Итоговая сложность O(n^5).
Задача К.
Нам нужна структура данных, позволяющая удалять один элемент, и говорить в какой позиции находится K-ый максимальны, и выполнять оба действия быстро.
Чтобы сделать это можно поддерживать два дерева, которые говорят, в каких позициях в оригинальном массиве нет уже элементов, и в каких позициях в отсортированном массиве нет элементов. Первое дерево позволяет по сдвинутой позиции получить оригинальную позицию (это надо для удаления, чтобы понять какой же элемент удалить), второе - ответить на вопрос, какое же сейчас число I-ое по величине.
Оба действия получаются log n
Задачу А более менее кажется понятным как решать - в каждый момент времени возможные позиции наших войск - это многоугольник с вырезанными дырами. С ходом времени все вершины внешнего многоугольника двигаются по диагонали в сторону расширения, а всех дыр - по диагонали в сторону уменьшения дыры. Когда происходит взрыв, надо улучшить многоугольник, вырезав из него квадрат, который взорвали, и так дальше продолжать. Это видимо самая сложная чась.
Или я не прав?
Задача H мне очень интересна after all :о)
Don't miss it. You can find additional information here:
http://code.google.com/codejam
Пост содержит explicit content. Если вам нет 18, возможно его не стоит читать :о)
Для тех кто не в курсе, 6-ого апреля у меня был День Рождения. К сожалению, шестое апреля выпало на середину рабочей недели, и куда-то вырваться в этот день было невозможно - так что празднование перенеслось на пару дней, чтобы зацепить оба выходных. Я взял отпуск на работе на пятницу, и уже в четверг вечером мы отправились в Вегас.
Прилетели мы около 10 вечера (да, фотография выше сделана явно не в тот же день :о)), зачекинились в экскалибур и пошли гулять. Машина мечта была увидеть фонтаны перед Беладжио, и от экскалибура до туда на первый взгляд должно было быть близко. Это было только на первый взгляд, реально там было фигачить пешком пол часа, и этот путь за три дня мы прошли наверное раз 10 :о(
Пока мы дошли до фонтана уже была полночь, и он не работал. Мы зашли в планету Голливуд, просрали кучу бабла в блэкджек и расстроенные пошли в экскалибур. На утро первым делом запечатлели меня с нашим отелем :о)
Вот вид на отель покучавее:
От экскалибура открывается отличный вид на стрип
Вообще, в Вегасе много всего удивительного и красивого. Отели пытаются как-то удивить посетителей. Я больше всего тащусь от оформления отлелей Нью-Йорк Нью-Йорк и Париж (после экскалибура, конечно :о))
Нью-Йорк Йью-Йорк находится через дорогу от экскалибура и изображает Манхэттен. Одна из фишек этого отеля - это неслабые американские горки с полным комплектом - долгий медленный подъем с резким спуском, мертвые петли, езда вверх головой. Когда я послдений раз был в Вегасе два года назад, это было одно из самых запомнившихся событий. В этот раз мы на них так и не прокатились, потому что Маша не решилась, а я один че-то не очень захотел.
Париж находится в самом центре Стрипа, и основная его фенька - это в два раза уменьшенная копия Эйфелевой Башни.
На самом деле это было бы не так круто, если бы напротив Парижа не было отеля Беладжио, а перед Беладжио не было невероятно крутого фонтанного шоу. Опять же возвращаясь к моей поездке в Вегас два года назад - однажды Маша пересматривала видео с того раза и смотря на видео с фонтаном думала о том, что ей никогда в жизни не увидеть его вживую. Поэтому с утра первым делом пошли смотреть на фонтаны опять. И они опять не работали, в этот раз потому что слишком рано. Даже с земли фонтаны смотрятся просто невероятно, а с Эйфелевой Башли это вообще не передаваемо.
В общем после второй неудачной попытки посмотреть на фонтан мы пошли дальше по стрипу в направлении к Миражу, посмотреть на вулкан. Вулкан был больной темой - на ТЦО я был в мираже три дня и даже не знал, что там вообще есть вулкан. После этого все, кому я не говорил, что мы останавливались в Мираже, спрашивали меня про то, как мне понравился вулкан, и я не мог ответить ничего вразумительного.
Вулкан тоже накрылся. Опять же потому, что было слишком рано.
Далее, надо отметить, что до Лас-Вегаса я не пил вообще ничего алкогольного, даже пиво, в течение полутора лет. Но в Вегасе продолжить это не удалось. Так что в Мираже мы взяли по коктельчику и двинулись в направлении Стратосферы. Надо отметить, что коктейли в Вегасе продаются в таре, которой хватает на пол дня
Как многие наверное знают (а кто не знает, узнает сейчас :о)) на стратосфере есть три аттракциона. X-scream - паровоз, который мчится с вершины стратосферы вниз в бездну по конечным рельсам и останавливается в последний момент останавливается, Insanity - каруселька, которая вылазит за пределы башни, наколняет всех на 45 градусов и начинает крутиться, и Big Shot. Вот Big Shot - это то, на что пошли мы. Я всегда его считал самым страшным аттракционом из трех, что оказалось не совсем так. Немного о нем. Сама стратосфера - это 350 метровая башня. Над ней возвышается шпиль. Точную высоту шпиля я не знаю, но на вид снизу высота шпиля равна где-то трети от высоты башни, то есть грубо говоря 100 метров.
Люди садятся на удобные места вокруг шпиля, после чего их с огромной скоростью поднимают где-то на половину от его высоты, и отпускают вниз с такой же огромной скоростью. То есть, люди, уже находящиеся на высоте 110 этажного дома, за несколько секунд поднимаются еще примерно на высоту 15-20 этажей и летят вниз, при этом просто сидя на седушке со свешенными ногами
С аттракциона остались отличные фотки, сделанные специально установленной там камерой. Забавные радостные лица до старта, и полные ужаса после :о) Маша не нравится себе с застывшим ужасом на лице и не хочет видеть этот кадр в интернете :о)
На обратном пути мы пошли к Беладжио, где Маша наконец-то увидела первый раз в своей жизни танцующие фонтаны
День продолжался, коктейли из Миража кончились, начались новые, из Парижа.
Далее вечер был все ближе, и надо было уже думать на какое шоу идти. Не смотря на то, что реально мы были в вегасе три дня, вечер пятницы был единственным, когда мы могли пойти на шоу, потому что суббота была запланирована на другие дела, а воскресенье вечер мы уже должны были застать в самолете. Вариантов шоу у нас было три. Концерт группы AC/DC, выступление Дэвида Коперфильда и стрип шоу с участием Холли Мэдисон. На концерт AC/DC можно было пойти разве что чтобы посмотреть на прыгающего на одной ноге с гитарой Ангуса Янга, но это явно не стоило целого вечера. На Коперфильда было два варианта. За 200 баков с рыла можно было после выступления сфоткаться с ним, а за 60 баков только посмотреть концерт. Первый вариант был бы клевый, но 400 баков было как-то жалко. А просто идти смотреть на фокусы - я могу Акопяна посмотреть на ютубе :о) В общем я двумя руками был за Peepshow с Холли. В буквальном смысле слова
Шоу было awesome. Даже если забыть о том, что это было стрип шоу, танцы были поставлены очень клево, были всякие смешные интермиссии, выступление я не знаю как это называется, короче когда мужик выступает на свисающем в потолка канате, прикольно вплели публику на первых рядах (один из ребят оказался подсадным, и потом неплохо укатывал тоже со сцены). Все это было заплетено в не очень умный сюжет, и кульминацией было то, на что видимо пришло половина зала - обнаженный бюст Холли. Силикона там анрил... :о)
Так кончился первый день. Второй день был целиком посвящен полету на Гранд Каньён.
Если вы когда-то мечтали полетать на маленьком самолетике, лучше размечтать обратно. При определенном стечении пилота, самолета и погоды=турбулентности через пол часа полета желудок очень просится наружу :о) Мы вроде пережили полет туда.
Первым делом мы поехали к стеклянному мосту - известному достаточно аттракциону над каньёном. В сущности он именно то, что отражено в его названии - стеклянный мост :о)
Ходить по нему нереально страшно, чтобы сделать эту фотку я вообще не знаю как пересилил себя. Потому что высота под мостом порядка 500 метров - полторы стратосферы, а стекло не выглядит очень толстым. В общем всякие американские горки отдыхают :о)
Дальше на каньоне уже было не так интересно, хоть и очень красиво.
Кстати, кто видит на следующей фотке орла?
Вечером того дня, после Каньена (кстати на обратном пути или погода была лучше, или пилот опытнее, или самолет круче, но летели мы гладко и без особых неприятных ощущений), мы вернулись к Эйфелевой Башне, чтобы уже посмотреть на фонтаны вечером. Очередь на башню была такой, что ожидаемое время (там оно оценивается) было один час. Пришлось доплатить и уже через пять мин мы были наверху. Фонтан сверху смотрится awesome, настолько awesome, что отвлекаться на то, чтобы снимать его не хочется. Вид на вегас с башни тоже awesome
Спустившись с башни мы вернулись к фонтану, чтобы все-таки сделать его видео
(значит вставка ролика накрылась, потому что тут знак доллара работает отлично. ссылка на видео: http://video.mail.ru/bk/shd/las_vegas/241.html)
Первые две минуты используется только небольшая часть всего арсенала. Самое интересое в конце :о)
В общем так все и прошло. Третий день зашел уже плохо. После двух дней непрерывного потребления алкогольных коктелей с полутора годами без капли алкоголя немного мучало похмелье и не давало наслаждаться днем. Только во второй половине стало получше, и вдарив еще по яблочному мартини мы пошли рубать на игровых автоматах. 40 долларов превратились в 50, и мы радостные, что хоть раз нам удалось выиграть (не важно что порядок выигрыша не сопоставим с тем, что мы успели проиграть до этого), отправились домой.
Характерно, что после всего четырех месяцев работы на C# я уже чуствую неудобство работы на других языках. Как однажды сказал один крутой (для меня :о)) ACM-щик, "я пишу не на С++, я пишу на STL". Вот также и тут, я пишу не на C#, я пишу на Linq :о) Потому что без Linq С# это таже самая Java, только без BigInteger (BigInteger появился тоже только в .NET 4.0). И поэтому я должен сказать спасибо Михаилу, так как реально сегодня нормальной версии C# с Linq почти нигде на регулярных соревнованиях нет (и на TC и у снарка C# cтарый, без Linq).
Теперь немного рекламы. Почему же я тащусь от C#.
1. Мне не надо писать тип объекта, который я создаю. На С++ это не проблема, но на Java в принципе она проявляется, хотя, конечно, Java программисты на нее не обращают внимания. Допустим,
List<int> q = new List<int>( );
Тупо - я пишу тип дважды. Конечно, это плохой пример - любая интегрированная среда сразу после набора слова new предложит по Enter или типа того тим переменной, и реально человек наберет List<int> только однажны. Но что, если мне надо
(тип переменной) q = SomeClass.SomeMethod( ).SomeOtherMethod( )...
Я не хочу задумываться, какого типа будет возвращаемое значение этого SomeOtherMethod, я могу вообще теоретически не знать до набора этой строки, какой будет тип. В C# на этот случай есть ключевое слово var.
var lst = new List<int>( );
var q = SomeClass.SomeMethod( ).SomeOtherMethod( )...
Всегда, когда компилятор может сам понять тип переменной (то есть грубо говоря всегда, когда вы ее сразу инициализируете), ее тип можно не указывать лапками.
2. Мне не надо создавать типы данных под все подряд
Я хочу создать переменную, с тремя полями: id, x и y. Когда параметров два, C++ шники всегда юзают pair - это круто, в Java даже для двух надо делать отдельный тип. В любом случае, если полей три, то на C++ тоже надо создавать новый тип. На C# все проще
var q = new { id = 4, x = 4, name = 5 };
И все, мне не надо проматывать код чтобы создать новый класс. Но вы не прочуствуете всей мощи этого, пока не прочитаете пункт 3.
3. А теперь, когда у меня есть непонятные типы, я хочу их сортировать. Я не хочу переопределять операторы, мне лень это делать :о Приходит на помощь Linq. Допустим, что qs - это массив чего-то типа q, который я создал на прошлом шагу
var qs_sorted = ( from q in qs orderby q.id select q );
И все. Никаких переопределений операторов :о)
Я хочу отфильтровать его, оставив только те, где x < 10?
var qs_filtered = ( from q in qs where q.x < 10 orderby q.id select q );
Я хочу при этом получить только x и y, и откинуть id?
var qs_xy = ( from q in qs where q.x < 10 orderby q.id let x = q.x let y = q.y select new { x, y } );
4. Это уже не про язык или платформу, а про среду. Почему многие любят C++? Потому что там можно записать макросы для циклов. На топкодере почти у всех есть макрос для фора. Потому что в 90% случаев фор делается по проторенной дорожке for( i = 0; i < n; ++ i ) или for( i = n - 1; i >= 0; -- i ). Меняется только i и n. Разумеется, у всех набита рука вбивать это дело, но хочется все-таки вбивать только i и n. Поэтому макросы типа FOR(i,n) или rep(i,n) или типа того очень популярны. В Visual Studio мы делаем так. Пишем for, дважды бьем кнопку Tab, нам сразу разворачивается вся конструкция и курсор установлен на то место, где мы хотим вбить название переменной. И название сразу i. Меняем название на j, все три вхождения i меняются на j. Жмем tab, попадаем на length, меняем length на то, что нам надо, скажем n, жмем Enter и попадаем в тело цикла. Надо цикл с конца - делаем все тоже самое, написав в начале forr вместо for. Эта фишка называется Code Snippets, и она реально крутая. Не удивлюсь, если в других средах разработки она тоже есть.
5. Добавим к этому перегрузку операторов, которая все-таки есть, параметры по умолчанию для методов, причем более мощные, чем в C++ - грубо говоря вы не обязаны предоставлять параметры для функции по порядку, вы можете сделать 100 параметров, все с значениями по умолчанию, а потом вызвать эту функцию, передав только 18-ый и 99-ый. В С++ вы обязаны передавать параметры начиная с начала и поюзать значения по умолчанию только для подрядидущих с конца параметров.
Но видимо это все уже олимпиаднику не надо :о)
С учетом SortedSet и BigInteger в .NET4.0 C# в принципе будет иметь все, что надо в стандартной библиотеке. Сегодня приходится использовать SortedDictionary вместо SortedSet, что немного тупо :о( И для длинной арифметики приходится писать на Java не редко.
Кстати, в .NET 4.0 для BigInteger перегружены все опреаторы, и с ним можно тискаться как с любыми другими типами :о) Это вам не громоздкие конструкции на Java писать с тонной вызовов методов :о
а) erase 0 в задаче B в тесте 42 :о)
б) пробелы до и после # в задаче E в тесте 139. AC по ней через 28 секунд после конца контеста/начала дорешивания :о) на контесте правильное решение отправил наверное через секунду после конца :о(
UPD: Если кому-то интересно, WA19 в задаче E обозначает что вы не учитываете случай, когда перед вызовом макроса стоит -, а внутри макроса плюсы или минусы. Это не ОК :о)
Забудем про то, что в Моно нет SortedSet, и участники, использующие C# оказываются позади тех, кто юзает C++ или Java по любой задаче, где надо строить любые деревья.
Практический пример. Задача E с последнего раунда. Решение за квадрат:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace moomoo
{
class Program
{
static void Main(string[] args)
{
int k;
int n;
string s = Console.ReadLine();
var ss = s.Split(' ');
n = int.Parse(ss[0]);
k = int.Parse(ss[1]);
s = Console.ReadLine();
int[] h = (from v in s.Split(' ') select int.Parse(v)).ToArray();
int ans = 0;
List<KeyValuePair<int, int>> ansv = new List<KeyValuePair<int, int>>();
List<int> mx = new List<int>(); ;
List<int> mn = new List<int>();
int lf = 0;
for (int i = 0; i < n; ++i)
{
mx.Add(h[i]);
mn.Add(h[i]);
mx.Sort(); mx.Reverse();
mn.Sort();
while (mx[0] - mn[0] > k)
{
for (int j = 0; j < mn.Count; ++j) if (mn[j] == h[lf]) { mn.RemoveAt(j); break; }
for (int j = 0; j < mx.Count; ++j) if (mx[j] == h[lf]) { mx.RemoveAt(j); break; }
++lf;
}
int cur = i - lf + 1;
if (cur > ans)
{
ans = cur;
ansv.Clear();
ansv.Add(new KeyValuePair<int, int>(lf + 1, i + 1));
}
else if (cur == ans)
{
ansv.Add(new KeyValuePair<int, int>(lf + 1, i + 1));
}
}
Console.WriteLine(ans + " " + ansv.Count);
for (int i = 0; i < ansv.Count; ++i) Console.WriteLine(ansv[i].Key + " " + ansv[i].Value);
}
}
}
Очевидно получить TLE. Система возвращает RE на тесте 7.
Меняем местами первые две строки (int k; и int n;). Отправляем - RE на тесте 5. То есть порядок объявления переменных важен для прохождения двух тестов? Добавляем пробел, перевод строки, что угодно - RE на другом тесте. Можно дойти аж до девятого, можно упасть на первом.
Я переписывал это решение дважды целиком с нуля, и каждый раз эта история.
"( ).( )"
Задача С
Давайте введем понятие баланса некоторого префикса подстроки - на сколько открывающихся скобок больше в этом префиксе, чем закрывающихся. Понятно, что некоторая строка является правильной скобочной подпоследовательностью, если для всей строки баланс равен нулю, а для любого ее префикса не отрицателен. Посчитаем баланс для каждого префикса данной нам в задаче строки и сложим их в массив prefs. Теперь рассмотрим любую подстроку это строки - пусть она идет от символа с позицией l включительно до символа в позиции r исключительно. Эта подстрока - правильная скобочная последовательность, если prefs[l] == prefs[r] и prefs[i] >= prefs[l] для любого i в интервале [l, r). Как нам теперь, зная это, найти максимальную подстроку правильную и их количество? Будем делать примерно так: поддерживать стек пар (баланс-позиция) - на какой позиции в строке впервые был замечен такой баланс, после которой еще не встречался меньший баланс. На самом деле можно даже хранить только позиции, потому что баланс всегда очевиден - в последнем элементе в стеке всегда будет текущий баланс, в предпоследнем на единицу меньше итд. Рассмотрим теперь скажем последовательность ((()())))(()). Балансы: 1,2,3,2,3,2,1,0,-1,0,1,0,-1
Будем идти слева на право и поддерживать наш стек следующим образом: добавляя открывающуюся скобку добавлять в стек позицию этой скобки, а добавляя закрывающуюся удалять последний элемент из стека, улучшая ответ. Пример с нашей последовательносью:
1. Помним, что на позиции 0 (то есть до добавления любой скобки) баланс был 0. То есть сейчас стек: 0
2. Добавляем первую скобку. Занесем ее позицию в стек. Стек: 0,1
3. Добавим вторую скобку. Занесем ее позицию в стек. Стек: 0,1,2
4. Аналогично для третьей скобки. Стек 0,1,2,3
5. Четвертая скобка - закрывающаяся. Соответственно удалим последний элемент из стека, Текущий стек: 0,1,2. Запоминаем, что мы нашли последоательность длины 2 (позиция-последний элемент в стеке после удаления, 4-2=2).
6. Пятая скобка - открывающаяся, добавим ее в стек: 0,1,2,5
7. Шестая скобка - закрывающаяся, удалим из стека последний элемент, запомним, что мы нашли последовательность длины 4. Стек: 0,1,2
8. Седьма скобка - закрывающаяся, удалим из стека последний элемент, запомнив, что мы нашли последовательность длины (7-1)=6. Стек: 0,1.
9. Восьмая скобка - закрывающаяся, удалим из стека последний элемент, запомнив, что мы нашли последовательность длины (8-0)=8. Стек: 0
10. Девятая скобка - закрывающаяся, удалим из стека последний элемент. Стек: пустой.
11. 10-ая скобка закрывающаяся, но стек и так пустой - ничего не меняем.
12. Скобка открывающаяся, стек: 11
13. Скобка открывающаяся, стек: 11,12
14. Далее две закрывающихся скобки очистят стек и еще одна ничего не изменит, ответа больше 8 найдено не будет, таким образом мы нашли ответ 8.
Задача D
Это задача хитрая на рассмотрение граничных случаев.
Сначала случаи до столба:
1. Самый простой - мы разгоняемся до макисимальной скорости, едем на ней участок и тормозим до скорости w. Достаточно просто - считаем время t1 и расстояние s1, проехав которое мы наберем макс. скорость, время t2 и расстояние s2, проехав которой мы с макс. скорости затормозим до w, проверяем, что сумма этих расстояний меньше d, прибавляем время t3=(d-s1-s2)/v, которое мы будем ехать с макс. скоростью. На второй участок мы попадем со скоростью w.
2. Вариант второй - мы не успеваем разогнаться до максимальной скорости и затормозить до скорости w к столбу, то есть s1+s2 > d. Тогда все очевидно - ищем, до какой скорости мы можем разогнаться (я делал это бинарным поиском, но не сомневаюсь что это не обязательно :о)), и считаем сколько времени уйдет чтобы разогнаться до нее и затормозить с нее до w. На второй участок выходим со скоросью w.
3. Третий случай - мы вообще за интервал d не успеваем даже разогнаться до w. Тогда проезжаем весь интервал d на разгоне, на второй участок выходим со скоростью, которую успели набрать.
Тут есть корнер кейс, который зачем-то поместили в первый семпл - если w > v, и третий случай рассматривается до первого, и за интервал d нельзя достичь скорости w, но можно успеть достичь скорости v. Тогда можно ошибочно на первом интервале разгоняться до скорости большей v. Но наличие первого семпла спасало от такой ошибки (и меня от лишнего штрафа :о))
На второй интервал мы выходим либо со скоростью w, если мы попали в первые два случая, либо со скоростью меньшей, если в третий. Теперь тут два достаточно простых случая - мы либо разгоняемся до максимальной и проезжаем часть дороги на максимальной скорости, либо, если мы не успеваем за оставшийся фрагмент дороги достичь максимальной скорости, просто проезжаем весь участок с ускорением a.
Задача E.
Задача подозрительно похожа на задачу С :о)
Найдем максимальный элемент в последовательности и сдвинем все так, чтобы он оказался первым (или любой из них, если их несколько). Теперь, если не учиытвать максимальные холмы, мы можем полагать, что холмы расположены на не окружности, а в ряд, что упрощает задачу. Дальше отдельно решим для пар холмов, оба из которых не максимальной длины, для пар холмов, один из которых не максимальной длины, и для пар холмов, оба из которых максимальной длины.
1. Как посчитать количество пар, где оба холма ниже максимального? Будем идти слева на право, поддерживая стек высот холмов, которые теоретически еще могут быть видны, и их количеств. Разумеется, этот стек всегда будет содержать высоты, идущие по убыванию. Добавляя очередной холм:
1.а) если он максимальной длины, просто очистим стек (ничто не может быть видно, он все загородил), и НЕ улучшаем ответ, и НЕ добавляем его в стек, так как сейчас считаем ответ только для пар, в которых оба холма ниже максимального.
1.б) иначе, пока последний элемент в стеке содержит высоту ниже текущего холма, удаляем этот элемент, прибавляя количество таких холмов к ответу (каждый из этих холмов виден с нашего более высокого).
1.в.i) если после этого высота последнего элемента в стеке равна нашей, прибавим его количество и еще единицу, если в стеке хотя бы два элемента (потому что мы видим все холмы нашей высоты и еще ровно один выше, если он существует)
1.в.ii) если же после этого высота последнего элемента в стеке выше нашей, то просто прибавляем к ответу единицу (мы видим только этот самый правый холм).
1.в.iii) если же стек после 1.б. остался пустой, не меняем ответ.
1.г) если последний элемент в стеке равен нашему, увеличим его количество. Иначе добавим в конец стека текущий элемент с количеством=1.
1.д) пройдя так по всему массиву мы посчитаем количество пар, где оба холма ниже макисимального
2. Как посчитать количество пар, где один из холмов максимальный, а второй нет? Очень легко, начиная от каждого максимального холма идем влево и вправо пока не встретим другой максимальный холм, и считаем сколько холмов мы видим. Это будет линейное время, потому что каждый элемент будет пройден ровно дважды: от холма максимальной высоты слева от него и от холма максимальной высоты справа от него.
3. Как посчитать количество пар, где оба холма максимальны? n*(n-1)/2 где n - количество холмов максимальной высоты.
Затем суммируем ответы из 1, 2 и 3.
1. ACRush (Lou Tian Cheng )
2. Petr (Петр Митричев)
3. UdH-WiNGeR
4. Tomek (Tomas Czaika)
5. Tourist
(Где-то перед шестым местом должен быть SnapDragon, он же Дэрек Кисман)
6. Marek Cygan (слева)
7. 8. Оба молодых человека мне не знакомы
9. bmerry
10. Дмитрий Джулгаков - от камеры скрылся
11. Андрей Станкевич
12 и 13 у меня нету
14. Eryx
15. nika (Н.Джимшелеишвили) (справа)
Пропускаем до 21-ого места
21. Burunduk3 - Олег Давыдов
25. Владислав Симоненко (vlad89) слева и 30. Андрей Гриненко (Gluk) по центру... Не очень удачный кадр :о)
Дальше дыры все больше :о)
Все медалисты СНГ 2010: http://blogs.mail.ru/bk/shd/52BBEFEB283AD6E9.html
Ну и конечно было бы преступлением не упомянуть Снарка, человека, поддерживающего всем известный сайт snarknews.info, открытый кубок и SN(W/S)S
Сейчас читал сообщение в блоге Alex_KPR про Казань и удивился тому факту, что ребята пишут в dev_cpp.
Среды разработки - это интересная тема. Если в случае с вопросом "почему вы используете тот язык, который используете" ответ "привык" будет дан 90% респондентов, то в случае со средой разработки это кажется как минимум глупым - стоимость перехода на другую среду в сотни раз ниже стоимости перехода на другой язык. Значит, выбирая среду, человек чем-то руководствуется.
Если забыть на секунду про финал, где надо работать под Linux, а, следовательно, и выбор совершенно другой, сосредоточимя на средах, доступных для Windows. При этом рассматриваем исключитеьно с точки зрения "кодячить олимпиадки".
Для Java есть несколько сравнительно равных сред - Eclipse, IntellijIDEA, NetBeans - у каждой есть фанаты, которые с пеной у рта будут доказывтаь, что другие две гавно, я работал во всех трех постольку поскольку, и больше работал в Eclipse, потому что это среда на финале. Я не нашел заметного преимущества какой-то из этих IDE для себя, но я и не так чтобы сильно много хотел.
Для C++ я вегда работал в MSVC. Я пытался работать в MinGW, и один раз даже писал контест из Dev-CPP. Может быть у меня были старые версии или кривые руки, но ни ту ни другую я не смог заставить в режиме отладки показать мне содержимое вектора. Так как решение на олимпиаде обычно содержит десятки STL-контейнеров, невозможность отлаживать STL формально для меня равна факту отсутствия отладчика в среде. Кстати, та же проблема существует и в Eclipse CDT, но отладчик в CDT - это отдельная тема. Мы на финале пользовались исключительно Debug Output :о)
Поэтому для меня объективно лучше MSCV. Любой важный для меня старт - отборочные или SRM (срм влияет на рейтинг, а я люблю манчить), я всегда пишу и буду писать из MSVC, потому что на важном старте возможность быстрой отладки для меня критично важна - как бы я не был крут, я все равно буду ошибаться и мне нужен быстрый способ ошибки отловить.
Другой вопрос, когда я пишу для удовольствия - открытые кубки, тимус, сборы. Это интересный момент - мне не приятно писать из студии :о) По ряду причин. Мне не нравится ее перформанс - студия, как и почти любая среда разработки, немного притормаживает - это не критично для работы, но это бееесит. Вторая причина - не очень удобное управление проектом - мне не очень нужен проект для олимпиадки, ведь на олимпиаде единица измерения - это один файл, а не проект. Мне не удобна любая среда разработки, потому что мне не нужен проект, мне нужно уметь быстро переключаться между двумя файлами, над которыми я работаю. Более конкретно - допустим я пишу контест и работаю над двумя задачами (допустим по одной тупняк, я переключился на другую, и периодически меня осеняет, я возвращаюсь к первой, вношу поправки, вруню опять, переключаюсь на вторую, кодячу, меня осеняет, и по циклу - пример редкий, но возможный. Другой пример - когда вы работаете над задачей и над генератором тестов для этой задачи чтобы отловить TLE). В студии мне надо убрать один файл из проекта и добавить другой. Это не удобно и требует очень много лишних действий.
Другая проблема - в MSVC я могу писать только на C++, мне надо переключиться в другую среду, чтобы написать задачу на Java. Надо ли говорить, как работает не очень быстрый компьютер, когда на нем запущено два мамонта-серыд? А старты для фана я всегда пишу на обоих языках, а когда есть поддержка C#, то на всех трех, потому зацикливаться на одном языке не интересно.
Поэтому я для фана пишу в... FAR Manager :о) После установки Colorer и настройки компиляции явы, шарпа и С++ по Enter FAR становится невероятно удобной средой. Приведу причины:
1. Быстрое переключение между задачами - вам надо просто перебежать от файла к файлу в FAR. Учитывая разницу в скорости FAR, который все действия выполняет моментально, и любой среды, которые все-таки притормаживают, в FAR переключиться между задачами одно удольствие.
2. Быстрая смена языка - я могу писать на любом языке, компиляция настроена для всех трех.
3. Не надо коментировать вывод. Формально, когда я работаю в студии (и я думаю многие так делают), я комментирую перенаправление выходного файла, потому что в студии не удобно смотреть каждый раз вывод в файл. Она еще назойливо спрашивает "файл обновился, перегрузить файл" - это вообще бесит. Поэтому я просто отключаю перенаправление. Надо ли говорить, сколько раз в жизни я забывал убрать коментарий и отправлял решение без перенаправления :О) В FAR я просто не убираю перенаправление - там я все равно при компиляции нахожусь в папке и могу сразу посомтреть вывод.
4. Использование экрана - редактор в фаре дает в ваше распоряжение весь экран. В студии конечно можно убрать все окна, но это не тоже самое - в FAR при этом все инструменты остаются доступны. Если я в студии уберу Solution Explorer - это будет копыто. Фар показывает больше кода, и это удобно.
Минусы тоже есть, и самый главный из них - отладчика-то нет :о) Приходится использовать Debug Output. Есть люди, которые говорят, что используя Debug Output могут отлаживать не медлененее чем я в студии. Это бред сивой кобылы :о) Сравнивать крутой отладчик и Debug Output нет смысла - второй всегда будет заведомо медленнее.
Кроме того, поначалу немного бесило отсутствие IntelliSence, но это нафиг не надо, когда языки уже все позубрил достаточно хорошо. Это критично, если Java - не основной язык ,но надо закодячить что-то на длинную арифметику, так как в этом случае можно не знать на память какие-то вещи, которые автодополнение заполнит. Но после пары лет кодячанья это нафиг не надо, потому что все итак знаешь.
So, this is my story :о)
Немного не объективной статистики. В петрозаводске доминирующее большинство команд писало в FAR когда я был там последний раз. Бурундуки, Орел с Жуковым, и многие другие. Не все, конечно, но реально очень многие.
В Ижевске на сборах - где даются задачи из ПТЗ, но приезжают топ2 команды, в FAR не писал вообще никто :о)
Так что тема для обсуждения - какие среды Вы юзаете для каждого из языков, и почему?
Дана матрица N на M с произвольными числами и тем свойством, что значения чисел в каждой строке не убывают, а в каждом столбце не возрастают
Задача определить, есть ли в матрице заданный элемент A.
Для начала, если вы не слышали об этой задаче прежде, попробуйте найти для нее решение за O(N+M).
Далее решение Алисы:
Задачу можно решить за O(log S * log S), где S - это максимум из ширины и высоты матрицы, следующим образом: возьмем нашу матрицу, без потери общности допустим, что ширина больше высоты. Возьмем средний столбец, и бинарным поиском будем искать А. Мы можем прийти к одному из трех случаев (не учитывая случай, что мы нашли А - тогда все очевидно):
1. Все элементы в столбце больше А, то есть бинарный поиск сошелся на самом нижнем элементе и не нашел А. Так как значения в строках возрастают, очевидно, что правее этого стобца все числа также больше А, а значит дальше имеет смысл рассматривать только левую половину матрицы.
2. Все элементы в столбце меньше А. Аналогично, только отбрасываем левую половину и повторяем решения для правой половины.
3. В столбце есть как элементы больше, так и элементы меньше. Бинарный поиск в конце концов остановился на какой-то ячейке, значение которой меньше А, такой, что прямо над ней находится ячейка, значение в которой больше чем А. Тут очевидно, что все элементы левее и ниже этой ячейки меньше А, а все элементы правее и выше - больше, то есть мы можем отбросить все, что левее и ниже или правее и выше. Можно понять, что при этом будет отброшена не менее чем половина всех элементов (можно нарисовать, чтобы понять почему - грубо говоря, в каждой строке будет отброшена либо левая половина, либо правая - так как в каждой строке будет отброшена хотя бы половина, то и в целом по матрице будет отброшена хотя бы половина).
Таким образом, не зависимо от обстоятельств, хотя бы половина элементов матрицы будет отброшена, а значит нам надо выполнить не более log(S) шагов, на каждом из которых мы выполним один бинарный поиск, сложность которого O(log(S)), таким образом общая сложность решения - O(log S * log S).
Опровержение Боба:
Построим квадратную матрицу, в которой все элементы выше не главной диагонали равны +oo, все элементы ниже не главной диагонали равны -oo, а все элементы на этой самой не главной диагонали равны случайным числам. Эта матрица удовлетворяет условию задачи. Совершенно очевидно, что если бы в такой матрице можно было найти заданный элемент быстрее, чем за линейное время, то для произвольного массива из N элементов можно было бы найти заданный элемент быстрее, чем за линейное время, а это не правда. Значит решения быстрее чем за линейное время быть не может.
Так кто же ошибается, Алиса или Боб?
Есть 100 узников. На 100 листах бумаги написалии их имена - одно имя на одном листе, каждое имя по одному разу. Затем эти листки положили в 100 абсолютно одинаковых коробок по одному листу в коробку, и поставили эти коробки в ряд. На следующий день узников по одному будут впускать в комнату, после чего узник будет иметь право открыть 50 коробок из 100. Если узник найдет свое имя, то все коробки закроют, и впускают следующего узника. Если же узник за 50 попыток не найдет свое имя, всех 100 узников казнят. При этом во время всего этого процесса у узников не будет никакого шанса общаться друг с другом, и сейчас у них последняя ночь, чтобы выработать стратегию.
Можете ли вы придумать стратегию, которая позволит узникам завтра с шансом не меньше 30% уйти живыми и невредимыми?
Пусть в известном фильме 12 стульев Клавдия Ивановна или как ее там звали зарыла бриллианты в один из стульев не гарантированно, а с шансом 90%. После вскрытия 11 стульев, и не обнаружения бриллиантов в них, каков шанс обнаружить бриллианты в 12-ом стуле?
Интересно:
1. Какой вы видели свою работу во времена ваших поездок на ICPC?
2. И какой класс задач реально встал после
3. Насколько вы круче своих коллег (чисто по ощущениям - кажется ли вам, что вы справляетесь с работой лучше их)
4. Какова роль полученных регалий в вашей жизни.
Это, разумеется, если вы уже закончили свою ICPC-карьеру. Иначе вопросы следующие:
1. Какой вы видите свою работу после ICPC?
2. И какой класс задач вы ожидаете решать?
3. Чего вы ожидаете от регалии, которую получите?
4. Как вы оцениваее свой шанс рано или поздно получить эту самую регалию, и какая регалия является вашей целью (попадание на финал, медаль финала, золотая медаль финала, чемпионство на финале)? Является ли вашей целью любая регалия или цель вообще иная?
В Ижевске за всю историю было четверо программистов-олимпиадников, которые достигали мирового уровня, и вместе смогли в сумме пройти на четыре финала и завоевать три медали. Это меньше, чем во многих городах. Но историю можно проследить: первое поколение ребят остались после олимпиад в Ижевске, и работают в местных компаниях. Лучше ли они чем их коллеги? Один - заведомо да. Но не за счет олимпиад, а за счет упорства, которое сначала принесло медаль, а потом позволило быстро расти по карьерной лестнице. Про второго ничего хорошего не скажу :о)
Еще один молодой человек из того поколения, который не был так крут, как они, но получил медаль, будучи "участником-зрителем", качественно поюзал свою регалию и попал в огромную московскую фирму.
Я уже видел их опыт и как только вернулся с второго финала, почти в тот же день подсуетился и написал в нужные места, и почти пустое резюме с медалью ICPC принесло мне отличную работу за рубежом, и класс задач очень приятный - модные нынче Data Mining и Machine Learning. Мораль из этого - медаль чемпионата мира имеет ОГРОМНЫЙ вес в глазах зарубежных гигантов. А с высоты вашего опыта интервью вы потом пройдете за нефиг делать. То есть, если нацеленность на результат есть, вы получите потом отличную работу.
А вот что, если нацеленность была, а разультата не получилось - я не знаю. Интересно было бы узнать судьбу ребят, которые пять лет занимались олимпиадками, а потом ничего не заняли по неудачному стечению обстоятельств.
Потому что, забыв о регалии, что мы имеем?
Я знаю один плюс, который реально помогает - это умение решать задачи, которые раньше не встречал. Я часто замечаю, что когда мы сталкиваемся с какой-то сложной задачей, я могу сразу предложить качественное решение, в то время как даже очень умные ребята могут потратить какое-то время на его поиск. Потому что это то, в чем я крут и на что я потратил пять лет. Но что кроме этого?
Много алгоритмов? Почти не пригождаются. Я не знаю задач на поток в реальной жизни, которые бы еще не были решены и требовали чьего-то вмешательства.
Командная работа? В чем заключается командная работа? На самом деле, есть ли кто-то, кто считает, что то, как работала их команда на ICPC, может действительно дать полезные навыки? Какие именно? Командная работа - это видимо то, в чем отличаются все команды. Я знаю, что то, как работала наша команда, было очень оптимизировано для ICPC, и не дало реального навыка для работы в команде над каким-то проектом. Если у кого-то это не так, мне было бы интересно узнать, а как тогда? Как должна работать команда, чтобы это приносило полезный опыт?
Знание языков и технологий - это вообще смешно, чаще всего на олимпиаде используются только базовые конструкции и несколько стандартных классов. Вспомнить хотя бы задачу J на ГП Удмуртии. Что, серьезно никто не знает, что в Java есть встроенный интерпретатор JavaScript? :о) И недавние примеры с задачами на определение, является ли число простым. Сколько человек знало про BigInteger.isProbablyPrime?
Это то, как это у меня. Я научился решать нестандартные задачи быстро, и это все, что я получил из практических навыков, на первый взгляд. Глубже я не копал :о)
Еще интересный момент, которого бы хотелось избежать сейчас. Часто пишут, например, "если ты не встречал задач на поток, это не значит что их нет". Но никто же не спорит - но где они? Интересно же реальные примеры, а не общие слова. Предположений и я строил много, на деле все повернулось как-то не так, как предполагалось :о)
Более обобщенно, хотелось бы построить коллективное мнение о
а) том, что ждет олимпиадников в будущем - опыт уже прошедших и ожидания тех, кто пока вертится в этом всем
б) том, что полезного мы вынесем и как это реально потом пригодится