### unbelievable02's blog

By unbelievable02, history, 4 years ago,

Hello Codeforces!!!

Izho 2018 have been finished. I wish everyone the best awards. Let's solve the problems together and compensate our mistakes on olympiad.

• +2

 » 4 years ago, # |   0 Can anyone provide a hint for problem gift for 100 pts?
 » 4 years ago, # | ← Rev. 4 →   +8 A (chessboard)My opinion Just a dirty problem Hint 1 Obviously, side of squares in which we will divide the board must be a divisor of N Hint 2 See this (in Russian). We can approximate number of divisors with Hint 3 Let X be the side of squares in which we will divide the board Also, let Y be For white board answer is Main idea Think about taking answer for a white board, fixing X-s, and iterating over all subrectangles and carefully adding to/subtracting from the answer Figure out the remaining part of the solution yourself (with a pen and a paper)
•  » » 4 years ago, # ^ |   +3 First 3-4 subtasks are possible with brute force only, right?
•  » » » 4 years ago, # ^ |   0 Yes
 » 4 years ago, # |   +8 B (plan)Hint 1 If there is an edge between si and ti then it is better to just go through it. (Why?) Answer will be min(min(dist(si, gj)), min(dist(ti, gj))). Hint 2 We can precompute distances from all NPPs to other cities instead of computing them every time. Hint 3 (Hint 2 continued) Do usual Dijkstra but set all distances to NPPs to 0 and put them all in set at the beginning. Hint 4 Denote min(dist(v, gj)) as dv. Notice that for a path si, v1, ..., vk, ti answer is min(dsi, dv1, ..., dvk, dti). We need to find the "maximum" path Hint 5 (Hint 4 continued) So, for a particular edge (u, v) in the path we can say that its "weight" is min(du, dv). Hint 6 (Hint 4, 5 continued) Maximizing path si, v1, ..., vk, ti is equal to maximizing its edges Hint 7 (Hint 4, 5, 6 culminating) Maximum spanning tree Hint 8 (last, obvious) A query is now a "minimum on path in tree"-query. Figure out the remaining part of solution yourself — this is pretty popular problem.
 » 4 years ago, # | ← Rev. 2 →   +8 F (treearrray)Hint 1 (must figure out yourself) All vertices in an arbitrary answer are from subtree of v Hint 2 (important) In an arbitrary answer there must be two vertices from subtrees of different sons of v Hint 3 (super important) Denote t(v) a subtree of v (including v itself) Denote in(v) as a vertex that is in t(v) Denote out(v) as a vertex that is not in t(v) Denote v1, v2, ... as a first son of v, second son of v, etc. Array looks like ..., out(v), in(v), ..., in(v), out(v), ... An arbitrary answer may look like ..., in(v), ..., in(vi), in(vj), ..., in(v), ... (!!!) Hint 4 (easy) If there is v in the array then it is the answer itself Main idea (last, combining 3 & 4) If there is no answer (suitable subarray) of length 1 or 2 then there is no answer Figure out the remaining part of the solution yourself — it is just a matter of implementation
•  » » 4 years ago, # ^ | ← Rev. 5 →   0 Would you please explain me why answer is always subarray of length 1 or 2?And would You please define a notion of subarray?, is it a continuous segment in array?fact: depth[lca(a, b)] >= depth[lca(a, b, c)]Let's denote V as set of vertices which are in subtree(v), so if we'll increase size of V, lca of all vertices of V won't at least become more distant from v, so all we need to do is find two vertices(x, y), lca(x, y) = v & if we'll denote i as index of x and j as index of y in array, is it correct that all vertices in range[i, j] in array must be in subtree(v) to say that answer for current query is (x, y)?Thanks in advance!UPD: I forgot that fact that those vertices (x, y) must be in two different children of vertex v, how should I do there?UPD': Probably, I got it! Thank you very much! But here's last request to confirm something: if we have set of vertices V that all vertices locate in subtree of v, will it be correct & enough to consider always & only adjacent vertices from set V?
•  » » » 4 years ago, # ^ |   0 Last UPD: YES
•  » » » » 4 years ago, # ^ |   0 Thank you so much!
 » 4 years ago, # |   -8 My result is 0, JUST KILL ME!!!