Привет всем!

Пару лет назад я делал пост-впечатление про учебу в Академическом университете. Но за два года для нас многое изменилось, так что пришло время очередного поста. Очень длинного поста. Теперь про учебу в Питерской Вышке :)

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

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

Буквально вчера появился пост от третьего курса про нашу жизнь на новом месте. Сегодня вышел еще один пост от четвертого курса. Здесь же я постараюсь как-то дополнить их и чуть подробнее рассказать про жизнь на старших курсах.

Для начала небольшое резюме этих постов:

• Переезд — очень быстрый, как следствие тяжелый, сильнее всего сказался на втором курсе, но вроде все в итоге живы. Хотя где-то по дороге мы и потеряли первый курс (ну то есть не набирали)
• Обратная связь, которой так славился АУ — не для всех курсов сразу (последствия переезда), но в итоге тоже выжила
• Учебная программа — адаптирована под новые реалии, пахать все еще надо
• Учиться — интересно. Тыкаться в разные направления — да пожалуйста
• Стипендии — сохранились в полном объеме. Меньше не станет, а вот о повышении слухи уже ходят
• В олимпиадах и хакатонах — участвуем, кстати, теперь с этим даже проще
• Как мне кажется, нетехнических предметов больше не стало. Меньше, как выяснилось, тоже. Но мнения разнятся
• Майноры, накопительные оценки и прочие прелести Вышки — присутствуют. Вроде бы ожидается и их адаптация под нашу программу с целью повышения КПД
• Общаги — хуже. Жить можно, все еще без тараканов. Местным просто так не дают. Зато в центре. Обещают новые
• Денег на поездки, выездные школы и конференции — несравнимо больше. Сопутствующей бумажной работы — вроде как меньше
• Атмосфера — не умерла и даже не при смерти. Она вполне себе жива. И не только в наших сердцах

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

Влияние Вышки

Теперь по порядку. Мне особо нечего рассказывать про сам процесс переезда, для самих студентов он прошел почти незаметно. Скорее хочется сказать про его последствия.

Модули и сессия

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

До сих пор нам за семестр читалось порядка 8-9 предметов, иногда больше. Экзамен обычно был не более чем по 5 из них, по остальным ставился зачет или зачет с оценкой. Правила Вышки также позволяют ставить зачеты (хотя и только с оценкой), но экзамен при этом формально должен быть по каждому предмету. Как я понимаю, формальность эта заключается в том, что экзамен ты можешь не проводить, но дату для него назначить обязан. А тогда принцип Дирихле подсказывает, что ну невозможно просто так взять и читать все наши предметы в течение семестра, надо бить на модули. И если третьему и четвертому курсу это было почти по барабану (из-за выбора специализации количество предметов в семестр резко сократилось), то второй курс чуть не умер, когда за один модуль им прочитали семестровый курс алгебры, а за второй — семестровые курсы матана и хаскеля. Почему нельзя было по-другому распределить нагрузку и сложные предметы читать целый семестр? Потому что тут снова проблема в короткой сессии, за которую почти нереально подготовиться и сдать тот объем, который нам читается за семестр.

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

Учебная программа

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

Если не вдаваться в подробности, то Вышка буквально запрещает студентам учиться слишком много, вводя некоторое ограничение сверху на количество учебных часов. Да еще и пары длятся не 1:40+, а 1:20. Казалось бы, ну и ладно, отдыхать же тоже надо когда-то, но вот только наша прежняя программа ну никак не укладывается в эти все ограничения :)

Пока не особо понятно, что конкретно с этим будут делать. Судя по всему, часть программы просто будет немного урезана, хотя учиться проще от этого и не станет. В принципе, как мы некогда обсуждали с Александром Владимировичем Омельченко, это может и не так плохо. И в случае некоторых математических курсов — как бы ни были интересны многие из читаемых нам разделов, но реальная их практическая полезность все же до конца не ясна.

Нетехнические предметы и майноры

Первые никуда не делись. В учебном плане присутствуют история, экономика, философия, БЖД. С этим ничего не сделать, стоит просто смириться. Из плюсов — преподаватели “непрофильных” предметов обычно довольно лояльны в выставлении оценок. Но это все, что могу сказать про них.

