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

Автор AlexErofeev, 13 лет назад, По-русски
Только что закончился этап Открытого Кубка.
Предлагаю здесь обсудить задачи.


В частности, интересуют задачи A и B.
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Более конкретно интересует 27 тест в задаче А. Если кто знает в чем там фишанда, было бы интересно узнать.
13 лет назад, # |
Rev. 5   Проголосовать: нравится +21 Проголосовать: не нравится

B: 

Наблюдение 1:
Сначала в суффиксном массиве идут позиции 0-ов, затем позиции 1-ек.
Наблюдение 2:
Если в конце нашего числа стоят k нулей, а потом единица, то в начале нашего суфф массива будут числа n, n-1, .., n-k+1, а число n-k будет первой позицией среди позиций, которые начинаются с 1, в суффиксном массиве. (потому что это строка 100..0 - это мин лекс строка, начинающаяся с 1)
Решение:
Смотрим сколько чисел вида n, n-1, .. идут в начале суффмаса, находим, где начинаются единицы. Получаем возможный ответ. Осталось его проверить. Это можно сделать либо построив суффиксный массив возможного ответа, либо посчитать частичные суммы хешей, а затем проверить, что каждые два суффикса в порядке суффиксного массива действительно упорядочены (делаем БП, чтобы найти на сколько элементов двух суффиксов совпадают, сравниваем хэшами, смотрим первые несовпадающие символы)

А:
1). Строим выпуклую оболочку. Добавляем к ответу кол.-во точек на ней * кол.-во точек не на ней. (Это если мы исключим любую точку не на оболочке)
2). Берем все четные точки оболочки + все не точки оболочки, строим выпуклую оболочку этого набора. Тогда получается, что мы исключили из оригинальной ВО каждую нечетную точку и заменили чем-то, что бы было если бы мы убрали ее. (Понятно, что наборы точек, которые добавяться в ВО если мы удалим 1,3,..,2х-1 точку оболочки не пересекаются, потому что они лежат соответственно в треугольниках 0-1-2, 2-3-4, 3-4-5,..
Тогда мы знаем, что сумма добавленных точек равна сумме количества точек на новой ВО - количество четных точек из старой оболочки. Прибавляем к ответу сумму новых точек + количество точек, которые мы удалили (нечетные) * (размер старой выпуклой оболочки -1). (То есть, мы знаем, что для каждой удаленной нечетной размер оболочки уменьшится на 1, а для всех в сумме он еще и увеличится на новые добавленные точки).
3). Делаем абсолютно ту же процедуру для четных точек вместо нечетных.
4). Если всего точек нечетное число, то надо проделать такую же процедуру еще для одной точки (мы сделали на 3 и 4 шагу для к/2 и к/2 точек оболочки соответственно, где к - ее размер).
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

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

      Кстати, а как определить, в какие просмотры попадает каждая точка?


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

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

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

    B можно было вообще без проверок. Рассмотрим пару соседних элементов суффиксного массива. Пусть это суффиксы длины l0 и l1. Тогда посмотрим на суффиксы длины l0 - 1 и l1 - 1. Если l0 - 1 лежит в суффмассиве после l1 - 1, то первый символ l0 равен нулю, а первый символ второго - единице. Назовем такую позицию разбиением. Очевидно, что сначала в суффиксном массиве идут позиции нулей, потом - единиц. Тогда, найдем все разбиения. Если разбиение не единственно, то ответа нет. Но, если единственно, то ответ всегда есть. Вроде бы, понятно почему: нет противоречий. Строго доказательство сформулировать не могу. Те, кто еще так писал, можете объяснить?

    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Пусть алгоритм нашел ровно одно разбиение. Тогда очевидно, что если есть какая-то бинарная строка, для которой данная перестановка П является суффиксным массивом, то эта строка единственна, и мы ее уже знаем. Теперь покажем, что условия, которые проверил алгоритм, являются достаточными для того, чтобы это П действительно было суффиксным массивом.

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

      Так как это подпоследовательность исходной перестановки П, то первые символы суффиксов в ней тоже будут идти в пордке …0000111… Таким образом, по крайней мере по первым двум символам суффиксы отсортированы правильно.

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

      Вот. Надеюсь понятно, как это превратить в строгое доказательство.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите, пожалуйста, как решать задачу про простые числа, где их на две группы надо разбить, или ошибку объясните. Написали ДП + ДА, не зашло.
