codeforces-scrape

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

463.md (2394B)


      1 Source: https://codeforces.com/blog/entry/13631
      2 
      3 [463A - Caisa and Sugar](/contest/463/problem/A "Codeforces Round 264 (Div. 2)"). This is a simple implementation problem.
      4 
      5 [Sample solution.](http://ideone.com/3UrmLQ)
      6 
      7 [463B - Caisa and Pylons](/contest/463/problem/B "Codeforces Round 264 (Div. 2)"). 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.
      8 
      9 [Sample solution.](http://ideone.com/buuUUm)
     10 
     11 [463C - Gargari and Bishops](/contest/463/problem/C "Codeforces Round 264 (Div. 2)"). 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).
     12 
     13 [Sample solution.](http://ideone.com/yBx3so)
     14 
     15 [463D - Gargari and Permutations](/contest/463/problem/D "Codeforces Round 264 (Div. 2)").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.
     16 
     17 [Sample solution with graph.](http://pastebin.com/HMF1CeDq)
     18 
     19 [Sample solution with dp.](http://ideone.com/zZZG8y)
     20 
     21 [463E - Caisa and Tree](/contest/463/problem/E "Codeforces Round 264 (Div. 2)"). 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.
     22 
     23 [Sample solution.](http://ideone.com/AlivM9)