PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kingmessi
Tester: watoac2001
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Prefix sums
PROBLEM:
There’s a circular cake, with M cherries placed at equal distances on its circumference.
N distinct flavors of cream are applied to this cake, the i-th of them along the sector from cherry P_i to cherry Q_i in anticlockwise order.
Find the maximum possible number of flavors a single diametrical cut that doesn’t pass through any of the cherries can touch simultaneously.
EXPLANATION:
The circular cake can be divided into M ‘segments’, the i-th segment being between the i'th and (i+1)-th cherries.
Each flavor is applied to some range of these segments - specifically, from P_i to Q_i in anticlockwise order.
So, let’s first find the number of flavors present in each of these segments.
Let A_i denote the number of flavors present in the i-th segment.
When adding a flavor from L to R,
- If L \lt R, we want to add 1 to every A_i such that L \leq i \lt R.
- If L \gt R, we want to add 1 to every A_i for each i from L to M, and then from 1 to R-1.
Each of these can be done with bruteforce in \mathcal{O}(M) time, for \mathcal{O}(N\cdot M) time in total.
This is too slow - however, notice that the operation we’re performing is always “add 1 to a segment” (or sometimes, “add 1 to two segments”).
There’s a standard way of doing many such operations fast when we only care about the final value of the array: prefix sums!
How?
Consider an array B of length M, initially filled with zeros.
To add 1 to the range [L, R) (i.e L is included but R is not), we can increase B_L by 1 and decrease B_R by 1.
After all the updates are done, consider the prefix sum array of B, i.e, the array P such that
P_i = B_1 + B_2 + \ldots + B_N.
The elements of P are exactly the final values we’re looking for!
The intuition here is that, when you do B_i += x and later take the prefix sums of array B, this is equivalent to increasing the value of the prefix sum of every index \geq i, by x.
So, our trick of increasing B_L by 1 and decreasing B_R by 1 is equivalent to:
- Increase the value of every prefix sum of indices \geq L by 1.
- Decrease the value of every prefix sum of indices \geq R by 1.
- This means only the prefix sums between L and R-1 will have their values changed, and that change will be exactly an increase by 1, which is exactly what we want!
So, using this trick, the values of array A can all be computed in \mathcal{O}(N+M) time.
Now, when performing a diametrical cut, lets see what exactly can be cut.
Suppose we cut through segment i, i.e, between cherries i and i+1.
Then,
- If M is even, we’ll also cut through segment i + \frac{M}{2}.
- If M is odd, we’ll cut through either segment i + \left\lfloor \frac{M}{2} \right\rfloor, or segment i + \left\lceil \frac{M}{2} \right\rceil.
If we cut through segments i and j, clearly we cut through A_i + A_j flavors; so try every i, find the appropriate j (there’s at most two of them, as noted above), and take the maximum A_i + A_j across them all!
There’s one small catch here though: you don’t always cut through A_i + A_j distinct flavors, because some flavor might be applied to such a large area that you cut through it twice!
However, observe that any flavor applied to half or more of the segments of the cake is one you’ll always cut through.
So, for any such flavor, add 1 to the answer immediately and simply don’t consider it when computing the A_i values.
This ensures that A_i only accounts for flavors that are applied on less the half the cake, and such a flavor can never be cut twice by a diametrical cut, so taking the maximum A_i + A_j value across all valid (i, j) pairs does work!
TIME COMPLEXITY:
\mathcal{O}(N + M) per testcase.
CODE:
Author's code (C++)
//Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) int a;cin>>a;
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define sis string s;
#define sin string s;cin>>s;
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
int smm,smn;
void solve()
{
int m,n;
cin >> m >> n;
assert(m >= 2);
assert(n >= 1);
assert(m <= 2e5);
assert(n <= 2e5);
smm += m;
smn += n;
vi l(n),r(n);
take(l,n);
take(r,n);
repin{
l[i]--;
r[i]--;
assert(l[i]!=r[i]);
}
vi pf(m);
int ans = 0;
int res = (m+1)/2;
repin{
if(l[i] < r[i]){
if(r[i]-l[i]>=res){
ans++;continue;
}
pf[l[i]]++;
pf[r[i]]--;
}
else{
if(m-l[i]+r[i] >= res){ans++;continue;}
pf[l[i]]++;
pf[0]++;
pf[r[i]]--;
}
}
rep(i,1,m){
pf[i] += pf[i-1];
}
int mx = 0;
if((m%2) == 0){
rep(i,0,m/2){
mx = max(mx,pf[i]+pf[i+m/2]);
}
cout << ans+mx << "\n";return;
}
else{
rep(i,0,m){
mx = max(mx,pf[i]+pf[(i+m/2)%m]);
mx = max(mx,pf[i]+pf[(i+m/2+1)%m]);
}
cout << ans+mx << "\n";return;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
di(t)
assert(t >= 1);
assert(t <= 100);
while(t--)
solve();
assert(smm <= 2e5);
assert(smn <= 2e5);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
m, n = map(int, input().split())
ls = list(map(int, input().split()))
rs = list(map(int, input().split()))
ct = [0]*(m+2)
always = 0
for i in range(n):
l, r = ls[i], rs[i]
if l <= r:
if 2*(r-l) >= m:
always += 1
continue
ct[l] += 1
ct[r] -= 1
else:
if 2*(m - l + r) >= m:
always += 1
continue
ct[l] += 1
ct[1] += 1
ct[r] -= 1
for i in range(1, m+1): ct[i] += ct[i-1]
mx = 0
for i in range(1, m+1):
j = i + m//2
if j > m: break
mx = max(mx, ct[i] + ct[j])
if m%2 == 1:
mx = max(mx, ct[i] + ct[j%m+1])
print(always + mx)