KhaustovPavel's blog

By KhaustovPavel, 8 years ago, In Russian

Задача A (div2) — Шкафы

Автор: max777alex

В этой задаче можно рассмотреть независимо все левые дверцы шкафов и, аналогично, все правые. Очевидно, чтобы привести все левые дверцы шкафов в одинаковое положение, нужно определить какое из двух состояний ("левая дверца открыта" или "левая дверца закрыта") встречается чаще. Все левые дверцы, которые находятся в другом состоянии требуется привести к этому. Аналогично надо поступить и с правыми дверцами. Если аккуратно посчитать в таком случае количество операций изменения состояния дверцы, то это оно и будет ответом.

Задача B (div2) — Котенок Гав

Авторы: max777alex, KhaustovPavel

В данной задаче требовалось найти минимальное положительное N-значное число, которое делится без остатка на 2, 3, 5 и 7. Очевидно, раз все эти четыре числа являются простыми, то число, которое делится на все эти четыре числа, должно делиться на их произведение 2·3·5·7 = 210. Для N < 3 такого числа не существует. Для N = 3, конечно же, ответ равен 210. Для N > 3 следуем следующему алгоритму.

Найдем остаток R от деления 10N - 1 на 210. Далее требуется добавить 210 - R к 10N - 1, чтобы получилось число, кратное 210. Учитывая, что 0 ≤ R < 210, получаем, что последние три разряда числа определяются значением R, а оставшиеся разряды — совпадают с соответствующими разрядами числа 10N - 1.

Можно также было заметить закономерность для последних трех разрядов с изменением N и заменить вычисления остатков аккуратным разбором случаев.

Задача A (Div1), C (div2) — Электроник-футболист

Авторы: am-real

Для начала временно избавимся от радиуса мяча — сдвинем верхнюю стену на радиус вниз. Мяч, в таком случае, можно считать материальной точкой. Штанги не трогаем. Отразим центр мяча относительно сдвинутой верхней стены. Соединим полученный отраженный центр мяча и точку (0, y1 + r).

Далее остается аккуратно определить, не касается ли мяч левой стены. Очевидно, что точкой стены, наиболее близко лежащей к траектории центра мяча, будет штанга (0, y2). Таким образом достаточно проверить расстояние от этой точки до траектории мяча. Если оно меньше радиуса, значит ответа нет, иначе — точка пересечения проведенной ранее линии и сдвинутой на радиус вниз стеной и будет ответом.

Если целиться выше точки (0, y1 + r), траектория центра мяча только приблизится к штанге (0, y2), поэтому целиться в другие точки смысла не имеет.

Задача B (Div1), D (div2) — Конфеты — каждому!

Автор: KhaustovPavel

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

С ростом количества изначально имеющихся с собой конфет, время, которое требуется для угощения всех жителей может либо не изменяться, либо уменьшаться. Следовательно, здесь применим бинарный поиск по количеству конфет. С помощью бинарного поиска закрепим количество конфет, которые мы изначально взяли с собой. Идем слева направо (от первого участка, до последнего). Если находимся на участке с магазином — обязательно покупаем конфеты (денег у нас бесконечно много, значит, нет смысла не покупать конфеты). Если мы находимся на участке с домом, то при наличии конфет — угощаем жителей этого дома. Если же конфет у нас нет, то пропускам этот дом. Несложно доказать, что возвращаться назад выгодно только тогда, когда у нас достаточно конфет, чтобы угостить жителей всех пропущенных домов. Пусть первый пропущенный дом оказался на участке L. На участке R мы купили конфеты, и теперь их достаточно, чтобы угостить жителей всех пропущенных домов. Тогда участок от L до R мы дополнительно пройдем еще на два раза. Если попытаться угостить жителей пропущенных домов раньше, чем мы достигнем участка R (на участке T), то участок от L до T нам так же придется преодолеть дополнительно на два раза. Однако, так как мы не можем угостить всех жителей на отрезке от L до T, это говорит о том, что придется преодолеть некоторую часть этого интервала еще два раза, для чего нам еще на два раза придется преодолеть отрезок от T + 1 до R. Очевидно, что преодолев на два раза отрезки (L, T) и (T + 1, R) мы, фактически, преодолели на два раза отрезок от L до R. Помимо этого, какую-то часть отрезка от L до T нам потребуется преодолеть еще два раза. Получается, что количество времени, которое нам потребуется, будет строго больше, чем в первом случае. Аккуратно моделируем процесс за O(N), чтобы определить минимальное количество времени, которое потребуется на выполнение прохода по улице.

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

