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 computing the tastiness.
The tastiness is calculated by running two loops: one forward and the other 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 common functions?
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, we can refactor the code in order to ditch duplication. This is left as an exercise.
A second approach consists in the combination of other 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));
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.
Note that c2 is not simply c reversed. You can be deceived by this example:
After the swap:
In this case, c and c2 are actually duals:
1
2
|
c: 0 0 1 2 2 3
c2: 3 2 2 1 0 0
|
However, this is just because they have the same number of occurrences.
On ther other hand, this example (suppose it’s already swapped):
Leads to very different c and c2:
1
2
|
c: 0 0 0 1 1 2
c2: 4 3 2 1 1 0
|
The core part of this solution can be rewritten with C++ 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, in this case we pay an extra vector (needed because we can’t apply view::reverse on view::partial_sum directly since this one does not produce a bidirectional range).