ДП :  
a[1] = 1, b[1] = 2, a[2] = 2, b[2] = 3;
a[i] = min(a[i-2]*p[i], b[i-2]*p[i-1]);
b[i] = max(a[i-2]*p[i], b[i-2]*p[i-1]);
p  -  заранее посчитанный массив простых чисел.
Ответом будет a[n]. 

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

    Мы заранее просчитали все значения, а потом их просто выводили. Просчитывали за О(2^n), программа выполнялась где-то 10-15 минут.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Аа, ну да, забыли мы про это. А длинку писали?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      За 2^n - это как-то по-умному в порядке кодов Грея чтобы каждый раз менять всего 1 бит или что? Потому что у меня было .. несколько дольше:)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Я за 2^n написал обыкновенную рекурсию.
        solve(id,mask,double a, double b)
        id - номер простого, которое мы будем сейчас размещать.
        mask - какие простые попали в первую группу
         1) если id==n и a<b, то мы смотрим, улучшили ли мы результат, и если да, то запоминаем новое b-a и новую маску
        2) Иначе пытаемся положить простое id-тое простое в первую группу и во вторую группу.
        solve(id+1,mask|(1<<id),a*p[id],b);
        solve(id+1,mask,a,b*p[id]);
        При переборе можно спокойно забыть о длинке. Даблов хватает. А вот ответ по маске уже придется восстанавливать ею
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          уверен что хватает? там вроде больше чем 18-20 знаков было, а даблы вроде больше и не хранят...

          да и сложность получается не O(2^n), а O(2^n*n) ибо ты ещё углубляешься в рекурсию...
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            А больше в этой задаче для нахождения правильного набора и не надо.

            А сложность всё-таки O(2n) - от углубления в рекурсию лишнего n вроде не должно появиться :)

            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              специально залез посмотрел:
              177792163538134124432895
              24 символа, разве дабл возьмет столько?

              а n всё таки думаю появляется, с делящей его константой, но появляется...
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Конечно возьмёт. Куда он денется?

                Только отдаст он 177792163538134124429312, а не столько, сколько взял.

                Но нам и этого хватит, чтобы максимум найти.

                Про n: Ну откуда оно появляется?

                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  =============================================
                  т.е. ответ ищем в даблах, а уже в конце считаем длинкой точно?

                  по поводу n да, думал что угулублясь и возвращаюсь получится что-то... но нет...
                  • 13 лет назад, # ^ |
                    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

                    =======================================

                    Да, в даблах.

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

                    Там (в даблах) вроде только четыре последних числа неточно считаются.

                    • 13 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      ===================================
                      классные приемчик - "ручная длинка", правда применима только при небольших входных объемах информации
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится +1 Проголосовать: не нравится
                      ======================================
                      Не проще ли вместо таких извращенств написать на Java с BigInteger ? :)
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится +6 Проголосовать: не нравится

                        ============================================

                        Иногда, когда пишу что-то на Java с BigInteger, кажется, что вся Java - это одно большое "извращенство" :)

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

                        ================

                        ну кто на яве, кто на питоне извращался, а кто вот так) и вообще эта задача сплошное извращение, над ней извращались кто как мог

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

      double

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      10-15 минут? Круто у нас под час генерилось...
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        У нас в Петрозаводске 3 часа генерилось :)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А в 64-битном компиляторе G++, если использовать 128-битные целые числа, то перебор за две с половиной секунды генерит все ответы.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если перебирать числа в порядке убывания, а не возрастания, и вставить отсечение по ответу (если произведение того, что мы нашли, больше половины, то выйти, и если всем оставшимся нельзя улучшить полученный ответ, то выйти), то работает секунд 8. Плюс вместо произведения чисел я считал сумму их логарифмов и не думал про то, что числа не влезают в double (но для восстановления нужна была маска).
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      повтор

  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Я просто написал перебор всех подмасок (2^30 * 30 * BigInteger), запустил в районе 0:20 и сдал в районе 2:40 константы:Р
    Но мне кажется, что тут надо было написать просто рюкзак + meet in the middle, разбив все на две части так, чтобы в каждой произведение простых не превышало 2^64, и решить где-то приблизительно за (2^10+2^20)log(2^20) рюкзаком и или константы или оно и вовсе проходит без них.
    • 13 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

      у нас перекалк работал где-то 5 минут
      ми искали первое число как максимальное число не больше квадратного корня с произведения первых N простых чисел, использовали даблом для произведений, поддерживая при етом маску использованых чисел
      потом просто по маске искали ответ, длинкой

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Можно же вроде за , ведь одно из множеств меньше 15. А это уже совсем немного.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я написал meet-in-the-middle + бинпоиск - все ответы сгенерились за пару секунд, однако на написание и придумывание потратилось не меньше часа, так что, наверное, оптимальнее было написать очевидный перебор.

      Решение такое (рассмотрим сразу для случая n = 30).
      Разбиваем на 2 части произвольным образом - например, берем первые 15 чисел в одну половину и остальные 15 в другую. Перебираем все возможные произведения в каждой половине и складываем в массив, а затем сортируем (2 * (2 ^ 15) * (1 + log(2 ^ 15)) ~= 2 ^ 20. Дальше перебираем все числа из первой половины и для каждого бин. поиском находим самое подходящее число во второй половине ((2 ^ 15) * log(2 ^ 15) ~= 2 ^ 19).

      Итого решение работает 2^20 * скорость операций с BigInteger.

      P. S. Не понял, как в этой задаче использовать рюкзак. Можно пояснить?
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Хм. То есть, в оптимальном ответе кол-во сомножителей в обеих частях не превышает ? А почему?

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Мы как раз находим ту часть в которой сомножителей не больше n/2 . Смысла находить в одной части больше n/2 множителей нет, т.к. во второй части их будет меньше n/2 и оптимальнее искать будет вторую часть.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я немного накосячил в объяснении. Дело в том, что моя команда писала это Гран-При на сборах в Ижевске неделю назад, поэтому я забыл детали. Теперь вспомнил.

          Нужно хранить в два раза больше информации.
          Рассмотрим, как считаем числа для первой половины (первые 15 штук).
          Пробегаемся по всем маскам (2 ^ 15): когда зафиксировали маску, перемножаем только те простые числа, которым в маске соответствует единица. Однако еще удобно посчитать другое число - произведение тех простых, которым в маске соответствует ноль.

          Таким образом, есть два массива пар бигинтов - A[2^15] и B[2^15].
          Отсортировали их по неубыванию по первому числу. Понятно, что в таком случае вторые числа будут отсортированы по невозрастанию.

          Пусть зафиксировали индекс i в первом массиве.
          Мы хотим найти такое j во втором массиве, что
          F(j) = (A[i][0] * B[j][0] - A[i][1] * B[j][1])
          принимает минимальное значение. Как мы уже знаем, если j возрастает, то B[j][0] тоже возрастает, а B[j][1] наоборот убывает. А[i][0] и A[i][1] фиксированы, поэтому с возрастанием j функция F(j) также возрастает. Раз функция монотонная, применим бинпоиск. В ответ мы запишем A[i][0] * B[j][0], такое что F(i, j) минимальна (тут уже i не фиксирована). В первом множителе перемножено до n/2 простых, во втором тоже, так что количество сомножителей в ответе может превышать n/2.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну, это и есть задача о рюкзаке: нам же надо набрать величин как можно ближе по произведению к корню из произведения всех простых. А чтобы делать это не втупую за 2^30, используется М-и-М.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто может пояснить причину таких малых ограничений в J? Там же вроде бы от порядка ничего не зависит? То есть можно для каждой територии посчитать минимальное число юнитов, необходимое для захвата, и получаемое количество очков, а затем просто перебрать все маски территорий с проверкой, что область связная и включает границу, нет?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
    Именно так. Только вот масок там C(30,10), повышать дальше уж некуда).
