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

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

Здравствуй, сообщество Codeforces, и с наступающим Новым Годом!

Прошу у вас помощи по одной интересной задачке. У нас есть массив чисел и запросы вида "l r k". Запрос "l r k" означает "найти k-тую минимальную сумму подпоследовательностей на отрезке от l до r. Возможно ли решить эту задачу за полиномиальное время, и, если возможно, то как?

Заранее спасибо!

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

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

И вас с наступающим.

Что такое "k-я минимальная сумма"?

Откуда задача?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Я не уверен встречалась ли где-либо такая задача, её идея возникла в процессе придумывания задач для одного локального контеста. Идею мы придумали, а вот решить не смогли)

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Если имеются в виду суммы на подотрезках, то, очевидно, можно. Просто за квадрат выписать все суммы а потом nth_element. Однако если имеются в виду суммы подпоследовательностей, то, наверное, нет. Их экспоненциальное количество, я сомневаюсь, что можно найти К-ую в этом случае.

»
11 лет назад, # |
Rev. 4   Проголосовать: нравится -49 Проголосовать: не нравится

Здравствуйте !!! Где ошибка на мой код!! можете говоритъ ??? Задача(http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=256&chapterid=166#1) мой код (http://mirror.codeforces.com/contest/376/submission/5546624)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    Продаю гараж! Обращаться в ЛС.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    Ну вам же дан тест и вердикт.

    Если ошибка на первом тесте (из примера), а у вас входные и выходные данные совпадают с теми, что в условии, то проблема не в решении. А, например, в вводе-выводе. Обычно это проблемы с именами файлов (или тому, что надо или не надо читать из файла). У вас именно такая проблема.

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

      Кажется, стоило ему на английском отвечать. Тут явно GT :)

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

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Но это не значит, что такую задачу давать нельзя. Для всего массива k-ую сумму можно найти за O(N * SUM), где SUM — сумма всех элементов. Сначала предподсчитываем сколько существует подмножеств сумма элементов в которых равна ровно х, где . Потом находим значение k-ой суммы и восстанавливаем ответ.

      В ограничениях 1 ≤ N ≤ 50, 0 ≤ Ai ≤ 100 вполне можно давать.

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

      Подпоследовательности, а не подстроки. Надо мне читать внимательнее.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -62 Проголосовать: не нравится

В первой правке я серьезно погорячился.

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

    Да вы, сударь, вообще офигели? Грамотным русским языком человек спрашивает как решить весьма чётко поставленную задачу (найти k-ую по величине среди сумм подпоследовательностей на отрезке от l до r в массиве), а вы ещё выделываться изволите?

    А я ещё думал, не слишком ли я резкий комментарий написал в вашем предыдущем посте...

    UPD: Говорят, текст поста исходно был другим, тогда прошу прощения за наезд. Надо бы добавить функционал истории правок постов, а то действительно могут случаться недоразумения.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -32 Проголосовать: не нравится

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится -24 Проголосовать: не нравится

        Тут должна быть картинка — Узбагойся), но у меня не получилось

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +12 Проголосовать: не нравится

          Лучше бы не говорил, что там должно быть :\

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

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится -7 Проголосовать: не нравится

        Тогда другое дело. Закапываю топор =) Как-то это неправильно, что править посты можно, а смотреть историю для них — нельзя.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится

      Может быть, меня вообще стоит за мои ошибки казнить, чтобы впредь такого не было? В чем смысл нападать на человека, без Вашего участия признавшего свою неправоту?

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

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

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

Хм... Довольно таки похоже на недавнюю задачу (https://mirror.codeforces.com/contest/1196/problem/F).

Прошу поделиться мыслями насчет решения, интересно).