# CHRGES - Editorial

Author: notsoloud
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

TBD

None

# PROBLEM:

There are N objects in a row; each with positive/negative/neutral charge.
Charged objects spread their charge to adjacent neutral objects every second; however, a neutral object receiving both a positive and a negative charge at the same instant remains neutral.

Eventually the system reaches a stable state. Find the number of neutral objects in this state.

# EXPLANATION:

Since each object only spreads its charge to its neighbors, any neutral object will only be eventually affected by at most two charged objects: the closest one to its left, and the closest one to its right.

Let’s consider two consecutive charged objects, say at positions L and R. They (and only they) will affect all the neutral objects between them.
For example, if S = 00+000-0, the + and - are consecutive charged objects here.

Let d = R-L-1 be the number of neutral objects between them.

Now,

• If L and R have the same charge, of course everything in-between will receive the same charge as them and cannot remain neutral.
• When L and R have different charges:
• If something is strictly closer to L than R, it’ll receive the charge of L.
• Similarly, something strictly closer to R than L will receive R's charge.
• So, the only way something can remain neutral is when it is equidistant from L and R. In such a case, it’s easy to see that it’ll always remain neutral since it will always receive different charges from each side.
• In particular, the third case above happens if and only if d is odd; since we need a unique middle element.

This gives us a pretty simple solution: for each maximal segment of 0-s in the string, add 1 to the answer if it has odd length and its endpoints have different charges.

There is one edge case: if the string contains only neutral objects, then of course the answer is N.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Setter's code (C++)
#include <bits/stdc++.h>
#define int long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;

const int N=500023;
bool vis[N];
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){
}
}
}

int sumN = 0;

void solve()
{
int n = readInt(1, 100000, '\n');
sumN += n;
assert(s.size() == n);
for(int i = 0; i < n; i++) {
assert(s[i] == '0' || s[i] == '+' || s[i] == '-');
}

int left[n], right[n];
bool lPos[n], rPos[n];
int last = -1;
bool pos = true;
for(int i = 0; i<n; i++){
if(s[i] == '+'){
pos = true;
last = i;
}
else if(s[i] == '-'){
pos = false;
last = i;
}
else{
if(last == -1){
left[i] = INT_MAX;
}
else{
left[i] = i - last;
lPos[i] = pos;
}
}
}
last = -1;
pos = true;
for(int i = n-1; i>=0; i--){
if(s[i] == '+'){
pos = true;
last = i;
}
else if(s[i] == '-'){
pos = false;
last = i;
}
else{
if(last == -1){
right[i] = INT_MAX;
}
else{
right[i] = last - i;
rPos[i] = pos;
}
}
}

int ans = 0;
for(int i = 0; i<n; i++){
if(s[i] == '0'){
if((left[i] == INT_MAX) && (right[i] == INT_MAX)){
ans ++;
}
else if((left[i] != INT_MAX) && (right[i] != INT_MAX) && (left[i] == right[i])){
if(lPos[i] != rPos[i]){
ans ++;
}
}
}
}
cout << ans << '\n';
}

int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
while(T--){
solve();
}
assert(getchar()==-1);
cerr << sumN << '\n';
assert(sumN <= 200000);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
ans, len, cur = 0, 0, 'x'
for i in range(n):
if s[i] == '0': len += 1
else:
if s[i] != cur and cur != 'x' and len%2 == 1: ans += 1
cur = s[i]
len = 0
if cur == 'x': ans = n
print(ans)


I just counted the no of zeros between ‘+’ and ‘-’ , and if the of zeros is odd ,then there will be a neutral object at the end or else if its even, then no neutral object will be left .

void solve()
{
ll n;
cin >> n;
string s;
cin >> s;
// n = s.length();
char prev = '$'; ll zero = 0; int ct = 0; for (int i = 0; i < n; i++) { if (prev != '$' and s[i] == '0')
{
zero++;
}
else if (prev == '$' and s[i] != '0') { prev = s[i]; } else if (prev != s[i] and s[i] != '0') { if (zero % 2 == 1) ct++; zero = 0; prev = s[i]; } else if (prev == s[i]) { zero = 0; } } if (prev == '$')
cout << n;
else
cout << ct;
}

1 Like

Can anyone they why is this code wrong or wrong test cases

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {

int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n];
char c;
for(int i=0;i<n;i++){
cin>>c;
if(c=='0'){
arr[i]=0;
}
if(c=='+') arr[i]=1;
if(c=='-') arr[i]=-1;
}
if(n==1){
if(arr[0]==0){
cout<<1<<endl;
continue;
}
else{
cout<<0<<endl;
continue;
}
}

if(arr[0]==0){
arr[0]=arr[1];
}
for(int i=1;i<n-1;i++){
if(arr[i]==0){
arr[i]=arr[i-1]+arr[i+1];
if(arr[i]<0){
arr[i]=-1;
}
else if(arr[i]>0){
arr[i]=1;
}

if(arr[i]!=0){
if(i!=0){
i=i-2;
}
}
}
}
if(arr[n-1]==0){
arr[n-1]=arr[n-2];
}
int ans=0;
for(int i=0;i<n;i++){
if(arr[i]==0){
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}