Ask snarknews

Can you please elaborate?

My solution was segment tree on values (a[i]) and in each segment dynmic convex hull tree. Although I could avoid dynamic cht because the slopes were always increasing and so we could just binary search for queries.

Do you mean segment tree when you said divide and conquer?

• The answer to query "a b c" is c if and only if p(a) = 0 or p(b) = 0. Using this, find p^- 1(0) in n / 2 + const queries.

• Now you know s, t such that p(s) ≠ 0 and p(t) = 0. The answer to query "a s t" is s if and only if p(a) = 1. Using this, find p^- 1(1) in n + const queries.

• The remaining part is easy to do in n + const queries.

G : Calculate the area of ((initial polygon) U (final polygon) U (N fan shapes)) (fan shapes : rotating segments between origin and vertices)

-> sort by angle about origin. For each angle range, we can calculate the maximum radius of fan shape. Also, there would be exactly one segment from initial polygon and final polygon. Then we can calculate the union of fan shape and two triangles.

D: if n is even, it is just 10^n / 2. Otherwise, the real fun begins. What we need is the number of palindromes such that sum of even digits equals to the sum of odd digits.

Let's iterate over the central digit: if it is fixed, we need to find the number of pairs (n₁-digit number, n₂-digit number) such that the difference between their sum of digits is equal to a fixed δ. Let's take a look at a generating function of the counts of n-digit numbers with a given sum of digits s: f_n(x) = c_n, 0x⁰ + c_n, 1x¹ + ... c_n, sx^s + .... One can notice that f_n(x) = (1 + x + ... + x⁹)ⁿ = ((x¹⁰ - 1) / (x - 1))ⁿ. What we need is the coefficient for x^δ in f_n1(x)·f_n2(1 / x) = f_n1 + n2(x) / x^n₂. So in the end we just need to be able to compute a given coefficient of some f_k(x). One can derive it from the closed formula for f, or just use an existing formula, e.g.

C: If there are consecutive same color cells, just keep one of them. Now divide the colors into two groups. If a color have more than sqrt(n) cells, call them big color, otherwise small. For each big color, keep: (how many color adjacent to this big color are on, how many are of, what are the adjacent colors). For each small color, keep: (what are the small colors adjacent to this small color).

Now you can update in sqrt(n) in every query. Suppose you are altering a big color. So go to that color's list and update. Also visit all other big colors, if your updated big color is in them update them accordingly.

If some small color gets changed, go to all the big colors and check if your altered small color is adjacent to them. Also process the list in small color side.

Please note, there are not more than sqrt(n) big color. And the adjacency list size in small color side is sqrt(n).

K: If you can precompute [r1][c1][r2][c2] = can you go from r1,c1 to r2,c2 using a palindromic string, then rest is easy, just a dijkstra/dp.

How to compute this matrix? Think in reverse, initially all [i][j][i][j] is visited, also [i][j][i1][j1] where (i1,j1) is adjacent to (i,j). Next try to apply same move to both (i,j) and (i1,j1). That is, try to expand palindromic string. It can be done in O(50^4) bfs.

I have an O(N*sqrt(N)*log(N) ) solution but i don't know how to improve time complexity. I got TLE. My idea is to mix Mo's algorithm with palindromic tree, but i needed to use LCA on palindromic tree to speed up the jumps over the structure links. If somebody have an idea please share it.

wrong, ignore