Английский также присутствует и читается в течение первых двух курсов. Из особенностей — по правилам Вышки студенты второго курса должны сдавать внутренний экзамен в формате IELTS. С одной стороны, это вроде бы должно являться неплохим бонусом для тех, кто планирует сдавать этот экзамен в будущем. С другой стороны, в этом году все в итоге вылилось в натаскивание студентов второго курса к этому экзамену. Проблема известна, решение обсуждается. Без подготовки к IELTS скорее всего обойтись не получится. Возможно будет организовано два независимых английских: простой и для подготовки к IELTS. Возможно, сама подготовка к IELTS будет так реорганизована, чтобы не отличалась при этом от простого изучения английского. Но наверняка ничего сказать не могу.

Что касается майноров, то это еще одна фишка Вышки. Майнор — это непрофильный предмет, который студенты выбирают на первом курсе из довольно широкого списка предметов и который читается в течение второго и третьего курса. Идея его довольно понятна — это хорошая возможность потыкаться в какую-нибудь новую интересную для вас область, не связанную с основным профилем. Что касается реализации — с этим все чуть сложнее. Возможности выбора этого предмета у нас попросту не было, так что лично я не готов комментировать это явление в системе Вышки. Слышал от третьих лиц, что на ФКН с ними все неплохо организовано, но не более.

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

Стипендии

Как уже говорилось, все стипендии у нас сохранились в том объеме, в котором были в АУ: основная стипендия варьируется от 7 до 13 тысяч, +3 тысячи для иногородних, а также возможность получить +5 тысяч от правительства Санкт-Петербурга на первых двух курсах. Вчера внезапно услышал еще и о том, что основную стипендию и вовсе могут поднять.

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

Учеба на новом месте

Вроде бы это все, что касается каких-то серьезных изменений, которые привнесла нам Вышка. Так что можно и к жизни перейти.

Новый корпус

Вся учеба у нас с этого года проходит в корпусе Вышки на Кантемировской. Сам корпус довольно большой, внутри есть несколько милых кофепоинтов (кофе, опционально сиропы, пирожки, сэндвичи, пирожные), столовая, спортзал. Снаружи — велопарковки. В шаговой доступности пара кафешек, где можно при желании поесть. Метро тоже сравнительно близко: от Лесной — 15 минут шагом или 7 минут на автобусе, от Петроградской — 25 минут пешком или 10 минут на автобусе.

Из минусов — у нас пропала студкомната, поэтому потусить программистской компанией сейчас можно разве что в холлах на этажах (которые, впрочем, довольно просторные и с диванчиками). Перерывы стали сильно короче: один 20 минут, остальные по 10, как следствие — не всегда успеваешь пообедать (но некоторые преподаватели были готовы чуть подвинуть пары). Первая пара — в 9, а не в 10. Во все аудитории вход только по пропуску, причем преподавательскому. Поэтому на парах двери приходится оставлять приоткрытыми, чтобы можно было свободно ходить.

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

Общежития

Тут могу сказать мало, сам в общаге уже не живу.

Вообще, когда случился переезд, нам предложили два (стула) варианта: остаться в общаге АУ (за дополнительную плату) или переехать в общагу Вышки.

Про первый вариант могу сказать, что лично для меня он был вполне неплох где-то до зимы. Хотя многие и выехали и тусить стало почти не с кем, все-таки с общагами АУ в Питере мало кто мог сравниться. С февраля же стоимость проживания для нас подняли до 10000, а за такие деньги имхо гораздо проще снять квартиру на пару с кем-нибудь. Тем не менее, этот вариант все еще рабочий. А руководство общежития (пока что) все еще готово селить в него новых людей.

Теперь про общаги Вышки. Осенью всех заселили в общежитие на Серпуховской. Кажется, единственный ее плюс в сравнении с общагой АУ — она находится в центре, буквально в пяти минутах ходьбы от станции метро “Технологический институт”. Но минусов, по отзывам, не так уж много: комнаты меньше, удобства на этаже, летом сильно надоедают комары с улицы. В остальном общаги чистые, управляющие адекватные, сантехника работает исправно и оперативно ремонтируется, в кухнях недавно сделали ремонт и там тоже хорошо.

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

