Блог пользователя Sereja

Автор Sereja, 12 лет назад, По-русски

Всем привет!

Совсем скоро, 16 декабря в 19:30 MSK состоится Codeforces Round #156, автором которого являюсь я. Это мой второй раунд на Codeforces и я надеюсь, что не последний.

Спасибо Steps09, Seyaua и sdya за помощь в тестировании задач, а также Gerald за помощь в подготовке раунда. Отдельное спасибо Delinur за перевод условий на английский.

Разбалловка в первом и во втором дивизионе стандартная: 500-1000-1500-2000-2500.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

Контест окончен, надеюсь вам понравилось :)

Поздравляю победителей див1:
1). YuukaKazami
2). al13n
3). rng_58
4). Bigsophie
5). KADR

И победителей див2:
1). ShadowSong
2). ynbpdy072
3). jiaobu

Разбор задач по ссылке.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +202
  • Проголосовать: не нравится

Автор Sereja, 12 лет назад, По-русски

Всем привет.
Не так давно закончилась 24я международная олимпиада по информатике. Приехав домой, немного отдохнув и полностью пришев в себя решил написать о олимпиаде.

Как все вы уже знаете, олимпиада была проведена в Sermione и Montichiari.
Sermione — не большой курортный городок, содержащий множество 3х и 4х звездочных отелей. В одном из таких отелей(точнее говоря поселке) под название Garda Village были поселены все участники олимпиады. Вот несколько фоток поселка:

Домики участников:

Домики организаторов:

Поселок находится на берегу озера Garda, за озером иногда было видно горы. Когда мы сидели на лавочке и любовались пейзажами, Рома(Furko) говорил, что даже ради того, что-бы посмотреть на это в живую стоит проходить на соревнования такого уровня.
Собственно пейзажи:


По последней фотке, в первый день, наличие кроликов напомнило Канаду, где было много белок.

Как на любом онсайте, в первые дни происходит много знакомств, мы тоже не упустили такой возможности :) Но к сожелению фоток с другими странами крайне мало.

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

или маски мексиканцев:

Фотки нашей сборной выложу чуть-чуть позже.

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

После обеда нас повезли домой, где мы уже настраивались на завтрашний тур. После ужина был карантин, нам выключили wi-fi, и забрали телефоны, организаторы пошли переводить задачи.

Следующим утром мы поехали в тоже место, где было открытие: писать тур. Про задачи вам уже рассказали тренеры России. Но все же тоже немного про них расскажу.
Первая задача была стиля "Unknown Laguage Round", разделена на 5 блоков по 9, 12, 19, 32, 28 баллов соответственно. Суть задачи: научить робота собирать камешки и перемещаться в нужную клетку по некоторой информации. Задача весьма интересна, но коды на нее были просто огромных размеров.
Вторая задача была про граф, в который в онлайне добавляется ребра и нужно говорить кол-во вершин, после удаления которых распадается на цепочки (компонента в которой нету циклов, и все вершины степени меньше-равно 2). Задача весьма простая, но я не придумал очевидной халявы: вся суть в том, что когда у вершины 3 соседа, то ответами могут быть только они или сама вершина. Я пропустил момент когда такое получается, и думал над случаем, когда у вершины порядка 100000 соседей, не знаю почему не придумал :(
Третья задача — персистентный стек, тоесть есть запрос добавить букву или отменить последние х команд, отмена тоже может быть отменена. Собственно достаточно заметить что у нас будет ребро в предыдущую вершину или в вершину которую приведет отмена. На ребре будет буква, для каждой вершины нужно запомнить длину слова в ней. Дальше простой двоичный подъем. Ответ на запрос (Хя буква текущего слова), очевиден при помощи такой структуры.

В результате у меня было 40+55+100 = 195, что выходило 30е место. Я очень сильно ругался когда у мне не хватило 1 миунты, что-бы доздать 1ю задачу на +10-18 баллов (4я подзадача).

Я и Фурик общаямся по скайпу после первого тура:

Потом был массовый прорсмотр результатов :) :

