Let's discuss the problems

How to solve A and C ?

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | W4yneb0t | 3218 |

3 | TakanashiRikka | 3178 |

4 | Petr | 3173 |

5 | moejy0viiiiiv | 3158 |

6 | LHiC | 3113 |

7 | izrak | 3109 |

8 | anta | 3106 |

9 | ershov.stanislav | 3105 |

10 | cubelover | 3071 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 178 |

2 | csacademy | 171 |

2 | tourist | 171 |

4 | Petr | 162 |

5 | Swistakk | 161 |

6 | Errichto | 156 |

7 | Zlobober | 151 |

8 | matthew99 | 145 |

9 | Endagorion | 142 |

10 | zscoder | 135 |

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2017 01:17:27 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|

What is the procedure to register for them??

Ask snarknews

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?

Maybe you did in wrong direction. I mean that,

Cbe (max(a) -min(a)) / 2.a_{1}~a_{n}into two groups Lower and Upper such thata_{i}<Cin Lower anda_{i}≥Cin Upper.Use

a' such thatpair(a_{i},i) isa'_{i}-th smallest innelements, instead ofa.How to solve F?

As I understand, we need to find such

xthatp(x) = 1. But how to findxusing ≤ 7500 queries?The answer to query "

abc" iscif and only ifp(a) = 0 orp(b) = 0. Using this, findp^{ - 1}(0) inn/ 2 +constqueries.Now you know

s,tsuch thatp(s) ≠ 0 andp(t) = 0. The answer to query "ast" issif and only ifp(a) = 1. Using this, findp^{ - 1}(1) inn+constqueries.The remaining part is easy to do in

n+constqueries.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 ofp^{ - 1}(0), and with a few hundreds of extra random queries we should be able to determinep^{ - 1}(0). The same works forp^{ - 1}(1) — I wrotenbut actually it'sn/ 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.

D: if

nis 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_{1}-digit number,n_{2}-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 ofn-digit numbers with a given sum of digitss:f_{n}(x) =c_{n, 0}x^{0}+c_{n, 1}x^{1}+ ...c_{n, s}x^{s}+ .... One can notice thatf_{n}(x) = (1 +x+ ... +x^{9})^{n}= ((x^{10}- 1) / (x- 1))^{n}. What we need is the coefficient forx^{δ}inf_{n1}(x)·f_{n2}(1 /x) =f_{n1 + n2}(x) /x^{n2}. So in the end we just need to be able to compute a given coefficient of somef_{k}(x). One can derive it from the closed formula forf, or just use an existing formula, e.g.I don't get how you are calculating

f_{n}(x) faster thanO(n^{2}). My approach is to differentiate this polynom byxand get a recursive formula for its coefficients from the following equality:nf_{n}(x)(1 + 2x+ ... + 9x^{8}) =f'_{n}(x)(1 +x+x^{2}+ ... +x^{9}).I don't need to calculate

f_{n}(x) altogether: I just need to calculatea single coefficientof it 10 times, so it's just 10O(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

nf_{n}(x)(1 + 2x+ ... + 9x^{8}) =f'_{n}(x)(1 +x+x^{2}+ ... +x^{9}) helpful to compute the coefficients of f?Suppose

f_{n}(x) =a_{0}+a_{1}x+a_{2}x^{2}+ ... What is coefficient forx^{i}in this equality? On the left we havena_{i}+ 2na_{i − 1}+ ... + 8na_{i − 8}. On the right we have (i + 1)a_{i + 1}+ (i)a_{i}+ ... + (i− 8)a_{i − 8}. Subtract one from the other and you have (i + 1)a_{i + 1}equal to linear combination of 9 previous coefficients. You only needa_{0}= 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?