# STRP - Editorial

Author: Sarthak Gupta
Tester: Anshu Garg

Easy

# PROBLEM:

We have to create a string S in minimum number of operations. In each operation, we are aloud to append a character either once or twice.

# EXPLANATION:

It can be observed that subarrays consisting of same letter that are surrounded by diffferent letters on both end can be treated independently. Now the problem becomes trivial to solve for the same letter as taking two letters whenevr possible is the best strategy. Therefore taking two characters whenever possible is optimal

O(N)

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
#define ll           long long int
#define pb           push_back
#define F            first
#define S            second
using namespace std;
void solve()
{
int n;
string s;
cin>>n>>s;
int ans=0,j=0;
for(int i=0;i<n;++i){
if(j){
++ans;
if(s[i]==s[i-1])j=0;
}
else j=1;
}
cout<<(ans+j)<<"\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
``````
Tester's Solution
``````#include<bits/stdc++.h>
using namespace std ;

#define ll              long long
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll>
#define pii             pair<int,int>
#define ld              long double

template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }

// #ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
// #else
// #define debug(...) 2401
// #endif

long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

int _runtimeTerror_()
{

int mx_N = 0, mn_N = 1e6, sum_N = 0;
for(int i=1;i<=T;++i) {
sum_N += N;
amax(mx_N, N);
amin(mn_N, N);
int ans = 0;
for(int j=0;j<N;++j) {
if(j + 1 < N and s[j] == s[j + 1]) {
++ans;
++j;
}
else {
++ans;
}
}
cerr << N << "\n";
cout << ans << "\n";
}
assert(sum_N <= 1e5);
cerr << sum_N << " " << mx_N << " " << mn_N << "\n";
assert(getchar() == -1);
return 0;
}

int main()
{
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initncr();
#endif
int TESTS = 1;
//cin >> TESTS;
while(TESTS--) {
_runtimeTerror_();
}
return 0;
}
``````

I didnâ€™t get what u guys doingâ€¦
Check this out
https://www.codechef.com/viewsolution/60056676

brief explaination:
max operations/time = length
each time we have equal pair (like aa bb), do lengthâ€“
i++ is done as in â€śbcccâ€ť, I can reduce for only one of them 1st 2 cc or last 2 cc

1 Like

Our solution also uses the same fact, that is use the double append operation whenever possible which is a greedy approach. This is one way of proving that it is correct.

2 Likes

Why it is showing that wrong ans on submission

https://www.codechef.com/viewsolution/59948481

Why it is showing Wrong ans

https://www.codechef.com/viewsolution/59948481

First mistake:
You are decreasing n whenever `s[i] = s[i + 1]` ,
and you used same n in `for(int i = 0; i < n; )`.
Thus, for some test cases, it will not traverse whole string.

Second mistake:
For some test cases `s[i + 1]` will not exist, i.e. when i = n - 1.