На 4й день мы решили забыть про результаты и круто оторваться в парке Garda Land :)
Я на фоне парка:

Несколько фоток из парка:

Наша команда:

Парк был просто крутой, очереди маленькие — катались много и везде, в отличии от Канады, где очереди в среднем были по 30 минут. Цены на все были весьма высоки.
На водном атракционе, когда мы свалились с горки, нас еще с автомата обстреливали ребятки, буквально через пару минут я их подменил :)) 1 минута поливания — 40 центов, кусается, но очень приятно :))

Иногда пересекались с другими командами, иногда даже катались вместе :) Фотка 6/8 участников команд Украины и Белорусии:

После поездки снова начался карантин.

Перед вторым туром я вспомнил, что это было мое последнее школьное соревнование, и что нужно не втыкать. А непосредственно перед туром полностью настроился его писать.
3! 2! 1! тур начался!
1я задача показалась очевидной в первых 3х блоках, но писать ее не стал, временно. 2ю задачу сразу читать не стал, при виде ВОСЬМИ страниц условия. 3я показалась весьма интересной, за час с лишним я ее осилил. Дальше пошли в ход решения по 1й, когдла сдал ее на 55 перешел к 2й, за 30 минут вник в условие, увидел халявное решение на первые 2 блока, через минуту придумал 3й, написал и на удивление получил еще 16 баллов за последний субтаск (как и предпологалаось авторами). Дальше я сел думать над 4й группой, и за 2 с лишним часа не придумал, да над 1й задачей я почти не думал, точнее думал в течении 20 минут где-то. Под конец тура я был уверен, что у меня серебро, но по окончанию тура я узнал что у 3их ребят из России такой-же балл (198) как и у меня. Мою радость было не описать когда я увидел таблицу. Единственное, что еще немного меня тревожило, что результаты могли быть не окончательны, как на 1м туре(там я был 29, хотя на самом деле 30й). Но меня успокоили, что уже точно все нормально. У наших ребят все было не так уж и хорошо, Рубик упал в бронpу, Фурик на границу, которая потом еще и сместилась. Виталик остался в серебре. После тура мы пошли релаксить на озеро, басейн, теннис и прочие места.

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

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

Закрытие прошло также не организовано. Начался дождь, и в зале сидели только медалисты, остальные были на балконе. На закрытии президент сказал, что олимпиада была проведена по "итальянски" :). Еще они начали вручать бронзу серебряным медалистам, потом одумались, правда. топ 3 вызывали по очереди, в отличии от всех остальных (группами). Победителю дали кубок и медаль. Странам-победителям дали чеки на 8К евро, как потом окзалось на обучение в Милане. Потом нас быстро отправили домой, по пути у половины участников поломались медали, точнее они поотрывались с ленточки. Ужин был значительно вкуснее предыдущих дней, нам дали сосиски :)
Пару фоток нашей сборной:

После ужина было пати, но это уже не публично :)

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +119
  • Проголосовать: не нравится

Автор Sereja, 12 лет назад, По-русски

У кого-то заходит на сервер в данный момент?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор Sereja, 12 лет назад, По-русски

214A - Система уравнений

В данной задаче решение — просто перебрать возможные пары чисел и проверить их на правильность. Делать это можно было любым способом.

214B - Домашнее задание

Число делится на 2,3,5 только в том случае, если сумма цифр кратна 3, а последняя цифра 0, то есть если в наборе нету нулей, то ответ -1. Дальнейшее решение — разбор случаев.
Возьмем все цифры в невозрастающем порядке, если сумма цифр кратна 3, то это и есть ответ. Если остаток от деления вышел 1, то нужно убрать 1 цифру у которой остаток от деления на 3 равен 1. Если такой не нашли то нужно убрать 2 цифры с остатком 2. Аналогично рассматривается случай когда изначальный остаток равен 2. Так-же нужно рассмотреть случай когда остались только нули, в этом случае нужно вывести только 1 ноль.

