Do 3 BFSes. Let G be the graph formed by the dependencies and G' be the same graph, with all its edge inverted. (changed direction)

Now, note that each correct labelling must "meet" at some point u (This may include 0, a or b), so the answer is the minimum possible value of this over all possible u :

Distance from 0 to u in G + Distance from a to u in G' + Distance from b to u in G'.

im

up

This is a max flow problem. A similar problem has appeared before ( Kyoto University Programming Contest 2016 — Problem E ), the difference is that the squares are weighted, we only need to block one square and we have to provide a certificate.

I've explained the solution in the link above. The only modification needed is the capacities of each square (change it to the respective weights). To construct a possible solution, we just have to find the minimum cut.

My code : here (I've used min cost flow as initially I thought that min cost flow is needed, but it turns out that max flow is sufficient)

Problem C: Call the output array res[]. For all number a from 0 to p-1, we calculate b = a^2 % p. Then res[b] = a.

B: Sort all dragons by (a — b), then do simulation from the end: imagine you have zero warriors at the beginning, then you fight dragons in sorted order, and after each fight you resurrect some warriors. If you don't have enough warriors, add some to be able to fight next dragon (you need (a — b) warriors to fight dragon because we're resurrecting warriors, not killing them).

There's some reasonable explanation why it works: if we sort dragons by amount of warrioirs needed to fight them, then total amount of warriors after all battles with dragons in sorted order will be minimal, it's greedy algorithm. Try represeniting dragons as oriented segments from a to a — b in number line to see why it works.

Well, I actually had more reasonable explanation when I was solving this problem, but that was 1.5 months ago and I already forgot it :D

My solution: http://pastebin.com/snwTke9g

It seems like 0.916297857297023 came from but idk why this is the answer either.

What you described was an intended solution.

Jury got the answer using this article: https://en.wikipedia.org/wiki/Radiodrome and some binary search and numerical integration. It calculates 7 correct digits in 1 second.

There is also a math solution, here is a document (in Russian, but you should be able to read formulas): https://yadi.sk/i/-BcFxkTry7mZm

Scanline. Events are: zork and axe. Sort all events by weight (for zorks weight is minimum axe weight they need), then go by events in reversed sorted order (from biggest weight to smallest). Maintain a set where you store curvature of all avaible axes. When you meet axe, add it to the set. When you meet zork, give him axe of minimum avaible curvature he can take (in other words axes.lower_bound(zork.curvature). Try imagining all events as points (x: weight, y: curvature) on coordinate plane to see why it works.

My solution: http://pastebin.com/j7JtgWZu

Solution "multiply answer from sample by square of distance between two points" was intended by jury. Read dalex comment above.

Answer is maximum element in array. It can be proven by induction.

I: find vertex of minimum degree and place policemen in all verticles except vertex of minimum degree and its neighbours.

J: every time a[i] > a[i-1] it means that there're a[i] — a[i-1] photos beginning at building i. So you have to find sum of max(a[i] — a[i-1], 0) for all i = 1..n (a[0] = 0)

Simulate a direct elimination table with the n people. Every time you get i < j, store i in the vector of all people that lost against j. When you only have one guy left, then you now it is the guy with the highest rank. This needs n-1 queries.

Then, simulate another elimination table with people that lost against the guy with the highest rank. This needs O(log(n)) queries. Therefore, you will always need strictly less than n+24 queries.

Note that, if you search for the guy with the highest rank naively, than the second part may need O(n) queries in the worst case, which is not good.

Let tab[i] the number of '('s that are necessary in the first i characters in order to get a valid sequence, then compute t[n], tab[n-1], ... tab[1] (this is actually dynamic programming).

Then, using this array, replace '?'s greedily from left to right in the sequence.

Then, check whether the resulted sequence is valid or not.

You're not excused, read the first comment and reply