See the original problem on HackerRank.
To solve the problem we can easily observe that swapping the first c
with the last p
minimizes the tastiness.
The answer is \(0\) when either:
- there are not
p
- there are not
c
- the last
p
is before the first c
For example:
Instead, if neither of the conditions above occur, we swap the first occurrence of c
with the last occurrence of p
and we proceed with measuring the tastiness.
To count the tastiness, we can just run two loops: one forward and one backwards. Here is the idea in C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
string s; cin >> s;
auto firstC = s.find_first_of('c');
auto lastP = s.find_last_of('p');
auto cost = 0ll;
if (firstC != string::npos
&& lastP != string::npos
&& firstC < lastP)
{
swap(s[firstC], s[lastP]);
auto cnt = 0;
for (auto i : s)
{
if (i == 'c')
cnt++;
else
cost += cnt;
}
cnt = 0;
for (int i=s.size()-1; i>=0; i--)
{
if (s[i] == 'p')
cnt++;
else
cost += cnt;
}
}
cout << cost;
|
The solution is linear and does not allocate extra space.
Playing with patterns
Can we replace loops with patterns?
Yes we can.
The first pattern we can think of is reduce. Here is the idea:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
string s; cin >> s;
auto firstC = s.find_first_of('c');
auto lastP = s.find_last_of('p');
auto cost = 0ll;
if (firstC != string::npos
&& lastP != string::npos
&& firstC < lastP)
{
swap(s[firstC], s[lastP]);
cost += accumulate(begin(s), end(s), make_pair(0ll,0ll), [](auto res, auto curr){
return curr == 'c' ? make_pair(res.first, res.second + 1) : make_pair(res.first+res.second, res.second);
}).first;
cost += accumulate(rbegin(s), rend(s), make_pair(0ll,0ll), [](auto res, auto curr){
return curr == 'p' ? make_pair(res.first, res.second + 1) : make_pair(res.first+res.second, res.second);
}).first;
}
cout << cost;
|
CLearly, refactoring is possible to remove code duplication. Left as an exercise.
A second approach consists in the combination of two patterns: map and prefix sum:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
string s; cin >> s;
auto firstC = s.find_first_of('c');
auto lastP = s.find_last_of('p');
auto cost = 0ll;
if (firstC != string::npos
&& lastP != string::npos
&& firstC < lastP)
{
swap(s[firstC], s[lastP]);
vector<long long> c(s.begin(), s.end());
transform(begin(c), end(c), begin(c), [](auto i) { return (char)i == 'c'; });
partial_sum(begin(c), end(c), begin(c)); // cakes on the right (dual: pies on the left)
vector<long long> c2(s.begin(), s.end());
transform(begin(c2), end(c2), begin(c2), [](auto i) { return (char)i == 'p'; });
partial_sum(rbegin(c2), rend(c2), rbegin(c2));
for (auto i=0u; i<s.size(); ++i)
{
if (s[i] == 'p')
cost += c[i];
else
cost += c2[i];
}
}
cout << cost;
|
c
and c2
are used to count respectively the number of c
on the left and the number of p
on the right.
This core part of this solution can be rewritten with C++20 ranges:
1
2
3
4
5
6
7
8
9
10
11
|
auto c = views::transform(s, [](auto c) { return (int)(c == 'c'); }) | views::partial_sum;
auto c2 = views::transform(s, [](auto c) { return (int)(c == 'p'); }) |
views::reverse |
views::partial_sum |
ranges::to<std::vector<int>>();
std::cout <<
ranges::accumulate(
views::zip(s, c, c2 | views::reverse) |
views::transform([](auto p) { return std::get<0>(p) == 'p' ? std::get<1>(p) : std::get<2>(p); }), 0);
|
Clearly, we pay an extra vector.