PROBLEM LINK:
Setter: Saurabh Yadav
Tester: Radoslav Dimitrov
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
Cakewalk
PREREQUISITES:
Implementation
PROBLEM:
Given a string s made of A and P characters. You can change A into P only if atleast one of the two characters just before it and one of the two characters just after has a P written initially. Now, we want s to have atleast 75% P. What is the minimum number of changes needed to achieve it. (Also we cannot change among first two and last two positions).
EXPLANATION
We will iterate on all A characters which are not among first two and last two positions. And check number of those that can be changed to P. For checking if an A can be changed to P, we iterate over each of the two adjacent characters (two on either side) and see if atleast one of them on each side is P. Lets say x can be changed to P.
Now, lets calculate minimum number needed to be changed to meet the 75% requirement (lets say y). y will be equal to ceil(0.75*n) or (75*n+99)/100 (incase you want to avoid decimals). you can see that the second formula is exactly same as ceil(0.75*n).
Now if y \leq x. we output y otherwise -1.
TIME COMPLEXITY
For checking each A, it takes constant time.
Since, total O(n) positions can be checked. Time complexity is O(n).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,i,proxy,temp;
string str;
double percentage,n,countP;
cin>>t;
while(t--)
{
cin>>n>>str;
proxy=0;temp=0;
countP=count(str.begin(), str.end(), 'P');
percentage=((countP)/(n))*100;
if(percentage>=75)
cout<<proxy<<endl;
else
{
for(i=2;i<n-2;i++)
{
if((str[i-1]=='P'||str[i-2]=='P')&&(str[i+2]=='P'||str[i+1]=='P')&&str[i]=='A')
{
countP++;
proxy++;
percentage=((countP)/(n))*100;
if(percentage>=75)
{
temp=1;
cout<<proxy<<endl;
break;
}
}
}
if(temp==0)
cout<<-1<<endl;
}
}
return 0;
}
Tester's Solution
import sys
def read_line():
return sys.stdin.readline()[:-1]
def read_int():
return int(sys.stdin.readline())
def read_int_line():
return [int(v) for v in sys.stdin.readline().split()]
############
# Solution #
T = read_int()
for _test in range(T):
N = read_int()
S = read_line()
ans = 0
cnt = 0
for c in S:
if c == 'P':
cnt += 1
for i in range(2, N - 2, 1):
if cnt < (3 * N / 4) and S[i] == 'A' and (S[i - 1] == 'P' or S[i - 2] == 'P') and (S[i + 1] == 'P' or S[i + 2] == 'P'):
ans += 1
cnt += 1
if cnt < (3 * N / 4):
ans = -1
print(ans)
Editorialist's Solution
//teja349
#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); 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 flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int d;
cin>>d;
string s;
cin>>s;
int i,cnt=0,gg=0;
int sz=s.length();
rep(i,sz){
if(s[i]=='P')
cnt++;
}
int j,val,good=0;
val=(75*sz+99)/100;
f(i,2,sz-2){
if(cnt>=val)
break;
if(s[i]=='P')
continue;
good=0;
f(j,-2,0){
if(s[i+j]=='P'){
good=1;
break;
}
}
if(good==0)
continue;
good=0;
rep(j,3){
if(s[i+j]=='P'){
good=1;
break;
}
}
// cout<<i<<endl;
if(good){
cnt++;
gg++;
}
}
if(cnt<val)
gg=-1;
cout<<gg<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
