codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

296.md (8285B)


      1 Source: https://codeforces.com/blog/entry/7329
      2 
      3 [296A - Yaroslav and Permutations](/contest/296/problem/A "Codeforces Round 179 (Div. 2)")  
      4 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.  
      5 [296B - Yaroslav and Two Strings](/contest/296/problem/B "Codeforces Round 179 (Div. 2)")  
      6 Будем решать обратную задачу: посчитать количество способов сделать сравнимые пары.  
      7 Для начала посчитаем количество способов сделать первую строку меньше равной второй.  
      8 Это количество равно произведению количества способов сделать это для каждой позиции по отдельности,так как они все позиции независимы. Посчитаем такую же величину, но когда вторая строка меньше-равна первой. И аналогично посчитаем количество способов сделать две строки равными. Для каждого символа величины можно считать простым циклом.  
      9 Теперь возьмем величину 10 в степени количества знаков вопроса во входном файле и отнимем полученный ответ на обратную задачу, это и будет ответом.  
     10 [295A - Greg and Array](/contest/295/problem/A "Codeforces Round 179 (Div. 1)")  
     11 Для того, что бы прибавить значение d на отрезке [x,y] достаточно завести массив b и поставить значения  
     12 b[x] += d  
     13 b[y+1] -= d  
     14 Дальше за один проход по массиву легко восстанавливаются все числа.  
     15 Применим данный метод дважды: сначала для запросов, а потом для операций(зная сколько раз мы ее выполним).  
     16 [295B - Greg and Graph](/contest/295/problem/B "Codeforces Round 179 (Div. 1)")  
     17 Для решения задачи нужно хорошо понимать принцип работы алгоритма Флойда.  
     18 Общий вид алгоритма Флойда:  
     19 for (k=1;k<=n;k++)  
     20  for (i=1;i<=n;i++)  
     21  for (j=1;j<=n;j++)  
     22  a[i][j] = min(a[i][j], a[i][k]+a[k][j]);  
     23 То есть на каждом шаге мы пытаемся пропустить путь через вершину К.  
     24 Будем не удалять вершины, а добавлять(идя с конца).  
     25 На каждом шаге будем пробовать пропустить путь между всеми вершинами через новую.  
     26 Таким образом мы получим решение, работающее за кубическое время.  
     27 [295C - Greg and Friends](/contest/295/problem/C "Codeforces Round 179 (Div. 1)")  
     28 Заметим, что на каждом шаге нас интересует только положение лодки(номер берега) и количество людей веса 50 и 100 на каждом береге. При чем количество людей на одном береге полностью определяется через другой.  
     29 Для поиска минимального количества переправ будем использовать волновой алгоритм, основанный на этом состоянии.  
     30 Для нахождения количества способов просто добавим сумму всех переходов в состояние при переходе будем переносить все способы из одного состояния в другое умножая на количество способов выбрать людей, которые нужны для перехода из одного состояний в другое.  
     31 [295D - Greg and Caves](/contest/295/problem/D "Codeforces Round 179 (Div. 1)")  
     32 Будем пользоваться динамическим программированием: dp[i][j] — сколько существует способов построить фигуру, что в строке i будет ровно j столбцов занятыми черными клетками и всем, что между ними. При этом фигура должная не убывать (иными словами мы берем только верхнюю часть фигуры).  
     33 Как делать переход? Заметим, что dp[i][j] = 1+dp[i-1][2] * (j-2+1)+ ... +dp[i-1][l] * (j-l+1)+ ... +dp[i-1][j].  
     34 Распишем это: 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).  
     35 Понятно, что если завести частичные сумму, то данные величины считать становится очень просто.  
     36 Как посчитать полный ответ: будем перебирать номер максимального подходящего t(обозначенного в условии).  
     37 Теперь единственное отличие, это то что следующая строка должна содержать строго меньше столбцов. То есть имеем аналогичный переход, с -1 слагаемым.  
     38 Так же заметим, что зафиксировав "основу" мы должны домножить количество способов на число способов разместить ее на плоскости, то есть основу шириной j мы можем поставить (m-j+1) способами.  
     39 [295E - Yaroslav and Points](/contest/295/problem/E "Codeforces Round 179 (Div. 1)")  
     40 Научимся решать задачу: найти сумму расстояний между точками.  
     41 Если расписать, что происходит при добавлении одной точки, то получим формулу: x_i*(2*i-n) Где x_i — отсортированные координаты, а n общее количество точек.  
     42 Научимся зная ответы для двух отрезков точек знать ответ для их объединения.  
     43 Понятно, что для подсчета такой информации нужно всего лишь сложить два ответа,  
     44 и добавить сумму координат первого множества умноженное на некоторое число и  
     45 и добавить сумму координат второго множества умноженное на некоторое, возможно другое, число.  
     46 Таким образом зная ответы для некоторых отрезков общий ответ.  
     47 Будем использовать корневую декомпозицию или декартово дерево для хранения таких отрезков.  
     48 Не сложно понять, что вставка и удаление делается достаточно быстро для этих структур.  
     49 Например для корневой декомпозиции можно каждый раз просто вырезать и вставлять точку в нужные отрезки, а если множество стало содержать длинные отрезки или много отрезков, то просто перестроим его заново. Асимптотика решения не меняется.