Problem : Problem - B - Codeforces
For a div2 problem B, this was a bit tough for me. Based on the constraints and time limits it’s obvious we’re not supposed to create the matrix, we’ll simply run out of time. How are we supposed to do this in linear time?
Can someone provide a brief explanation/logic of the solution for this problem? I’ve read the editorial but can’t seem to understand. TIA
In this problem first you need to understand if the area of rectangle formed is given k, and we know that length*breadth = k, so what you need first is possible value of length and breadth.
It is easy to see that, this can be easily calculated by finding divisors of k.
Another, observation is the matrix formed c contains only 1 and 0 and every time it looks like the way it is given in example.
So, you just need to calculate the continuous value of 1 found in row and same for column. It is easy to find.
After that iterate in array of divisors of k calculated previously and add answer for every combination of length and breadth.
My AC code looks like:
#include<bits/stdc++.h>
using namespace std;
#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define pow2(x) ((x)*(x))
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n,m,k;
cin >> n >> m >> k;
ll ar1[n],ar2[m];
for(int i=0;i<n;i++)
cin >> ar1[i];
for(int i=0;i<m;i++)
cin >> ar2[i];
vl v;
for (int i=1; i<=sqrt(k); i++)
{
if (k%i == 0)
{
if (k/i == i)
v.eb(i);
else // Otherwise print both
{
v.eb(i);
v.eb(k/i);
}
}
}
sort(all(v));
ll pre1[n+1],pre2[m+1];
pre1[0] = ar1[0];
pre1[n] = 0;
for(int i=1;i<n;i++)
{
if(ar1[i]==1)
pre1[i] = 1+pre1[i-1];
else
pre1[i]=0;
}
pre2[0] = ar2[0];
pre2[m] = 0;
for(int i=1;i<m;i++)
{
if(ar2[i]==1)
pre2[i] = 1+pre2[i-1];
else
pre2[i]=0;
}
ll ar3[n+1];
memset(ar3,0ll,sizeof(ar3));
for(int i=1;i<=n;i++)
{
if(pre1[i]==0)
{
for(int j=1;j<=pre1[i-1];j++)
ar3[j] += pre1[i-1]-j+1;
}
}
ll ar4[m+1];
memset(ar4,0ll,sizeof(ar4));
for(int i=1;i<=m;i++)
{
if(pre2[i]==0)
{
for(int j=1;j<=pre2[i-1];j++)
ar4[j] += pre2[i-1]-j+1;
}
}
// for(int i=0;i<=n;i++)
// cout << ar3[i] << " ";
// cout << nl;
// for(int i=0;i<=m;i++)
// cout << ar4[i] << " ";
// cout << nl;
ll ans = 0ll;
// watch2(v[0],v[1]);
for(int i=0;i<v.size();i++)
{
int temp1 = v[i];
int temp2 = k/v[i];
if(temp1<=n && temp2<=m)
{
ans += ar3[temp1]*ar4[temp2];
}
}
cout << ans << nl;
return 0;
}Thanks, I’ll try to solve it and share my attempts here. 
See,the question asks you to find out the count of subrectangles of 1s which are a multiple of k.So,as usual your initial approach would be to create a matrix using the given data and check(but this approach doesn’t go at par with the time constraints)
So,you need to optimise
See,first of all you need to create a continuous values of 1s in each array which can easily be done by using prefix sum array
as we know,lengthxbreadth=k,so you need to check for each divisor of k,how many numbers are >= k in 1st prefix sum array(let it be x)and >=k/divisor in 2nd prefix sum array (let it be y)which can be done by using binary search(lowerbound function in c++ stl) and as we are interested in length and breadth we got our length and breadth that is x and y,so multiply them,do it for each of the divisors)
Explanation through example:-
3 3 2// n m k
1 0 1// array a
1 1 1// array b
create prefix sum array p1={1,0,1}(as we are interested in only continuous 1s,so if we get a zero,then set that element to zero)
similarly p2= {1,2,3)
now,the factors of k i.e 2 are 1 and 2 which means we can make subrectangles of size either 1x2 and 2x1
so,for (1x2) subrectangles,we check how many numbers are greater than>=1 in p1 array and how many numbers are greater than >=2 in p2 array,we multpily them(i.e 2x2=4)
similarly for (2x1)subrectangles,we find how many numbers are greater than>=2 in p1 array and how many numbers are greater than >=1 in p2 array (0)
so our answer comes out to be 4+0=4
Great explanation. I’m almost done, one doubt. How do we apply binary search on prefix sum array if it isn’t sorted? Like for [1, 1, 0, 1, 1] the presum would be [1, 2, 0, 1, 2] right? How would I find, say, no. of digits >= 2 in this?
I did try sorting it but went TLE, lol. How should I fix it?
Edit : Oh I guess the point where I’m computing divisors is taking a bit too long. I suppose i can do that in n^(0.5) time and that could fix it. Gonna try.
Glad you liked it!