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

Автор AndreySiunov, 14 лет назад, По-русски
Обсуждение задач.
(Изначально вопрос был задан только по C и D)
  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Еще хотелось бы услышать B и что делать в А, когда N > 10^18.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В А, у меня была некоторая идея. Понятно, что у нас получается на один делитель меньше, потому что само число больше 10^18. Потом рассмотрим числа от 2*10^18 до N, каждое второе число теряет ещё один делитель, так нам нужно выбрать числа от 2*10^18+1 до 3*10^18, которые не делятся на 2. Аналогично с числами, от 3*10^18+1 до 4*10^18, но уже число либо не делится ни на 2 ни на 3, либо делится на оба.. и т.д. все числа (всего нужно рассматривать до делителя 9). Но это так геморно, что я забил.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А не многовато чисел от 2*10^18 до N?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Нет, естественно я не имею ввиду, что там надо перебрать числа. Допустим чисел которые не делятся на 2 всего около k/2 (грубо, нужны ещё случаи), где k - длина рассматриваемого отрезка
  • 14 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится
    В B k граней не в циклах и c = m - k граней принадлежат какому-либо циклу.  Дальше, если 0 < c < 3, решения нет; если же это не так, то можно найти такой наименьший x, что и расставить c граней между вершинами от 1 до x так, что между никакими двумя из них нет "прямой" грани (т.е., есть грани (1, 2), (2, 3), ..., (x, 1), дальше любая уже не будет "прямой"). Остальные k проводим от 1 к вершинам от x + 1 до x + k.
    (В реализации нужно ещё всякие мелочи учитывать).
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В B идея в том, что наиболее выгодно (больше рёбер можно упихать) строить граф так: одна большая компонента рёберной двусвязности, устроенная сначала как цикл, а потом туда ещё можно рёбра добавлять по самое не могу, и от неё мостами отходят вершинки по одной штуке. И ещё некоторые вершины можно вообще без рёбер оставить. Ну и всё, дальше - несколько утомительный разбор кучи случаев.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    A мы сдали на дорешивании.
    Пусть мы делаем Z итераций (в данном случае их 10^18). Тогда на куске 1.. Z будут зажжены только квадраты, на куске Z+1..2Z зажженность будет все квадраты поксорить на все числа, на куске 2Z+1..3Z - все квадраты поксорить на все числа поксорить на все, которые делятся на 2, и т.д.
    На каждом из этих кусков решаем отдельно.
    Для чисел зафиксируем набор свойств - квадрат ли он, а так же делится ли оно на 1, 2, 3, 4 и т.д. Зажжеными останутся только те, которые имеют ровно нечетное количество этих свойств.
    Теперь зафиксируем какую нить маску свойств. Посчитать количество лампочек, которые этой маске удовлетворяют, можно с помощью формулы включения-исключения по тем свойствам, которые не входят в зафиксированную маску.

    Если додумать детали, можно получить решение за 10*10*3^10.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Задача А:
    Обозначим m = 1018
    Если n > m
    рассмотрим отрезки [m * i + 1, min(m * (i + 1), n)]
    Рассмотрим отрезок i. Пусть l = m * i + 1, r = min(m * (i + 1), n)
    Посчитаем для начала сколько чисел в отрезке имеют нечетное кол-во делителей больше m. Делители числа a больше m могут иметь такой вид a / j, где 1 <  = j <  = i. Пусть тогда b = lcm(1, 2, ..., i). Для каждого j от 0 до (b - 1) посчитаем odd[j]. odd[j] = 1, если кол-во делителей числа j от 1 до i нечетно, иначе odd[j] = 0. Тогда число a имеет нечетное число делителей больше m, если и только если odd[a%b] равно 1. Ну тогда не сложно посчитать кол-во чисел от l до r, у которые нечетное кол-во делителей, это кол-во прибавим к ответу. Осталось в этом отрезке разобраться с квадратами. Если квадрат имеет нечетное кол-во делителей больше m, то лампочка с этим номером не будет гореть, то есть мы что-то лишнее к ответу прибавили. Если же четное, то мы не прибавили еще его к ответу. С квадратами разберемся похожим образом. пусть l' - это минимальное число, что sqr(l') >  = l, а r' - максимальное число, что sqr(r') <  = r. Тогда берем rem от 0 до (b - 1). Посчитаем сколько чисел от l' до r' сравнимы с rem по модулю b. Пусть это будет c чисел, тогда если odd[rem2%b] равно 1, то из ответа вычитаем c, иначе прибавляем.
    Я это реализовал за O(9 * lcm(1, 2, ..., 9) * log(lcm(1, 2, ..., 9))) = O(9 * 2520 * log(2520)).
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Задача С:

