EigenScore
EigenScore
An FX market quotes m exchange rates between n currencies. A quote i j r means one unit of currency i converts into r units of currency j. Quotes are one-directional; the reverse conversion exists only if it is separately quoted.
An arbitrage is a sequence of conversions that starts and ends in the same currency and strictly multiplies the amount held: currencies c_1, c_2, ..., c_k (k >= 2, all distinct) such that every conversion c_1 -> c_2, ..., c_{k-1} -> c_k, c_k -> c_1 is quoted and the product of their rates exceeds 1.
Determine whether an arbitrage exists, and exhibit one if so.
The first line contains n and m. Each of the next m lines contains i, j and r: a quote from currency i to currency j at rate r, a positive number with at most 8 digits after the decimal point. Currencies are numbered 1 to n. No pair (i, j) is quoted twice.
If no arbitrage exists, output NO.
Otherwise output YES, then on the next line k, then on the next line the currencies c_1 ... c_k of any arbitrage cycle. Any valid cycle is accepted.
2 <= n <= 250
1 <= m <= 12000
0.1 <= r <= 10
This is a standard problem: a submission scores full points if it produces the correct output for every test case, and zero otherwise.
3 3 1 2 1.10000000 2 3 1.10000000 3 1 0.90000000
KEY YES 3 3 1 2 1.10000000 2 3 1.10000000 3 1 0.90000000
3 3 1 2 1.10000000 2 3 1.10000000 3 1 0.80000000
KEY NO 3 3 1 2 1.10000000 2 3 1.10000000 3 1 0.80000000