tanvir_cse's blog

help me with this mo's problem
By tanvir_cse, history, 10 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?
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
← 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