A profitable round of exchanges
You are given exchange rates: “x units of currency A buy y units of currency B”. Is it possible, starting with some sum in some currency, to make several exchanges and come back to the same currency with a larger sum? If it is, show such a round.
The rates are integer, and the check is exact: the product of the rates y/x along your round must be strictly greater than one. Tests 3 to 6 are the real reference rates of 9 October 2026, as in the article: the National Bank's tenge rates, the ECB's euro rates, together and separately, and the ECB table re-based to each currency and rounded.
Input
The first line holds n and m, the number of currencies and the number of rates (2 ≤ n ≤ 200, 1 ≤ m ≤ 6000). Then m lines A B x y: currency codes of three capital Latin letters and two integers, 1 ≤ x, y ≤ 3 · 109. A pair of currencies may have several rates; any of them may be used. It is guaranteed that if a profitable round exists, there is also a round that increases the sum by at least one millionth of it.
Output
NO if there is no profitable round. Otherwise YES and on the second line the currency codes of the round in the order of exchanges, the first and last being the same currency, for example KZT ZAR EUR KZT. Any profitable round will do.
Examples
Example 1
3 4 AAA BBB 1 2 BBB CCC 1 3 CCC AAA 5 1 BBB AAA 2 1
YES AAA BBB CCC AAA
Example 2
3 4 AAA BBB 1 2 BBB CCC 1 3 CCC AAA 6 1 AAA CCC 1 6
NO
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Products are awkward for shortest path algorithms. How do you turn a product of rates into a sum, and “greater than one” into “less than zero”?
2Hint 2
Take −log of the rate. A profitable round is a cycle of negative length. It need not be searched for from one currency: you can start from all at once.
3Hint 3
In the fourth test every currency has a rate to the tenge and the reverse one, and their product is exactly 1. What will your program say?
4The idea
Let the weight of the edge A → B be log x − log y. Then the product of rates along a round is greater than one exactly when the sum of the weights is negative; this is the problem of finding a negative cycle, and Bellman–Ford solves it. To find a cycle in any part of the graph, not only one reachable from a single currency, start from all vertices at once: all distances are zero, as if there were an invisible currency with edges of length 0 into every other. If the n-th round still improved something, take n steps back along the parent pointers from the last improved vertex, and you are on the cycle.
5Walkthrough
The main trap is precision. The National Bank's rates QAR → KZT and KZT → QAR are 12,317/100 and 100/12,317, and their product is exactly 1. But floating-point logarithms add up to −10−16 or +10−16, as luck would have it, and a program without a margin finds “profit” where there is none: on the fourth test it answers YES and offers the round KZT → QAR → KZT. So an improvement counts only if it is greater than 10−9. This is safe: by the statement a profitable round, if there is one, gives at least 10−6 in logarithms, and a round of 200 edges losing at most 10−9 on each edge will not be missed.
You can do without logarithms too, comparing products of fractions exactly, but the numerators and denominators after two hundred exchanges become huge. Logarithms with a margin are simpler, and the condition about a millionth is enough for them.
On the real rates the outcome is the same as in the article. Separately the National Bank and the ECB are consistent: all rates go through the tenge or through the euro, and no round with profit exists. Together they diverge, and the round ZAR → EUR → KZT → ZAR is found. And the rounded ECB table gives “profit” from rounding alone: buy rupiah for dollars and sell them straight back.
5+Solution
6Complexity
O(n · m): at most n rounds over all rates, and the rounds stop earlier if nothing changes.
7Common mistakes
- Comparing without a margin. The fourth, fifth, seventh and twelfth tests: exact rates and “profit” from rounding errors.
- Searching from one currency only. In the seventh and eighth tests a profitable round may be unreachable from the chosen currency.
- Printing the path to the cycle instead of the cycle. The last improved vertex may hang on a tail leading to the cycle rather than lie on it: first take n steps back.
- Dijkstra. The weights are negative, and a currency already processed may become cheaper; see the trap in the article on Dijkstra.