13 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
Динамическое-то решение кто-нибудь писал?
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Ребята рассказывали, что по B проходила проверка строки сортировкой суффиксов, обрезанные по 256 символов...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Киньте ссылку на условия, пожалуйста.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как G решалась?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Обычная Дейкстра.
    • 13 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится
      да вроде это потоки, насколько я понял поток + чуть динамики... честно говоря потоков не знаю, так что утверждать не могу
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я её сдал в дорешивании обычной Дейкстрой.
        Веса ребер - w[i]
        Граф - неориентированный.
        Ищем кратчайшее расстояние от 1 до n вершины. Если оно меньше C, то выводим Unfair и востанавливаем ответ, иначе - Fair.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится
        Гы-гы. Станкевич на разборе сказал, что на то и рассчитывал, что люди будут думать над задачей на потоки. Даже ограничения специально маленькие, чтобы пострашнее было. Ну, там, строго говоря, конечно, действительно надо найти поток минимального веса, но поток величины 1. Да, пожалуй, если бы в условии задачи была картинка *trollface*, её бы сдало больше народу :)
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Первая мысль которая возникает при прочтении задачи - макс. поток. И, вы правы, ограничения на это намекают. Немного подумав, я решил отправить в дорешивании Дейкстру не сильно надеясь на ОК. Я был очень удивлён:)

          • 13 лет назад, # ^ |
              Проголосовать: нравится -15 Проголосовать: не нравится
            Первая мысль, которая возникает при чтении ЛЮБОЙ задачи - правильно понять условие.
        • 13 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          но разве там всегда выгоден поток величины 1 или просто этого условия достаточно ???!

          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Вам ведь даже уже объяснили почему...
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            По идее стоимость каждого следующего увеличивающего пути будет не меньше предыдущего, поэтому смысла делать минкост нет.
            У меня была другая проблема, не увидел в условии, что можно выбирать направление у трубы, поэтому не добавлял обратных ребер и хапнул 10 бревен. Даже писал минкост, но видимо для того чтобы убедиться в том, что поток не нужен.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Кто-нибудь, расскажите, пожалуйста, как решалась задача I (про социальную сеть и френдлист).
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Будем поддерживать кол-ва сообщений написанных к текущему моменту каждым из пользователей и set друзей каждого пользователя. Когда добавляем какого-нибудь пользователя A в друзья пользователю B отнимем от ответа для A текущее кол-во сообщений пользователя B. Когда будем удалять пользователя A из друзей пользователя B, прибавим к ответу для A текущее количество сообщений у пользователя B. В конце удалим всех друзей у всех пользователей и посчитаем ответы.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        классно решение, а мы в мап кидали и запоминали сколько сообщений было у друга в момент добавления, а при удалении вычисляли сколько добавилось за то время...
      • 13 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится
        действительно классное решение, но думаю большинство решило, так, как описал yarrr или как-то подобно, до такого красивого решения, как у тебя, непросто додуматься сходу
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Для каждого пользователя запишем действия, связанные с ним в вектор. Действия по добавлению и удалению разобьём на два, т.к. они, связаны с двумя пользователями.

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

      Заведем массивы when[n], pluses[2*m] и вектор добавленных.

      Идём по действиям пользователя. В pluses[t] мы будем поддерживать количество сообщений, которые запостил пользователь:
      pluses[t] = pluses[t - 1]
      pluses[t] = pluses[t - 1] + 1, если тек. действие -- пост сообщения.

      В when[p] будем поддерживать момент времени, когда мы добавили пользователя.
      when[p] = curTime, если тек. действие -- добавление пользователя.

      При удалении, нам нужно для этого пользователя добавить к ответу:
      pluses[curTime] - pluses[when[p]].

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

      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        +1) точь-в-точь такое решение
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Понятно. Спасибо большое за столь понятный, содержательный ответ и код.
        Решение довольно простое и понятное. Я же думал над какой-нибудь крутой структурой:)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ага, мы не сильно задумываясь написали декартово дерево.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            я тоже хотел писать декартово дерево, но мой сокомандник меня переубедил, что он придумал что-то проще пищущееся
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Мы так же вычитали кол-во сообщений при добавлени и прибавляли при удалении. Но в конце, чтобы не было nlogn, прошли по списку в обратном порядке, заменяя + на - и наоборот. Потом ответы надо поделить на 2.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    надо проверить только тот случай когда поток равен 1... т.е. найти минимальный путь и его проверить, т.к. все последующие увеличения потока будут увеличивать стоимость в больше или столько же чем в первый раз, т.е. f(a) * c будет расти медленней чем сумма используемых wi
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      спасибо за объяснение, задача была расчитана на "лоха" ((( и я повелся(
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Для ясности лучше написать, что для следующего потока нужно еще один путь из 1й в Ную вершину(те ребра что уже есть ничего не дадут), который будет больше-равен 1го, то есть только ухудшит ситуацию.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Обычное моделирование
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать F? Что-то не могу найти зацепку, чтобы написать динамику или оптимизированный брутфорс.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    при добавлении очередного 0/1 надо проверить что условие по прежнему выполняется, т.е. надо найти все позиции на которые добавленая 0/1 влияет и если она была ещё хорошей то превратить её в плохую... исходник пока не буду кидать, полезней будет...
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Т.е. перебор с начала? Просто я написал перебор с конца слова, но видимо отсечений больше, если перебирать с начала.
      • 13 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

        А причина в том, что таких строк всего 384 (всех возможных длин) и существуют они до длины 37.

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А я специально писал на С++, все строки и массивы заменил битовыми масками для максимальной быстроты. Но тупанул от усталости в концовке с перебором с конца :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        хм, наверное и больше... но навен 
        и с конца можно... ведь если есть окончание строки, то для всех последних позиций ты точно можешь сказать будут они хорошие или плохие... даже не могу сказать что будет лучше...
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Для последних я могу, но сумма позиций будет постоянно меняться у последних чисел, в итоге там получается отсечение в стиле - "даже если все оставшиеся позиции я сделаю хорошими и мне все равно не хватит для ответа, то return"
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Полконтеста пытался понять, почему моя J получает WA4 - после контеста оказалось, что в слове "defence" была опечатка :)


13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мы в петрозаводске в команде со сборной солянкой умудрились 8 сдать :) В D вообще такой бред пропихнули...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В D правильное решение - на каждом шаге максимизировать максимальный суммарный размер обрабатываемых поддеревьев
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Интересно было услышать поподробнее :)
    Как и про С и E :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Я вообще считаю, что некоторым отдельным составителям контестов нужно больше внимания уделять придумыванию тестов против тупых решений, а то уже не первый раз на контесте Станкевича огромное количество народа успешно запихивает какую-нибудь невообразимую ботву в некоторых задачах.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А Вы сами много качественных контестов/задач сделали ?

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

      Я не оправдываю автора, но и наезды делать думаю, что не стоит.
13 лет назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

E. Elections (Division 1 Only!)


У нас решение вроде как правильно, но ВА12. Идея вроде как очевидная - динамическое программирование. Суть в том что можно перебрать значение A, оно будет не больше чем s + 50, так как сумма mi ≤ 50. Затем считается динамика fi, j, k, i - количество обработанных партий, j - сколько людей уже взяли, k - сумма выбранных людей по параметру a. Если писать динамику вперед, то получаем, что из fi, j, k можем перейти в fi + 1, j + x, k + a(i, x), где 0 ≤ x и j + x ≤ s и k + a(i, x) ≤ A с увеличение на |a(i, x) / A - vi / V| или в целых числах |a(i, x) * V - vi * A| (a(i, x) это значение ai если я выбрал из i партии x человек). Ответ для нашего A будет находится в fn, s, A

Вот мое решение (перебор значение A я делал как 4 параметр в дп)... кто разобрался или решил её буду очень признателен, если сообщите (или лучше намекнете) мне в чем баг...

UPD.
Ответ для нашего A будет  fn, s, A / (A * V).
Также подправил своё решение, но по прежнему ва12...

UPD.
Сделал INF поменьше и условия в конце стали проще...

UPD
Немного не так понял условие, перефразировал по своему - в моем решение нельзя было выбрать ai одним из тех, который отказывался из i-ой партии, а идея в принципе правильная. Решение подправил. Большое спасибо туристу.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Леша, тебе не кажется, что ты ошибочно целевую функцию считаешь ?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      да, кажется, там надо ещё делить на A * V... но так как V одинаково для всех, то только на A, но исправил... отправил... ВА12... сейчас заменю исходник...