Результирующая асимптотика O(N·logN) (логарифм возникает из-за использования бинарного поиска).

Задача C (Div1), E (div2) — День рождения ослика Иа-Иа

Авторы: am-real, KhaustovPavel

Сформулируем ряд утверждений, которые помогут нам решить задачу. При любом действии Винни-Пуха количество нетронутых горшков на любой из полок не может быть увеличено. Таким образом, если на полке с номером i изначально находилось Ai горшков, то в любой момент времени нетронутых горшков на этой полке будет C, причем 0 ≤ C ≤ Ai. Несложно поддерживать вероятность P(i, C) того, что на полке с номером i находится C нетронутых горшков для всех возможных значений i и C. Это можно сделать с помощью динамического программирования.

Очевидно, ответом после каждой операции будет сумма P(i, 0) по всем возможным значениям i. Заметим, что после каждой операции число нетронутых горшков может измениться только на полке, с которой Винни-Пух берет горшки. Формулы для переходов между состояниями динамического программирования достаточно тривиальны. Какие-то трудности могут возникнуть при выводе формул для ki ≠ 1. Этих трудностей можно избежать, если разбивать запросы с ki ≠ 1 на ki запросов с ki = 1, ведь 1 ≤ ki ≤ 5, и, следовательно, время выполнения существенно увеличено не будет. Допустим и вариант, когда запросы не разбиваются. Для этого требуется аккуратно вывести несложные формулы переходов.

Несложно заметить, что перед первым запросом можно посчитать сумму P(i, 0) по всем значениям i. Далее, при выполнении каждого запроса ui, vi, ki, до его выполнения отнимать P(ui, 0) от ответа, а после его выполнения — добавлять новое значение P(ui, 0) к ответу.

Если обозначить наибольшее значение Ai по всем i, как MaxA, то асимптотика такого решения, очевидно, будет O(N·MaxA). Памяти такое решение так же требует O(N·MaxA).

Задача D (Div1) — Ежик и звезды

Авторы: am-real, KhaustovPavel

Для начала заметим, что задачу можно свести к более простому варианту аналогичной задачи. В первую очередь, можно избавиться от точек, которые не находятся между двумя заданными во входных данных лучами, выходящими из начала координат. После чего можно повернуть все точки относительно начала координат на такой угол, чтобы один из лучей совпал с одной из осей координат. Для определенности положим, что мы повернули все точки на угол α1 так, чтобы луч, который был пущен под этим углом совпал с осью OX.

Теперь задача существенно упрощается. Все точки лежат в первой координатной четверти (то есть все координаты строго положительны), и имеется прямая L0 под углом α2 - α1, которая проходит через начало координат и все точки лежат ниже нее. Добавим точку начала координат в наш набор, как фиктивную. Проведем через каждую из точек прямую Li параллельную прямой L0. Отсортируем точки в порядке убывания ординаты пересечения прямой Li с осью Oy. Пойдем с конца. Для каждой точки i будем считать длину наибольшей цепочки MaxL(i), которая начинается из этой точки (смотреть будем на те точки, которые уже рассмотрены в нашем обратном порядке обхода). Для каждой точки i мы будем рассматривать все точки j между заданными лучами и выбирать такую, что MaxL(j) максимально, после чего полагать MaxL(i) = MaxL(j) + 1.

Чтобы рассмотреть только те точки, которые находятся в области между лучами выходящими из точки i, требуется выбрать такие точки j, для которых Li пересекает ось Oy выше, чем Lj, и ордината Yj не меньше, чем ордината Yi. Заметим, что из-за порядка сортировки первое условие всегда выполняется, если аккуратно обработать точки с одинаковыми прямыми Li. Для соблюдения оставшегося ограничения достаточно воспользоваться стандартной идеей с деревом интервалов. Но гораздо лучше заметить, что эта задача эквивалентна задаче нахождения поиска наибольшей возрастающей последовательности. Ответом будет значение MaxL для фиктивной точки начала координат.

