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

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

Саратовский государственный университет в рамках Чемпионата мира по программированию ACM-ICPC 2010/11 с 19-го по 23-е октября 2010 проводит ХIII Четвертьфинальные соревнования Чемпионата мира по программированию Южного региона России.

За право выйти в полуфинал Чемпионата мира будут бороться команды вузов из Астраханской, Волгоградской, Воронежской, Нижегородской, Пензенской, Ростовской, Самарской, Саратовской, Тамбовской, Ульяновской областей, Краснодарского, Ставропольского краев, из республик Адыгея, Марий Эл, Мордовии, Северной Осетии, Татарстан. 63 команды примут участие в соревновании.

Кроме того, 19-го октября 2010 будет проведена IХ Региональная командная олимпиада школьников по программированию, которая является отборочным этапом на Всероссийскую командую олимпиаду школьников. Лучшие пять школьных команд завоюют право участия в финальном этапе олимпиады.

На официальном сайте http://contest.sgu.ru/ вы сможете следить за результатами в процессе соревнования.

Уже пятый год подряд кроме официального соревнования участникам предлагается неофициальное развлекательное соревнование Code Game Challenge. В рамках Code Game Challenge команды будут писать программы, которые будут помещаться в симулятор игрового мира, чтобы напрямую соревноваться с программами других участников! Таким образом, вместо проверки на наборе тестов, ваши подходы будут помещаться непосредственно в эмулятор игрового мира, чтобы непосредственно соревноваться с программами других команд.

23-го октября в 11:00 на сайте http://acm.sgu.ru/  состоится онлайн-контест по задачам четвертьфинала. В систему будут интегрированы результаты участников официального онсайт соревнования.

Всем удачи!
MikeMirzayanov


UPD: Соревнование закончено. Всем спасибо за проявленный интерес! Результаты соревнования опубликованы.

Поздравляем победителей соревнований:
  • Саратовский государственный университет #2 (Иванов, Рахов, Кузнецов) — 1 место (9 решенных задач)
  • Нижегородский государственный университет (Епифанов, Вадимов, Шмелев) — 2 место (8 решенных задач)
  • Саратовский государственный университет #1 (Фефер, Агапов, Бондаренко) — 3 место (8 решенных задач)
В соответствии с квотами нашего подрегиона, 14 команд завоевали право участия в полуфинале:
  • Саратовский государственный университет #2
  • Нижегородский государственный университет
  • Саратовский государственный университет #1
  • Волгоградский государственный технический университет #1
  • Саратовский государственный университет #3
  • Казанский федеральный университет #1
  • Ульяновский государственный технический университет
  • Самарский государственный аэрокосмический университет #2
  • Волгоградский государственный университет #1
  • Таганрогский технологический институт Южного Федерального университета #1
  • Астраханский государственный университет
  • Таганрогский технологический институт Южного Федерального университета #2
  • Адыгейский государственный университет
  • Самарский государственный аэрокосмический университет #1
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится
Хочу пожелать удачи не только всем участникам соревнования, но и организаторам. Надеюсь, в очередной раз будет продемстрирована прекрасная организация и интересный контест. Желаю организатором избежать всяческих проблем и, самое главное, серьезных ошибок в задачах, а достойным участникам - поездку в полуфинал. Всем удачи и до встречи!

С уважением, 
Иван Горбачев
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ты так переживаешь за организаторов, аж страшно становится.
    Не приготовил ли ты им какой нить сюрприз? )
    Мне кажется, что на столь серьезном мероприятии и в столь уважаемом ВУЗе всё и всегда должно было и быть на высшем уровне. Или прецеденты уже бывали?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится
      Смотрите. Вы делаете вечеринку на 5-х своих самых близких людей. Всё подготавливаете: меню, музыку, развлекательную программу и т.д. Всё спланировали, до самых мелочей. Вроде бы какие могут возникнуть проблемы?
      И вот наступает час X, Ваши друзья приходят к Вам, начинается вечер и вдруг выключают свет. Приехали, называется. Особенно, если Вы не побеспокоились о таком развитии событий заранее.

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

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

      Я искренне пожелал удачи организаторам и всем участникам. Не знаю откуда Вы увидели какой-то сарказтический контекст в моих пожеланиях. 
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Бывало всякое... вот, например, интересная табличка. И мероприятие серьезное и ВУЗ более чем, тем не менее косяк был.
      Я уже не помню в чем именно, вроде в одной задаче были неверные тесты и в итоге это довольно сильно повлияло на штрафное время лидеров, вот и решили их уровнять по этому показателю.
      На топкодере тоже бывали ошибки в решениях жюри, причем как просто небольшие баги, так и в принципе неверные алгоритмы решения...
      И это нормально, чем выше уровень мероприятия, тем меньше вероятность ошибок, но она никогда не ноль.
