PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Milos Puric
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
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:
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:
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:
where T is the total number of 1's present in the given array.
And total cost of conversion will be:
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) {
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,' ');
}
int a[200005];
int sum_n=0;
void solve() {
int n=readIntSp(1,200000),k=readIntLn(1,n);
sum_n+=n;
assert(sum_n<=400000);
fr(i,1,n)
if(i!=n)
a[i]=readIntSp(0,1);
else
a[i]=readIntLn(0,1);
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=readIntLn(1,200);
// 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;
}