Если у нас зафиксированы dx и dy, то на сетке будут лежать все точки, у которых либо x при делении на K дает остаток dx, либо y при делении на K дает остаток dy.

Зафиксируем какую-то одну точку, которая лежит на вертикальной линии сетки. Тогда все точки у абсцисс которых такой же остаток от деления на K так же будут лежать на вертикальных линиях сетки. Исключим все такие точки из нашего множества. Среди оставшихся точек зафиксируем какую-то одну точку, которая лежит на горизонтальной линии сетки. Тогда на горизонтальных линиях сетки будут лежать все точки с таким же остатком от деления их ординаты на K. Мы получили решение за O(N2).

Ускорим это решение. Для начала для каждого остатка от деления на K посчитаем сколько точек с такой y координатой всего в нашем множестве и запишем это в дерево отрезков. Теперь переберем остаток x координаты от деления на K, отнимем от всех остатков по y координате эти точки и затем найдем размер максимального множества точек с одинаковым остатком по y координате. Таким образом, максимум по всем остаткам икс координат среди вот таких максимумов и будет ответом. Сложность O(N+KlogK).

Осталось заметить что нам нужны не все остатки, а только такие, которые встречаются во входных данных, а их O(N). Суммарная сложность выходит O(NlogN).
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Задача D:
Если мы покрасили x рядов и y столбцов, то у нас получилось x * m + y * n - x * y клеток, среди них  x * y зеленых клеток. 
Посчитаем вероятность pr[i](pc[i]), что мы покрасим i рядов(i столбцов). Это легко делается за O(N2 + M2). Переберая (x, y) мы посчитаем вероятность покраски, чтобы было ровно g зеленых клеток pg = ΣxΣypc[x] * pc[y], где x * y = g.  Тогда мат. ожидание будет равно m = ΣxΣy(pc[x] * pc[y] / pg) * (x * m + y * n - x * y), где x * y = g
  • 14 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится
    Это всё понятно, но возникают проблемы с точностью, когда речь идёт о перемножении большого числа маленьких вероятностей. Там становится как будто бы ноль, а на самом деле не ноль. Мы так и не смогли пройти 11 тест.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      у меня  не было проблем с точностью использовал обычные даблы, может какой-то другой косяк?)
      • 14 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Нет, точно из-за этого. Сначала был PE11, обнаружили, что есть деление на "ноль", исправили, стали получать WA11. Пробовали и double, и long double. Хотя, вообще говоря, странно - как будто бы double должен держать показатель экспоненты до -400, однако ж не держит. Или там экспонента двоичная?
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я в конце делил просто на сумму... Вроде не было проблем вообще с точностью
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вообще-то, у вас проблема совсем не с даблами. Посмотри внимательно на условие, при котором обновляешь числитель и знаменатель дроби.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Сейчас не могу - код остался только на компе в терминалке, а из тестирующей системы его не достать. Насколько я помню, там написано так:
            for (i=1; i<=n; ++i) if (g/i<=m && g/i>=1 && g%i==0) - смотрим на pr[i] и pc[g/i] - это для g>0;
            для g==0 - смотрим на n+m+1 вариантов, что раскрашены либо только некоторые строки, либо только некоторые столбцы, либо вообще ничего.
            Это разве неправильно?
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Там написано "if (i<=n && g/i<=m && j/i>=1 && g%i==0)", а j вообще неясно что такое.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                O_O Правда, что ли? И цикл поди до n? Если так, то мы идиоты...

                Кстати, а почему ты можешь смотреть наш исходник?
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Цикл-то до g, но не спасает.

                  Хм, потому что я автор)

                  А вообще contest_id=10133, можешь и сейчас зайти и код скачать.
                  • 14 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Понятно, благодарю, сейчас исправил, получил OK.

                    Я удивился, потому что на сайте OpenCup написано просто "Гран-При Двух Столиц", слова "Других" нет, поэтому неочевидно, что это не Москва и Питер :)

                    И, раз уж на то пошло, что там было с чекером? Сейчас вроде всё работает, но на контесте нам пришлось вместо printf сделать cout, причём ещё и выровнять его аккурат на 5 знаков после запятой, чтобы пройти первый тест 8-)
                    • 14 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      Там где-то посередине event ленты написаны авторы контеста.

                      С чекером всё в порядке было с самого начала, я думаю проблема у вас была в printf("%Lf") - L нужно маленькую писать, по крайней мере для компилятора gcc.
                      • 14 лет назад, # ^ |
                          Проголосовать: нравится +3 Проголосовать: не нравится
                        Прямо в условиях было написано.
                      • 14 лет назад, # ^ |
                          Проголосовать: нравится 0 Проголосовать: не нравится
                        Не может быть. У нас было сначала printf("%.8Lf",ans) - это не проходило первый тест. А вот сейчас я попробовал так сделать - всё прошло. Если, конечно, первый тест - это тот, что в условии.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Скажите пожалуйста, на чем может валиться такая идея в Н:
