# CONDEL - Editorial

Author: Milos Puric
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

Easy

# PREREQUISITES:

Sliding Window, Greedy

# PROBLEM

You are given a positive integer K and an array A of length N whose elements A_1, A_2, \ldots, A_N are only zeros and ones. Your task is to turn all elements of A into zeros by operating as many times.

Operation is defined as follows:

• Choose two indices L and R (L \le R) such that R-L+1=K.
• The cost of this operation is A_L+A_{L+1}+\ldots+A_{R-1}+A_R.
• Choose an index P such that L \le P \le R and set A_P=0.

You need to find the minimum cost to turn all the elements of A into zeroes.

# QUICK EXPLANATION:

Initially we repeatedly select the window of length K that has minimum number of 1's in it as our subarray, until all its 1's have been flipped. Then we consecutively select successive subarrays of length K moving the window to the right by a single unit for each operation. We repeat this to the left of the initial window as well.

# EXPLANATION:

Since we want the cost to be the minimum possible, the optimal choice of selecting a subarray of size K is the one that has the minimum number of 1's. Since this subarray will have a minimum sum i.e. minimum cost.

Suppose a subarray S (having M 1's) has the minimum number of 1's among all subarrays. Thus for S, the cost for turning one of the 1's to 0 will be M initially.

After having flipped one of the 1's, there will remain (M-1) 1's which means S again has the minimum number of 1's and thus is the optimal choice yet again. We will continue selecting subarray S until we have flipped all the 1's in it.

Hence, the cost needed to turn all elements of subarray S to 0 is:

C_1 = M+(M-1)+ \dots +2+1
C_1 = \frac{M*(M+1)}{2}

After having one subarray that has all its elements as 0's, the cost of flipping each of the remaining 1's throughout the array will be 1 unit each. This is because once K consecutive elements have been made 0, we can select successive subarrays such that they contain at most a single 1

How?

Suppose there is an array A such that:

A_1, A_2, \dots , A_L, \dots,A_R, \dots, A_N

After turning all the elements of a subarray S{[A_L, A_{L+1, }\dots, A_{R-1},A_R]} to 0, we will keep moving the window of K elements to the left by one unit until we find the index i such that A_i=1. Now the subarrary S' will contain elements [A_i, A_{i+1, }\dots, A_{x-1},A_x] among which all the elements except A_i would be 0. Hence the minimum cost to turn A_i into 0 is 1.

After turning A_i into 0 we will resume moving the window to the left until we reach the leftmost index and thus continue this operation of shifting window until the entire array to the left of R has become 0.

Similar operation is also performed to the right of the selected subarray (i.e. by moving the window a unit to the right) until we reach the rightmost index of the array, thus making the entire array consist of 0's.

Hence the total cost needed to convert all 1's into 0's which were not part of the subarray S will be:

C_2 = T-M

where T is the total number of 1's present in the given array.

And total cost of conversion will be:

C=C_1+C_2
C=\frac{M*(M+1)}{2}+T-M

# TIME COMPLEXITY:

O(N) per test case.

# SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+45;

int n,k,a[N];
ll pf[N];

void solve(){
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
pf[i] = pf[i-1]+a[i]; /// prefix sum array
}

ll s = pf[n],m = n;
for(int i = k; i <= n; i++){ /// finding the minimum number of ones in a segment of length k
m = min(m,pf[i]-pf[i-k]);
}

ll sol = (m*(m+1))/2 + (s-m); /// the minimum cost
cout << sol << endl;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
/*freopen("04.txt","r",stdin);
freopen("out4.txt","wb",stdout);*/
int t;
cin >> t;
while(t--){
solve();
}
}

Tester
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
//#define double long double
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}

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;
}
assert(l<=x&&x<=r);
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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

