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

Opencup.ru: GP of Ural (XV Открытый чемпионат Урала по спортивному программированию)
Автор map, 15 лет назад, По-русски
Подскажите пожалуйста, как решать задачу С.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
За sqrt(n) посчитаем все делители числа, их будет не больше 150-200.

Затем, идём по буквам (n) и перебором всех делителей выбираем минимально возможную букву.
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Код решения на Джаве:
    → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Мы точно так же сделали, только без страшных слов функция Гранди. Ещё бы доказать неплохо было, почему такая тупая жадность - и проходит...
    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Как оказалось, она проходит,  не из-за ошибки авторов, а из-за того, что для данных ограничений всегда есть раскраска менее чем из 26 цветов. Они это специально проверили для всех n
      → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +10 Проголосовать: не нравится
        Это понятно, что раскраска всегда есть. Непонятно, почему можно жадно красить.
        → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +8 Проголосовать: не нравится
        "Как оказалось, она проходит,  не из-за ошибки авторов, а из-за того, что для данных ограничений всегда есть раскраска менее чем из 26 цветов. Они это специально проверили для всех n."
        Это не есть доказательство верности алгоритма.
        → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Бред. В общем случае это NP-полная задача, однако для данных ограничений ответ существует всегда и находится простейшим жадным алгоритмом. Для этого необходимо заведомо сгенерировать все делители числа n, и далее, крася по очередности людей в любой доступный цвет, мы перебираем всех его соседей (и левых и правых) и запрещаем им цвет, в который мы покрасили данного человека
    → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +29 Проголосовать: не нравится
    Мы решали по-другому. Выбираем наименьшее число k, на которое не делится n. Это число не больше 13. Разбиваем круг на две равные/почти равные половинки и в каждой половинке красим числа в один цвет с интервалом k. Для разных половинок используем разные цвета. Доказательство правильности такой раскраски тривиально.
    → Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится
НОК чисел до 13 больше максимального n
http://pastie.org/1828216
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Как же решается задача N о пикселях. Все свои тесты проходит. А выдаёт WA4 . Спасибо.
→ Ответить
  • 15 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится
    Разобьём круг на 4 сектора. Посчитаем для каждого сектора.

    Затем, разобъём сектор по x на r столбиков. Для каждого столбика нужно посчитать его высоту, она равна sqrt(r*r-i*i), где i = 0...r
    Если число целое, то тогда в этот столбик можно уместить ровно sqrt(r*r-i*i) пикселей, иначе sqrt(r*r-i*i) + 1.

    Код решения:

    Фигово я, короче, объясняю :)
    → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Задача N http://pastie.org/1828285
    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите, пожалуйста, как A (про книгу) и G (про аквариум) решались.
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится
    А - чтобы можно было поменять состояние i-й страницы надо чтобы i-1я страница была включена, а меньшие - выключены. Рекурсия с мемоизацией
    G - если нету нулей, то суммы противоположных уровней должны быть равны. Считается несложно. Дальше идет разбор случаев с 0, почитать эту и остальные сданные нами задачи можно здесь
    → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    G. Если нулей нет. Проверить все легко.
    a+c=b+d условие возможности.

    V=(a+c+b+d)/4*k^2=(a+c)/2*k^2
    Дальше интереснее.

    3 нуля. ambiguous

    2 нуля напротив- еррор
    2 нуля рядом ambiguous

    1 ноль. по 3 точкам проверим где должна быть четвертая.(а+с=б+д)
    Если больше 0 - error
    Иначе посчитаем объем так, как в первой части, заметим что некий тетраэдр с тремя прямыми углами при одной вершине, снизу от аквариума был посчитан зря(отсчитан с минусом в направленном объеме), добавим его.
    → Ответить
  • 15 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +8 Проголосовать: не нравится
    A - 
    напишем 000000
    из него можно сделать 1 ход.
    Далее на каждом шаге можно сделать 2 хода, один из них обратно, второй в какую-то ситуацию с измененным 1 битом.

    Закончится на 000001, из которой только ход назад

    Заметим, что это стандартный код Грея. Посчитаем номера позиций, данных в условии. Ответ: модуль разницы этих номеров.
    → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится
    A - это коды Грея http://pastie.org/1828286
    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите кто-нить Д. Спасибо.
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +5 Проголосовать: не нравится
    Раздвоим вершины. В получившемся двудольном графе найдем минимальное вершинное покрытие и дадим каждой вершине в нем k/2
    Доказывать не умею :)
    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Можно чуть поподробнее? Что в данном случае есть раздваиваемые вершины и откуда куда там пускать рёбра? Вопрос, возможно, идиотский, но мне вот, например, реально непонятно :-[
      → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +5 Проголосовать: не нравится
      Доказывается несложно. Надо только доказать, что для случая k = 1 всегда есть полуцелый оптимум. Это можно сделать с помощью потоковых соображений (задачу можно переформулировать в терминах стоимостного потока), либо непосредственно (в точке оптимума хотя бы n линейно независимых неравенств должны обратиться в равенства, нарисуем это как граф, чётных циклов там не бывает, нечётные циклы дают полуцелое решение - как-то так).
      → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Как переформулировать задачу в терминах потока?
        → Ответить
        • 15 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          Да, 3 месяца спустя суровый вопрос :)
          По идее там для каждой переменной надо создать 2 вершины, а каждое неравенство порождает 2 дуги. Т.к. для соединённых дугой остаточной сети вершин есть неравенство на потенциалы и стоимость дуги, то правильно расставив дуги можно получить те неравенства, которые требуются, точнее попробуйте продумать сами. Но вообще это довольно известное сведение, можно и загуглить.
          → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
