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.

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

1 | tourist | 3581 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Petr | 3161 |

4 | LHiC | 3158 |

5 | CongLingDanPaiSh…5 | 3116 |

6 | ko_osaga | 3115 |

7 | mnbvmar | 3111 |

8 | Um_nik | 3104 |

9 | Benq | 3098 |

10 | Swistakk | 3089 |

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

1 | Radewoosh | 185 |

2 | Errichto | 162 |

3 | rng_58 | 161 |

4 | tourist | 158 |

5 | Vovuh | 150 |

5 | Um_nik | 150 |

7 | Petr | 149 |

7 | Swistakk | 149 |

9 | 300iq | 148 |

9 | PikMike | 148 |

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.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/15/2018 12:49:26 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Can anyone provide a hint for problem gift for 100 pts?

A (chessboard)My opinionHint 1NHint 2Hint 3Xbe the side of squares in which we will divide the boardYbeMain ideaX-s, and iterating over all subrectangles and carefully adding to/subtracting from the answerFirst 3-4 subtasks are possible with brute force only, right?

Yes

B (plan)Hint 1s_{i}andt_{i}then it is better to just go through it. (Why?)min(min(dist(s_{i},g_{j})),min(dist(t_{i},g_{j}))).Hint 2Hint 3 (Hint 2 continued)Hint 4min(dist(v,g_{j})) asd_{v}. Notice that for a paths_{i},v_{1}, ...,v_{k},t_{i}answer ismin(d_{si},d_{v1}, ...,d_{vk},d_{ti}).Hint 5 (Hint 4 continued)u,v) in the path we can say that its "weight" ismin(d_{u},d_{v}).Hint 6 (Hint 4, 5 continued)s_{i},v_{1}, ...,v_{k},t_{i}is equal to maximizing its edgesHint 7 (Hint 4, 5, 6 culminating)Hint 8 (last, obvious)F (treearrray)Hint 1 (must figure out yourself)vHint 2 (important)vHint 3 (super important)t(v) a subtree ofv(includingvitself)in(v) as a vertex that is int(v)out(v) as a vertex that is not int(v)v_{1},v_{2}, ... as a first son of v, second son of v, etc.out(v),in(v), ...,in(v),out(v), ...in(v), ...,in(v_{i}),in(v_{j}), ...,in(v), ... (!!!)Hint 4 (easy)vin the array then it is the answer itselfMain idea (last, combining 3 & 4)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

Vas set of vertices which are insubtree(v), so if we'll increase size ofV, lca of all vertices ofVwon't at least become more distant fromv, soall we need to do is find two vertices(x, y),lca(x, y) = v& if we'll denoteias index ofxandjas index ofyin array, is it correct that all vertices in range[i, j] in array must be insubtree(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 vertexv, 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, will it beVthat all vertices locate in subtree of vcorrect & enoughto consideralways & onlyadjacent vertices from setV?Last UPD: YES

Thank you so much!

My result is 0, JUST KILL ME!!!