Как результат, имеем решение с асимптотикой O(N·logN) и O(N) затратами памяти.

Задача E (Div1) — Бесконечная матрица

Автор: KhaustovPavel

Несложно заметить ряд закономерностей. Для начала обратим внимание на первую строку матрицы. В i-ом столбце первой строки находится элемент со значением (i - 1)2 + 1. Несложно найти закономерность для первого столбца — там в чистом виде квадраты натуральных чисел. Диагональ тоже задается легкой закономерностью i2 - i + 1.

Дальше несложно заметить, что в любом столбце до элемента главной диагонали значения увеличиваются с шагом в единицу. После элемента главной диагонали элемент в i-ой строке равен i2 - i + 1. Как видим, можно и диагональный элемент отнести к этой же закономерности.

Для подматрицы, в которой нужно найти сумму, выполняем разбиение на участки над главной диагональю и под ней и производим вычисления согласно приведенным закономерностям. В авторском решении использовались суммы для квадратов первых N чисел, для суммы сумм квадратов первых N чисел и (выраженная через них) сумма кубов первых N чисел. Существуют и другие варианты формул.

Теперь стоит выполнить все вычисления по модулю 1010. Для того, чтобы отследить, имеет ли число более десяти знаков, будем хранить (помимо остатка) частное от деления на 1010 по модулю нескольких различных простых чисел порядка 109. На практике достаточно и одного простого числа, но для генерации тестов использовалось сразу четыре.

Для решения задачи также можно использовать и типы данных, связанные с длинной арифметикой. Много решений с такой реализацией проходили. Однако, стоит отметить, что нельзя погарантировать хорошее быстродействие такому решению.

 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

»
8 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

There is a slightly different solution of D: you can change basis with affine transformation: replace coordinates (x, y) with (x·c - y·d, y·b - x·a). You can treat it like 'oriented distances' to the lines.

Now we have a1 = 0 and a2 = 90 and this is standard DP problem, which can be solved in