213A - Игра

Решение — жадность. Пусть у нас компьютеры стоят по кругу, и ходами "вперед" назовем перемещения (1->2, 2->3, 3->1), а перемещением "назад" (1->3,3->2,2->1).

Заметим что ходить "назад" не выгодно, так как можно 2 раза походить "вперед", что в сумме равноценно. Будем перебирать стартовую вершину. Дальше будем ходить по кругу до тех пор, пока не "откроем" все уровни. В авторском решении для каждого уровня поддерживается количество уровней, которые нужны для него. После того как мы находим очередной 0 в этом списке, мы просто уменьшаем такую величину для всех уровней, которые от него непосредственно зависят. Сложность решения O(n^3).

213B - Числа

Решение — динамика. Перебираем длину числа, которое будем строить. Далее будем пользоваться динамикой f(len,i) — сколько чисел диной len можно составить из цифр i..9.
Пересчет:
- f(len,0) = sum(f(len-i,1)*C(len-1,i), i=a[0]..len);
- f(len,j) = sum(f(len-i,j+1)*C(len,i), i=a[j]..len), 0<j<9;
- f(len,9) = 1, если len>=a[9], 0 если len<a[9].
C(n,k) — количество способов выбрать k элементов из n.

213C - Эстафета

Решение — динамика.
Заметим, что мы можем просто провести два пути их клетки (1,1) в клетку (n,n).
Заметим, что после каждого шага клетки будут оставаться на одной диагонали. Будем решать задачу динамикой f(d,i1,i2), d — номер диагонали, i1 — 1я координата 1го маршрута, i2 — 1я координата 2го маршрута. Понятно что вторую координату мы можем определить однозначно. Переходы — очевидны, делаем 4 возможных перехода, если маршруты пересеклись, то добавляем величину клеточки один раз, иначе добавляем величины посещенных клеток. Так как данная динамика не влазит по памяти, то ее нужно делать двумерной, просто перенося значения из прошлой диагонали в новую.
Еще нужно не забыть про то, что ответ может выйти отрицательным.

213D - Звезды

Предоставлю разбор как небольшую презентацию картинками:
https://get.google.com/albumarchive/pwa/115317317397602031319/Solutions131

Реализация.
Единственную сложность могло составить определение координат, все координаты можно найти из правильного пятиугольника. Все что о нем нужно описано тут.

213E - Две перестановки

Первый шаг: заменить перестановки на обратные, то есть из перестановки A мы делаем перестановку B, такую что B[A[i]] = i. Если посмотреть на то, что получилось, то выходит такая задача: сколько подотрезков второй перестановки равны первой, в случае если мы "сожмем координаты", то есть числам сопоставим их номер в отсортированном виде. Эту задачу предполагалась решать хэшами, но брать их нужно было не только по основанию 2^64, а и еще по нескольким простым модулям, тайм лимит специально стоял 3 секунды.
Теперь, собственно, как ее решать: Для каждой позиции i — сопоставим коєфициент step[i], где step[i] = 1000003^i. Теперь Рассмотрим такую функцию: F(A) = num[1]*step[1] + num[2]*step[2] + num[3]*step[3] + ... + num[n]*step[n], где num[i] — порядковый номер элемента A[i] в отсортированном списке. Понято что эта функция однозначно задает множество, от нее и будем считать хэш.
Как пересчитывать при переходе не следующий элемент.
Заметим что когда мы убираем какой-то элемент, то все элементы которые больше его уменьшают значение num на единицу. Ровно как и после добавления они его увеличивают. То есть заведем Дерево отрезков/Фенвика для хранения таких величин как сумма степеней на отрезке и количество элементов на отрезку, что-бы за O(log(n)) находить величину num для числа и после каждого добавления/удаления будем пересчитывать хэш, тоже за O(log(n)). Так-же нужно будем умножать хэш на от первой перестановки на 1000003 после каждого смещения на 1 элемент вправо, так как коэффициенты step уже не будут идти от единицы.

