NelsonMondialu's blog

By NelsonMondialu, 10 years ago, In English

463A - Caisa и сахар. This is a simple implementation problem.

Sample solution.

463B - Caisa и колонны. 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 и слоны. 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 и перестановки.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 и дерево. 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.

Full text and comments »

  • Vote: I like it
  • -15
  • Vote: I do not like it

By NelsonMondialu, 10 years ago, In English

Hello everyone,

I'd like to invite you to participate in a 2-hours Div2 round which will be held this Saturday, August 30th at 11:30 AM MSK. Div1 coders can take part out of competition, as usual. The problems were prepared by me and Archazey (B and C). I'd like to thank Gerald for helping preparation, Archazey for english translation and MikeMirzayanov for the Codeforces system.

The main characters of this round will be Caisa and Gargari,which have some interesting tasks for you. I hope you will enjoy the round. Good luck and have fun!

UPD: It will be used a standard scoring.

Here are the winners:

1.lymmd

2.for_the_pride

3.danilka.pro

4.zld3794954

5.nxihkke

Stats about hacks can be found here.

Editorial is here.

Full text and comments »

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