скажите,пожалуйста,как решалась задача I.какие там такие фишки особенные?
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Никаких. Ищем все отрезки, на которых одна из палок падает и строим объединение. Чтобы левая палка упала влево, надо разрубить ее слева от первой стойки, или справа не дальше, чем длина от края до первой стойки. Чтобы левая палка упала вправо, ей надо упасть с какой-то стойки(т.е. палка будет касаться этой стойки, когда упадет). Тогда надо отступить от этой стойки как минимум на расстояние равное расстоянию от левого края до стойки (при этом нельзя разрубить правее следующей стойки). Справа также.
    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А как решалась F? Достаточно простое решение через суффиксный массив, мы так и не смогли запихать в ТЛ (хотя локально работало 4с).
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Нам помогла отсечка "если размер всех bucket'ов ровно 1, то прекратить делать итерации удваивания длины". Есть гипотеза, что на тестах, где приходится делать все итерации, получается меньше промахов кеша, поэтому эта отсечка спасает (ну или просто тесты не очень сильные).
    → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +13 Проголосовать: не нравится
    У нас было линейное решение:
    1. Отложим все допустимые правые части емэйлов в бор.
    2. Будем откладывать левые части также в бор. Для каждой допустимой левой части емэйла, пометим самую длинную правую часть для того же символа @, цветом (номером) равным вершине в этом левом боре.
    3. Теперь надо для каждой вершины правого бора подсчитать количество различных цветов в ее поддереве, и все это просуммировать. Это умеет делать алгоритм Хью.

    Пример:
    a.b@c.d
    b@c.de.
    @qq
    q@.q

    Правый бор:
    (root)
    |-c
    |  |-c.d
    |      |-c.de
    |-q
       |-qq

    Левый бор (строки записаны справа налево - в направлении от @):
    (root) [0]
    |-b [1]
    |  |-b.a  [2]
    |-q  [3]

    Пометки в правом боре:
    (root) [3] (в поддереве [1][2][3])
    |-c (в поддереве [1][2])
    |  |-c.d  [1][2]  (в поддереве [1][2])
    |      |-c.de [1]  (в поддереве [1])
    |-q  (в поддереве нет пометок)
       |-qq  (в поддерево нет пометок)

    Итого: [1][2] в вершине c, [1][2] в вершине c.d, [1] в вершине c. Ответ: 5.
    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Было желание написать суф мас за нлогквадрат (со стандартной сортировкой), по идее там таких проблем с кэшем не должно было быть.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Как решать О?
Я написал scanline + set. Но получил TL 9. Всего событий 2*N. Проход по сету для объединения отрезков - O(N). Добавление отрезка и удаление из сета - O(logN). В среднем должно выходить O(N^2 + 2*N*logN). В сортировке событий и сете оперировал только индексами.
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    ну наверно O(n^2) много для n = 2 * 10^5. Есть решение за O(n log n).
    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Там TL был 9 секунд. Я думал зайдет.
      А как решать за O (N*logN) ?
      → Ответить
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Я бы решал сжатие координат + сканирующая прямая + дерево интервалов
        Аналогичная задача была недавно на UVa, только там надо было отвечать найти количество целых точек, покрытое не менее чем k прямоугольниками. Соответственно это частный случай с k = 1
        PS 100000 в квадрате не проходит никогда, стоит забыть такой вариант ;)
        → Ответить
15 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится
Никто случаем по F WA#33 не ловил? Локально тестил с полным перебором, всё проходит, до и номер теста странно большой, учитывая что уже 13ый тест с достаточно большими входными данными.

PS. И еще, any hints по Е?
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится
    Очень похожая задача на тимусе.
    Идея такая - если мы сделали N операций, то каждому вагону можно поставить в соответствие N-битный код, в бите i стоит 0, если вагон в операции i поехал налево, 1 - если направо. Далее, если у нас есть два вагона с кодами X1 и X2, то несложно понять, какой из них будет в результате идти раньше. Ну и затем нужно назначить вагонам коды (не обязательно различные).
    Это всего лишь "hint", могу написать подробное решение.
    → Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
Wrong branch.
→ Ответить