Все замечания просьба писать в комментарии.

Через некоторое время постараюсь сделать формулы более красивыми.

Полный текст и комментарии »

Разбор задач Codeforces Round 131 (Div. 1)
Разбор задач Codeforces Round 131 (Div. 2)
  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

Автор Sereja, 12 лет назад, По-русски

Всем привет!

Сегодня, 30 июля в 19:30 MSK состоится Codeforces Round #131, автором которого являюсь я(Сергей Нагин). Это мой первый раунд на Codeforces и надеюсь, что не последний.

Спасибо Фурко Роману(Furko) и Геральду Агапову(Gerald) за помощь в подготовке задач, а Марии Беловой(Delinur) за перевод условий. Также выражаю благодарность создателю Codeforces Михаилу Мирзаянову (MikeMirzayanov) за прекрасную систему.

Удачи на раунде!

Разбалловка в первом дивизионе: 1000-1000-1500-2000-2500. Разбалловка во втором дивизионе: 500-1000-2000-2000-2500. Настоятельно рекомендую прочитать условия ВСЕХ задач.

Контест завершен! Поздравляю победителей!

1й дивизион:
1 место: Egor
2 место: Petr
3 место: tourist
2й дивизион:
1 место: antimatter
2 место: c175353
3 место: takaramono

Надеюсь, задачи вам понравились.

Разбор задач.


Полный текст и комментарии »

  • Проголосовать: нравится
  • +220
  • Проголосовать: не нравится

Автор Sereja, 12 лет назад, По-русски

Всем привет!
Думаю, уже наступило время создать нужный пост. Пишите в комментарии предварительный состав команд которые уже знаете, а я буду по мере поступления данных добавлять их в таблицу.

