Xbalanque's blog

Help with last Div3 Problem H
By Xbalanque, history, 2 months ago, In English

2008H - Sakurako's Test

Editorial says Let's fix one x and try to solve this task for it.

okay makes our time complexity q*(something), moving on...

How to find number of i that ai mod x ≤ m for some m

We can use binary search of some sort, making our complexity

q*log(x)*checkerForM, how in the world is this complexity not TLE

Can anyone explain it to me.

  • Vote: I like it
  • -20
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

read the complete tutorial.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So, the idea is to precompute answer for all x. For each x, we found answer in $$$O(\frac{n}{x}\cdot log(n))$$$ and in sum it will be $$$O(n\cdot log^2(x))$$$. So, we can answer querry in constant time.

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
    #include<bits/stdc++.h>
using namespace std;
 
 
bool check(vector<int>&v, int x, int m){
    int n = v.size(); int ct = 0;
    for(int k=0;k<=n/x;k++){
        ct += upper_bound(v.begin(),v.end(),k*x+m) - upper_bound(v.begin(),v.end(),k*x-1);
    }
    return ct>=(n+2)/2;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin>>t;
    while(t--){
        int n,q; cin>>n>>q;
        vector<int>v(n);
        for(int i=0;i<n;i++) cin>>v[i];
        sort(v.begin(),v.end());
        vector<int>dp(n+1);
        for(int i=1;i<=n;i++){
            int l = 0, r = i-1;
            while(l<=r){
                int m = l + (r-l)/2;
                if(check(v,i,m)){
                    dp[i] = m; r=m-1;
                }
                else l=m+1;
            }
        }
        while(q--){
            int x; cin>>x;
            cout<<dp[x]<<" ";
        }
        cout<<'\n';
    }
}

    Why does this simple code implementing your approach giving TLE

    btw Pa_sha orz

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      instead of upper bound
      use prefix count
      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        why does it matter, logx or logx*logx should be almost equal, why TLE in my case ?

        → Reply