Sereja's blog

Codeforces Round #179 tutorial
By Sereja, 12 years ago, translation, In English

296A - Yaroslav and Permutations
Note that after applying the operations of the exchange, we can get any permutation of numbers. Not difficult to understand that the answer is "YES", if you can place a single number that it would not stand in the neighboring cells. Thus, if a some number is meeted C times, it must fulfill the condition C <= (n+1) / 2.
296B - Yaroslav and Two Strings
Будем решать обратную задачу: посчитать количество способов сделать сравнимые пары.
Для начала посчитаем количество способов сделать первую строку меньше равной второй.
Это количество равно произведению количества способов сделать это для каждой позиции по отдельности,так как они все позиции независимы. Посчитаем такую же величину, но когда вторая строка меньше-равна первой. И аналогично посчитаем количество способов сделать две строки равными. Для каждого символа величины можно считать простым циклом.
Теперь возьмем величину 10 в степени количества знаков вопроса во входном файле и отнимем полученный ответ на обратную задачу, это и будет ответом.
295A - Greg and Array
Для того, что бы прибавить значение d на отрезке [x,y] достаточно завести массив b и поставить значения
b[x] += d
b[y+1] -= d
Дальше за один проход по массиву легко восстанавливаются все числа.
Применим данный метод дважды: сначала для запросов, а потом для операций(зная сколько раз мы ее выполним).
295B - Greg and Graph
Для решения задачи нужно хорошо понимать принцип работы алгоритма Флойда.
Общий вид алгоритма Флойда:
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
То есть на каждом шаге мы пытаемся пропустить путь через вершину К.
Будем не удалять вершины, а добавлять(идя с конца).
На каждом шаге будем пробовать пропустить путь между всеми вершинами через новую.
Таким образом мы получим решение, работающее за кубическое время.
295C - Greg and Friends
Заметим, что на каждом шаге нас интересует только положение лодки(номер берега) и количество людей веса 50 и 100 на каждом береге. При чем количество людей на одном береге полностью определяется через другой.
Для поиска минимального количества переправ будем использовать волновой алгоритм, основанный на этом состоянии.
Для нахождения количества способов просто добавим сумму всех переходов в состояние при переходе будем переносить все способы из одного состояния в другое умножая на количество способов выбрать людей, которые нужны для перехода из одного состояний в другое.
295D - Greg and Caves
Будем пользоваться динамическим программированием: dp[i][j] — сколько существует способов построить фигуру, что в строке i будет ровно j столбцов занятыми черными клетками и всем, что между ними. При этом фигура должная не убывать (иными словами мы берем только верхнюю часть фигуры).
Как делать переход? Заметим, что dp[i][j] = 1+dp[i-1][2] * (j-2+1)+ ... +dp[i-1][l] * (j-l+1)+ ... +dp[i-1][j].
Распишем это: dp[i][j] = 1+dp[i-1][2] * j+ ... +dp[i-1][l] * j+ ... +dp[i-1][j] * j — dp[i-1][2] * 1 — dp[i-1][3] * 2 — ... — dp[i-1][j] * (j-1).
Понятно, что если завести частичные сумму, то данные величины считать становится очень просто.
Как посчитать полный ответ: будем перебирать номер максимального подходящего t(обозначенного в условии).
Теперь единственное отличие, это то что следующая строка должна содержать строго меньше столбцов. То есть имеем аналогичный переход, с -1 слагаемым.
Так же заметим, что зафиксировав "основу" мы должны домножить количество способов на число способов разместить ее на плоскости, то есть основу шириной j мы можем поставить (m-j+1) способами.
295E - Yaroslav and Points
Научимся решать задачу: найти сумму расстояний между точками.
Если расписать, что происходит при добавлении одной точки, то получим формулу: x_i*(2*i-n) Где x_i — отсортированные координаты, а n общее количество точек.
Научимся зная ответы для двух отрезков точек знать ответ для их объединения.
Понятно, что для подсчета такой информации нужно всего лишь сложить два ответа,
и добавить сумму координат первого множества умноженное на некоторое число и
и добавить сумму координат второго множества умноженное на некоторое, возможно другое, число.
Таким образом зная ответы для некоторых отрезков общий ответ.
Будем использовать корневую декомпозицию или декартово дерево для хранения таких отрезков.
Не сложно понять, что вставка и удаление делается достаточно быстро для этих структур.
Например для корневой декомпозиции можно каждый раз просто вырезать и вставлять точку в нужные отрезки, а если множество стало содержать длинные отрезки или много отрезков, то просто перестроим его заново. Асимптотика решения не меняется.

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