Имя Страна Ник на Codeforces
Vardanyan Armen Армения
Mamikonyan Tigran Армения tikfiz
Davtyan Robert Армения
Harutyunyan Hrayr Армения
Геннадий Короткевич Беларусь tourist
Адам Бардашевич Беларусь subscriber
Сергей Кулик Беларусь CherryTree
Владислав Подтелкин Беларусь vlad107
Floris Kint Бельгия FKint
Victor Lecomte Бельгия vlecomte
Benoît Vernier Бельгия TheCamel
Hannes Vandecasteele Бельгия
Yordan Chaparov Болгария dancho
Rumen Hristov Болгария exod40
Georgi Georgiev Болгария gogokefakefa
Hristo Venev Болгария mustrumr
Andrej Ivanis Босния и Герцеговина
Daniel Ferizovic Босния и Герцеговина dani93.f
Ishak Numanagic Босния и Герцеговина
Aleksandar Kelecevic Босния и Герцеговина
Marcos Kawakami Бразилия marcoskwkm
Caíque Lira Бразилия caiquelira
Renato Ferreira Бразилия Renato_Ferreira
André Amaral de Sousa Бразилия
David Morán Венесуэла
Luis Arguello Венесуэла
Fernando Valarino Венесуэла
Jesus Soto Венесуэла
Nguyen Viet Dung Вьетнам RetiredKid
Nguyen Huu Thanh Вьетнам giongto35
Vu Dinh Quang Dat Вьетнам darknsux
Nguyen Tuan Anh Вьетнам con_nha_ngheo
Chan Pak Hei Гонконг AlanC
Yik Wai Pay Гонконг jasonyik
Lee Chun Yin Sampson Гонконг Sampson
Tsang Chun Chi Гонконг
Торнике Мандзулашвили Грузия TMandzu
Джимшер Схиртладзе Грузия jskhirtladze
Николоз Сванидзе Грузия svanidz1
Николоз Надирадзе Грузия nikanick11
Yousef Salamaе Египет Yousef_Salama
??? Египет
??? Египет
??? Египет
Nathan Azaria Индонезия nathanajah
Jonathan Irvin Gunawan Индонезия jonathanirvings
Cakra Wisnu Wardhana Индонезия semicfly
Muhammad Aji Muharrom Индонезия imiro
Seyed Hamed Valizadeh Иран havaliza
Saeed Ilchi Иран mR.ilchi
Alireza Farhadi Иран LGM
MohammadReza Maleki Иран mruxim
Darío Nieuwenhuis Испания dirbaio
David Balaghi Испания Sorington
Pol Olivella Испания farell94
Darío de la Fuente Испания dariofg
Gabriele Farina Италия (неоф.) obag
Giada Franz Италия (неоф.) Giada
Davide Pallotti Италия (неоф.) davidepallotti
Sebastiano Tronto Италия (неоф.)
Matteo Almanza Италия matteojug
Federico Glaudo Италия dario2994
Giuliano Gregori Италия
Luca Versari Италия veluca93
Вячеслав Ким Казахстан imslavko
Мади Хамитбеков Казахстан Kh.Madi
Аман Сариев Казахстан Aman
Даурен Муратов Казахстан DaurenMuratov
Chao Li Китай chnlich
YuQing Ai Китай scottai1
Peilin Zhong Китай zpl2
Yuzhou Gu Китай sevenkplus
Yuri Alcantara Olivero Куба
Азаматбек Ахмедов Кыргызстан Ahmedov
Шакарим Каландаров Кыргызстан mukt
Алибек Таалайбек Кыргызстан alibek_1
Нурсултан Алдаяров Кыргызстан
Алексей Попов Латвия popoffka
Марк Зельдес Латвия
Никита Ларка Латвия JustN
Ojars Vilmars Ratnieks Латвия OVR
Saul Gutierrez Мексика sggutier
Saul de Nova Мексика
Edgar Santiago Мексика
Freddy Roman Мексика frcepeda
Егор Суворов Россия yeputons
Макс Ахмедов Россия Zlobober
Олег Иванов Россия tigvarts
Алексей Гордеев Россия Copymaster
Ranald Lam Сингапур
Hubert Teo Сингапур
Bernard Teo Сингапур
Gan Wei Liang Сингапур
Johnny Ho США random.johnnyh
Scott Wu США scott_wu
Daniel Ziegler США ziedaniel1
Mitchell Lee США mitchell
Boris Grubic Сербия borisgrubic
Ivan Stosic Сербия ivan100sic
Demjan Grubic Сербия Demjan
Andrej Ivaskovic Сербия
Абдукодир Курбонзода Таджикистан abdukodir
Джамшед Хаитов Таджикистан Jamik
Бехруз Муротов Таджикистан BEHA
Хайём Одинаев Таджикистан GameR
Cheng-Min Chiang Тайвань bobogei81123
Liang-Chieh Chen Тайвань JamesQAQ
Shih-Wei Liu Тайвань
Ting-Yuan Cheng Тайвань
Ahmet Hudayberdyyev Туркменистан turkmen
??? Туркменистан
??? Туркменистан
??? Туркменистан
Yusuf Hakan Kalayci Турция t0nyukuk
Omer Eren Турция reink
Alperen Yakut Турция ayakut
Abdullah Alperen Турция abdullah_alperen
Нагин Сергей Украина Sereja
Рубаненко Роман Украина Rubanenko
Герасимов Виталий Украина witua
Фурко Роман Украина Furko
Jules Pondard Франция Artix
Simon Mauras Франция Simon
Auguste Olivry Франция auguste42
Gabriel Barrutia Франция
Luka Bulatovic Черногория MudoBog
Lazar Radinovic Черногория clzola
Kosta Pavlovic Черногория
Petar Djerkovic Черногория
Stepan Simsa Чехия simsa.st
Ondrej Hubsch Чехия ondrah
??? Чехия
??? Чехия
Marten Wiman Швеция
Simon Lindholm Швеция
Johan Sannemo Швеция jsannemo
Anton Grensjo Швеция
Shogo Murai Япония semiexp
Kazumi Kasaura Япония Hujiwara
Ikumi Hide Япония EnumerativeCombinatorics
Kohji Liu Япония hogloid

