Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

Блог пользователя ivan.popelyshev

Автор ivan.popelyshev, 13 лет назад, По-русски
Member single round match 501 will start at 3.00 PM Moscow, 12:00 AM GMT.
Discuss it here.
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
I have the 250 problem...
I saw DP solution only in the end of round. 75 points.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    забыл выставить язык (теперь выставил).
    Д там не дп можно было , а тупость. надо совершить несколько раз 2-ое действие, потом nA раз 1-ое потом остаток вторых.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ДП просто быстрее писать, и думать меньше :)
      • 13 лет назад, # ^ |
        Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится
        только у меня не прошло О_о

        UPD

        да уж, перепутал в 1 строчках крайних случаев количество и значение :((
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
250 div.1 = 500 div.2 ?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У меня в 1000 какое-то палево ТЛнутое. во время контеста не придумал как его исправить, сделал грязный хак. Сейчас знаю как надо было писать, но надеюсь что у жюри слабые тесты
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Почти каждый раз кто-нибудь пишет историю своего успеха и/или провала.
На этот раз я напишу, как не надо делать, когда до конца матча остается пара минут.

Я в 500 написал динамику 2 * 40 * 40 * 1600.
После этого я скомпилил задачу на сервере и начал оптимизить в среде, до последнего не отправляя. Сделал какую-то лажу, а когда оставалось 10 секунд, решил отправить (решение ведь старое на сервере хранится), но по привычке сначала нажал компилирование, которое, естественно, затерло мое старое решение и выдало кучу ошибок в новом. В итоге нет 500ой, 4 неудачных челленджа, которые я считал стопудовыми, и -11 очков.

Кстати, как думаете, решение с такой сложностью, как я указал, прошло бы? У меня на компе макстест из 40 "-1" (я прав, это макстест?) работает 14 секунд. Может у них комп быстрее?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Блин, кажется мне пришла идея решения за 2 * 2 * 40 * 1600. Это ведь правильное?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня решение за 2 * 40 * 40 * 1600 на 40 переходов работало на сервере 0.5 сек.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А у меня такое же ловило TL - я проверил, максимум до 36-го элемента доходило. И, подумав, что у правильного решения сложность меньше, а в таком же все так же не умеют писать хаки, как и я, я весело заработал -50 очков на челленджах %)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        правильная сложость. надо было по памяти еще сжать :)
        • 13 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
          Тьфу, ну да, можно же было сумму не хранить, хранить собственно среднее арифметическое и пересчитывать...
          Не представляю, как это сделать. Придётся посмотреть у других и/или подумать.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            В каком порядке у тебя шли размерности?
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Сначала - в каком попало, потом - в каком надо, но это всё равно не спасло.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Решение, которое зашло у меня:
                DP(текущий индекс, текущая сумма, значение на предыдущей позиции, флаг[true/false] - меньше ли последнее значения своего предшественника)
                Внутри цикл от 0 до 40 и все решение в целых. Ясен пень, что даблы там не нужны и вполне могут замедлить работу. Как избавиться от них, думаю, знаешь :)
            • 13 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
              Думаю есть намного более адекватные оптимизации. Например не переходить из состояния до которого 0 путей(а таких казалось бы много), цикл по сумме до 40*i, а не 40*n и вычитание вместо взятия модуля. Ибо единственная операция которая приводит к переполнению модуля - сложение двух чисел меньших модуля.

              UPD: С этими тремя оптимизациями работает 220 мс на 40 -1. С 50*1610*50*2 памяти. На С++.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится
                На java неправильный порядок индексов может замедлить программу в 20 раз, т.к. многомереный массив там - массив массивов и на каждый instance массива есть overhead.
                Остальные оптимизации у меня тоже были, кстати сложение с if'ом работает даже немного медленнее взятия остатка (на макстесте)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Интересно... Почему же медленнее сложение. Казалось бы % значительно медленнее. Впрочем может это засчет другого языка.
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Теоретически условный оператор может обламывать speculative evaluation процессора, может в этом дело
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Обидно. 500 не прошла именно из-за неверного порядка индексов=( Причем вердикт: java.lang.OutOfMemoryError: Java heap space
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Первые две я и так делал. А вот сейчас добавил третью (минус вместо модуля) - прошло!
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Там ведь можно считать внутри динамы результат в 64-битную, а потом, после цикла, один раз взять по модулю.
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    (Только если в 64-битную unsigned, конечно.) Не факт, кстати, что это быстрее, - у них процессоры 32-битные.
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится +3 Проголосовать: не нравится
                      Нафига там unsigned? :) Там максимум будет 40 * (109 + 7).
                    • 13 лет назад, # ^ |
                      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
                      "у них процессоры 32-битные".
                      Любопытно, Вы тут никакое слово не перепутали?
                      P.S. Просто процессоры могут быть и 128-разрядные, а компиляторы генерировать код для системы команд 32-разрядного процессора.
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится +5 Проголосовать: не нравится
                        Вполне мог перепутать, я же блондинка, даже ноутбук под цвет ботинок выбирал :)
                        А Вы поняли, что имелось в виду? Как это по-нормальному-то сказать?
                        • 13 лет назад, # ^ |
                          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                          Пояснил выше. А есть какой-нибудь свободный компилятор С++, который 64-разрядность процессора использует?
                          К java все это, конечно, не относится.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              А в каком правильно? От большего к меньшему ([max]...[min])? По идее в этом случае прыжки по памяти будут меньше, однако я еще ни разу не ловил на этом TL (C++). Но страшных историй наслышан :)
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                От меньшего к большему, но для c++ это не критично, только для java, там каждый массив - объект
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  На C++ главное - чтобы вложение циклов было в том же порядке, в котором и размерности массива объявлены. Соответственно, от меньшего к большему (впервые слышу, кстати, возможно, это действительно не сильно ускоряет) - это уже второй приоритет, если ещё можно что-то переставить.
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Будем хранить от меньшего к большему. Тогда, небольшое изменение меньшего параметра повлечет за собой большой "прыжок" по памяти (ячейки dp[2][млн] и dp[3][млн] находятся "дальше", чем dp[млн][2], dp[млн][3]). Разве не так?
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Ещё, если массив большой (целиком не влезает в кэш) и одна из внутренних размерностей (то есть не первая) — большая степень двойки, то очень вероятны проблемы с кэшом, из-за которых будет работать медленнее в несколько раз, чем могло бы.

                На сборах в Петрозаводске я видел решение, которое работало 10 секунд с массивом a[MUCH][256] и 2 секунды с массивом a[MUCH][300].
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Я сталкивался с задачей в которой решение с массивом z[1 << N] работает в 10 раз дольше чем с массивом z[(1 << N) + 3]
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Вероятно, там были другие большие массивы, кроме этого. Иначе непонятно, почему так.
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится +8 Проголосовать: не нравится
                      ____________________________________________
                      http://igoro.com/archive/gallery-of-processor-cache-effects/
                      see example 5
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится 0 Проголосовать: не нравится
                        ____________________________________________
                        Дык, да. Но если бы работало для 1 << N и не работало для 1 << N + 3, это бы означало на картинке дырку в вертикальной прямой в точке, например, (step = 512, array length = 16M + 3). А она сплошная.
                        • 13 лет назад, # ^ |
                          Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
                          _______________________________
                          Ну дык работает то решение (1<<N)+3, а не работает (1<<N) )

                          UPD. А, кажется понял о чем ты)) Картинка показывает немного другое - там не особо важно какой размер массива, там важно через какие промежутки мы обращаемся к массиву. Т.е. грубо говоря возьмем массив T[x][256] и пройдемся по всем T[i][0] - это то же самое, что посмотреть каждый 256-й элемент в массиве длиной x*256 (о чем и говорит картинка).
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Как вариант не сжимать память, а хранить дополнительно для каждого окончания последовательности вектор достижимых сумм и идти только по ним. Итого - 0,35с.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Так для не достижимых сум количество вариантов - ноль. Поставив один if мы экономим 40 вариантов перехода.

            Хранение вектора достижимых оптимизирует это же, но оно более сложное.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да, наверное всё так, проверка на недостижимость должна выигрывать гораздо больше чем просто сжатие по памяти :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Короче, не нравятся мне такие задачи. Когда для прохождения нужна оптимизация в ~1.5 раза... вроде бы мы здесь в алгоритмах соревнуемся, а не в хаках... Автору можно дать совет впредь писать свои решения чуть более говнисто - и ограничения подгонять соответственно =)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          У меня на java 300мс. Сжатие по памяти серьезно помогает, вся структура 40х1600х2х2 впихивается в хэш, в отличие х40
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Задача вроде норм. По крайней мере мне ничего хачить не пришлось. Без всяких сжатий и прочего прошла. Единственное я модули не брал, но вот говорят что это вообще ничего не меняет
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Может из-за того что внутри динамики ты модули брал. Можно вычитаниями это быстрее
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Специально проверял - время работы изменяется не сильно, видать не модуль тут самая дорогостоящая операция.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Может кстати обращение к памяти. Может указателем ходить будет быстрее. (инкая его каждый раз)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Там нужно еще чуть сократить. Например, перебор суммы на каждом шаге. Он макс. равен i*40, где i номер массива - тогда зайдет.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    У меня решение со сложностью 40^5, работает у них ~секунду на макстесте
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
расскажите пожалуйста решение 500 div 1 
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Динамика по кол-ву элементов в последовательности, последнему элементу, сумме элементов и тому был ли последний меньше предпоследнего.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Динамика по (номер элемента, сумма всех предидущих, что стоит на преидущей позиции, длина наибольшей убывающей последовательности включающей последний элемент)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А зачем нужна длина наибольшей убывающей последовательности включающей последний элемент? Кажется достаточно только того является ли предпоследний больше последнего.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      спасибо
      ну я дал конечно
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А у меня была немножко другая динамика (номер элемента, сумма всех предыдущих, предпоследний, последний). В итоге получалось решение примерно за 40^6, и сделав пару оптимизаций оно уложилось в ТЛ :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Прощай, таргет
Из-за каких тупняков я очень долго писал 500. Сначала сделал динамику с мемоизацией, но почему то на массив (который стопудово должен влезать в память) у меня сервер по очереди ругался либо мемори лимитом, либо тайм лимитом (при том, что я уже оставил только инициализацию массива)
Загадка
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тебе прощай таргет а мне -4 балла. офигеть, я теперь не могу занимать 40-ые места! :(
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я согласен на -4 балла за этот контест :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
как посмотреть тесты к задаче на TC ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Правая кнопка по нику - History и смотришь где упало.
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
крутая в этот раз 250! нужно либо подумать и чуть-чуть написать, либо не думать и писать динамику

широкий выбор, высокое качество... =)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Думать у меня получается хуже, чем думать динамику :) Я вообще удивился, что многие люди сидели долго без 250 задачи, а потом сдавали какую-то кучу ификов в перемешку с циклами. Пишите вы эту динаму, да и все.
    В задаче 500 я пошел Ва-Банк :) Если бы не прошла самая тупая динама за 2*N4, то хотя бы попытался сдать ее быстро :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      и каков результат выступления?) кстати, какой у тебя ник на TC?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        В день, когда я первый раз стал синим, я боролся с тобой в руме второго дивизиона за первое место :)
        Можешь проверить :) Мы даже поговорили в чате.
        Что касается результатов, то на TopCoder'е я смотрюсь как-то печально. Не получается у меня там решать хорошо.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится
          и ты злобно забедил =)

          я не считаю TC объективным показателем уровня участника, там достаточно своеобразные задачи (например, в большей половине раундов div-1 500-ые на динамику)

          так что печаль там - это фигня ;)
          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            А что можно считать показателем уровня ?
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Видимо, имеется в виду ACM, а самая близкая аппроксимация для него - Codeforces?
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                То есть чтобы уровень вырос можно просто попасть в хорошую команду ? Команда из скольких человек скрывается за ником Ferlon ?
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Ну вот и зачем Вы придираетесь к словам? Я верю, что Вы прекрасно поняли, что я имел в виду.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      у тебя N^5, зря я лез смотреть твоё решение
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Чем отличается Member SRM от обычного?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Member'ом.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится
      хорошо, что на русский хоть не перевёл :D
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      :) А если серьезно?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Авторам не платят деньги - в этом основное отличие.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, авторам вместо денег -- Member.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ах, так уже пошутили. Пичаль.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            даже не минуснешь Captain за кэпство после http://codeforces.com/blog/entry/1627#comment-30797 ! :)
            • 13 лет назад, # ^ |
                Проголосовать: нравится -7 Проголосовать: не нравится
              Конечно, минусовать капитана за кэпство как-то неправильно =)
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Но почему капитан - лейтенант? Флот? :-X
                • 13 лет назад, # ^ |
                    Проголосовать: нравится -8 Проголосовать: не нравится
                  Это был страшный слив, честно :-)
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    А история рейтинга утверждает обратное: скорее чуть раньше только был страшный вин :)
                    • 13 лет назад, # ^ |
                      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                      пора_уже_разобраться_с_далеко_вложенными_комментариями
                      Может прозвучать (и прозвучит) как оправдание, но это на самом деле не мой уровень) Все фейлы были обязательно в Aи B, остальные решаются внимательно :-)
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Кстати, давно хотел спросить, как сделать ссылку на человека?
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +1 Проголосовать: не нравится
                нужно скопировать его ник :)
                сам недавно догадался :)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +1 Проголосовать: не нравится
                  Спасибо, Kostroma :-)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Но это же не работает, если впоследствии у человека меняется цвет.
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    хм, а в положениях старых контестов цвета старые, но ссылки работают :)
                    надо узнать у Майка, как он это делает :)
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится +1 Проголосовать: не нравится
                      А_такими_наглыми_методами_я_делаю_мое_сообщение_читабельным

                      Да что тут узнавать, откройте окно кода и посмотрите, что вставляется в качестве сообщения. Просто копируется текущий HTML-код страницы.

                      С тем же успехом можно скопировать в сообщение любой форматированный элемент интерфейса, скажем:

                      4 часа назад, #
                         +2 
                      у petr'а новый максимум ))
            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Это меняет что-то только для авторов контеста. Им не платят что-ли.