Олимпиады, хакатоны, конференции

Первые все еще популярны. В ICPC участвуем независимо от Москвы. Burunduk1 все так же проводит тренировки. Летом три команды от нашего вуза едут в Петрозаводск. Спонсирует эти поездки Вышка.

И, кстати, со спонсорством все теперь стало гораздо проще: Вышка действительно готова вкладываться в своих студентов, оплачивать поездки на сборы, хакатоны, конференции. Чтобы понимали, Вышка без проблем оплатила не самые дешевые поездки на Google IO (проводилась в Mountain View, California) и на хакатон ZuriHac (проводился в Цюрихе, как можно догадаться). Не могу ничего сказать про то, насколько легко это делается в других вузах, но в АУ с этим точно так просто не вышло бы. Причем от самих студентов это почти ничего не требует: носиться со всякими бумажками по всему вузу, чтобы получить деньги на поездку, сейчас уже не приходится.

Учеба на старших курсах

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

В этом же году у Питерской Вышки появился свой блог на хабре. Там вы можете найти и довольно подробный пост про обучение на направлении SE от yeputons, и много интересных постов про проекты, которыми занимаются наши студенты.

Семестровые практики и НИРы

Изначально мне хотелось здесь рассказать про то, как у нас организованы семестровые практики и НИРы, но кажется, что yeputons в своём посте и так довольно хорошо описал их суть. Главное — у вас всегда есть выбор.

К примеру, идею приложения под Android студенты должны придумывать самостоятельно. Как и придумывать затем различные киллерфичи, отличающие их приложения от других.

То же и в случае НИРов. Начиная с третьего курса студентам каждый семестр предлагается большой список проектов от различных компаний (JetBrains, Yandex, Geoscan, Agisoft, SimLabs и многие другие). Среди этих проектов можно найти как промышленные, так и исследовательские, в самых разных областях. Как следствие, вы можете менять сферу деятельности хоть каждый семестр. Что касается задач, то они сильно зависят от конкретных проектов. Где-то нужно допилить плагин для IntelliJ Idea, где-то — доработать крутой мультиклассовый классификатор и сравниться с другими подходами, а где-то — решить vertex cover :)

А для интересующихся — вот несколько примеров возможных проектов, которые предлагались в прошлых семестрах: SE, ML, PL, CS.

Итог

Направление хорошее. Учиться интересно. Мне тут нравится. Остальным тоже. Плюсы от переезда — есть. Без проблем тоже никуда, но решаются.

Хочется лишь отметить, что мы, как мне кажется, смогли сохранить прежнюю атмосферу. И это хорошо.

Ссылки всякие

Полагаю, этот пост может быть сейчас интересен не столько широкой общественности, давно не слышавшей про АУ, сколько абитуриентам. Поэтому, наверное, есть смысл оставить здесь пару ссылок:

• Сайт новой программы
• Группа новой программы в vk
• Чат в telegram, здесь студенты и преподаватели умеют отвечать на разные вопросы по программе

Буквально несколько дней назад закончилась сессия. Как и мой первый год в Академическом университете и третий год в жизни бакалавриата...

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

О том, как всё начиналось

Для начала хочется рассказать о том, как всё начиналось, и кто у нас вообще учится в Академическом университете.

В нашем году был набор 47 человек. Среди поступивших 14 человек — призёры и победители Всероса, причём двое по математике и один по физике. Также четверо — победители олимпиад 1 уровня (призёра для поступления не хватит). Оставшиеся 29 человек поступали по ЕГЭ.

В текущем же году набор составит уже 36 человек.

По уровню подготовки, как видно, люди действительно поступали совсем разные. Однако всё это было учтено при подготовке программы. В частности, в первую неделю обучения нам предложили написать тесты, по результатам которых нас распределили на группы по математике и программированию в зависимости от начальной подготовки. Так что скучать никому не приходилось ;)

Что касается программы нашего курса, то Петя Смирнов подробно написал про неё в своём посте.

