Links:
Contest Link Div1
Contest Link Div2
Contest Link Div3
Setter : Kaushal Solanki
Tester : Manan Grover, Samarth Gupta
Difficulty
Easy
Prerequisites
Greedy,Maths(basic)
Problem
For given N ( length of string ) and M (number of 1 ’s in string)
We have to find a minimum number of substrings that contain only 0 ’s.
Quick Explanation
For the minimum number of substrings that contain only 0 ’s, the best way to create
that type of string is to minimize the number of $0$’s in each of the (M + 1) parts. So the best way to divide all zeroes into equal parts or as equal as possible.
Explanation
We have to calculate the total number of Sub-string which contain only $0$’s.
we only need to find every continuous substring of 0's if its length was L then total substring
for this part = (L*(L+1))/2.
There are total M $1$’s so the number of $0$’s in string = N - M and we want to divide these $0$’s
into (M+1) part so that the sum of (L*(L+1))/2 for every part is minimized.
The best way is to divide them into equal groups or as equal as possible
The number of zeros in the string is Z = N - M and the total part in which we want to divide
zeros = M + 1 so in each part, there are nearly P = (Z/(M+1)) zeroes. ( Z % (M+1)) part
contains P+1 zeroes and the remaining part contains P zeros).
So , the final answer = (((P+1)*(P+2))/2)*(Z % (M+1)) + ((P*(P+1))/2)* (M+1 - (Z %
(M+1))).
Setter’s Code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define LOL cout << '\n';
#define kill(x) {cout << x << '\n'; return;}
#define sz(x) ((int)x.size())
#define INF LONG_LONG_MAX
#define NINF LONG_LONG_MIN
#define deb(x) cout << "[" << (#x) << "=" << (x) << "]" << '\n'
#define deb2(x,y) cout << "[" << (#x) << "=" << (x) << "] [" << (#y) << "=" << (y) << "]" << '\n'
#define deb3(x,y,z) cout << "[" << (#x) << "=" << (x) << "] [" << (#y) << "=" << (y) << "] [" << (#z) << "=" << (z) << "]" << '\n'
const int _max=2e5+1,nmax=1e6+1;
void solve(){
int n,m; cin>>n>>m;
assert(n>=1 && n<nmax);
assert(m>=0 && m<=n);
int zers = n - m;
int x = zers/(m+1);
int t = zers%(m+1);
int ans = (t* (( (x+1)*(x+2))/2 )) + (m+1-t)*( (x*(x+1))/2 );
cout << ans << "\n";
}
signed main() {
#ifdef Kaushal_26
freopen("a.in", "r", stdin);
freopen("b.out", "w", stdout);
freopen("e.out", "w", stderr);
#endif
int _ = 1; cin >> _;
assert(_>=1 && _<_max);
for(int i = 1 ; i <= _ ; i++){
// cout << "\nCase #" << i << ": \n";
solve();
}
return 0;
}
Tester’s Code:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
int main(){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<I> randGen;
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
I t;
cin>>t;
while(t--){
I n,m;
cin>>n>>m;
n-=m;
m++;
I x=n/m;
I y=n%m;
I z=m-y;
I ans=z*(x*(x+1))/2+y*((x+1)*(x+2))/2;
cout<<ans<<"\n";
}
return 0;
}
Time Complexity
O(1) per test case, hence O(T) for all cases.