14 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится
Может кто поделиться решениями задач?
14 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится
Для начала, небольшая опечатка: "... На официальном сайте http://contest.sgu.ru/ вы сможете следить ЗА результатами в процессе соревнования ..."
А что касается самого контеста, то это один из самых сложных четвертьфиналов. И задачи не самые простые и команды достаточно сильные.
Есть команды, за которыми завтра буду следить с особым вниманием:
Astrakhan SU #1 - Ваня Горбачев почти в одиночку нарешивает контест за контестом, он сделает невозможное, если таким составом выйдет на полуфинал. Удачи, Ваня.
Volgograd STU #1 - Ну если не они, то кто?! Эти ребята лишили нас третьего места в Ижевске. Очень хорошо решают, им пора бы уже на финал... Удачи, ребята.
Saratov SU #2 - Не исключаю их победу в четвертьфинале. Состав сильный, вполне может выйти на финал и взять там медаль. 
Nizhniy Novgorod SU #1 - Ну больше всего верится в их победу на четвертьфинале, однако не поставил бы со стопроцентной вероятностью на них. Хотя, уверен, что на финале эта команда будет.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а в чем суть опечатки?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Был пропущен предлог "за". Я уже исправил. Но, чтобы такого не возникало, принято отправлять такие замечания автору в личку.
      • 14 лет назад, # ^ |
          Проголосовать: нравится -21 Проголосовать: не нравится
        Я уже второй раз вижу фразу автора про "принято отправлять в личку".
        ИМХО было бы правильно просто исправлять ошибки.
        А еще лучше - перечитывать перед опубликованием.

        BTW, спасибо за все, удачи
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Отлично. Я давно ждал возможности реабилитироваться после четвертьфинала 2009 года. Я и моя команда очень усердно тренировались, чтобы на этот раз съездить минимум в Санкт-Петербург.

Всем удачи. Увидимся в среду ; )

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну, вы туда попали. Извини, я думаю, что Макса с Темиком вы в Питере не обгоните)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А много кто думал, что в 2009 году команду чемпионов мира обгонит команда из их университета? :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На контест ,который будет проходить на сайте acm.sgu.ru нужно регистрироваться?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Достаточно регистрации на сайте acm.sgu.ru
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Для того, чтобы в таблице отображалось имя команды, нужен отдельный командный аккаунт?
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

А когда будут результаты?

