G: Let's find a closest point to the given three(that the max distance is the smallest) This can be done by 2 ternary searches : one by X-coordinate and the second by Y-coordinate

G: If an answer exists, it can be a point for which 2 of 3 inequalities are actually equalities, so it's the 3rd vertex of an iscosceles triangle with base (or or , you can try all 3). Consider : let , then — we decide that P is supposed to be at (height of ) from the center of the base and that it lies on that height. Finding a perpendicular vector in 2D is easy, so we can calculate the coordinates of . Then, it suffices to check if it's close enough to the 3rd vertex of our triangle.

E: The time (from 0) until the 1st superpositions without star j is , because star i is directly above us exactly at all integer multiples of l_i. We just need to find these LCMs, for each one (call it L) check if it isn't too large, and find the smallest k such that kL ≥ M and (if l_j|L, then it's impossible, otherwise if k doesn't work, then k + 1 certainly does), and check if the answer isn't too large again. Since LCM is associative, we can calculate the LCM of all elements in an array except the j-th as LCM(LCM of all l_i: i < j, LCM of all l_i: i > j), and these 2 can be pre-calculated as prefix and suffix sums... well, LCMs.

D — заметим, что внутри леса нам вообще не важно число V, мы всегда можем делать внутри него сколько угодно ходов. Это нам оставляет 3 возможных перехода : точка (то есть клетка без леса) — точка, точка — лес, лес — точка. Понятно, что когда мы делаем первый или третий переход — мы платим за это 1 движение, а когда заходим в лес из точки, мы можем сказать что до клетки с лесом расстояние 0 (типа забываем про все что делали до этого, и просто ходим из этой клетки как из начала). Ну вот, сделаем что — то вроде алгоритма дейкстры, если расстояние до вершины, которую мы достали из очереди уже >= v, то забиваем на эту вершину, иначе делаем переходы выше, если улучшили ответ опять кидаем в очередь. O(NMlogNM)

C — сделаем бинпоиск по ответу, теперь пустим поиск в глубину, состояние будет (вершина, 0 или 1). 0 будет, если мы еще не проходили по ребру, строго большему чем наш ответ, и 1 иначе. Если у нас сейчас в состоянии 0, то переходим по любым ребрам, не забыв проверить, что новое ребро не больше чем ответ (иначе говорим что в новом состоянии будет 1), а если у нас и так 1, то переходим только по ребрам, не большим чем наш ответ. O(NlogAns)

Как решать J?

Это случайный тест с n=5, и он не последний. Ну, не совсем случайный, он сгенерирован так, чтобы ответ балансировал на грани.

Notice that all you need is an increasing subsequence of a_i (and similarly of b_i), constructed by taking the first element, then the first one greater than the first, etc. always the first greater one, since if a_j ≤ a_i for j > i, then if a_j could do anything, then a_i would do that earlier. You can store each subsequence in a map of (a_i, i).

This way, you can find the first joke that would make either person laugh (or that there's none), just by taking lower_bound(). Then it's just about checking which one goes first.

В первой правке

6 test is a random test with n = m = 100, try to stress your solution locally

Sort all the points, then check whether all the points are "zoomed" from the original one compared to the first point, just check the gradient and distance.

I solved it with shortest path, need to read the statement carefully.

Imagine you're going X rooms to the right. While going to the right you can remember what is the state for each room you went through. Now after going X rooms right, switch the states of the candles in the last room and go X rooms left. If cycle is longer than X then you will observe all X rooms in the state as you left them while going to the right. Otherwise you will find the difference and you will be able to calculate the cycle length.

Now to make number of steps no more than 10·N you can start with small X and if you didn't find the cycle with such X make it two times bigger and try again.

My submission: 6994198

PS: Though I have no idea whether it is an intended (if there is any at all) solution or not, just shared an idea which seems to be simple to implement.