### fmota's blog

By fmota, history, 4 years ago, Let's discuss the problems
How to solve A and C ? ural, Comments (31)
 » What is the procedure to register for them??
 » A: Divide and Conquer in the direction of the value + Convex Hull Trick. If you D&C in normal wrong direction, you need dynamic CHT.
•  » » 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?
•  » » » 4 years ago, # ^ | ← Rev. 4 →   Maybe you did in wrong direction. I mean that, let C be (max(a) - min(a)) / 2. split a1~an into two groups Lower and Upper such that ai < C in Lower and ai ≥ C in Upper. first, calculate DP table of Lower recursively. second, propagate DP table of Lower to DP table of Upper. this can do by Convex Hull Trick. third, calculate DP table of Upper recursively. Use a' such that pair(ai, i) is a'i -th smallest in n elements, instead of a.
 » 4 years ago, # | ← Rev. 2 →   How to solve F?As I understand, we need to find such x that p(x) = 1. But how to find x using  ≤ 7500 queries?
•  » » 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.
•  » » » You said: The answer to query "a b c" is c if and only if p(a) = 0 or p(b) = 0.But, p(a)p(b)+p(c)=p(c) means p(a)p(b)= multiple of n, not necessarily one of them has to be 0 right? For example one is 2 and the other is n/2. Probably I am misunderstanding you?
•  » » » » Yes, I missed that.Still, in n / 2 queries, we can limit the candidates of p - 1(0), and with a few hundreds of extra random queries we should be able to determine p - 1(0). The same works for p - 1(1) — I wrote n but actually it's n / 2 again. So, we have 2512 queries in total for extra random queries.
•  » » » » » I also used random queries, but are there no way to solve without randomized algorithm? The statement said that there is a deterministic solution which works for every possible permutation.
 » How to solve D, E, I and G?
•  » » 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.
•  » » 4 years ago, # ^ | ← Rev. 2 →   D: if n is even, it is just 10n / 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 (n1-digit number, n2-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: fn(x) = cn, 0x0 + cn, 1x1 + ... cn, sxs + .... One can notice that fn(x) = (1 + x + ... + x9)n = ((x10 - 1) / (x - 1))n. What we need is the coefficient for xδ in fn1(x)·fn2(1 / x) = fn1 + n2(x) / xn2. So in the end we just need to be able to compute a given coefficient of some fk(x). One can derive it from the closed formula for f, or just use an existing formula, e.g.
•  » » » I don't get how you are calculating fn(x) faster than O(n2). My approach is to differentiate this polynom by x and get a recursive formula for its coefficients from the following equality: nfn(x)(1 + 2x + ... + 9x8) = f'n(x)(1 + x + x2 + ... + x9).
•  » » » » I don't need to calculate fn(x) altogether: I just need to calculate a single coefficient of it 10 times, so it's just 10 O(n) computations.
•  » » » » » Ah, I see, you are exploiting the fact that polynom is symmetric.
•  » » » » We tried following nlogn but resulted tle.Basically f^n = ifft(n*fft(f)).And since the mod was not a friendly one so we took two different primes. Is this approach wrong?
•  » » » » How is nfn(x)(1 + 2x + ... + 9x8) = f'n(x)(1 + x + x2 + ... + x9) helpful to compute the coefficients of f?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   Suppose fn(x) = a0 + a1x + a2x2 + ... What is coefficient for xi in this equality? On the left we have nai + 2nai − 1 + ... + 8nai − 8. On the right we have (i + 1)ai + 1 + (i)ai + ... + (i − 8)ai − 8. Subtract one from the other and you have (i + 1)ai + 1 equal to linear combination of 9 previous coefficients. You only need a0 = 1 to start recurrent calculations (assume all negative coefficients are zero).
 » How to solve C and K?
•  » » 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).
•  » » » Could you explain please how you calculate the answer after update? I'm still not understand what do you do with the values you keep
•  » » 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.
 » How to solve J?
 » 4 years ago, # | ← Rev. 5 →   Bad post. Ignore it.
 » anyone willing to post solution for H?
•  » » 4 years ago, # ^ | ← Rev. 2 →   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.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   Why not LCA in O(1) with Sparse Table?
•  » » » » because i need to perform some other operations on each jump, i need to find the longest palindrome that start at a position i with lenght less or equal to some x. The x is variable among the queries, so i can't precompute the hole sparse table.
•  » » 4 years ago, # ^ | ← Rev. 3 →   wrong, ignore
 » What is GP of Ural?