PROBLEM LINK:
Practice]
Div-2 Contest
Div-3 Contest
Div-4 Contest
Author: Sarthak Gupta
Tester: Anshu Garg
DIFFICULTY:
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
TIME COMPLEXITY:
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 readString(int l,int r,char end){
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){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int _runtimeTerror_()
{
int T = readIntLn(1, 1000);
int mx_N = 0, mn_N = 1e6, sum_N = 0;
for(int i=1;i<=T;++i) {
int N = readIntLn(1, 1e5);
sum_N += N;
amax(mx_N, N);
amin(mn_N, N);
string s = readStringLn(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;
}