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

COCI 2011/2012 Contest #2
Автор alex.alex, 12 лет назад, По-русски
Всем привет....

Сегодня состоится очередной раунд COCI.
Желающие участвовать могут войти в систему/зарегиться здесь. 
Для входа выберите COCI 2011/2012 - Contest #2.

Всем заранее желаю удачи...

UPD: появились результаты.
  • Проголосовать: нравится
  • +37
  • Проголосовать: не нравится

12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мда, от 650 баллов отделил один символ, который, как оказалось, стоил 150 баллов...

Мне кажется, что контест не сбалансирован. Резкий прыжок между 4 и 5 задачами.
→ Ответить
  • 12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Лично мне показалась самой сложной 5я задача, а 6я по сложности где-то между 4й и 5й. Собственно, и не хватило минут 10, чтобы дописать 6ю - много времени ушло на 5ю. Так что, мне кажется, что порядок был неправильный, а вот сбалансированность в итоге была.

    Не понравилось то, что 3я задача задачей являлась только на C/C++ и Pascal, где длинной арифметики нет.
    → Ответить
    • 12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Согласен :) Поэтому написал ее на JAVA.
      → Ответить
    • 12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Не понял, а зачем в этой задаче длинная арифметика, можно же без нее обойтись?
      → Ответить
      • 12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        +1. Нужен только флаг, правда ли, что число >= 1e9.
        → Ответить
        • 12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну или вместо флага найти десятичный логарифм от ответа и если он больше чем, скажем, 9.5, то выводить с нулями. 
          → Ответить
      • 12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Понятно, что без неё можно обойтись, просто тем, кто писал на Python или Java, можно было вообще не думать как без неё обойтись, а просто перемножить числа и получить А и В длиной в 9000 цифр, и просто найти их GCD.
        → Ответить
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересует решение задач 4, 5, 6... 
→ Ответить
  • 12 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    В 4-й можно посчитать по формуле включений-исключений. Для этого нужно найти количество чисел, которые содержат данную маску цифр (для всех 210 масок). Затем просуммировать по всем маскам, беря с минусом все маски, в которых четное число единиц.

    Чтобы найти для каждой маски, сколько чисел содержат цифры из нее, можно в начале для каждой маски найти сколько чисел содержат данные цифры и только их, а затем пройти по всем ее подмаскам и прибавить к ним это количество.
    → Ответить
  • 12 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    В пятой для начала построим граф зависимостей циклов друг от друга. Этот граф представляет собой лес. Понятно, что можно посчитать сколько раз выполнится самый внутренний цикл для каждого дерева и перемножить эти результаты.

    Когда у нас есть одно дерево, в нем корень перебирается от числа до числа, а все остальные перебираются либо от предка до числа, либо от числа до предка. Посчитаем динамику f(v, i) - сколько раз выполнится внутренний цикл в поддереве с корнем в v, если счетчик цикла, который соответствует v, сейчас равен i. Как пересчитывать эту динамику?

    Для этого, заметим, что для всех потомков при фиксированном i обе границы цикла становятся фиксированными числами. Значит, если бы у нашей вершины был всего один потомок w, то посчитать f(v,i) можно было бы как f(w, a) + f(w, a + 1) + ... + f(w,b), где a и b - границы цикла. Так как у вершины может быть более одного потомка, то для фиксированного i найдем суммы, написанные выше для каждого из них, а затем перемножим. Это и будет значением f(v, i). Перемножать нужно, потому что эти циклы не зависят друг от друга, а зависят только от i.

    Для того чтобы быстро вычислять суммы на отрезках, можно хранить вместо самой функции f(v,i) ее частичные суммы. Тогда сложность O(NR), где R - максимальная возможная правая граница цикла.
    → Ответить
  • 12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Краткие идеи:

    4. Разобъём все числа на 1024 группы, в зависимости от множества числа {присутствует 0, присутствует 1, ...}. После этого достаточно квадратичного перебора по группам, каждый раз проверяя, есть ли между ними хотя бы одна общая цифра.

    5. Представим все переменные в виде множества деревьев, где b сын a, если b зависит от a. После этого запускаем ДП. Посчитаем для каждой переменной, сколько раз выполниться код, если учитывать только поддерево этой переменной, и значение этой переменной равно х. Для конкретного х - произведение по всем сыновьям сумм значений сына на отрезке, который даёт использование конкретного х. Сумму на отрезке считаем константно, с ипользованием частичных сумм. Ответ - произведение корней по всем деревьям сумм значений на допустимом отрезке.

    6. Заметим, что ответ для одного случая ответ = (сумма времён трапез) - x. Чтобы получить х, отсортируем времена приготовления пиц по возрастанию, посчитаем частичные суммы (у нас только одна печь) и сумма всех частичных сумм и будет х. Соответственно, если мы храним частичные суммы, нам надо уметь изменить все значения на отрезке на какую-то дельту - для реализации прихода и ухода числа. Это можно реализовать с помощью двух деревьев отрезков, например. Одно - для хранения частичных сумм, при этом оставлять свободные места для тех чисел, которые ещё придут; а второе - чтобы определить, каких элементов в первом дереве ещё (или уже) не существует, чтобы мы могли всё время пересчитывать, сколько именно мы пересчитали.
    → Ответить
  • 12 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    В шестой можно заметить, что нам всегда выгодно готовить пиццу по не убыванию ее времени приготовления. Это значит, что первая пицца будет готова в момент p1=t1, вторая - в p2=t1+t2, n-я в pn=t1+t2+...+tn (считаем что времена уже отсортированы). Тогда мы получим (L1-p1) + ... + (Ln-pn)=L1+...+Ln - (p1 + ... + pn) чаевых. 

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

    Сложность O((N+C)logN).
    → Ответить
    • 12 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

      Да и сжимать координаты не обязательно. Ti, T ≤ 100000 же — достаточно хранить количество или сумму, чтобы корректно обрабатывать ситуации, когда Ti повторяются.

      Ещё можно pi не хранить, а считать на лету (всё тем же деревом), а их сумму отдельно хранить и вместо уменьшения/увеличения всех pi, стоящих после заданного TR, сразу уменьшать/увеличивать эту сумму на pR + (N - j)TR, где j — номер (начиная считать с единицы), на котором TR стоял бы в отсортированном списке всех Ti; этот номер можно получить из дерева (если TR там встречается несколько раз, годится любой номер — взяв какой-то один вместо другого, мы вычтем ровно столько, сколько потом и прибавим, и в итоге от этого ничего не изменится, — но pR должен соответствовать сумме первых j отсортированных Ti).

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

