Как такое возможно, что замостив треугольник одними и теми же фигурками в первом случае мы его замостили целиком, а во втором остался свободный квадратик? Не читайте коментарии, если хотите решить задачку сами.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
27:34:49
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
27:34:49
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Пост содержит 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, и мы радостные, что хоть раз нам удалось выиграть (не важно что порядок выигрыша не сопоставим с тем, что мы успели проиграть до этого), отправились домой.
Перечитав все, чем я был недоволен С# тут я выяснил, что кроме отсутствия SortedSet, который был объявлен только в .NET 4.0, C# тут абсолютно perfect. CBR7 это подтвердил.
Характерно, что после всего четырех месяцев работы на 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 писать с тонной вызовов методов :о
Характерно, что после всего четырех месяцев работы на 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 обозначает что вы не учитываете случай, когда перед вызовом макроса стоит -, а внутри макроса плюсы или минусы. Это не ОК :о)
а) erase 0 в задаче B в тесте 42 :о)
б) пробелы до и после # в задаче E в тесте 139. AC по ней через 28 секунд после конца контеста/начала дорешивания :о) на контесте правильное решение отправил наверное через секунду после конца :о(
UPD: Если кому-то интересно, WA19 в задаче E обозначает что вы не учитываете случай, когда перед вызовом макроса стоит -, а внутри макроса плюсы или минусы. Это не ОК :о)
В общем, все мои попытки показать, что моно шлак, и это НЕ C#, не увенчались успехом.
Забудем про то, что в Моно нет 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 на другом тесте. Можно дойти аж до девятого, можно упасть на первом.
Я переписывал это решение дважды целиком с нуля, и каждый раз эта история.
Забудем про то, что в Моно нет 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 на другом тесте. Можно дойти аж до девятого, можно упасть на первом.
Я переписывал это решение дважды целиком с нуля, и каждый раз эта история.
Сначала хотел написать полный разбор, но как разбирать задачи A и B я не представляю :о) Разве что можно сказать, что на C++ чтобы читать до конца надо использовать while( gets( s ) ), а если вы не любите перенаправлять файлы и вводите тест прямо в консоль, то чтобы обозначить конец файла надо нажать Ctrl+Z.
Задача С
Давайте введем понятие баланса некоторого префикса подстроки - на сколько открывающихся скобок больше в этом префиксе, чем закрывающихся. Понятно, что некоторая строка является правильной скобочной подпоследовательностью, если для всей строки баланс равен нулю, а для любого ее префикса не отрицателен. Посчитаем баланс для каждого префикса данной нам в задаче строки и сложим их в массив 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.
Задача С
Давайте введем понятие баланса некоторого префикса подстроки - на сколько открывающихся скобок больше в этом префиксе, чем закрывающихся. Понятно, что некоторая строка является правильной скобочной подпоследовательностью, если для всей строки баланс равен нулю, а для любого ее префикса не отрицателен. Посчитаем баланс для каждого префикса данной нам в задаче строки и сложим их в массив 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.
Разбор задач Codeforces Beta Round 5
Итак, сегодняшний рейтинг TopCoder в картинках.
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
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 элементов можно было бы найти заданный элемент быстрее, чем за линейное время, а это не правда. Значит решения быстрее чем за линейное время быть не может.
Так кто же ошибается, Алиса или Боб?
Дана матрица 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% уйти живыми и невредимыми?
Есть 100 узников. На 100 листах бумаги написалии их имена - одно имя на одном листе, каждое имя по одному разу. Затем эти листки положили в 100 абсолютно одинаковых коробок по одному листу в коробку, и поставили эти коробки в ряд. На следующий день узников по одному будут впускать в комнату, после чего узник будет иметь право открыть 50 коробок из 100. Если узник найдет свое имя, то все коробки закроют, и впускают следующего узника. Если же узник за 50 попыток не найдет свое имя, всех 100 узников казнят. При этом во время всего этого процесса у узников не будет никакого шанса общаться друг с другом, и сейчас у них последняя ночь, чтобы выработать стратегию.
Можете ли вы придумать стратегию, которая позволит узникам завтра с шансом не меньше 30% уйти живыми и невредимыми?
Задача достаточно старая, но не очень известная, поэтому я надеюсь кто-то здесь ее еще не видел и получит удовольствие от ее решения :о)
Пусть в известном фильме 12 стульев Клавдия Ивановна или как ее там звали зарыла бриллианты в один из стульев не гарантированно, а с шансом 90%. После вскрытия 11 стульев, и не обнаружения бриллиантов в них, каков шанс обнаружить бриллианты в 12-ом стуле?
Пусть в известном фильме 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?
Это то, как это у меня. Я научился решать нестандартные задачи быстро, и это все, что я получил из практических навыков, на первый взгляд. Глубже я не копал :о)
Еще интересный момент, которого бы хотелось избежать сейчас. Часто пишут, например, "если ты не встречал задач на поток, это не значит что их нет". Но никто же не спорит - но где они? Интересно же реальные примеры, а не общие слова. Предположений и я строил много, на деле все повернулось как-то не так, как предполагалось :о)
Более обобщенно, хотелось бы построить коллективное мнение о
а) том, что ждет олимпиадников в будущем - опыт уже прошедших и ожидания тех, кто пока вертится в этом всем
б) том, что полезного мы вынесем и как это реально потом пригодится
Интересно:
1. Какой вы видели свою работу во времена ваших поездок на ICPC?
2. И какой класс задач реально встал после
3. Насколько вы круче своих коллег (чисто по ощущениям - кажется ли вам, что вы справляетесь с работой лучше их)
4. Какова роль полученных регалий в вашей жизни.
Это, разумеется, если вы уже закончили свою ICPC-карьеру. Иначе вопросы следующие:
1. Какой вы видите свою работу после ICPC?
2. И какой класс задач вы ожидаете решать?
3. Чего вы ожидаете от регалии, которую получите?
4. Как вы оцениваее свой шанс рано или поздно получить эту самую регалию, и какая регалия является вашей целью (попадание на финал, медаль финала, золотая медаль финала, чемпионство на финале)? Является ли вашей целью любая регалия или цель вообще иная?
В Ижевске за всю историю было четверо программистов-олимпиадников, которые достигали мирового уровня, и вместе смогли в сумме пройти на четыре финала и завоевать три медали. Это меньше, чем во многих городах. Но историю можно проследить: первое поколение ребят остались после олимпиад в Ижевске, и работают в местных компаниях. Лучше ли они чем их коллеги? Один - заведомо да. Но не за счет олимпиад, а за счет упорства, которое сначала принесло медаль, а потом позволило быстро расти по карьерной лестнице. Про второго ничего хорошего не скажу :о)
Еще один молодой человек из того поколения, который не был так крут, как они, но получил медаль, будучи "участником-зрителем", качественно поюзал свою регалию и попал в огромную московскую фирму.
Я уже видел их опыт и как только вернулся с второго финала, почти в тот же день подсуетился и написал в нужные места, и почти пустое резюме с медалью ICPC принесло мне отличную работу за рубежом, и класс задач очень приятный - модные нынче Data Mining и Machine Learning. Мораль из этого - медаль чемпионата мира имеет ОГРОМНЫЙ вес в глазах зарубежных гигантов. А с высоты вашего опыта интервью вы потом пройдете за нефиг делать. То есть, если нацеленность на результат есть, вы получите потом отличную работу.
А вот что, если нацеленность была, а разультата не получилось - я не знаю. Интересно было бы узнать судьбу ребят, которые пять лет занимались олимпиадками, а потом ничего не заняли по неудачному стечению обстоятельств.
Потому что, забыв о регалии, что мы имеем?
Я знаю один плюс, который реально помогает - это умение решать задачи, которые раньше не встречал. Я часто замечаю, что когда мы сталкиваемся с какой-то сложной задачей, я могу сразу предложить качественное решение, в то время как даже очень умные ребята могут потратить какое-то время на его поиск. Потому что это то, в чем я крут и на что я потратил пять лет. Но что кроме этого?
Много алгоритмов? Почти не пригождаются. Я не знаю задач на поток в реальной жизни, которые бы еще не были решены и требовали чьего-то вмешательства.
Командная работа? В чем заключается командная работа? На самом деле, есть ли кто-то, кто считает, что то, как работала их команда на ICPC, может действительно дать полезные навыки? Какие именно? Командная работа - это видимо то, в чем отличаются все команды. Я знаю, что то, как работала наша команда, было очень оптимизировано для ICPC, и не дало реального навыка для работы в команде над каким-то проектом. Если у кого-то это не так, мне было бы интересно узнать, а как тогда? Как должна работать команда, чтобы это приносило полезный опыт?
Знание языков и технологий - это вообще смешно, чаще всего на олимпиаде используются только базовые конструкции и несколько стандартных классов. Вспомнить хотя бы задачу J на ГП Удмуртии. Что, серьезно никто не знает, что в Java есть встроенный интерпретатор JavaScript? :о) И недавние примеры с задачами на определение, является ли число простым. Сколько человек знало про BigInteger.isProbablyPrime?
Это то, как это у меня. Я научился решать нестандартные задачи быстро, и это все, что я получил из практических навыков, на первый взгляд. Глубже я не копал :о)
Еще интересный момент, которого бы хотелось избежать сейчас. Часто пишут, например, "если ты не встречал задач на поток, это не значит что их нет". Но никто же не спорит - но где они? Интересно же реальные примеры, а не общие слова. Предположений и я строил много, на деле все повернулось как-то не так, как предполагалось :о)
Более обобщенно, хотелось бы построить коллективное мнение о
а) том, что ждет олимпиадников в будущем - опыт уже прошедших и ожидания тех, кто пока вертится в этом всем
б) том, что полезного мы вынесем и как это реально потом пригодится
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 14:00:11 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
