tanvir_cse's blog

help me with this mo's problem
By tanvir_cse, history, 8 years ago, In English

i used mos algo for this problem but got TLE on case 43,38 etc;;; i can't get whats wrong with me,,,i saw a solve my type but i got TLE

problem link : http://mirror.codeforces.com/contest/86/problem/D

my code : http://mirror.codeforces.com/contest/86/submission/19782537

thanx in advance

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

Comments Comments (9)
| Write comment?
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Advice
Let me begin with a simple advice. When you are going to ask someone to look at your code in order to help you, just don't write such an ugly code! Really, reading those defines is awful if you are not used to them.

My experience with this problem
When I was solving the problem, I was also getting TLE in the beginning but I managed to get accepted with some optimizations (I see I have a solution running in 1.3 seconds). So here is how I managed to make your code get accepted...

Optimization 1 — Storing the block for each query in the structure, instead of computing it every time we compare two queries (TL #51)
Well, it is well known that division is a slow operation, so it's better to do it O(N) instead of O(NlogN) times — http://mirror.codeforces.com/contest/86/submission/19783742.

Optimization 2 — Dividing unsigned instead of signed integers (Lucky accepted)
I think it's not so well known but division (and modulo operations) are faster on unsigned integers, so I just replaced int with unsigned everywhere I need to use division and it managed to get accepted very luckily — http://mirror.codeforces.com/contest/86/submission/19783819.

Optimization 3 — The simplest one — using int instead of long long for cnt[] (Not so lucky accepted)
I guess this was just enough to get accepted without the other two optimizations but I saw it lately (while writing this comment) — http://mirror.codeforces.com/contest/86/submission/19784032. However, I decided to keep the first two optimizations because I believe it's good to have them in mind and I don't want to feel like I wasted my time :D

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    int cmp(const nd& l,const nd& r){

    if(l.uu/Block==r.uu/Block){
    if (l.uu / Block % 2 == 0)
        return l.vv < r.vv;
    else
        return l.vv > r.vv;

}
else return l.uu/Block<r.uu/Block;

    } it takes only 2 second what does it mean? bro

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What two seconds are you talking about? It's clear that in this case you need some constant time optimizations, as UnknownNooby said. You have no error, it's just slow.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes im talking about @Noobgam solution but i can't understand about this condition

        if (l.uu / Block % 2 == 0) return l.vv < r.vv;

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I have never used and seen that but maybe it speeds up, as we can see from the running time.

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yah bro i just minimize division by storing block and use unsigned int it take 1.7 sec only http://mirror.codeforces.com/contest/86/submission/19785069 and thanx to u for all of this advice and help

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Your code is working so fast because it is incorrect. You can not do cans += b*(cnt[b]*2 +1); without casting it to long long anywhere.

      Testset is probably just bad. b * cnt[b] might overflow so this is undefined behaviour.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Mo's is all about constant factor. You can improve it in your case in two ways:

First major fix is fixing add and remove functions. With this simple math you will speed up your solution drastically in some cases. This time the solution barely passes the limit with that.

Second major fix is changing the way how you sort your queries, you can take a look at this example.

Third fix which is minor is that: you should not use long long values to store cnt, this isn't really helping much.

Solution with all three optimisations passes faster than half of time limit: 19784268

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Maybe It's TLE because constant of multiplication void add(int b){

cans -= cnt[b]*cnt[b]*b;
cnt[b]++;
cans += cnt[b]*cnt[b]*b;

} because (a+1)*(a+1)-a*a= 2*a+1;

change to

void add(int b){

cans += (2*cnt[b]+1)*b;
cnt[b]++;

}

So does remove function

→ Reply