14 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Круто, с победой Saratov SU #2! Вот как знал, что могут занять первое место :)
С выходом в полуфинал команду Volgograd STU #1.
Хочется посмотреть, что там за задачи, которые никто не сдал... Такие пади даже в Петрозаводске не дают.

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну не знаю, мы те задачи даже не читали, однако могу сказать, что задача А-реализационный гроб)) Там короче нужно было сказать правильно ли строится строка, там даны были условия на то что последовательность символов является строкой или числом. 
    Короче, у Волгограда он падал на 37 тесте забыли проверять лидирующие нули) Ну они сами потом расскажут))). У Епифанова вроде К дошла до 20-го и упала
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    А вообще даже если так (хотя сомневаюсь, много задач было решаемых даже для не самых подготовленных программистов типа нас)-то что странного? Организаторы по именам ничуть не хуже-Мирзаянов, Матов, Бондаренко, Мещеряков, Левшунов, Романов, Денисов, Кленов, Алексеенков.... Чемпионы мира, Европы, России... Очень солидный состав жюри 
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А мы продумали заранее, но всё равно по ходу написания обнаруживались всякие тонкости, и в результате последние минут 40 только и сидели, что баги отлавливали (штук 5 набралось). Неприятная задача, но остальные три были ещё неприятней :)
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Это да) Мы ее сели писать и забили в какой-то момент, к тому же я как-то через 5 точку построил дерево игры на D и мы думали что наша жадность на С прокатит(на 20-м тесте упала). 
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    в Петрозаводске один раз был контест где победители решили 2 задачи, а наша команда сдала одну на 5-ом часу соревнования (насколько я помню)

    посмотрим сколько на acm.sgu.ru сделают. 10 вполне реально сдать. я правда до начала ЧФ думал что 11 сдадут...
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Просто когда сам составляешь контест, все задачи наверное кажутся очевидными и яйца выеденного не стоящими. А когда решаешь чужой проблемсет...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Кто ж мешает - смотрите :)

    Там другая нумерация задач, правда - "гробы" это E, K (задача A на четвертьфинале) и L.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я так понимаю уже можно обсуждать задачи? Просто интересно как решать задачу про дерево и вообще 4 гроба которые были?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Задача E решается жадностью.

    Для начала заметим, что если есть 2 точки (x1,y1) и (x2,y2), таких что x1<x0 и x2>x0 или y1<y0 и y2>y0, то искомого пути не существует.

    Без ограничения общности будем считать что все наши точки находятся в первой четверти при переносе точки (x0,y0) в начало координат.

    Пусть первая группа команд состоит только из 'E' и 'N', а вторая, соответственно, из 'W' и 'S'. Первый шаг всегда будем делать вправо. Затем если правее от текущего местоположения есть источники с таким же игреком, то идем вправо, иначе идем вверх. Единственное исключение: если игрек координата нашего текущего местоположения равна Y-1 (Y - максимальный игрек среди всех источников, а X - максимальный икс), то ходить вверх мы можем только в случае если текущий икс равен X, иначе идем вправо.

    Таким образом мы построили первую группу команд. Аналогично, из точки (X,Y) нам нужно добраться до (0,0) при помощи только шагов влево и вниз. Будем поступать так же, только теперь если мы стоим в точке (x,y) и в точке (x,y-1) мы уже были, то ходем влево, иначе решаем куда ходить так же как и в первой группе команд.

    Отдельно нужно рассмотреть случай когда все точки лежат на одной вертикальной или горизонтальной прямой (забор не должен иметь самокасаний).
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Кстати, одна команда решила почти все задачи в онлайн-туре, кроме очевидных масочек, и нам сказали на разборе, что это киевская команда. Это вы? 
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Нет, я писал один. А это была команда Exploitless из моего университета.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что-то не так с новыми задачами на acm.sgu.ru. С тех пор, как они переехали в глобальный problemset, народ стал падать на первом тесте. 
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У меня K упала на 162 тесте (в онлайн-контесте на acm.sgu.ru). Нельзя ли как нибудь посмотреть этот тест? А то обидно :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Хаха, я слышал, эти тесты (в районе 160-го) добавлялись в последнюю ночь - какие-то хитрые особые случаи. Не зря значит авторы старались :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать D?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Сжать координаты, отсортировать точки по возрастанию икса.

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

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

    Чтобы найти вторую группу точек (которые принадлежат всем самым длинным путям), достаточно просто выделить такие точки, которые принадлежат хотя бы одному самому длинному пути, причем точек с такой же максимальной длиной пути до них в первой группе больше нет.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня другое решение:

      Сортируем точки по возрастанию x, а при равных x по убыванию y. Теперь чтобы найти максимальную длину пути можно забыть про x и найти наибольшую возрастающую подпоследовательность по y. К сожалению, саму длину нам искать не надо, но оказывается можно модифицировать стандартный алгоритм нахождения LIS за логарифм под наши нужды. А именно, будем поддерживать не только массив a[i] из минимальных элементов, на которые закачиваются все возможные подпоследовательности длины i, но и при его обновлении будем складывать в такие же "корзины" сами точки. Итого, после рассмотрения всех элементов последняя корзина у нас будет содержать все точки которыми может заканчиваться самый длинный путь. Мы будем идти по этим корзинам от последней к первой и, убирая лишние точки, делать вывод о том, обязательная точка или возможная (если после убирания лишних в корзине осталась одна точка, то она обязательная, если больше одной, то все они возможные).
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
ignore
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать J (с онлайн)? Реально тупим и не видим решения, пока думаем в сторону потока, но что-то какие-то дикие сети в голову приходят...не укладывающиеся в лимит по времени...
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Я решал перебором за 2^25 всех строк, в которые мы будем бомбить. Все строки таблицы представляем в виде битмасок.

    Теперь чтобы для фиксированного набора строк размера Х проверить, сколько выстрелов нам не хватило чтобы все убить, нужно взять побитовое "или" всех строк, которые не вошли в наш набор, и найти количество единиц в этом числе (пусть это Y). Тогда нам нужно max(X,Y) выстрелов, если мы будем бить по данному набору строк.

    Чтобы быстро считать количество единиц в числе - предпосчитаем это количество для всех чисел от 0 до 2^16 и затем просто делим наше число на 2 части и суммируем количество единиц в ней.

    Осталось научиться быстро находить для данной маски строк побитовое "или" всех строк, которые не вошли в эту маску. Для этого применим такой же прием: разделим таблицу на 2 части и для всех масок отдельно в каждой части предпосчитаем побитовое "или" строк, не вошедших в нее. Тогда для целой таблицы нам достаточно будет разделить маску на 2 части и взять "или" двух предпосчитанных значений для половин таблицы.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
