PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Authors: Daanish Mahajan
Testers: Abhinav Sharma and Lavish Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
You are given a string S consisting of only the characters \verb+P+ and \verb+N+. In one move, you can flip a single \verb+P+ to \verb+N+ or vice versa. Find the minimum number of moves required to obtain a string that can be partitioned into an equal number of \verb+P+ and \verb+NP+ substrings.
EXPLANATION:
Suppose S can be partitioned into an equal number of \verb+P+ and \verb+NP+ substrings. Let’s make a few observations:
- The last character of S cannot be \verb+N+, because if this were the case, it cannot be part of either a \verb+P+ or an \verb+NP+ substring — but each character must be part of one such substring.
- In the same vein, \verb+NN+ cannot occur as a substring in S, because the first \verb+N+ cannot occur in either a \verb+P+ or an \verb+NP+ substring.
- Each \verb+N+ occurs in exactly one \verb+NP+ substring, and the number of these equals the number of \verb+P+ substrings. Thus, the number of occurrences of \verb+N+ in the string must be exactly |S|/3.
It turns out that these above conditions are also sufficient, i.e, if S is a string such its last character is \verb+P+, no two occurrences of \verb+N+ are next to each other in S, and there are exactly |S|/3 occurrences of \verb+N+ in S, then there exists a way to split S into \verb+P+ and \verb+NP+ substrings such that there is an even number of each.
Proof
There are exactly |S|/3 \verb+N+-s in the string, and since no two of them occur next to each other and the last character is not \verb+N+, each of the \verb+N+-s also has a \verb+P+ immediately after it. This gives us |S|/3 substrings of the form \verb+NP+, using 2|S|/3 characters.
The remaining characters are all \verb+P+, and there are exactly |S| - 2|S|/3 = |S|/3 of them, which also gives us |S|/3 \verb+P+ substrings, and so we are done.
So, all we need to do is compute the number of moves to bring the string to this form.
First, let’s deal with the condition on the last character - if it is \verb+N+, we have no choice but to use one move to make it \verb+P+.
Now, let’s deal with the second condition.
Consider a substring of S whose characters are all \verb+N+. Suppose the length of this substring is k.
We know that in the final string, we cannot have two \verb+N+ adjacent to each other. Thus, we can keep at most \lceil \frac{k}{2} \rceil of these \verb+N+-s — in other words, this substring needs at least \lfloor \frac{k}{2} \rfloor moves to ‘fix’.
Finally, let’s deal with the third condition.
From the first two conditions, we have used some moves to make the string such that the last character is \verb+P+, and no two \verb+N+ are adjacent.
Suppose the string currently has k occurrences of \verb+N+.
- If k = |S|/3, no more moves are required.
- If k > |S|/3, simply pick any k - |S|/3 \verb+N+-s and delete them. This satisfies the third condition while not breaking the first two
This leaves us with the case when k < |S|/3, where we need to turn some \verb+P+-s into \verb+N+ while maintaining the first two conditions. Of course, this requires, at minimum, |S|/3 - k moves.
It turns out that it is possible to do this using exactly |S|/3 - k moves, with a fairly simple construction.
Construction
Split the string into |S|/3 blocks of three characters each.
There are k < |S|/3 \verb+N+-s, so at least |S|/3 - k of these blocks don’t have any \verb+N+ at all.
Pick |S|/3 - k blocks without an \verb+N+, and turn the middle character of these blocks into \verb+N+.
It’s easy to see that all three constructions are now satisfied.
Every move we made was essentially forced by one of the three conditions, so the number of moves we made is optimal.
TIME COMPLEXITY:
\mathcal{O}(N) per test case.
SOLUTIONS:
Setter's Solution (C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
using namespace std;
const string newln = "\n", space = " ";
const int maxt = 3.5e4, maxl = 1e6, maxs = 1e5 - 1;
bool verify(string s, int ans){
int l = s.length();
int vans = l;
for(int i = 0; i < (1 << l); i++){
string ps = s; int cnt = 0; bool can = true;
for(int j = 0; j < l; j++){
if((i >> j) & 1){
if(ps[j] == 'N')ps[j] = 'P';
else ps[j] = 'N';
}
if(j > 0){
if(ps[j] == ps[j - 1] && ps[j] == 'N'){can = false; break;}
if(j == l - 1 && ps[j] == 'N'){can = false; break;}
}
cnt += (ps[j] == 'N');
}
if(cnt == l / 3 && can){
vans = min(vans, __builtin_popcount(i));
}
}
// cerr << vans << " " << ans << " " << s << endl;
return vans == ans;
}
int main()
{
int t, tn = 0; cin >> t;
string s, ps;
while(t--){
cin >> s;
int l = s.length(); tn += l;
assert(l % 3 == 0);
for(char c : s){
assert(c == 'N' || c == 'P');
}
string ps = s;
// last character must always be P
ps[l - 1] = 'P';
// making every second consecutive N as P
for(int i = 1; i < l - 1; i++){
if(ps[i] == ps[i - 1] && ps[i] == 'N'){
ps[i] = 'P';
}
}
// count N
int cnt = 0;
for(char c : ps){
cnt += (c == 'N');
}
// balance count
if(cnt > l / 3){
for(int i = 0; i < l && cnt > l / 3; i++){
if(ps[i] == 'N'){
ps[i] = 'P';
cnt--;
}
}
}else if(cnt < l / 3){
for(int i = 0; i < l - 1 && cnt < l / 3; i++){
if(ps[i] == 'P' && ps[i + 1] == 'P' && (i == 0 || (i > 0 && ps[i - 1] != 'N'))){
ps[i] = 'N';
cnt++;
}
}
}
// verify
assert(cnt == l / 3);
// cal ans
int change = 0;
for(int i = 0; i < l; i++){
if(ps[i] != s[i]){
change++;
}
}
// if(l <= 15){
// assert(verify(s, change));
// }
cout << change << endl;
}
assert(tn <= maxl);
}
Tester's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
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,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 35000;
const int MAX_N = 100000;
const int MAX_SUM_N = 1000000;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll seed;
mt19937 rnd(seed=chrono::steady_clock::now().time_since_epoch().count()); // include bits
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll z = 998244353;
void solve()
{
string str = readStringLn(1 , MAX_N) ;
int n = str.size() ;
assert(n%3 == 0) ;
sum_n += n ;
max_n = max(max_n , n) ;
for(int i = 0 ; i < n ; i++)
{
assert(str[i] == 'N' || str[i] == 'P') ;
}
int ans = 0 ;
for(int i = 0 ; i < n ; i++)
{
if(str[i] == 'N')
{
if(i == n-1)
{
str[i] = 'P' ;
ans++ ;
}
else
{
if(str[i+1] == 'N')
{
str[i+1] = 'P' ;
ans++ ;
}
}
}
}
int cnt_n = 0 ;
for(int i = 0 ; i < n ; i++)
{
if(str[i] == 'N')
cnt_n++ ;
}
int tot = n/3 ;
//cout << "ans = " << ans << " cnt_n = " << cnt_n << " tot = " << tot << endl ;
ans += (abs(cnt_n - tot)) ;
cout << ans << endl ;
return ;
}
signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int t = 1;
t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve() ;
}
assert(getchar() == -1);
assert(sum_n <= MAX_SUM_N);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n << '\n';
cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution (Python)
for _ in range(int(input())):
s = list(input())
ans, nct = 0, 0
reqd = len(s)//3
if s[-1] == 'N':
ans = 1
s[-1] = 'P'
for c in s:
if c == 'P':
keep = min(reqd, (nct+1)//2)
ans += nct - keep
reqd -= keep
nct = 0
else:
nct += 1
print(ans + read)
