We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Amount After Two Days of Conversions

Number: 3613

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

You are given an initial currency and start with 1.0 unit of it. There are two sets of conversion rules provided as currency pairs with associated rates – one set for day 1 and one set for day 2. For each conversion given (from A to B with rate r), the reverse conversion (from B back to A) is also allowed at rate 1/r. On day 1, you can perform any number of conversions using the first set, and then on day 2, any sequence of conversions using the second set. The task is to determine the maximum amount of the initial currency you can end up with after applying conversions on day 1 followed by day 2.

Key Insights

  • Both day1 and day2 conversion rules form a bidirectional graph, where each edge is available in both directions (with the inverse rate used for the reverse conversion).
  • The problem can be separated into two independent stages: • Compute the maximum conversion multiplier from the initial currency to every other currency on day 1. • Compute the maximum conversion multiplier from any currency back to the initial currency on day 2.
  • Using a relaxation algorithm (similar to Bellman–Ford for maximum products) works because the graphs are small and there are no arbitrage cycles that allow infinite profit.
  • Finally, the answer is the maximum product over all intermediate currencies v, where the overall multiplier is the product from day1 (S→v) and day2 (v→S).

Space and Time Complexity

Time Complexity: O(V * E) per day where V is the number of currencies and E is the number of conversion pairs (including both directions); given the constraints, V and E are very small. Space Complexity: O(V + E) for storing the graph and the multiplier arrays.

Solution

We first build the conversion graph for day 1 using the provided currency pairs and their inverses. We then use a relaxation algorithm to compute the highest conversion factor from the initial currency to every other currency. For day 2, our goal is to compute the maximum conversion factor from any currency back to the initial currency. To do this efficiently, we reverse the direction of edges (which effectively computes the maximum multiplier from the currency to the initial) and again use the relaxation algorithm starting from the initial currency. Finally, we iterate through all currencies and compute the product of the maximum multiplier from day 1 (S to v) and day 2 (v to S), and return the maximum product.

The key trick is that by decomposing the problem into two separate maximization steps, we can easily combine the best conversion multiplier from day 1 with the best "reverse" conversion multiplier from day 2 for each currency. Since the conversion graphs are bidirectional with known inverse rates, the relaxation approach (over at most |V| - 1 iterations) suffices to compute the optimal conversion factors.

Code Solutions

# Python solution
def maximizeAmount(initialCurrency, pairs1, rates1, pairs2, rates2):
    from collections import defaultdict

    # Helper: Build a bidirectional graph from pairs and rates.
    # Graph is represented as: graph[currency] = list of (neighbor, conversion_rate).
    def build_graph(pairs, rates):
        graph = defaultdict(list)
        for (start, target), rate in zip(pairs, rates):
            graph[start].append((target, rate))
            graph[target].append((start, 1.0 / rate))
        return graph

    # Helper: Perform maximum conversion factor relaxation using a Bellman-Ford style algorithm.
    # start is the starting currency.
    def get_max_conversion(graph, start):
        # Initialize best multiplier for each currency.
        best = defaultdict(float)
        best[start] = 1.0
        # Get all unique currencies
        currencies = set(graph.keys())
        for key in graph:
            for neighbor, _ in graph[key]:
                currencies.add(neighbor)
        # Relax for (|V| - 1) iterations.
        for _ in range(len(currencies) - 1):
            updated = False
            for u in currencies:
                if best[u] > 0:
                    for v, rate in graph[u]:
                        # If conversion from u to v increases the multiplier, update best[v]
                        if best[u] * rate > best[v]:
                            best[v] = best[u] * rate
                            updated = True
            if not updated:
                break
        return best

    # Build graphs for day1 and day2.
    graph1 = build_graph(pairs1, rates1)
    graph2 = build_graph(pairs2, rates2)
    
    # Day1: maximum multiplier from initialCurrency (S) to every other currency.
    best_day1 = get_max_conversion(graph1, initialCurrency)
    
    # To compute maximum multiplier from any currency to initialCurrency on day2,
    # we build the reverse graph of day2.
    # For each edge u->v with rate r in graph2, add edge v->u with rate r in reverse graph.
    reverse_graph2 = defaultdict(list)
    for u in graph2:
        for v, rate in graph2[u]:
            reverse_graph2[v].append((u, rate))
    
    best_day2 = get_max_conversion(reverse_graph2, initialCurrency)
    
    # Compute the maximum overall product by trying all intermediate currencies.
    max_amount = 0.0
    # We combine all currencies that appear in either day.
    all_currencies = set(list(best_day1.keys()) + list(best_day2.keys()))
    for currency in all_currencies:
        product = best_day1.get(currency, 0) * best_day2.get(currency, 0)
        if product > max_amount:
            max_amount = product
    return max_amount

# Example usage:
print(maximizeAmount("EUR", [["EUR", "USD"], ["USD", "JPY"]], [2.0, 3.0],
                      [["JPY", "USD"], ["USD", "CHF"], ["CHF", "EUR"]], [4.0, 5.0, 6.0]))
# Expected output: 720.00000
← Back to All Questions