Пятую залажал, в итоге -150. Оказывается, топсорт был неверной идеей и лес не всегда вырождался в бамбук. Шестую отправил за 20 секунд до конца - давно не писал декартовы, отсутствие практики сказывается.

→ Ответить
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to solve the 5th problem?
→ Ответить
  • 12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    First, notice that the graph of dependencies between variables is a forest. We call b a "left child" of a if a is the Xi of b. Similarly, b is a "right child" if a is the Yi of b.

    Now consider variable a, value i, and the subtree rooted in a. We want counter[a][i] contain the number of all possible value assignments of the variables in the subtree such that a=i and that each of them respects the constraints (given by Xi and Yi).

    We notice that this value can be computed easily based on the values of the children of a. It's the product of sum(c,i) for each child c of a, where sum(c,i) is the sum of counter[c][1..i] if c is a right child or the sum of counter[c][i..100000] if c is a left child.

    So, through recursion (well, actually dynamic programming), we can compute counter[a][i] for all a and for all i. To get the final result we multiply, for all roots r of the trees, the sum of counter[r][i] for all values of i.

    Don't worry, it sounds more complicated than it actually is!

    The complexity should be O(N) (with a factor of 100000 :) and it actually runs really fast: my implementation has an execution time of max. 0.04s.

    → Ответить
    • 12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      I forgot to mention that, obviously, counter[a][i] is zero when i<Xa or i>Ya.
      → Ответить
      • 12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        The Node may have more than one left-child or right-child .. How to solve it ..?
        → Ответить
        • 12 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          To compute the value of counter[a][i] you iterate over all children of a (regardless of their type) and for each of them you compute the value of sum(c,i) (where c is the child you're currently iterating on). As I said, sum(c,i) is:
          • counter[c][1] + ... + counter[c][i] if c is a right child of a
          • counter[c][i] + ... + counter[c][100000] if c is a left child of a (this hardcoded constant is the maximum value of Xi and Yi)

          When you have the values of sum(c,i) for all children, you multiply them all to get the value of counter[a][i].

          I hope it's more clear now!

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

            Thanks a lot ..
            I'll have a try ..

            -----------

            How about this input:

            3
            2 3
            1 a
            b a

            You can't get a fix count[r][i] for some node ..

            → Ответить
            • 12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              The input is invalid: at most one of Xi and Yi is a reference to another variable!
              → Ответить
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Может ли кто-нибудь запостить эталонное решение на Яве, хотя бы первую задачу. У меня падает по IOException
→ Ответить
  • 12 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

    вот моя реализация третьей задачи на JAVA


    → Ответить
    • 12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      странно, тогда поставим вопрос по другому:
      что в этом коде может быть не так (код на самую первую задачу), что оно вылетает с сигналом 1?
      → Ответить
      • 12 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится
        in.close() 
        out.close() 
        этого делать не надо ))) аналогичная была проблема .... пришлось переписать на сканер 
        → Ответить
        • 12 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          Но почему не надо? Ведь везде я так писал и если бы не написал, то в вывод могло не выйти часть вывода (масло масляное).


          То есть в таком случае на произошел бы fflush(stdout), я полагаю.
          А есть ли универсальный способ, который бы работал на всех проверяющих системах?
          На COCI out.fflush() работает :)
          → Ответить
          • 12 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

            судя по всему он выкидывает System.exit(1), т.к. не может закрыть реадер ... когда я отписал по этому поводу организаторам, мне сказали не закрывать реадер и врайтер :) Ну а вообщем на JAVA пишу редко :) Предпочетаю С++ :)

            → Ответить
        • 12 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Я писал на Java, все было нормально, но я закрывал только out.
          → Ответить
          • 12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            +1 только что проверил :) все действительно сработало :)
            → Ответить
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Скажите, а дорешивание где-нибудь есть ?
→ Ответить
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
These problems are easy. But since I write a function to output long long, and it doesn't work with negative number, I lost a lot of points. TAT...
→ Ответить