The Master of Cryptocurrencies

See the original problem on HackerRank.

Crypto Bank provides $n$ crypto currencies, each of which has a fixed conversion rate with respect to dollar. The conversion rate w.r.t dollar is not subject to change over time. But as you may have imagined, the conversion rate between each pair of crypto currencies may change over time, due to economic and political factors.

Ron has $m$ bitcoins with him. The conversion rate of a bitcoin w.r.t dollar is $k$. You are given the conversion rates of every other crypto currency with respect to bitcoin. You are also given the conversion rate of these crypto currencies w.r.t dollar. You have to find the currency, that Ron can buy with $m$ bitcoins, such that the total value in dollars is maximized.

Note that, Ron cannot buy crypto currency in fractions and Ron can own only one type of crypto currency at the end of the transaction.

Input Format

In the first line, you are given three integers - $n$, $m$ and $k$, where $n$ is the number of currencies excluding bitcoin, $m$ is the amount of bitcoins Ron has and $k$ is the conversion rate of bitcoin w.r.t dollar.

In the next line, you will be given $n$ integers $(a_{i})$, the $i^{th}$ of which denotes the conversion rate of the $i^{th}$ crypto currency w.r.t dollar.

In the third line, you will be given $n$ integers $(b_{i})$, the $i^{th}$ of which denotes the number of units Ron can buy with one bitcoin, Ron can buy $b_{i}$ units of $i^{th}$ crypto currency with 1 bitcoin.

Constraints

$1<n,m,k<101$
$1<a_{i}<1001$
$1<b_{i}<1001$

Output Format

In a single line, you have to output the maximum value in dollars that you can have. It is guaranteed that the answer will fit into a 32-bit integer.

Solutions

The challenge can be solved by applying map | reduce on both sequences at the same time, that results in applying zip before.

In C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int n, m, k;
cin >> n >> m >> k;
vector<int> dollars(n);
copy_n(istream_iterator<int>(cin), n, begin(dollars));
vector<int> btc(n);
copy_n(istream_iterator<int>(cin), n, begin(btc));

cout << inner_product(begin(btc), end(btc), begin(dollars),
                      m*k,
                      [](auto... arg){ return max(arg...); },
                      [=](auto wrtBtc, auto wrtDollar) { return m * wrtBtc * wrtDollar; });

We can factor m out:

1
2
3
4


cout << m*inner_product(begin(btc), end(btc), begin(dollars),
                  k,
                  [](auto... arg){ return max(arg...); },
                  multiplies<>{});

Rust, first map, then reduce:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


fn solve(m: u32, k: u32, btc_to_i: &[u32], i_to_usd: &[u32]) -> u32 {
    use std::cmp::max;

    let best_buy_sell = (btc_to_i.iter().zip(i_to_usd))
        .map(|(bi, iu)| bi * iu)
        .max()
        .unwrap();

    m * max(k, best_buy_sell)
}

Rust, find max while iterating. The fold init is k, i.e. the best exchange before trying with other currencies. Note that this version, compared to the previous, doesn’t need to check for errors (max on an empty collection returns a None), so it’s safer.

1
2
3
4


fn solve(m: u32, k: u32, btc_to_i: &[u32], i_to_usd: &[u32]) -> u32 {
    btc_to_i.iter().zip(i_to_usd)
      .fold(k, |best, (bi, iu)| std::cmp::max(best, bi * iu)) * m
}

In Rust, we can even use a library for parallel computation: rayon

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


pub fn solve(m: u32, k: u32, btc_to_i: &[u32], i_to_usd: &[u32]) -> u32 {
    use std::cmp::max;
    use rayon::prelude::*;

    let best_buy_sell = btc_to_i.par_iter().zip_eq(i_to_usd)
        .map(|(bi, iu)| bi * iu)
        .max().unwrap();

    m * max(k, best_buy_sell)
}

Using reduce. The identity is (k, 1)

1
2
3
4
5
6
7


pub fn solve(m: u32, k: u32, btc_to_i: &[u32], i_to_usd: &[u32]) -> u32 {
    use std::cmp::max;
    use rayon::prelude::*;

    btc_to_i.par_iter().copied().zip_eq(i_to_usd.par_iter().copied())
        .reduce(|| (k, 1), |(best, _), (bi, iu)| (max(best, bi * iu), 1)).0 * m
}

patterns