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

Автор NelsonMondialu, 10 лет назад, По-английски

463A - Caisa and Sugar. This is a simple implementation problem.

Sample solution.

463B - Caisa and Pylons. We have to use greedy method. Start from the first element and pass all the elements in order(also update by the energy).When energy < 0, add abs(energy) to solution and energy becomes 0 or we can find the answer by binary search.

Sample solution.

463C - Gargari and Bishops. We preprocess the sum for all the diagonals(principals and secondary diagonals) in two arrays(so that for every element i,j we can find sum of elements which are attacked in O(1) time).Also for avoiding the intersection,we need to find two cells so that for one the sum of row and column is even and for the other one the sum of row and column is odd.Finally,we analyze every cell ,we see if the sum of row and column is even or odd,and update that two positions(solutions).

Sample solution.

463D - Gargari and Permutations.We can build a directed acyclic graph with n nodes.If j is after i in all vectors then we add in graph edge (i,j).Now we have to find the longest path in this graph. Another way is using dp.

Sample solution with graph.

Sample solution with dp.

463E - Caisa and Tree. We use an array of dynamic stacks for every prime factor.We start a DFS from node 1.For node 1 we decompose its value in prime factors and push it to every prime factor's stack.To answer the question for x,we need to see the y (y belongs to the chain from 1 to x) that has a common prime factor with x,so the stacks will help us to see the earliest update(so the nearest y). For every x ,we decompose x to prime factors,look in the array and see the earliest update of the prime factors' stacks(if exists,of course). Also when we get back to fathers recursively,we need to pop from the prime factors' stacks. For every update we have to start dfs again.

Sample solution.

Полный текст и комментарии »

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

Автор NelsonMondialu, 10 лет назад, перевод, По-русски

Всем привет!

Приглашаю вам принять участие в двухчасовом Div2 раунде, который состоится в эту субботу 30-го августа в 11:30 по московскому времени. Как обычно, участники из первого дивизиона могут решать задачи вне конкурса.

Задачи были подготовлены мной и Archazey (задачи B и C). Хочу сказать спасибо Gerald за помощь в подговке раунда, Archazey за перевод задач на английский и MikeMirzayanov за создание Codeforces.

Главными героями задач сегодняшнего раунда будут Caisa и Gargari. Надеюсь задачи вам понравятся. Желаю удачи и удовольствия от контеста!

UPD: Будет использоваться стандартная разбалловка.

Полный текст и комментарии »

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