Раздвоим каждую вершину. Теперь для первых n вершин сделаем ребро с минимальной пропускной способностью 1 и максимальной 1, стоимостью 0, а для остальных - с минимальной 0 и максимальной 1, стоимостью 1. Если мы сможем насытить все ребра из n с потоком мин стоимостью, то эта стоимость - ответ. Если нет потока величины n, то -1.
Вердикт - WA 12
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    У тебя не получится так, что из первых n идет ребро в одно из m, а из другого m идет куда-то в другую одну из n вершин?

    Я делал так: 
    разводим вершины
    Пусть n вершин нумеруются 1..n, а знакомые (m) -- n+1..m. соответствующие им раздвоенные вершины i'.
    Проведем ребра такие как в матрице с пропускной способность 1 и стоимостью 0
     + добавим ребра i->i' для i >= n + 1 с пропускной способностью 1 и стоимость -1, тогда, если мы и будем задействовать кого-то из знакомых, то и ему и он подарит подарок, либо он же сам подарит подарок себе (в таком случае к стоимости прибавиться -1). 
    Теперь найдем mincost maxflow и если поток полный, то ответ будет m + стоимость потока.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если я верно истолковал идею, то это то что мы закодили и оно у нас прошло.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Вот на таком графе будет работать?:
    n = 2, m = 2
    NNNY
    YNNN
    NYNN
    NNNN
    (Ответ -1 должен быть)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      -1. Я что то не понял, что ты имел в виду по моему решению? Просто вроде само толкование идет как по условию. Найти циркуляцию, чтобы по вершинам не пересекалось и чтобы из m было минимально (это ограничим стоимостью).
      Вроде багов в коде нет, думал в идее, но не нашел..
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я просто подумал, что у тебя несколько не так ребра проводятся, сейчас понял как ты решал - должно быть норм тогда.
        У меня просто несколько иная идея -- взвешенное паросочетание в двудольном графе.
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Добавь пожалуйста в заголовок поста название Гран-При
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно как решать задачу G? Кто нибудь может рассказать?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Предположим, что первая точка в (0,0), сгенерируем в этом предположении все возможные конфигурации с вершинами в целых точках. Очевидно, их будет очень мало - способов поставить вторую точку не больше чем максимальное количество представлений в виде суммы a2 + b2 для чисел  ≤ 108, третью - не более двух, а дальше вообще всё однозначно. Теперь переберём первую точку и попробуем переместить в неё каждую из наших конфигураций. Имхо, задача красивая - довольно неожиданно, что её можно решать быстрее, чем за квадрат.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо, действительно красиво =)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ну как я понял у меня такая же идея) 
      Получается сложность O(T * N * log(N)), где T кол-во решений в целых числах a2 + b2 = d2?
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Ну на самом деле , т.к. для каждой точки множества и для каждого набора сдвигов надо сделать M проверок.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Насколько я понимаю, log(N) нужен для определения, существует ли на небе соответствующая звезда. Благодаря маленьким координатам, можно всё небо хранить битмасками и делать этот шаг за O(1).
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            И получить в качестве бесплатного бонуса сплошные промахи кеша. С бинпоиском как-то спокойнее.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ну асимптотику хоть улучшает, теоретически приятно.

              Авторское решение было немного другим - вместо генерации возможных созвездий оффлайн, я выбирал пару точек и потом строил созвездие онлайн за O(M^2) для каждой подходящей пары. Такому подходу битмаски давали значительное ускорение по сравнению с логарифмом.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Утром участвовать в контесте не получилось. Где можно посмотреть условия?

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А что насчет E? через поиск компонент связности на ДФС, ловили TL
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Могу предположить навскидку, что либо в ДФС-е вообще не помечали пройденные вершины, либо помечали на выходе, а не на входе =)
    Но это всё равно бы не спасло, там не просто компоненты связности ведь, если что.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      валилось на седьмом тесте. помечали сразу на входе. 

      а какое решение правильное?

      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Конденсация.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          ...по сильно связным компонентам. Потом в графе компонент посчитать число тех, у которых входящая степень - ноль, исключая ту компоненту, которой принадлежит первая вершина.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            спасибо за помощь
            • 14 лет назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится
              Вы сдайте сначала на дорешивании, потом благодарить будете. Раз у вас был TL на поиске в глубину и это не экспонента, то, скорее всего, где-то вылазит квадрат. Обратите внимание ещё и на это.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Топологически сортируем вершины графа. Потом обходим и первой вершины. После из всех остальных в соответствии с сортировкой и считаем кол-во компонент связности.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А кто-нибудь может рассказать как I решается?