Comments Comments (23)
| Write comment?
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

where's english toturial??!!

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

    you can get main idea by translating it with Google translator.

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

please, someone translate it to english.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

296A — Yaroslav and Permutations

Note that after applying the operations of the exchange, we can get any permutation of numbers. Not difficult to understand that the answer is "YES", if you can place a single number that it would not stand in the neighboring cells. Thus, if a some number is meeted C times, it must fulfill the condition C <= (n + 1) / 2.

296B — Yaroslav and Two Strings

We solve the inverse problem: count the number of ways to make a comparable pair. To start count the number of ways to make the first line is less than equal to the second. This number equals the number of ways to do this for each item individually as they are position independent. Let's count the same amount, but when the second string is less than, equal to the first. And similarly to count the number of ways to make the two strings equal. For each symbol values ​​can be regarded as the simple cycle. Now we take the value of 10 to the number of question marks in the input file, and subtract the resulting response to the inverse problem, it will be the answer.

295A — Greg and Array

In order to add the value of d in the interval [x, y] is enough to have the array and put the values ​​b b [x] + = d b [y + 1] — = d Then in a single pass through the array easily reduced all numbers. We apply this method twice: first to query, and then to operations (knowing how many times we run it).

295B — Greg and Graph

To solve this problem you need a good understanding of the principle of Floyd algorithm. General view of the Floyd algorithm: for (k = 1; k <= n; k ++) for (i = 1; i <= n; i ++) for (j = 1; j <= n; j ++) a [i] [j] = min (a [i] [j], a [i] [k] + a [k] [j]); That is, at every step of the way we try to skip through the top K. We will not remove the top, and add (going from the end). We will try to skip the path between all nodes through a new on every step. Thus we get a solution that works for cubic time.

295C — Greg and Friends

Note that at each step we are interested in only the position of the boat (number coast) and the amount of weight people and 50 100 on each shore. What does the number of people on one side is completely determined by the other. To find the minimum number of crossings will use wave algorithm based on this condition. To find the number of ways to add just the sum of all transitions in the state during the transition will carry all the way from one state to another by multiplying the number of ways to choose the people who need to go from one state to another.

295D — Greg and Caves

We use dynamic programming: dp [i] [j] — how many ways there are to construct a figure that in row i will be exactly j columns occupied by black cells and all that is between them. This figure should not decrease (in other words, we take only the upper part of the figure). How to make the transition? Note that dp [i] [j] = 1 + dp [i-1] [2] * (j-2 + 1) + ... + dp [i-1] [l] * (j-l + 1) + ... + dp [i-1] [j]. We write it: dp [i] [j] = 1 + dp [i-1] [2] * j + ... + dp [i-1] [l] * j + ... + dp [i-1] [ j] * j — dp [i-1] [2] * 1 — dp [i-1] [3] * 2 — ... — dp [i-1] [j] * (j-1). It is clear that if make partial amount, the value of the data count becomes very simple. How to find a complete answer: we will sort out the maximum number of suitable t (indicated in the subject). Now, the only difference is that the next line should contain strictly fewer columns. That is, we have a similar transition from -1 term. Also note that fixing the "foundation", we have to multiply the number of ways at a number of ways to place it on the plane, that is the basis of the width of j we can supply (m-j + 1) ways.

295E — Yaroslav and Points

Learn to solve the problem of finding the sum of the distances between points. If you paint, what happens when you add one point, we get the formula: x_i * (2 * i-n) Where x_i — sorted coordinates, and n is the total number of points. Let us learn to know the answers to the two segments of the points to know the answer to their associations. It is clear that for the calculation of such information need only add two reply and adding the sum of the first plurality of coordinates multiplied by a number and and add the amount of the second set of coordinates multiplied by a possibly different number. Thus knowing the answers for some segments of the overall response. We use the root decomposition or Treap storage of such segments. It is not difficult to understand that insertion and deletion is done quickly enough for these structures. For example, for the root decomposition is possible each time to just cut and paste the point in the desired lengths, and if the set was contain long stretches or many pieces, just reconstruct it again. Asymptotics of the solution does not change.

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

