StefanUwU's blog

By StefanUwU, history, 2 months ago,

Let's denote k1 = number of times the first action was done and k2 = number of times the second action was done. We know that for the pointer to be in its starting position after finishing k1 needs to be equal to k2, telling us that the sum of the elements int a has to be zero.

     for(int i=1; i<=n; i++){
cin>>a[i];
sum+=a[i];
}
if(sum!=0){
cout<<"No"<<endl;
return;
}


Now that we know the sum is equal to zero lets denote build[i] = number of times the first operation was applied on v[i], and subtract[i] = number of times the first operation was applied on v[i].

a[i] = build[i] — subtract[i] and subtract[i] = build[i-1] because the pointer needs to be in its starting position, build[1] = a[1].

From this we can see that a[i] = build[i] — build[i-1] which means that build[i] = a[i] + build[i-1].

    for(int i=1; i<=n; i++){
build[i] = a[i] + build[i-1];
}


Now, we need to verify some conditions to make sure that our array is valid.

build[i] >= 0

If build[i] = 0 -> all of the numbers build[j] (j>=i && j<=n) have to be equal to zero, or else that means we didn't go through build[i] but we went through build[j] and that would mean the pointer's starting position was in [i, j] — i, which is false.

    for(int i=1; i<=n; i++){
if(build[i]<0)
CheckMinus=true;
if(build[i]==0){
CheckZero=true;
}
if(CheckZero==true && build[i]!=0){
CheckInt=true;
}
}
if(CheckInt==true || CheckMinus==true){
cout<<"No"<<endl;
return;
}
cout<<"Yes"<<endl;


My full implementation : 161532230

• 0