PROBLEM LINK:
Author: Raja Vardhan Reddy
Tester: Felipe Mota
Editorialist: Rajarshi Basu
DIFFICULTY:
Simple
PREREQUISITES:
Implementation, logic
PROBLEM:
There are N \leq 10^5 students standing in a row and numbered 1 through N from left to right. You are given a string S with length N, where for each valid i, the i-th character of S is ‘x’ if the i-th student is a girl or ‘y’ if this student is a boy. Students standing next to each other in the row are friends.
The students are asked to form pairs for a dance competition. Each pair must consist of a boy and a girl. Two students can only form a pair if they are friends. Each student can only be part of at most one pair. What is the maximum number of pairs that can be formed?
EXPLANATION:
We do a linear traversal of the array, and whenever we see that the i^{th} and (i+1)^{th} characters are different, we increase our counter cnt by 1, and skip over that next element to ensure that the chosen pairs are all disjoint. Choosing pairs in this greedy approach is optimal, since our chosen pairs are more “towards the left” and thereby freeing up more space “towards the right” to choose possible more pairs.
I write those in quotes, since they are not mathematically rigorous statements but more of the intuition and the “feel” for the solution.
Since we just do a linear traversal, the time complexity is O(n)
SOLUTIONS:
Setter's Code
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t,t1;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
cin>>t;
while(t--){
int i,ans=0,prev_taken=0;
string s;
cin>>s;
//cout<<rng()<<endl;
prev_taken=0;
f(i,1,s.length()){
if(prev_taken){
prev_taken=0;
continue;
}
if(s[i]!=s[i-1]){
ans++;
prev_taken=1;
}
}
cout<<ans<<endl;
}
return 0;
}
Tester's Code
t = int(raw_input())
while t > 0:
s = raw_input()
p, res = 0, 0
while p + 1 < len(s):
if s[p] != s[p + 1]:
res += 1
p += 1
p += 1
print res
t -= 1
Editorialist's Code
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define ld long double
//#define int ll
//#define int short
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<iii,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
//#define mp make_pair
#define vv vector
#define endl '\n'
using namespace std;
const int MAXN = 200*1000 + 5;
const int MAXT = 263*1000;
void solve(){
string s;
cin >> s;
int n = s.size();
int dp[n];
dp[0] = 0;
FOR(i,n){
if(i == 0)continue;
else if(i == 1){
if(s[i] == s[i-1])dp[1] = 0;
else dp[1] = 1;
}else{
if(s[i] == s[i-1]){
dp[i] = dp[i-1];
}else{
dp[i] = max(dp[i-1],dp[i-2]+1);
}
}
}
cout << dp[n-1] << endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)solve();
return 0;
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 