int a[200005];
int sum_n=0;
void solve() {
sum_n+=n;
assert(sum_n<=400000);
fr(i,1,n)
if(i!=n)
else
int su=accumulate(a+1,a+k+1,0);
int ac=accumulate(a+1,a+n+1,0);
int ans=(su*(su+1))/2+(ac-su);
fr(i,k+1,n) {
su+=a[i]-a[i-k];
ans=min(ans,(su*(su+1))/2+ac-su);
}
cout<<ans<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
//	int t;
//	cin>>t;
fr(i,1,t)
solve();
assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}


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

#define int long long

void solve()
{
int n,k;
cin>>n>>k;

int a[n];

int sum=0,cnt=0;

for(int i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];

if(i<k && a[i]==1)
cnt++;
}

int min_cnt=cnt;

for(int i=k;i<n;i++)
{
if(a[i-k]==1)
cnt--;
if(a[i]==1)
cnt++;

min_cnt=min(min_cnt,cnt);
}

sum-=min_cnt;

sum+=(min_cnt*(min_cnt+1))/2;

cout<<sum<<"\n";
}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
solve();

return 0;
}


12 Likes

Hey can anyone explain to me what is wrong with my code for this question. TIA.

Solution: 44029917 | CodeChef

@f20180018
n <= 2e5
So minSum can be equal to 2e5 in the worst case, and square of that would exceed the range of int.

1 Like

Cursing myself for skipping silding-window technique this very morning >.<

2 Likes

They have defined macros for int as long long

1 Like

sucks to do this stupid mistakes again and againâ€¦ smh

Sorry for the confusion, it was a mention to @f20180018.
And itâ€™s okay, @f20180018, I got stuck with blunders with the second problem and couldnâ€™t even come up with an optimal solution for the third. Happens.

1 Like

same

3 things need to be corrected:
1.Convert int to long
2. Formula is M(M+1)/2 you have written M(M-1)/2
3.Substract minsum from count as number of 1â€™s in minsum are already taken so we need to remove those from total 1â€™s.

Just curious, Can this problem be solved using DP?

1 Like

https://www.codechef.com/viewsolution/44033600
Can someone tell me why am i getting TLE in this solution

I think so, but time complexity wouldnâ€™t remain same, I guess.

2 Likes
for i in range(N-K+1):
a.append(A[i:i+K])


For K = N/2 and N = 2\times10^5, the number of instructions you perform in this loop will be
(N - K + 1) \times (K), viz., (10^5 + 1) \times 10^5 or, simply, 10^{10}. Hence, TLE.

I wonder you should also get RE because you are appending the slices of the given list, which should exceed the memory limits for worst case input as discussed above.

3 Likes

Really Nice Mathematical Formulation of Problem

I have used the prefix sum method to find the minimum number of 1â€™s in subarray of length k .
You can check it here code

same

please tell me where i am wrong in this code defalut test cases running fine

import java.util.*;

import java.io.*;

class CodeChef {

public static void main(String[] args)  throws java.lang.Exception {

// Scanner scn = new Scanner(System.in);

while(tc-- > 0 ){

int n= Integer.parseInt(line[0]);

int k= Integer.parseInt(line[1]);

int ssf[]= new int[n];

ssf[0]=line[0].charAt(0)-'0';

for(int i =1 ;  i < line.length;i++){

ssf[i]= ssf[i-1]+line[i].charAt(0)-'0';

}

int minWindow = k ;

for(int i= k-1; i< line.length;i++){

int prev = i-k>=0 ? ssf[i-k]: 0;

minWindow =Math.min(ssf[i]-prev, minWindow );

}

// System.out.println("min windows is  : "+minWindow);

// System.out.println("number of  one : "+ssf[line.length-1]);

int ans =( (minWindow *(minWindow+1)) / 2) + ssf[line.length-1]-minWindow;

System.out.println(ans);

}

}


}

One of the reason the code is getting W A might be the range of the cost. Please see to it.
Thanks

1 Like

check the range of cost. Hope it helps !

Yeah, time complexity wouldnâ€™t remain same.
But can you tell you how we can solve using DP?