как решать задачу про каркас?
14 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
http://saratov.kp.ru/daily/24579/749891/

>Илья Литерман, выпускник СГУ, в настоящий момент являющийся одним из руководителей компании Crid Dynamics
:(

P.S. Отправил исправление. Посмотрим, как долго у них займет проверка)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите, пожалуйста, как решалась Revolutionary Roads.
Мое решение методично ловит ВА21.
  • 14 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится
    Сначала сконденсируем исходный граф, затем построим матрицу достижимости g[i][j] - если true то j сильная компонента достижима из i, затем перебирая исходное ребро делаем его двунаправленным, пусть ребро соединяло "u" и "v", тогда "a" = компонента который принадлежит "u", "b" = компонента который принадлежит "v", если "a"=="b" то обновим ответ через размер компоненты "a", иначе ответ нужно обновить через следующую сумму :
    sum = size(a) + size(b) + ( size(t) |    g[a][t] && g[t][b] )
    size(x) - размер компоненты x.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо.
      Идея была та же, только такое обновление ответа гораздо проще и, выходит, правильнее, чем мое :)
14 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Задача Problem G. Buoys. WA9. В чем ошибка, помогите плиз.


#include <iostream>
#include <iomanip>
#include <math.h>
double mi=0.0;
int n;
int a[401];
    double s[401],b[401];
    double k=0;
using namespace std;
void funt(int h,double d)
{
    for (int i=h-1; i>=1; i--)
    { s[i]=s[i+1]-d;
    };
    for (int i=h+2; i<=n; i++)
    { s[i]=s[i-1]+d;
    };
    k=0;
    for (int i=1; i<=n;i++)
    k=abs(s[i]-a[i]+0.0)+k+0.0;
    if (k<mi)
    {
        mi=k;
        for (int i=1; i<=n;i++)
        b[i]=s[i];
    }
}