Могу лишь написать о некоторых изменениях по сравнению с 2014 годом. А именно, из программы пропала физика (что, наверное, для многих будет плюсом ;)). В остальном же всё осталось по-прежнему.

Обучение

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

Особенно сложной для многих выдалась первая четверть учебного года. К примеру, кто-то, поступая в университет, совсем не умел программировать, никогда не слышал об алгоритмах. Другие же, наоборот, имели большие пробелы в математике. А потому работать приходилось очень много.

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

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

Радует ещё и то, что преподавательский состав у нас в большинстве своём довольно молодой и весьма перспективный. Нудных лекций и практик у нас не бывает :)

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

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

Олимпиады

Хочется несколько слов сказать про олимпиады. Хотя, по-видимому, я и повторю уже сказанное Петей...

Во-первых, курс алгоритмов предполагает еженедельное решение контестов.

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

Если есть желание, то существует возможность поехать на Петрозаводские сборы.

Есть также возможность съездить и на разные студенческие и не только олимпиады. В этом году нашу команду приглашали на командный чемпионат в Самару. Из более значимых — в этом году несколько наших команд успешно съездили на Google HashCode во Францию, а также уже второй год наши команды вполне достойно показывают себя на финале ACM :)

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

Отдых

"Какой же отдых?!", — спросите вы после всех рассказанных страшилок о постоянной учёбе.

Свободного времени и правда, как правило, остаётся не слишком много. Но, как говорится, было бы желание.

Так, мы курсом выбирались в театр, ходили на лазертаг. На каникулах ездили компанией в Великий Новгород на Бегущий Город.

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

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

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

Общежитие

К слову о. В общежитиях у нас очень круто :)

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

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

Также в общежитии предусмотрена специальная комната, в которой можно оставить ваш велосипед, если таковой имеется.

А ещё совсем скоро у нас откроется второй корпус общежития. И тогда станет совсем просторно жить :)

В завершение...

Год закончился. У всех свои планы на это лето. Двое едут на стажировку в Google, ещё один человек — уже стажируется в JetBrains. К слову, все трое — милые девушки :)

Очень многие едут в ЛКШ в качестве преподавателей. А кто-то решил ботать и отдыхать в своё удовольствие.

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

...

Пожалуй, на этом всё :)

703A — Мишка и игра

Всё, что Вам требовалось сделать в этой задаче, — посчитать количество раундов, в которых победит Мишка, количество раундов, в которых победит Крис. Для этого следовало завести две переменные countM и countC. Если в очередном раунде Мишка выкидывала на костях большее значение, чем Крис, то 1 следовало прибавлять к переменной countM. Если меньшее — к переменной countC. В конце нужно было сравнить полученные значения и вывести ответ.

703B — Мишка и путешествие

Рассмотрим первую столицу. Заметим, что стоимость исходящих из неё дорог равна c[id₁] · (sum - c[id₁]), где sum — суммарная красота всех городов. Таким образом, переходя от одной столицы к другой, мы сможем посчитать суммарную стоимость дорог, исходящих из столиц. Однако не стоит забывать, что дороги между столицами в таком случае будут посчитаны дважды. Для этого на очередном шаге мы должны вычитать из переменной sum значение красоты текущей столицы. В конце нам остаётся посчитать стоимости дорог, проложенных между "не столичными" соседними городами.

Асимптотика полученного решения — O(n).

703C — Крис и дорога

Для начала представим, что автобус в действительности стоит, а сами мы передвигаемся "вправо" с постоянной скоростью v. Тогда заметим следующий факт: нам всегда выгодно перемещаться по прямой вида y = (u / v) · (x  -  v · t₀), где t₀ — время, спустя которое мы начинаем своё перемещение по пешеходному переходу. Ответ же будет определяться как t = t₀ + (w / u). Теперь рассмотрим два варианта развития событий.

Если t₀ = 0, то мы начинаем наше движение сразу же. В таком случае нам следует проверить, что прямая не пересекает многоугольник (т.е. либо мы можем перейти дорогу перед автобусом, либо автобус уже прошёл и не угрожает нам).

Если же проверка не удалась, то нам следует найти такое минимальное положительное значение t₀, при котором описанная прямая будет касаться многоугольника. Это может быть сделано при помощи бинпоиска.

