Блог пользователя ant.ermilov

Автор ant.ermilov, 12 лет назад, По-русски

Сегодня в 20:00 по Москве будет сабж продолжительностью 2.5 часа.
Допускаются все, кто вышел из квала, но ещё не прошёл в раунд 2.
В раунд 2 выходят топ1000 участников.

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

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

Как решать С large?

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

    Можно понять что ограничение 500 на самом деле это просто запутывание. В массиве можно оставить только 46 наименьших а дальше meet-in-the-middle.

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

      Прикольно. А не долго получается, как я понимаю у тебя 3^23 на log3^23 ?

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

        Поэтому я и не сдал. На хорошем компе с хешмепами может и пройдёт.

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

          Тут же еще 3^23 long long надо хранить. У меня прошло когда рассматривал 28 наименьших.

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

      А что если первые 46 чисел будут такие: 1 2 4 8 16....?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        2^45 > 10^13
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        На самом деле можно даже не наименьшие брать а любые и все равно получается 2^46 > 46 * 10^12

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

      Как писать meet-in-the-middle тут? Хотел просто посмотреть решение, но homo_sapiens не нашелся.

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

        Там хендл не может содержать подчеркивание, поэтому точка. На самом деле я её не сдал потому что это медленно, надо еще немного подхачить

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

      А можно пояснить почему надо брать только 46 наименьших(любых) чисел?

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

        Максимальная их сумма: 46*1e12, кол-во подмножеств: 2^46, далее приницп Дирихле

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

    Просто генерируем рэндомный вектор из 10 чисел из набора и так до тех пор, пока не найдем две одинаковые суммы. Я зафейлил эту задачу, считывал числа как int :) Но, когда заметил — оутпут на large генерирует где-то за полторы минуты.

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

      Т.е. размер каждого вектора из ответа не превосходит 10?

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

        Я генерировал ровно по 10 элементов. В среднем нужно было около двух миллионов итераций. Можно сделать оценку, почему это должно работать. Это как парадокс дней рождения — с какой вероятностью среди случайных чисел найдутся два одинаковых.

        В целом, сочетаний из 500 по 10 порядка 1021, а максимальная сумма 10 чисел лишь 1013. Понятно, что совпадений очень много.

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

        Даже шести

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

    У меня зашла такая байда: генерим около 10^7 рандомных подмножеств из первых 250 чисел и запихиваем полученные суммы в хэш-таблицу. Потом рандомно выбираем подмножества из других 250 чисел, пока не найдем с какой нить суммой, что есть в хэш-таблице.

    Ну, какой нить механизм восстановления подмножеств по сумме придумать не сложно. Я, например, сохранял 40000 случайных перестановок в массивчиках, а в хэш-таблицу складывал суммы по всем префиксам вместе с номером перестановки.

    Оно искало ответы чуть больше 5 минут.

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

    Я делал так: возьмём два простых числа p и q, p чуть меньше 2^20, q чуть меньше 2^25. Разобьём исходный массив на 25, по 20 элементов в каждом. В каждом таком маленьком массиве найдутся две одинаковые суммы по модулю p. Получаем массив из 25 пар. Посмотрим теперь на них по модулю q. Посчитаем 2^25 сумм (из каждой пары берём одно число). Получим две одинаковые по модулю q. Ясно, что эти суммы совпадают по модулю pq. pq несколько меньше, чем 500 * 10^12, но и этого хватает.

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

    А я генерировал в порядке возрастания все возможные суммы и ждал пока повториться хоть одна — за минуту все 10 тестов успело сделать :)

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

    Моё решение (см. комментарий ниже) отработало меньше чем за секунду.

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

    Я тоже довольно долго думал над этой задачей, и в итоге пришел к решению. Понятно, что из 48 чисел есть 2^48 возможных подмножеств, а их максимальная сумма 48*10^12 т.е. подмножеств в несколько раз больше(в 5.6 раз), чем максимальная сумма. Я рандомно перемешал массив, для первых 24 чисел сгенерил всевозможные маски, посортил по сумме пары (сумма, маска), для чисел с 25-ое по 48-ое проделал тоже самое. теперь генерим случайно два индекса в обоих массивах, и пытаемся двумя указателями найти эту сумму в массивах, если нашли и индексы не совпали, то мы молодцы, иначе снова генерим индексы. Такое решение у меня зафейлилось на чем-то, я успел отдебажить и закончить тесты до окончания времени, время работы было около минуты, у меня 4гб оперативы на ноуте, прога должна была жрать около гига, но все влезло. Интересно было почитать другие варианты решений, потому привёл свой.

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

Вопрос снят

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

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

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

    может залазил туда, где нельзя залезть(типа места мало, но сильно выше уровня моря). А вообще проще было это тудаже внутрь дейкстры пихнуть

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

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

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

      Так я это вроде учитываю — пихаю начальные вершины в очередь и пока она не пуста пытаюсь улучшить время до всех соседей (учитывая глубину/время прихода/etc), улучшил — добавил в очередь. Должно же работать.

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

а есть что нибудь типа дорешки? а то я кажеться у себя нашла ну ооочень обидную багу в В =(

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

Я решал C таким образом: запускал рюкзак до двух миллионов, если ответ не находился, то сортировал числа и переходил к попарным разностям (если числа были i1, i2, ..., in, то новые числа будут i2 - i1, i4 - i3, ..., ) и пытался ещё раз, так повторял, пока не находил ответ. Как доказать, что это работает, я не знаю, но работает достаточно быстро.

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

    Мне сейчас вспомнилось Ваше решение задачи про разбиение гиперпространства гиперплоскостью (Петрозаводск, контест MIT). Как у Вас получается постоянно придумывать решения из серии "а оно ведь работает"?

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

      Не знаю. Наверное, мой мозг работает по такому же принципу.

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

      Кстати, если я правильно понимаю, о какой задачке из Петрозаводска вы говорите, то это — "построить линейный классификатор, который не ошибается на выборке, при условии, что выборка линейно разделима". Кажется, они написали что-то вроде градиентного спуска для вектора весов. Так вот, есть теорема Новикова(http://www.machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9D%D0%BE%D0%B2%D0%B8%D0%BA%D0%BE%D0%B2%D0%B0) о том, что если взять правильный шаг для градиентного спуска(правило Хебба), то процесс сойдется и, более того, за конечное число шагов. Это я всё к тому, что, кажется, правильность решения в Петрозаводске все пытались объяснить слабыми тестами, что на самом деле, видимо, неправда, и решение абсолютно честно получало AC.

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

Из раунда 1C. КАК?

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

    Отправил не тот исходник на маленькую задачу и вовремя об этом сообщил.