Полный текст и комментарии »

  • Проголосовать: нравится
  • +60
  • Проголосовать: не нравится

Автор Sereja, 13 лет назад, По-русски

Давайте здесь обсуждать задачи.
Кто как делал J в усложненке?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

Автор Sereja, 13 лет назад, По-русски
Задача А(cAPS lOCK)
 В задаче делаем все что просят в условии, если есть хоть одна строчная буква не считая первую, то оставляем все как есть, иначе меняем все буквы на противоположные. Что-бы поменять значение регистра, нужно в случае большой буквы прибавить к коду 32, иначе отнять 32.
 Посчитаем кол-во каждого числа, пускай кол-во числа i - B[i] тогда ответом будем сумма B[i]*B[-i], i=1..10 + B[0]*(B[0]-1)/2.
 Перебираем сколько мы будем брать мальчиков(пуская будет х) , считаем сколько нужно девочек на оставшиеся места(пускай будет у), если оба параметра удовлетворяют входные данные то к ответу добавим C(N,x)*C(M,y), где C(n,k) - кол-во способов выбора k элементов из n. В данной задаче лучше считать с помощью треугольника паскаля используя свойство: C(n,k) = C(n-1,k-1) + C(n-1,k), C(n,0) = 1. Так-же важно не забыть что если не проверять границы , то-есть допускать M<y, то возможны переполнения или еще какие-то тупые баги.
Задача D(Метро)
 Найдем цикл (например обходом в глубину, Ссылка, еще нужно не забыть что граф неориентированный, и ходить в предка нельзя). Добавим эти вершины в очередь, и пометим расстояние до них как 0, потом запустим обычный волновой алгоритм и получим ответ.
 Посчитаем для каждого ферзя, угрожает-ли он кому-то в каждом направлении. Как это сделать:
Ответы по горизонтали: сортим по X, идем слева на право, если уже встречалась раньше, вершина с таким Y, то ответ для ферзя +1, ну и еще нужно пометить что такой У уже встретился. Аналогично сделаем с проходом с права на лева. 
Для ответов по горизонтали, все так-же, просто меняем местами X и Y во всех местах.
Остались диагонали: каждая диагональ может относиться к двум видам, первый однозначно задается как X+Y, второй как X-Y, то есть снова сортируем все по X, делаем два прохода, слева на право и наоборот, только в данном случае считаем встречались/нет не X, а значение диагонали.
Задача F(Подарок маме)
 Определим где есть и где нету звезд, если она есть то в ячейке матрицы будет 1, иначе 0. Посчитаем частичные суммы таких прямоугольников. Дальше зафиксируем левую и правую границы прямоугольника, а дальше будет идти с двумя указателями, смещать первый вниз и двигать второй вниз пока между ними кол-во звезд больше-равно К. Кол-во звезд в прямоугольнике можно посчитать через частичные суммы: пускай координаты прямоугольника будут (x1,y1,x2,y2), а частичные суммы для позиции (i,j) будут лежать ячейке a[i,j], тогда ответом будет a[x2-1,y2-1]-a[x2-1,y1]-a[x1,y2-1]+a[x1,y1], так-как границы мы не можем включать в ответ. Теперь допустим в какой-то момент левая граница равна l(l = 0, если еще даже взяв все не получим сумму в К), то к ответу нужно прибавить это-же l, то-есть все не меньшие прямоугольники.


Полный текст и комментарии »

Разбор задач Codeforces Beta Round 95 (Div. 2)
  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

Автор Sereja, 13 лет назад, По-русски
Задача А. Лифт
Задача, на аккуратную реализацию:
- если мы находимся в пункте назначение, то ответ T.
- иначе лифт может находится в 2*М-2 состояниях, которые будут циклично повторятся. Состояние это номер этажа и направление, таких состояний будет 2*М-2. что-бы узнать состояние можно просто взять время по модулю. По состоянию можем определить этаж и направление, для удобства напишем функцию, которая определяет время которое нужно лифту что-бы добраться от одного этажа со стартовым направлением до другого, там нужно рассмотреть 4 варианта, этаж выше/ниже, и направление вверх/вниз. Дальше ответом будет функция от начального положения лифта в момент Т до старта+расстояние от старта до финиша.

