P_NP - Editorial

Authors: Daanish Mahajan
Testers: Abhinav Sharma and Lavish Gupta
Editorialist: Nishank Suresh

Easy

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 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){
}
long long readIntLn(long long l,long long 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;

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;

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

4 Likes

https://www.codechef.com/viewsolution/54906571
Can anyone help why the first test case is failing?

can we know what are the test cases in codechef?

No, test cases are hidden.

1
PNNPPN


1 Like

thank you.

https://www.codechef.com/viewsolution/54905956
Can someone please identify a testcase which doesn’t satisfy my code?

1
PNN


correct ans is 1 no?

Flip the last N to P so it becomes PNP.

3 Likes

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

Why you guys post solution in python if c++ is de facto language for CP

3 Likes

Yes, apologies for the confusion. I meant his code gave output as 3, correct output is 1 @aryanagrawal_0

1 Like

These are a few test cases for anyone struggling to debug their solution.
input.txt
output.txt

1 Like