competitive

[nikita00]

problem link : https://www.spoj.com/problems/DQUERY/


i applied MO's ALgorithm and i don't know why i am getting TLE please tell what changes i should make in my code
My code:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#define ll long long int
using namespace std;

vector < pair < ll, pair<ll,ll >> > vec;

std::unordered_map<ll, ll> m;
ll ans=0,bucket;
ll final[200005],a[200005];
bool compar(pair<ll,pair<ll,ll>> p1 , pair<ll,pair<ll,ll>> p2){

if(p1.second.first/bucket!=p2.second.first/bucket)

return p1.second.first/bucket < p2.second.first/bucket;

return p1.second.second<p2.second.second;
}

void add(ll currl){
m[a[currl]]++;;
if(m[a[currl]]==1)
ans++;
}

void remove(ll currl){
m[a[currl]]--;
if(m[a[currl]]==0)
ans--;
}
int main(int argc, char const *argv[])
{ ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,i;
cin>>n;
bucket = (ll)sqrt(n);
for(i=0;i<n;i++){
cin>>a[i];
}
ll q,l,r;
cin>>q;
for(i=0;i<q;i++){
cin>>l>>r;
l--;r--;
vec.push_back(make_pair(i,make_pair(l,r)));
}
sort(vec.begin(),vec.end(),compar);
ll currl=0,currr=0;
for(i=0;i<vec.size();i++){

while(currl<vec[i].second.first){
remove(currl);
currl++;
}

while(currl>vec[i].second.first){
add(currl-1);
currl--;
}
while(currr<=vec[i].second.second){
add(currr);
currr++;
}
while(currr>vec[i].second.second+1){
remove(currr-1);
currr--;
}

final[vec[i].first] = ans;

}

for(i=0;i<q;i++){
cout<<final[i]<<endl;
}
return 0;
}

[ne555]

> i applied MO's ALgorithm
please, DEA


> i don't know why i am getting TLE
¿what's the complexity of the preprocessing?
¿what's the complexity of solving one query?

read the limits and suppose the worst case: you may have 200000 queries, each one being the range 1, n
¿how many operations would you do in such case? that shouldn't exceed 10e6


so reduce your query complexity to O(1) or O(lg n)

[jonnin]

use code tags for nontrivial code samples.

the code looks to not be tweaked for performance at all.

just a couple of the quick spots:

you did not preallocate a size for vec.

compare is terribly inefficient (assumption that this will be called a LOT).

bool compar(pair<ll,pair<ll,ll>> p1 , pair<ll,pair<ll,ll>> p2)
{

//if(p1.second.first/bucket!=p2.second.first/bucket)
if(p1.second.first!=p2.second.first) 
//this is the same, right?  x/3 == x/3 is the same as  x==x, right? division costs. 
return p1.second.first < p2.second.first; //bool result is same, as above
//return p1.second.second<p2.second.second; 
return (false or true).  I am not sure WHAT you know here, 
but you should know if this should be false or true result at this point, I think.  
Is it possible to just return a constant?
}

ideally the function would be as simple as you can make it following this format:
if(something) 
return true
return false
or, even better when you can,
return expression;

m[a[currl]]++;; //why two ; ?? does not matter but weird.

does make pair cost you anything (data copy or memory allocation?) I haven't used it a lot and don't know if its a hit or not, but you are calling it a lot.

[ne555]

@jonnin
you are reading the comparison incorrectly
it's on the form

if(A)
   return true;
return B;

also, don't sweat the small stuff

[jonnin]

it is called a bunch due to being used in the sort. anything that can be done to improve it will have an impact, a significant one if the # of things sorted is large. If the sort is NlgN comparisons done and there are 100k items in the list, it does over 200k unnecessary divisions, which is a multi-clock cycle operation. Yes, it can do that in under a second, but the fastest correct code wins these competitions, and waste is waste.

if it can be rewritten to return comparison result or if not to a comparison / return true else return false it would save significant effort for larger sorts.

To your point though, if the overall algorithm is borked, it won't help. Fix that first, and if that eliminates the sort, so much the better. My point wasn't even the sort though, so much that the whole program has not had a performance pass at all. There are several other 'small stuff' things that drag it down.

[TwilightSpectre]

As an aside, for integers, you can't simplify a/x == b/x to a == b – the second implies the first, but the first does not imply the second.

1 2 3 4

3/3 4/3 3/3 == 4/3 3 == 4

1 1 true false

[jonnin]

True, I was totally working as if that were doubles. You can't avoid the divisions if that behavior is intentional. Which puts me back where I started, the comparison is convoluted making the sort result weird (its not truly sorted, as far as I can tell, its 'almost sorted'??) and Ill just admit I don't know what he is doing here or the real intentions.

[nikita00]

do you guys know the concept of mo's algorithm? i am first sorting on the basis of blocks/buckets and then on the basis of r (right query)

[ne555]

you could at least provide a link.
https://www.hackerearth.com/practice/notes/mos-algorithm/
it says it has O((N + Q) * sqrt(N) * F) complexity, using the limits it gives around 400e6

that's too much, you may solve this problem with O(N lg N + Q), which is around 0.5e6, with a prefix sums approach

[nikita00]

@ne555 i have seen people's submission and it was accepted using MO's Algorithm. What change shoulld i make so that it should not show tle . like look through the code below this was accepted.

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 311111
#define A 1111111
#define BLOCK 555 // ~sqrt(N)

int cnt[A], a[N], ans[N], answer = 0;

struct node {
int L, R, i;
}q[N];

bool cmp(node x, node y) {
if(x.L/BLOCK != y.L/BLOCK) {
// different blocks, so sort by block.
return x.L/BLOCK < y.L/BLOCK;
}
// same block, so sort by R value
return x.R < y.R;
}

void add(int position) {
cnt[a[position]]++;
if(cnt[a[position]] == 1) {
answer++;
}
}

void remove(int position) {
cnt[a[position]]--;
if(cnt[a[position]] == 0) {
answer--;
}
}

int main() {
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);

int m;
scanf("%d", &m);
for(int i=0; i<m; i++) {
scanf("%d%d", &q[i].L, &q[i].R);
q[i].L--; q[i].R--;
q[i].i = i;
}

sort(q, q + m, cmp);

int currentL = 0, currentR = 0;
for(int i=0; i<m; i++) {
int L = q[i].L, R = q[i].R;
while(currentL < L) {
remove(currentL);
currentL++;
}
while(currentL > L) {
add(currentL-1);
currentL--;
}
while(currentR <= R) {
add(currentR);
currentR++;
}
while(currentR > R+1) {
remove(currentR-1);
currentR--;
}
ans[q[i].i] = answer;
}

for(int i=0; i<m; i++)
printf("%d\n", ans[i]);
}

[E0p9LyTq]

@arj0001,

could you PLEASE learn to use code tags? They will making reading your source MUCH easier.

HINT: you can edit your posts and add code tags.

http://www.cplusplus.com/articles/jEywvCM9/

[jonnin]

what changes did you make from our suggestions so far, and how much improvement did that give?

what is your current code?

[nikita00]

Nothing much! and am damn sure that my comparator is fine rest what else should i change

[jonnin]

the vector not being preallocated.
And consider that Ness said about using a better algorithm?

Then run it through a profiler and see what is eating the time.