Задача Б. Очень занимательная игра
Перебираем какое число мы поставим(I) первым оно будет от 1 до min(mod-1,A) потому-что дальше mod перебирать нет смысла, числа по модулю будут повторяться. Дальше домножим наше первое число на (109)%mod и возьмем произведение по модулю, пускай оно будет X тогда число I подходит если X!=0 и X+B<mod, что вроде-бы очевидно.
Задача С. Цикл
Тут было много решений с ДФС, но я писал немного другое:
Зафиксируем вершину V и разобьем все вершины на 2 группы, те которые имеют ребра в V и те которые имеют ребра из V. Теперь ребра делятся на такие группы: идут в V(d1), идут из V(d2), лежат в первой группе(m1), лежат во второй группе(m2), выходят из первой во вторую(n1), выходят из второй в первую(n2). Теперь мы можем утверждать что ответ есть если последняя группа не пустая. Как нам посчитать величины групп? Для начала посмотрим на то что мы знаем: по степеням входа и выхода вершин мы знаем значение n1+m1 и n2+m2, так-же мы знаем значение n1+n2 которое очевидно равно произведению этих двух групп, так-как между каждой парой есть ребро. Из этого несложно выразить значение n2,если оно положительное то переберем все пары и проверим их, хотя-бы одна найдется, так-что асимптотика O(N2).
Задача Д. Небыстрое преобразование
Делать можно разбиением задачи на подзадачи. Для начала заметим что любой отрезок до того как его преобразовали можно задать 2мя числами: 1м числом и разницей между числами, то-есть последовательность ничто другое как арифметическая прогрессия. При разбиении на два отрезка мы из состояния (l,r,q,w) l,r - границы отрезка, q - первое число,w - разница между числами. перейдем в состояния: (l,(l+r)/2,q,w*2) и ((l+r)/2+1,r,q+w,w*2). Теперь если мы попали в отрезок который полностью лежит в той области которая нас интересует, то нам не важно как стоят числа, нам важны сами числа. Суммы можно посчитать обрезав ненужные части как сумму арифметической прогрессии. В ненужных отрезки(которые не имеют общих частей с интересующих) мы просто ходить не будем. А кол-во отрезков будет как при подсчете суммы на отрезке в дереве отрезков, то-есть порядка O(log(N)). Что довольно мало.
Задача Е. Дерево или не дерево
Ее не сдавал, но решение придумал. Рассмотрим наш граф, он является деревом + одно ребро, то-есть цикл к вершинам которого прицеплены деревья. Рассмотрим задачу для дерева, сначала посмотрим на связь кол-во включенных вершин и количеством компонент связности: в дереве без выключенных вершин 1 компонента , при каждом добавлении выключенного ребра кол-во компонент увеличивается на 1, то-есть кол-во компонент в дереве это просто 1+кол-во выключенных ребер. То-есть нам каждый раз нужно знать кол-во включенных вершин. Эта задача решается с помощью Heavy-light декомпозиции, в подробности вникать не буду, если знать ее, то решение становится ясным, единственно над чем стоит подумать, это как поддерживать в дереве отрезков кол-во вершин с непарными числами. Теперь что-же делать если у нас есть цикл, все так-же просто у нас путь всегда будет один из: путь по дереву которое "свисает с цикла" решается стандартно, и если начало и конец пути лежать в разных деревьях, то-есть проходит по циклу, это можно решать так: решим задачу для корней деревьев которые содержат наши старт и финиш и старта и финиша, и осталось малая часть: разобраться с циклом. Замечу что лексикографичность(по какую сторону будем идти) выбрать не сложно, там всего максимум 2 варианта, то-есть можно сказать что отрезок на котором мы будем менять цвет мы знаем. Осталось установить закономерность как влияют кол-во выключенных клеток. Замечу что то какие деревья и сколько в них чего нас не интересует, нас интересует только их кол-во и кол-во выключенных ребер в цикле. Сначала если у нас все включены, то от ответа нужно отнять N и добавить 1, потому-что у нас все компоненты объединены, при добавлении выключенного ребра ответ будет увеличиваться на 1, то-есть нам нужно будет еще всего-лишь узнавать кол-во выключенных ребер. Вроде-бы все.

