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

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

Problems of October 01, 2011 Contest


Team standings of today's contest


Personal standings of today's contest

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может кто-нибудь рассказать как в J - Abstract Thinking придумывалось/доказывалось решение C(n, 6) + C(n, 5) * 5 + C(n, 4) * 4. Или может есть другое решение?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Просто выбираем множество точек, которые будут образовывать хорды: 
    1) из 6 точек можно одним образом соединить точки так, чтобы они попарно пересекались и каждая точка была использована. Таких комбинаций C(n, 6)
    2) из 5 точек надо сделать три хорды, так чтобы ровно две хорды имели одну общую точку и все хорды попарно пересекались, таких способов всего 5 (отличаются поворотом), а выглядит способ, как буква "А", то есть угол, пересеченный третьей хордой.
    3) из 4 точек. Ну и тут порисовав, можно понять, что всего 4 способа расстановки хорд, которые отличаются поворотом.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      непонятно почему рассматриваем именно 4,5,6 точек и на них останавливаемся?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Окей, рассмотрим 3 точки, из которых можно собрать три хорды, которые пересекаются и имеют "хорошую" точку пересечения, таких комбинаций нет, потому что пересекающиеся хорды из трех вершин - это треугольник, он не подходит. 2, 1 тоже понятно почему. 7 и более, естественно тоже, потому как хорды в худшем случае занимают 6 вершин, а мы рассматриваем множества вершин, которые все будут заняты хордами.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          я наверно совсем тугой... но почему хорды в худшем случае займут 6 вершин?
          • 13 лет назад, # ^ |
              Проголосовать: нравится +6 Проголосовать: не нравится
            По задаче нужно найти количество способов выбрать три хорды с "хорошим" условием, в худшем случае каждая хорда занимает 2 вершины, не так ли?
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

            И вообще, хорда в окружности соединяет ровно две точки с окружности!

            3 хорды  — 3 * 2 = 6 вершин.

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            понял. спасибо!
    • 13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      Допустим точек 6. Тогда по первому случаю, все хорды пересекутся в одной точке. Эту точку нужно было считать треугольником?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Нет, это означает, что вот эти три хорды хорошие, потому что они имеют в пересечении внутреннюю точку. По задаче треугольник - это три хорды
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Блин, а я прицепился к слову треугольник и такие точки вычитал из ответа.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      "...1) из 6 точек можно одним образом соединить точки так, чтобы они попарно пересекались и каждая точка была использована. Таких комбинаций C(n, 6)..."

      нам же нужно не попарно пересекались, а чтобы хотя бы одна пара хорд пересекалась... не?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Нет, нужно попарное пересечение - в условие так написано, а для шести точек хотя бы пара хорд пересекаться будет - все будут пересекаться.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
как решалась F?
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    1) разделим на блоки, которые будут ограничиваться 0.

    2) каждый блок обработаем независимо друг от друга
    3) в блоке посчитаем кол-во отрицательных чисел. пусть будет k. Если k не четно, вычтем из него 1. Перемножим префикс блока, пока не встретятся k отрицательных чисел точнее пока не встретим k+1ое отрицательное число, его не обработаем. Аналогично с суффиксом. Запомним максимум
    4) ответ довольно большой, поэтому все в длинных числах
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Можно не перемножать каждый раз, а находить сумму логарифмов(это быстрее). И перемножить все числа входящие в ответ в конце.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится
        можешь поподробнее? а то из-за этого только и не сдал, что не придумал, как неперемножая каждый раз?
        • 13 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

          Можно считать не A1*A2*A3*A4...*An - это надо будет хранить в длинном числе и считать долго, а считать ln(A1)+ln(A2)+ln(A3)+ln(A4)...+ln(An) - это можно хранить в дабле и считать за O(R-L+1). ln тут - это натуральный, логарифм, например. И сравнивать тогда надо не длинные числа а даблы. Это правильно потому, что A*B = exp(ln(A)+ln(B)), где exp(x) - е в степени x(совсем не умею пользоваться LaTeX'ом).

          upd: мой код

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            надо будет это изучить, я в принципе понимал(был уверен даже), что что-то такое есть, но не знал что именно, ну спасибо за объяснение!
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ну до первых трех частей я догадался, но разве при перемножении суффиксов и префиксов тле не словится? 
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        ну если в качестве основания брать не 10, а 10^k(хотя бы 10^6), то нет.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          странно, я вообще 10^15 пробовал - тле12
          • 13 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            ну 10^15 могут лонги тормозить, не знаю. Может вектора там какие-нибудь?..
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              да я и 10^9 пробовал, ну наверное где то накосил кроме длинки((
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                могло быть переполнение при умножении на три так как 3 * 109 > 231
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Если F - вот эта задача (http://acm.timus.ru/problem.aspx?space=1&num=1587), то давным-давно я написал это решение: http://pastebin.com/HG6WdW6k, там, кажется, вычисляются лучшие степени положительных и отрицательных единиц, двоек и троек, и только в самом конце - сравнение в даблах и ответ в BigInteger.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Расскажите, пожалуйста, как решать C.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    mincost-maxflow. Можно разбить поле на группы по 4 клетки, получающиеся поворотами друг из друга. Вершины сети - буквы и группы. Стоимости и пропускные способности считаются несложно. Как-то так.

    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      "...Вершины сети - клетки исходного поля, буквы, группы..."

      А почему клетки исходного поля будут вершинами?.. У меня из истока идут ребра в буквы, из букв в группы и из групп в сток...
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Может кому будет полезно, для дорешивания: acm.timus.ru problems 1582:1592