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

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

Это был мой 3-ий SRM.

Прерыдущие 2 были слиты и я находился на 521 месте в своём дивизионе.

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

Но взяв себя в руки сел его писать.

Первая задача сдалась быстро.

Вторая же показалась весьма интересной.

Написав первое придуманное решение и проверив его на демо тестах, я его отослал.

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

Не придумав ничего путного по 3 задаче до конца соревнования пытался понять своё решение, но так и не понял.

Каково же было моё удивление, когда обе задачи прошли System Test и я с 521 места переместился на 38, получив +221 рейтинга.

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

Я уже перестал верить в чудеса и то, что ко мне приходит озарение и "заходит" вообще непонятно каким образом моё решение.

В общем у меня вопрос - может ли кто нить объяснить - почему моё решение зашло. Это weak tests или на несколько минут в меня вселился дух какого то профи и при этом свалил тут же после отправки этого решения, не объяснив его корректность.

Исходый код 

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто-нибудь будет постить анонс SRMа ? :) 
Охота узнать как решаются  2 и 3 задача.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Молодец, поздравляю с успешным написанием SRMа. Странно, что это всего третий твой SRM, хотя на CodeForces ты писал чаще.
ИМХО, однако, профессионализм ("дух профи") определяется умением стабильно решать задачи (и желательно в первом диве), а не сиюминутным озарением.
Кроме того, возможно, у других менее оптимальное решение, но они потратили на его придумывание меньше времени, что на соревнованиях типа ТопКодера с маленькими ограничениями и зависимостью очков от времени критично.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    http://forums.topcoder.com/?module=Thread&threadID=693376&start=0
    вот тут решение обсуждают
    может, lyrically потом editorial по матчу напишет.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Написал по задаче ДП за O(n).
    http://www.topcoder.com/stat?c=problem_solution&rm=306316&rd=14240&pm=11157&cr=22840202

    У тебя в решении тоже ДП, только вместо конечного результата у тебя хранится его изменение.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Я не понял - почему моё ДП - корректное.
      Заодно - объясни своё решение, если можно.
      • 14 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Исходная задача распадается на несколько независимых. Выпишем k+1 раз сл. числа c индексами:
        0, k+1, 2k+2 ...
        1, k+2, 2k+3 ...
        ...
        k, 2k+1, 3k+2 ...
        Для каждого набора таких чисел посчитаем следующее ДП:
         в dp[i] будем хранить максимальную сумму включенных чисел. Переходы следующие:
        1) Мы можем включить числа i, i+1 в отрезок. Тогда сумма, которую мы получим будет: dp[i-1]+p[i]+p[i+1]. (dp[i-1], потому что каждое число мы можем включить макс. в 1 отрезок)
        2) Мы можем пропустить число i+1 (не включать в отрезок с i). Тогда мы получим сумму просто dp[i].
        Из этих 2-х переходов выберем максимальный: dp[i+1]=max(dp[i-1]+p[i]+p[i+1],dp[i])

        Можно не разбивать на наборы в явном виде.

        В твоем случае: в res[i] хранится изменение итогового результата, если мы возьмем числа i, i-k-1. Тут действие одно:
        1) Мы берем числа i, i-k-1. Тогда нужно отнять изменение, если мы взяли числа i-k-1, i-2k-2. Т.е. результат dp[i]-dp[i-k-1].
        Если лучше взять числа i, i-k-1 а не числа i-k-1, i-2k-2, то результат будет положительный. И мы добавим его к сумме. Если же нет, то ничего добавлять не надо.

        P.S. Чем-то похожая задача:
        http://olympiads.ru/sng/2/description2.shtml
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Молодец)
Кстати приезжайте к нам на itfest, а то чего-то совсем в последнее время притихли
14 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится
А я 4 рейтинга потерял на этом SRM'e 
Решил в лоб и меня зачеленджели =D
ДП я ни разу на контестах не писал, опыта нету с ДП =(
И, вообще, 2-3 года назад я думал что графы это модуль Graph в паскале, 
а ДП это работа с указателями =/