Div 2 C, what does it mean? "Greg wrote down k queries on a piece of paper. Each query has the following form: xi, yi, (1 ≤ xi ≤ yi ≤ m). That means that one should apply operations with numbers xi, xi + 1, ..., yi to the array."

which operation?!

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    did u find meaning of operation?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Yes Bro!

      Need explanation ?

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

        Yes bro..:)

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

          I'm explaining the first t.case

          n ( array items ) = 3, m(operations) = 3, q( queries ) = 3

          1 2 3 [ Initial Array ]

          1 2 1 [ OPERATION 1 ]
          1 3 2 [ OPERATION 2 ]
          2 3 4 [ OPERATION 3 ]

          So, Our Array is ARR = [ 1,2,3 ]
          Now The queries:

          q1 : 1 2 [ perform operation 1 and 2 ] 

          after op_1: ARR = [ 2,3,3]

     after op_2: ARR = [ 4,5,5]

          q2 : 1 3 [ perform operation 1,2,3 ] 

          after op_1: ARR = [ 5,6,5]

     after op_2: ARR = [ 7,8,7]

     after op_3: ARR = [ 7,12,11]

          q3 : 2 3 [ perform operation 2,3 ] 

          after op_2: ARR = [ 9,14,13]

     after op_3: ARR = [ 9,18,17]

          So, Here is our Final Array :[ 9 18 17 ] that is the ans.

          Operation means Those N operation. We will make change in our initial array when we get the queries, else we won't perform anything.

          I hope You understand!

          → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone explain my solution of http://mirror.codeforces.com/contest/295/problem/A is giving wrong answer for test case 11 My code : http://mirror.codeforces.com/contest/295/submission/33406530

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the Div 1.B Greg and Graph problem in detail. I Know Floyd's algorithm. But how is it used in this problem.

What is the meaning of "We will not delete the vertices, but add (going from the end). At each step we will try to skip the path between all the vertices through a new one" in the editorial.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

    i know , i am late . for those who come after me. "going from end" means we are constructed the graph again. ex 1 test case 4 1 2 3 if we go like this (3 2 1 4), now imagine with me . first we have 3 and nothing else . so ans=0 then we have 2 and 3 , so we will only consider those edges 2 and 3 then similarly , we will have 2 3 1 and then 2 3 1 4

    we will apply flyod algo on each step while building the graph and then print the answers , check my solution(40024887) for more insight. and let me know if you can't.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's a very nice explanation of problem 295C — Greg and Friends. And here's my submission based on the logic discussed in the linked comment: 45487013

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the solution for div2c / div1a ? i can't understand it just from the editorial.

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

    This problem is from the topic difference array. (learn the logic before) The problem says - we need to perform operations from $$$x_i$$$ to $$$y_i$$$. Well, what's the operation? increase from $$$l_i$$$ from $$$r_i$$$ by $$$d_i$$$. That means, if we have array say $$$[1, 2, 3, 4, 5, 6 ]$$$ and we need to increase $$$[1, 3] by 5$$$, then we know that our $$$1st, 2nd$$$ and $$$3rd$$$ indices values are increase by $$$5$$$ times. Now, say our query has $$$[1, 3], [2, 4], [1, 3] [5, 6]$$$. Now as our query has $$$[1, 3]$$$ two times so, in $$$1st, 2nd$$$ and $$$3rd$$$ values we add $$$10$$$ to the array values others remain same.

    The whole process can be accomplished using difference array logic. First we need to find out how much difference does a query make to the difference array ? $$$dif[l]++, dif[r+1]--;$$$

    Then, after we have our initial difference array we can add it's values to $$$d_i$$$ to another difference array. After our $$$2nd$$$ difference array is processed then a linear scan will suffice :)

    my submission

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

      thanks!

      → Reply
    • »
      »
      »
      15 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you so much for specifying the topic at the beginning! It's a small thing, but it makes so much difference; thank you again, you're amazing

      → Reply