You can also see my code: 2646289. It's pretty straightforward

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Same problem and same solution I've seen in All-Ukrainian Olympiad of Informatics. Problem (F).There is also a tutorial for this problem on CF, but only in Russian.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Also somewhat harder version of problem E was proposed on Topcoder.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Harder? I don't think so. Here solution is quite trivial. We've dicussed it before the contest with Seyaua and we've found a lot of differences between this two problems.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Oh, come on. I can assure you that it was not the hard idea which stopped people from solving problem E from your contest.

          Just for your notice: it wasn't necessary to derive all the formulas by hand. One could use Maple/Wolfram Mathematics/Matlab/whatever else to perform polynomial interpolation and then just add up these 3 polynomials to get the answer. The problem was in this part of statement which asked to output only the last 10 digits. Why didn't one ask to output 17 digits or even the last 10 digits of panswer? Both of these cases are also solvable, but take even more time than the original problem. I believe that all solutions that didn't pass final tests either got TL or just had some error related to the output format. Was it intended?

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Well, it wasn't intended, but I did realize that this part of the problem could be the tough one. I've noticed that output modulo some number is quite boring, so I've decided to complicate this problem a little. The cost of this problem corresponds to the risks that this problem brings.

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Is there any chance to have this solutions translated into english. Thank you :D

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    read top to down as mentioned above however i have mentioned the division and TAsk Letter:

    A div 2 cupboards:

    In this problem, you can consider independently all the left cabinet doors and, similarly, all the right ones. Obviously, to bring all the left cabinet doors to the same position, you need to determine which of the two states ("left door open" or "left door closed") is more common. All left doors that are in a different state are required to bring about this. We must do the same with the right doors. If you carefully calculate in this case the number of operations to change the state of the door, then this will be the answer.

    B div 2:

    In this problem, it was required to find the minimum positive N-digit number that is divisible by 2, 3, 5, and 7. It is obvious that since all these four numbers are prime, the number that is divided by all these four numbers must be divided by product 2 · 3 · 5 · 7 = 210. For N <3, such a number does not exist. For N = 3, of course, the answer is 210. For N> 3, we follow the following algorithm.

    Find the remainder R from dividing 10 N — 1 by 210. Next, add 210 — R to 10 N — 1 to get a multiple of 210. Given that 0 ≤ R <210, we find that the last three digits of the number are determined by the value of R , and the remaining digits coincide with the corresponding digits of the number 10 N — 1.

    One could also notice a pattern for the last three digits with a change in N and replace the residual calculations with a neat analysis of cases.

    C div 2:

    In this problem, it was required to find the minimum positive N-digit number that is divisible by 2, 3, 5, and 7. It is obvious that since all these four numbers are prime, the number that is divided by all these four numbers must be divided by product 2 · 3 · 5 · 7 = 210. For N <3, such a number does not exist. For N = 3, of course, the answer is 210. For N> 3, we follow the following algorithm.

    To get started, temporarily get rid of the radius of the ball — move the top wall down a radius. The ball, in this case, can be considered a material point. We do not touch the rods. We reflect the center of the ball relative to the shifted upper wall. We connect the obtained reflected center of the ball and the point (0, y 1 + r).

    Then it remains to accurately determine whether the ball touches the left wall. Obviously, the rod point (0, y 2) will be the point of the wall closest to the ball center path. Thus, it is enough to check the distance from this point to the ball trajectory. If it is less than the radius, then there is no answer, otherwise — the point of intersection of the line drawn earlier and the wall shifted downward by the radius will be the answer.

    If you aim above the point (0, y 1 + r), the trajectory of the center of the ball only approaches the bar (0, y 2), so aiming at other points does not make sense.

    D div 2:

    In the task, it was assumed that friends from Prostokvashino could end their journey anywhere on the street. Let's initially assume that friends can finish their route only on the last stretch of the street. In this case, the solution is more than obvious.

    With the increase in the number of sweets originally available with you, the time required to treat all residents may either not change or decrease. Therefore, binary search by the number of candies is applicable here. Using a binary search, we fix the number of candies that we originally took with us. We go from left to right (from the first section to the last). If we are on a site with a store, be sure to buy sweets (we have an infinite amount of money, which means that it makes no sense not to buy sweets). If we are on a site with a house, then in the presence of sweets we treat the inhabitants of this house. If we don’t have sweets, then this house will be omitted. It is easy to prove that it is profitable to go back only when we have enough sweets to treat the residents of all the missed houses. Let the first missed house be on site L. On site R, we bought sweets, and now there are enough of them to treat the residents of all the missed houses. Then the section from L to R we will additionally go through two more times. If we try to treat residents of the missed houses earlier than we reach section R (on section T), then we will also have to overcome the section from L to T twice as much. However, since we cannot treat all residents on the segment from L to T, this suggests that we will have to overcome some of this interval two more times, for which we will have to overcome the segment from T + 1 to R two more times. Obviously, having doubled the segments (L, T) and (T + 1, R), we, in fact, doubled the segment from L to R. In addition, we need to overcome some part of the segment from L to T two more times. It turns out that the amount of time that we need will be strictly longer than in the first case. We carefully simulate the process in O (N) in order to determine the minimum amount of time it takes to complete the passage along the street.

    Now we will offer a modification for the case when friends can finish their journey on any site. In this case, it is not necessary to visit some part of P street. This part of the street represents several (possibly zero) last sections of this street and does not contain houses. Such a part can be determined by O (N) for each initially available amount of candy in the hands of friends. We call the street minus its part P the useful part. At some point in time it may turn out to be more profitable to reach the end of the useful part and go back until the residents of all the missed houses receive their sweets, after which the distribution of sweets stops. Such a check can be performed in O (1) at each step of the solution described above.

    The resulting asymptotic behavior is O (N · logN) (the logarithm arises due to the use of binary search).

    E div 2:

    We formulate a series of statements that will help us solve the problem. With any action of Winnie the Pooh, the number of untouched pots on any of the shelves cannot be increased. Thus, if on the shelf with number i there were originally A i pots, then at any moment of time untouched pots on this shelf will be C, and 0 ≤ C ≤ A i. It is easy to maintain the probability P (i, C) that on shelf number i there are C intact pots for all possible values ​​of i and C. This can be done using dynamic programming.

    Obviously, the answer after each operation will be the sum of P (i, 0) for all possible values ​​of i. Note that after each operation, the number of untouched pots can only change on the shelf with which Winnie the Pooh picks up pots. Formulas for transitions between states of dynamic programming are quite trivial. Some difficulties may arise when deriving the formulas for ki ≠ 1. These difficulties can be avoided by breaking queries with ki ≠ 1 into ki queries with ki = 1, because 1 ≤ ki ≤ 5, and therefore, the execution time is not significantly increased will be. We also allow the option when the requests are not broken. To do this, you need to carefully derive simple transition formulas.

    It is easy to see that before the first query, you can calculate the sum P (i, 0) for all values ​​of i. Further, during each request u i, v i, k i, before it is fulfilled, subtract P (u i, 0) from the answer, and after it is completed, add a new value P (u i, 0) to the answer.

    If we denote the largest value of A i for all i, as MaxA, then the asymptotic behavior of such a solution will obviously be O (N · MaxA). Such a solution also requires O (N · MaxA) memory.

    D div 1:

    To begin with, we note that the problem can be reduced to a simpler version of a similar problem. First of all, you can get rid of points that are not between two rays specified in the input data coming from the origin. Then you can rotate all the points relative to the origin at such an angle that one of the rays coincides with one of the coordinate axes. For definiteness, we assume that we have rotated all the points by an angle α1 so that the beam that was fired at this angle coincides with the axis O X.

    Now the task is greatly simplified. All points lie in the first coordinate quarter (that is, all coordinates are strictly positive), and there is a line L 0 at an angle α2 — α1, which passes through the origin and all points lie below it. Add the origin to our set as a dummy. Draw a line L i parallel to the line L 0 through each of the points. Sort the points in decreasing order of the intersection of the line L i with the axis O y. Let's go from the end. For each point i, we will consider the length of the largest chain MaxL (i) that starts from this point (we will look at those points that have already been considered in our reverse traversal order). For each point i, we will consider all points j between given rays and choose such that MaxL (j) is maximum, and then set MaxL (i) = MaxL (j) + 1.

    To consider only those points that are in the area between the rays emanating from point i, it is necessary to select those points j for which L i intersects the axis O y higher than L j and the ordinate Y j is not less than the ordinate Y i. Note that, due to the sorting order, the first condition is always satisfied if the points with the same lines L i are carefully processed. To comply with the remaining restriction, it is enough to use the standard idea with the interval tree. But it is much better to notice that this task is equivalent to the task of finding the search for the greatest increasing sequence. The answer will be the MaxL value for the fictitious origin.

    As a result, we have a solution with the asymptotic behavior of O (N · logN) and O (N) memory costs.

    E div 1:

    It is easy to notice a number of patterns. First, pay attention to the first row of the matrix. In the i-th column of the first row there is an element with the value (i - 1) 2 + 1. It is easy to find a pattern for the first column - there are pure squares of natural numbers there. The diagonal is also set by the easy regularity i 2 - i + 1.

    Further it is easy to notice that in any column to the main diagonal element the values ​​increase in increments of one. After the element of the main diagonal, the element in the i-th line is i 2 — i + 1. As we see, the diagonal element can also be attributed to the same regularity.

    For the submatrix in which it is necessary to find the sum, we divide into sections above and below the main diagonal and perform calculations according to the above laws. The author’s solution used the sums for the squares of the first N numbers, for the sums of the sums of squares of the first N numbers and (expressed through them) the sum of the cubes of the first N numbers. There are other options for formulas.

    Now it’s worth doing all the calculations modulo 1010. In order to track whether the number has more than ten characters, we will keep (in addition to the remainder) the quotient of dividing by 1010 modulo several different primes of order 109. In practice, one prime number is enough, but four were used to generate the tests.

    To solve the problem, you can also use data types associated with long arithmetic. Many decisions with such an implementation have been made. However, it is worth noting that it is impossible to guarantee good performance for such a solution.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      one more tip if you unable to understand any mathematical equation or symbol simply see the explanation in Russian and figure out the equation as mathematics is mathematics its same in all languages as long as expressed in mathematical terms.

      Thanks.