Good luck)

Also with first 1/8 fifa game [Brazil — Chile] Sad. hadn't decide which one I will choose.

У Anuar было так же.

The graph is directed.

Считаем, какая вероятность получить ровно i для каждого игрока (например, динамикой), пусть это p_i для первого и q_i для второго. Тогда ответ — по определению матожидания. И надо не забыть про случай с "-1".

http://ru.wikipedia.org/wiki/Условная_вероятность

Какая?

Не очень понял, чем помогает OEIS. То, что нужно посчитать сумму квадратов взаимно простых, вроде и так ясно?

Не говоря уже о том, что практически та же самая задача есть на ProjectEuler: http://projecteuler.net/problem=202

А мне одного балла не хватило до зеленого(

в practice room можно отсылать на проверку

Your solution may have passed the given test cases, but it was not correct.

The person who hacked(challenged) your solution found a test case, where your algo gave the wrong output

Я так решал: Посчитаем сначала кратчайшие расстояние между всеми парами вершин, без использования отрицательных ребер. Допустим это G[u][v].

Теперь будем считать кратчайшие пути с использование не более 2ⁱ отрицательных ребер. F[i][u][v] — длина кратчайшего пути из u в v используя не более 2ⁱ отрицательных ребер.

Для 2⁰ — посчитаем влоб: для всех пар u и v выберем минимум по всем ребрам (from_i, to_i, w_i) выражения G[u][from_i] - w_i + G[to_i][v]. Пусть это будет F[0][u][v].

Для остальный 2ⁱ при i > 0 будем считать так:
F[i][u][v] = min(F[i - 1][u][v], min_w(F[i - 1][u][w] + F[i - 1][w][v]).
Т.е. переберем некоторую промежуточную вершину w и воспользуемся 2^i - 1 отрицательными ребрами на пути от u к w и на пути от w к v.

Теперь чтобы посчитать ответ с заданным ограничением — разобьем наш лимит на количество отрицательных ребер по степеням двойки и соберем ответ. Пусть наш лимит . Я решал это динамикой по типу Форда-Беллмана -- dp[i][u] — минимальная стоимость пути от исходной вершины, причем мы шагнули через первые i степени двойки из need.
dp[0][0] = 0.
dp[i][v] = min_u(dp[i - 1][u] + F[need_i - 1][u][v]).

Ответ min(dp[|need|][n - 1], G[0][n - 1]).

Ассимпотика получается примерно такой: O(V²·E + V³·log(charges)).

У меня другое решение. Работает за O(n⁵), это полторы секунды на случайном тесте максимального размера. Возможно, можно подумать и сократить время работы хотя бы до O(n⁴).

1. Посчитаем динамикой f(k, u, v): минимальное расстояние от вершины u до вершины v при инвертировании не более чем k рёбер по пути. Пригодится таблица примерно до k ≤ n² + n. У меня это делается за O(n⁵).

2. Интуитивно понятно, что для очень больших значений charges выгодно потратить почти все заряды в наиболее «удельно выгодном» для этого цикле данного графа — то есть найти такую вершину u на цикле и такое k > 0, что отношение f(k, u, u) / k максимально. Возможно, нужно будет ещё потратить немного зарядов по дороге от начальной вершины до этого цикла, а также по дороге от этого цикла до конечной вершины. Естественно, пути от начала до u и от u до конца должны существовать.

3. Утверждение (без доказательства): оптимальный путь состоит из предпериода длины r ≤ n², периода длины d ≤ n, повторённого целое число раз s, и постпериода длины t ≤ n². То есть ответ — это минимум f(r, 1, u) + f(d, u, u)·s + f(t, u, n), где r + d·s + t = charges.

4. Переберём длину предпериода и длину периода. Длину постпериода будем подбирать как можно ближе к n² + ε, чтобы не перебирать. Если она получится слишком большая, в ней окажется ещё несколько копий периода. У меня это делается за O(n⁴).

5. Пример теста (взлом), в котором предпериод и постпериод не могут одновременно быть порядка n: ориентированный цикл из n вершин, в котором можно в одном месте сократить путь на одну вершину. Если, например, n = 50, цикл перебирает вершины по порядку и нужно сделать ровно 2425 шагов от вершины 1 до вершины n, то у диофантова уравнения x·50 + y·49 + 49 = 2425 есть единственное решение с ограничениями x ≥ 0 и y ≥ 0: это x = 24 и y = 24. То есть нужно 24 раза пройти по одному пути и 24 раза по другому в любом порядке.

dp[a][b][c] — answer for way from a to b with c charges.

1. if c==0 then answer is shortest path (floyd helps)

2. if c is even then for some vertex i answer is dp[a][i][c/2]+dp[i][b][c/2]. for all such i we take best.

3. if c is odd then instead of vertex we choose edge (i,j) and answer is dp[a][i][c/2] + dp[j][b][c/2] — weight(i,j).