Асимптотика решения — O(n log n).

Упражнение: Улучшите асимптотику до O(n).

703D — Мишка и интересная сумма

Посмотрим, что из себя представляет запрос. Несложно заметить, что ответом на него будет являться XOR-сумма всех элементов на подотрезке с XOR-суммой различных элементов на том же подотрезке. Первое мы умеем находить за O(1) с предподсчётом за O(n) (используя префиксные суммы). Что же касается второго, то научимся для начала решать похожую, но более простую задачу.

Пусть нам поступают запросы вида "найдите количество различных чисел на подотрезке". Отсортируем все запросы по правой границе и будем последовательно итерироваться по элементам массива, попутно заведя массив last, где last[value] — последняя позиция вхождения значения value в массив на обработанном префиксе. Допустим, мы обработали все элементы до позиции r включительно. Тогда заметим, что ответом на запрос на отрезке [l,  r] (l ≤ r) будет являться , где cnt[i] = 1, если last[a_i] = i, или 0 в противном случае. Поддерживать эти значения в массиве cnt довольно просто, для этого при переходе к очередному элементу a_i нам всего лишь требуется сделать следующие присвоения: cnt[last[a_i]] = 0, cnt[i] = 1, last[a_i] = i. Если же для поддержания значений cnt использовать дерево отрезков или дерево Фенвика, описанную сумму мы сможем находить за O(log n).

Теперь вернёмся к нашей задаче. Всё, что нам требуется сделать, — заменить присвоения cnt[i] = 1 на cnt[i] = a_i и считать не сумму, а XOR-сумму. Таким образом, мы научились решать задачу с асимптотикой O(n log n).

Solution (with Fenwick)

P.S.: Существует также решение этой задачи за O(n sqrt n) с использованием алгоритма Мо, однако мы постарались отсечь его. Кажется, получилось :D

703E — Мишка и делители

Для решения этой задачи воспользуемся динамическим программированием.

Пусть в dp[i][d] будет храниться минимальное количество таких элементов на префиксе размера i, что их произведение кратно d. Переход в этом случае будет следующим: dp[i][d] = min(dp[i  -  1][d],  dp[i  -  1][d  /  gcd(d,  a_i)]  +  1). Формально это можно объяснить тем, что нам всегда выгодно как можно больше "брать" от a_i. Ответ будет храниться в dp[n][k].

Давайте оптимизируем наше решение. Заметим, что в качестве значений d нам следует использовать исключительно делители k (которых, кстати, в худшем случае будет 6720). Что касается gcd, то его мы можем находить за O(primes(k)), где primes(k) — количество простых чисел в разложении k. Сами же делители следует перенумеровать в соответствии с их разложением на простые множители.

Таким образом, для получения AC нужно было оптимизировать описанную выше динамику, добавив к ней минимизацию суммы используемых элементов. Итоговая асимптотика — O(n · divs(k) · primes(k)).

Solution

Всем привет!

4 августа в 18:05 MSK состоится очередной рейтинговый раунд Codeforces #365 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Автором всех задач являюсь я, и это мой первый раунд на Codeforces. Советую Вам ознакомиться со всеми задачами, они наверняка придутся вам по душе, да и не зря же я старался :)

Хочется выразить благодарность координаторам раунда GlebsHP и danilka.pro за помощь в подготовке контеста, MikeMirzayanov за замечательные системы Codeforces и Polygon, а также IlyaLos за дельные советы по некоторым задачам.

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

UPD. 5 задач, 2 часа на их решение и следующая разбалловка: 500 — 1000 — 1750 — 2000 — 2250.

UPD. Приносим извинения за доставленные неудобства. В ближайшее время все решения будут протестированы. Вопрос нерейтинговости пока обсуждается.

UPD. Было принято решение сделать раунд нерейтинговым.

UPD. Соревнование завершено. Поздравляем победителей!

Div1: 1. uwi 2. kmjp 3. savinov 4. BigBag 5. KrK

Div2: 1. meteor 2. TmEnd 3. chenjiamin 4. vokeal 5. Denisson

Разбор будет опубликован в ближайшее время.

UPD. Разбор