Если-что-то не так, то пишите. Надеюсь вам понятно.

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 88
  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

Автор Sereja, 14 лет назад, По-русски
Сегодня прошла пятая индивидуальная интернет-олимпиада на сайте neerc.ifmo.ru/school. Давайте здесь обсуждать решения задач.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

Автор Sereja, 14 лет назад, По-русски

Задача А. Автодополнение

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

Задача B. Фотография в блог

В этой задаче так-же нужно было переборное решение.
Сначала перебираем первую сторону как степень двойки(пускай это будет S) , когда мы знаем это число пытаемся определить максимальную 2ю сторону(пускай это будет L) которую мы можем получить(возможно ее мы не можем получить): первый вариант S*0.8>m ,тогда L=0 (мы ее не можем получить можно поставить 0, и произведение будет 0), второй вариант S*1.25<m , тогда L равно максимальному целому числу меньше равному S*1.25, иначе S*0.8<=m<=S*1.25 L=m. Посчитав их проверяем на оптимальность. Аналогично делаем и для второй стороны. Единственно что нужно помнить в случае равности ответа приоритет отдается тому, когда высота больше.

Задача С. Лягушонок

Ответом будет последовательность: 1 ,N  ,2 ,N-1, 3 ,N-2 ...
Доказать это можно очень просто, так-как разница между числами всегда будет уменьшаться на единичку.

Задача D. Физкультура

Алгоритм задачи такой: идем слева на право и берем для каждого человека из первого множества самого ближнего из второго , который стоит не левее его самого , ну то есть если мы рассматриваем человека номер i, то нам надо найти минимальное j, что i<=j и A[i]=B[j]. И сделать нужные переходы. Так-как ограничение всего-лишь 300, то такое решение будет работать. Так-же это решение будет выдавать самый оптимальный ответ. Для больших ограничений эта задача решается сортировкой слиянием. Ну то есть сначала нужно сделать некоторые преобразования, а именно для каждой ячейки определить где она должна будет стоять, дальше выходит довольно не сложный алгоритм.

Задача Е. Тупики

Зададим динамику Ans[tree,dl] (tree,dl - битмаски) где будем хранить ответ:
1). мы составили дерево из вершин tree.
2). тупиками у нас вершины dl.
Очевидным есть ответ для двух бит, если между вершинами есть ребро то 1 , иначе 0.
Если кол-во бит больше(пускай єто будет состояние (m1,m2)) то ответ считаем так: зафиксируем некоторую вершину i которая есть тупиком и некоторую вершину j которая не есть тупиком и есть ребро между i и j. Мы будем убирать вершину i из дерева, тогда возможны два перехода , тупик i исчезает и получаем состояние (m1 xor (1 shl i),m2 xor (1 shl i)) , тупик i исчезает и j стает тупиком (m1 xor (1 shl i),m2 xor (1 shl i) xor (1 shl j)). Когда посчитали ответ для состояние(Ans[m1,m2] ),тогда разделим его на кол-во бит в m2.
Ответом будет сумма Ans[(1 shl n)-1,dl] , причем кол-во бит в dl = K.

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 49 (Div. 2)
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

Автор Sereja, 14 лет назад, По-русски
У меня иногда , когда я нажимаю на рейтинг, сбоку выводит другого человека. И в рейтинге тоже, голубая полоса на том человеке, уже несколько раз так было.
В чем может быть проблема?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится