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

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

Изначально мы хотели расположить задачи по сложности так: A-C-E-D-B. Насчет порядка последних двух мнения разделились. Посмотрим, что покажут результаты.

166A - Ранклист

В этой задаче нужно сделать то, что написано в условии — отсортировать команды по заданному компаратору: (p1 > p2) или (p1 = p2 и t1 < t2). После этого надо разбить команды на группы одинаковых, и найти размер группы, команды из которой делят k-ое место. Многие почему-то при равенстве числа задач сортировали команды по убыванию времени, а не по возрастанию. Такие решения случайно проходят претесты и получают WA #13.

166B - Многоугольники

Так как многоугольник A — выпуклый, достаточно проверить, что все вершины многоугольника B лежат строго внутри многоугольника A. Идейно самое простое решение – построить выпуклую оболочку из точек обоих многоугольников, и проверить, что в нее входят точки только из первого многоугольника. Но в таком решении придется писать выпуклую оболочку, которая обязательно берет все точки, лежащие на одной прямой, а это на порядок сложнее других решений и содержит частный случай.

Второе решение – разрежем A на треугольники (по номерам вершин): (1, 2, 3), (1, 3, 4), (1, 4, 5), …, (1, n - 1, n). Последовательность углов 2 - 1 - 3, 2 - 1 - 4, 2 - 1 - 5, …, 2 - 1 - n монотонно возрастает. Значит, для каждой точки многоугольника B можно за log(n) бинпоиском найти, какому треугольнику она может принадлежать по углу относительно вершины 1.

Аналогично можно разрезать многоугольник A вертикальными линиями на O(n) трапеций. В таком случае бинпоиск будет просто по x-координате.

166C - Медиана

Если в исходном массиве нет числа x, то, очевидно, нужно его добавить, +1 к ответу. Далее делаем следующим образом. Пока медиана массива строго меньше x, нужно ее увеличивать. Очевидно, самый надежный способ увеличить медиану – добавить в массив максимальное число (105). Аналогично, пока медиана строго больше x, добавляем в массив числа 1. Ограничения позволяют добавлять числа по одному и пересчитывать медиану “в лоб”.

Также есть решение вообще без случаев: пока медиана не стала равна x, добавляем в массив число x.

166D - Обувной магазин

Будем рассматривать всех людей в порядке убывания их размера обуви. Заметим, что при рассмотрении i-го человека нам важны максимум две пары обуви: размера li и li + 1. Это позволяет написать динамику с состоянием: (номер первого нерассмотренного человека i, доступна ли для покупки обувь размера li, доступна ли для покупки обувь размера li + 1). Переходы: оставить i-ого человека без обуви, или продать ему обувь одного из двух подходящих размеров.

166E - Тетраэдр

Очевидное решение динамикой: нам важно только сколько ходов осталось сделать муравью, и в какой из четырех вершин он стоит. Получается 4n состояний, из каждого по 3 перехода – при аккуратной реализации такое может пройти. Можно заметить, что вершины A, B, C эквивалентны между собой. Это позволяет написать такое решение:

int zD = 1;
int zABC = 0;
for (int i = 1; i <= n; i++) {
	int nzD = zABC * 3LL % MOD;
	int nzABC = (zABC * 2LL + zD) % MOD;
	zD = nzD;
	zABC = nzABC;
}
cout << zD;

Также задачу можно решать за log(n) бинарным возведением в степень n некоторой матрицы 2 × 2.

Разбор задач Codeforces Round #113 (Div. 2)
 
 
 
 
  • Проголосовать: нравится  
  • +30
  • Проголосовать: не нравится  

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

Ничего себе "случайно проходят"!

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

Спасибо за разбор. На Д писал такую же динамику, вылезли проблемы со случаем, когда делался переход по типу:

Тест: 3 пары (1-1, 1-2, 1-3) 3 покупателя (1-1, 1-1, 1-2) Динамика начинает ошибаться в таком месте:

3-ий человек покупает для себя обувь своего размера. переход в предыдущий максимум, где: 2-ой человек покупает для себя обувь своего размера. переход в предыдущий максимум, где: 1-ый человек покупает для себя обувь на размер больше.

Моя программа выдает:

3 1 2 2 1 3 2

Выходит что 1-ый и 3-ий купили одну и туже обувь!

Я не правильно строю переходы? Помогите, пожалуйста! (вот код: 1395703)

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

А как проверить лежит ли точка внутри треугольника?

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

В задаче E у матрицы хорошие собственные значения, значит есть простая формула через какие-то степени чисел.

UPD: а именно , как и было замечено ранее

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

можно небольшой вопрос, про задачу B. Она у меня упала на 22 тесте. Числа в тесте превышали 10^9, хотя в условии было сказано, что числа <10^9. Почему так?

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

    показалось)

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

    Возможно при умножении происходило переполнение.

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

      я не использовал умножение. Скорее всего, на следующих тестах программа упала бы...

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

        Так у Вас ошибка времени исполнения — выход за пределы массива.

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

          точно,забыл при объявлении нолик дописать

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

B наверное можно решить немного быстрее: за MlogM+N(M-количество вершин внутреннего многогульника)

Нужно заметить ,что точка входит в многоугольник тогда и только тогда, когда существует сторона, которая ниже этой точки и сторона, которая выше этой точки(в обоих случая вертикальная проекция точки лежит на стороне). Отсортированный по X список сторон можно получить за O(N) исходя из того факта, что стороны заданы в порядке обхода по часовой стрелке,а точки внутреннего многоугольника отсортировать по X за MLOGM.

Далее, пройти по отсортированным по X сторонам и выкидывать/добавлять из очереди точки,которые проецируются/не проэцируются на cоответствующую сторону. Для каждой точки проверять выше или ниже она рассматриваимой стороны. Так как для выпуклого многоугольника существует максимум 2 стороны на которые проецируется какая либо точка,то всех таких проверок будет O(N).

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

P.S Правда,я это не сдал,где то баг:)

UPD: Сдал. Правда не совсем так,но суть не поменялась:) Это же надо руки такие кривые , компаратор неправильно написать.

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

    Что-то подобное сдал я. Только проще идти по точкам многоугольника B, для каждой из которых будет только одна сторона многоугольника A, на которую указывает текущий вектор. Можно поддерживать указатель на такую сторону с суммарной сложностью O(N + M). Вектор можно проводить из любой точки, которая находится внутри многоугольника A. Такую точку можно найти в целых методом неадекватного извращения (если можно проще, то дайте знать). Умножим все координаты обоих многоугольников на N (количество вершин в многоугольнике A). Затем найдем сумму значений по каждой из координат и разделим на N — вот и искомая точка. Теперь, при поиске векторного произведения у нас будет происходить переполнение 64-битного целого, но метод извращения предусматривает и это! Для любого вектора при векторном произведении мы будем выполнять деление его координат на N. Теперь у нас есть решение в целых и ничего не переполняется. Теперь нам остается написать все это безобразие и люто молиться весь систест.

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

А почему в В нельзя просто проверить лежит ли каждая точка второго внутри первого?

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

Edited -- Fixed my code! Thanks to Igel_SK!

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

Isn't the state for D too big?

Also, I see people doing bipartite matching in a greedy way, why does this work?

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

    Bipartite matching with sorting shoes works correctly, it can be proofed (in russian). I think it should get TLE but the tests were weak :)

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

    I solved with the DP this way: you have the current person and a mask that represents if the 2 sizes of shoes that this person can use are available (costumers are sorted by shoe size), so it will be a dp[10⁵][4] table.

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

Great explainatiions:) Can you explain your second solution on Problem B in detail ? Thx How do you perform binsearch on angles to calculate whether every vertex is in Polygon A or not

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

I solved E:Tetrahedron using the problem (3^n+3*(-1)^n)/4 . Here is my solution . However it failed the system test and when I used BigInteger it passed.Here is the 2nd version. 2 question: 1.Why does the first solution fail... 2.Is there any thing I can do to avoid BigIntegers

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

    Use long

    Doubles are not accurate

    Your code with long instead of double 1403711

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

    Got the same problem.

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

    Hi , can you explain your solution for this question some better ? I mean i know the your solution is true but how did you reach this solution ? Plz answer

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

    how did you arrive at this formula can you please explain??

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

      do the adjacency matrix A (in this problem you will have a matrix where A[i][j] = 1 if i!=j and A[i][j] = 0 if i==j). now A^2 count paths with two edges, A^3 count paths with three edges and so on, do exponentiation using diagonalization i.e A = P*D*P^(-1)

      A^n = P*D^n*P^(-1)

      You have to find a formula for one element on the diagonal using matrix P, D^n and P^(-1), just there you will notice the formula (3^n+3*(-1)^n)/4. (all of elements on diagonal are equal for this reason you need to find the formula of only one of them)

      be carefull doing division using modulo, here you will find good information of how to do that https://codeaccepted.wordpress.com/2014/02/15/output-the-answer-modulo-109-7/

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

    Hey! I am a beginner learning coding. I was solving 166E in problem set but couldn't. Read your comment and solution can you please explain me your code after ans%=mod on line 34? I will be thankful to you.

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

Интересные задания, со смыслом, так сказать.

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

What 2 x 2 matrix can be used in E? I've only seen it solved with a 4 x 4 matrix with diagonal = 0 and rest = 1.

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

    See Egor's solution: 1390234

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

      Can you explain the idea behind this solution?

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

        In general, you can do matrix exponentiation (that is, raising matrix M to the N-th power) in O(logN) time, where N is the exponent. If you exploit a "matrix notation" for your dp recurrence, then you can reduce it to this problem, thus solving it in O(logN).

        For example, it is possible to find the N-th fibonacci number using this method. For a better explanation, check out the "Fibonacci log N" tutorial on e-maxx.ru

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

Sorry about that, just ignore the post.

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

from math import *

def fast_exponentiation(base, n): if n == 1: return base else: if n % 2 == 0: base1 = fast_exponentiation(base, n/2)**2 return base1%1000000007 else: return (base*fast_exponentiation(base,(n-1)/2)**2)%1000000007

t = int(raw_input()) if t%2 == 0: print ((fast_exponentiation(3,t) + 3)/4)%1000000007 else: print ((fast_exponentiation(3,t) — 3)/4)%1000000007

Why is this code in Python wrong for thetraedron?

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

    Note: you can use the built-in function pow for fast modular exponentiation:

    pow(3, t, 1000000007)
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I keep getting wrong answer...

      I get right values if I put modulus outside all the expression, so:

      print ((fast_exponentiation(3,t) + 3)/4)%1000000007 gives correct value, but slow and print ((fast_exponentiation(3,t) + 3)/4) within the fast exp with mod gives WA, why?

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

        You can't divide by 4 if you use mod before it. You should multuply pow(4, p-2, p) instead

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

        Try ((fast_exponentiation(3,t) + 3) * 250000002) % 1000000007, and take modulo on each fast_exponentiation step.

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

          ant.ermilov thank you for the tip, I have seen it in a solution as well, but can you explain to me, or point me to somewhere that can tell me, why is that particular number used?

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

            At first, let's try to understand, why your approach does not work. For example, we have
            Y = M+1, Y % M = 1,
            but (Y / 4) % M != (Y % M) / 4.

            So division can be substituted by multiplication. In general, we have modulo M, divisor D and want to find such Z that for each X: (X / D) % M = ((X % M) * Z) % M.
            After simple transformation we will get (X * Z) % M = 1.
            For particular case 250000002 * 4 = 109 + 7 + 1.
            Some extra info: Z can be found iff gcd(X, D) = 1, and simpliest way described at AlexDmitriev's comment above. From Euler's theorem we get Z = (DM - 2) % M.

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

What does non-degenerate mean in 166B - Polygons (Div2 B) ?

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

@AlexDmitriev Can you please explain In the solution to E why has nzABC been multiplied by 2 in the fifth line?

int nzABC = (zABC * 2LL + zD) % MOD;

Thanks a lot.

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

    Let Ai denote number of ways to finish near the vertex A after i moves (same for Bi, Ci, Di). Easily,

    Ai = Di - 1 + Bi - 1 + Ci - 1
    Bi = Di - 1 + Ai - 1 + Ci - 1
    Ci = Di - 1 + Ai - 1 + Bi - 1
    Di = Ai - 1 + Bi - 1 + Ci - 1

    with the initial conditions

    A0 = 0, B0 = 0, C0 = 0, D0 = 1

    Due to the symmetry $A_i=B_i=C_i=ABC_i$, so

    ABCi = Di - 1 + ABCi - 1 + ABCi - 1 = Di - 1 + 2 * ABCi - 1
    Di = ABCi - 1 + ABCi - 1 + ABCi - 1 = 3 * ABCi - 1
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

TETRAHEDRON : can this problem be think in a way that if u want to reach at D in n steps, then to travel n — 1 steps 3 ^ (n — 1) ways possible, now this case include that if u reached at D in n — 1 steps therefore to reach in n steps ans(in n steps) = 3 ^ (n — 1) — ans(in n — 1 steps); which is a DP solution

eg — to reach in 1 steps = 0 to reach in 2 steps — 3 ^ (2 — 1) — 0; to reach in 3 steps — 3 ^ (3 — 1) — 3 = 6 to reach in 4 steps — 3 ^ (4 — 1) — 6 = 21 to reach in 5 steps — 3 ^ (5 — 1) — 21 = 60

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

I'm interested in E,whether there is any simple formula without matrix.i can't get it,anybody got it and coubld you share it?

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

    CAN anybody explain E in detail? Can't get it.Thanks!

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

      Let f[A][j] is the number of ways from D to A by going j steps,as same,f[B][j], f[C][j] and f[D][j], we know f[D][0] = 1, f[A, B, C][0] = 0(because the ant starts at D).

      then you get four equations below:

      f[A][j] = f[B][j - 1] + f[C][j - 1] + f[D][j - 1]

      f[B][j] = f[A][j - 1] + f[C][j - 1] + f[D][j - 1]

      ......

      f[D][j] = ...

      you can solve this problem in O(n),the answer is .

      but it's too slow.you can express the four equations by matrix.then it's obvious to solve the problem by Successive Square Method with matrix in .

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

@RAD In question B Polygons, What's the problem if we directly compute the convex hull of all points and check if any point of B is present in it ? I couldn't understand the mistake!!

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi... . Could you please explain why is the output for testcase #13 of problem 166A - Rank List 1?

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

I am getting a RTE when I am submitting the solution for A. I have used a custom sort function and am baffled as to why I am getting the RTE sometimes (it is giving RTE sometimes only). Here is the code

35896046

Thanks in advance!