13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
у petr'а новый максимум ))
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Еще 1 хороший матч - и будет новый рекорд ТС.


    • 13 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится
      хм разве максимум Петра != максимум тс? 
      О, как же я мог забыть об AcRush... :)) 

      Что касается 500 div 1 - я вообще не понимаю почему такой ажиотаж и много фейлов. В СРМ, к сожалению, поучаствовать не получилось, но на дорешивании вполне быстро написал ленивую динамику "в 4 строчки", со взятием модуля и вообще "не парясь" - прошло за 0.150 сек.... (http://pastebin.com/kh2GWgAf)

      Мне кажется, это повод подумать об отказе от явной табличной динамики, которая имела место у многих с размером кода в один экран, там где это возможно - так быстрее, красивее и багов меньше.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Как совет - посмотри на график и maxRating господина ACRush. Даже на Snarknews писали о его новом рекорде в свое время.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Изначально та задача, что была Div1 500 планировалась только как Div2 1000. Для Div1 500 автор предложил версию, где элементы последовательности могли быть от 0 до 100, а их количество до 50. В итоге эту версию зарубили, как слишком трудную, учитывая что и 1000 была сложновата. Предлагаю подумать над этой более сложной версией Div1 500.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А 1000 как решается?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    Рассмотрим три величины:
    F(i,j) - максимальная сумма при остановке на i-том бриллианте при условии, что еще можно сделать j ходов в лево-право.
    G+(sum,col) - максимум по таким F(i,j) что a[i].x=col и a[i].x+j=sum.
    G-(sum,col) - максимум по таким F(i,j) что a[i].x=col и W-a[i].x+j=sum.
     Будем заполнять табличку F в порядке по i по j. Будем делать переходы в F(i,j) только из таких типов состояний:
    F(i,j+1) - если мы как будто сделали больше ходов влево-вправо, мы ответ точно не улучшим.
    F(k,l): a[k].x+l = a[i].x+j,
    F(k,l):W-a[k].x+l=W-a[i].x+j
    Переход из этих трех состояний в наше соответствует переходом влево/вправо, влево по диагонали, вправо по диагонали. Таким образом, этими переходами можно симулировать проход по всей таблице.
    Если обсчитывать переход так, как я написал, то сложность кубическая.

    Между делом: зачем нужна табличка F? Если F(i,j)>=goalValue то мы можем обновить ответ значением a[i].y*timeY+(LR-j)*timeX. И минимум таких значений - ответ.

    А теперь заметим, что 
    F(k,l): a[k].x+l = a[i].x+j,
     - это максимум из G+(a[k].x+l,t), где t, номер колонны, левее или равен текущему ( то есть то все позиции вверх по диагонали влево от данной).
    Аналогично со вторым случаем, только там G-.

    Таким образом, можно хранить что-то ДО-подобное/Фенвико-подобное, позволяющее взять максимум на отрезке, чтобы найти значение F(i,j) и потом изменить значение в точке a[i].x+j на максимум из того, что было и F(i,j). Понятное дело, брильянты надо проходить в порядке сортировке по у, при равном - по х.

    Главная сложность - бриллианты на одной прямой. Для них надо сначала пройти слева направо обновляя значения, затем наоборот, справа налево, так как это единственный случай, когда может понадобиться идти не к брильянту, который лексикографически больше.
    ЗЫ, Вот за это честно говоря лучи ненависти). Задача же и так сложна, а эта проблема с брильянтами на одной прямой ее очень усложняет.(
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вот до G+ я догадался на контесте но дописать ее в код не успел, послал грязный TL-ный хак :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I enjoyed div 2 1000 (or div 1 500) .. nice problem.. :D
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Итого три динамы на контесте
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Это те, которые жадность, динамика и структуры данных?
    See the bright side:)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Привет, Игорь :) Я тоже думал, что там три динамики. После того, как началась Challenge Phase я очень удивился. Кроме второй задачи, динамику редко где можно было найти. Разве что в редких решениях 250-ой задачи и какие-то попытки запихать 1000-ую.
    Мне лично было гораздо проще написать две динамики, чем выдумывать какие-то жадности и переборы. Кому-то наоборот.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Кстати, мне в 250 тоже сразу пришла в голову динамика с хранением каких-то максимальных и минимальных значений. Но я не сообразил, почему это верно, и подумал, что вдруг это "фишковая" задача - все так и напишут, а потом будет весёлая челлендж-фаза. Вот поэтому взял и тупо в мясо раскатал все случаи. Хорошо ещё, мне ума хватает не пытаться валить всех подряд блайндами %)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Здорово, Паша) Ок, прочитав ответы я решил, что поторопился посмотреть на все как на динамику.