int main()
{
    
    cin >>n;
    
    for (int i=1; i<=n; i++)
        cin>>a[i];
    double f=(a[n]-a[1]+0.0)/(n-1+0.0);
    s[1]=a[1];
    for (int i=2; i<=n;i++)
    {
        s[i]=s[i-1]+f;
        k=abs(s[i]-a[i]+0.0)+k+0.0;
    };
     mi=k;
    for (int i=1; i<=n;i++)
        b[i]=s[i];
    double dist;
    for (int i=1; i<n; i++)

    {    
        dist=(a[i+1]-a[i]+0.0);
        s[i]=a[i]; s[i+1]=a[i+1];
         funt(i,dist);


    }; 
    cout<<fixed<<setprecision(4)<<mi<<endl;
    for (int i=1; i<=n; i++)
    cout<<fixed<<setprecision(10)<<b[i]<<" ";
    return 0;
}
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нужно фиксировать любые два буйка, не обязательно первый и последний, и два смежных, как у вас. 
    + нужно в функции funt писать так

    for (int i=h+1 (!!!); i<=n; i++)
    { s[i]=s[i-1]+d;
    }
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Дайте решение задачи Kidnapping. Поймал ошибку TLE на 11 тесте.
  • 14 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    http://pastie.org/1250704

    Попробую немного объяснить.

    Вершин у нас до 200.Дорог в маршруте тоже <=200.

    Сделаем массив boolean NextIter[N][I],где N-это количество дорог в маршруте,и Next[N][I]==TRUE,если город I входит в маршрут длиной N.

    Тогда,очевидно,можно получить какие города входяд в маршрут длиной N+1,зная какие города входят в N:

    for(int i=0;i<r;i++)//текущее количество дорог
    {
    for(int j=0;j<n;j++)
    {
      if(NextIter[i][j])//Если j входит в текущий маршрут
    {
      for(int k=0;k<n;k++)//перебираем  все  соседние города 
    {
      if(G[j][k]==lgs[i])NextIter[i+1][k]=true;//Если расстояние до них-то что нужно,добавляем в NextIter[N+1]
    }
    }
    }
    }

    Ответом будет такие I,для которых NextIter[r][I]=TRUE

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А фото с контеста будут???
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Дайте решение задачи Fire in the Country, не понимаю как ее реализовывать?
14 лет назад, # |
Rev. 5   Проголосовать: нравится -8 Проголосовать: не нравится
задачка  Explode 'Em All. WA20. В чём трабл?
#include <iostream>
using namespace std;
int main()
{
char s[26];
int d[26][26],n,m,bom=0,k=0,rem,max=0,remx=0,remy=0;
cin>>n>>m;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){ d[i][j]=0;}}
for(int i=0;i<n;i++)
{
cin>>s;
for(int j=0;j<m;j++)
{
if(s[j]=='.') d[i][j]=1; else d[i][j]=2;
if(d[i][j]==2) {d[n][j]++;d[i][m]++; bom++;}
}
}
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Насколько я знаю, WA20 - это тупейший жадный алгоритм, бьющий каждым ходом так, чтобы взорвать больше всего камней.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, ВА20-это то что мы пытались сдать на протяжении 2,5 часов по ходу контеста. Решения полиномиального к этой задаче сложно придумать, если вообще можно(хотя наша команда подозревала что можно поизвращаться с паросочетаниями(это похоже на задачу о расстановке ладей), возможно что тогда и будет что-то)
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Не могли бы люди, сдавшие задачу Running Hero, сказать, за какую сложность её предполагалось решать? Судя по ограничениям, O(N^2) должно проходить, однако TL #9 на Java.

UPD: ого, TL 9 - это на acm.sgu.ru, а вот на neerc.ifmo.ru/trains это же решение получает Accepted. Что-то я совсем ничего не понимаю =/ . Особенно интересной ситуацию делает то, что с другой задачей(а именно Rectangles с четвертьфинала Центрального региона) все абсолютно наоборот - на neerc.ifmo.ru/trains TL 29, а на другом сайте(к сожалению забыл название) - OK...


  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Расскажите кто нибудь как проще всего делать L? (не надо давать ссылки на статьи про dynamic mst)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      На разборе рассказывали примерно такую декомпозицию.
      Разбиваем все запросы на 200 групп по q = 200 запросов, затем смотрим, какие ребра из неизмененных точно войдут в МСТ. Получится граф с O(q) вершинами. На нем уже можно и Краскала позапускать