Marc's Cakewalk

See the original problem on HackerRank.

Solutions

This easy problem can be solved by first sorting the calories in decreasing order:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
long long n; cin >> n;
vector<int> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
sort(begin(v), end(v), greater<>{});
auto miles = 0ll;
for (auto i=0; i<n; ++i)
{
    miles += v[i] * (1ll<<i);
}
cout << miles;

The zip | map | reduce pattern emerges from the code: conceptually, it’s like zipping each calory with the ith power of 2, mapping the pair with product and summing along the way:

1
2
3
4
5
6
long long n; cin >> n;
vector<long long> v(n), twos(n, 2); twos.front() = 1;
copy_n(istream_iterator<int>(cin), n, begin(v));
partial_sum(begin(twos), end(twos), begin(twos), multiplies<>{});
sort(begin(v), end(v), greater<>{});
cout << inner_product(begin(v), end(v), begin(twos), 0ll, plus<>{}, multiplies<>{});

Using partial_sum that way generates the first n powers of 2.

Similar approach in Python:

1
2
input()
print(sum(c * 2 ** j for (j, c) in enumerate(sorted(map(int, input().split()), reverse=True))))

Javascript one-liner:

1
calorie.sort((p,c) => c - p).reduce((p,c,i) => p + c * Math.pow(2, i), 0)
comments powered by Disqus