I have tried to solve the problem of finding k-interesting pairs [here].(http://codeforces.net/contest/769/submission/26220768)
My solution is quadratic O(n^2). If it is run on the sequence of numbers given, then n = 10^5 at most. I have followed the trick of the editorial and built an array of the frequencies of each element. This happens in O(n) time, with n = 10^5, at most
And have then applied the quadratic time algorithm on the frequency array so now n = 10^4. However, this isn't enough to get past the time limit.
What are further optimizations I can perform ?
Edit — I have performed some optimizations and managed to get an acceptance. Please tell me how I can make this faster ? I am not able to understand the algorithm some other people who got faster solution used. Some stored only those values of x, for which Population Count[x] is k and then did something I am unable to understand. For example, programs like this one.
Here's my code. Please help me.
Also, one more question — The same program seems to be performing at 78 ms here and at 93 ms here. What is the reason for the difference ? This may help me understand and speeden things up.
Since Xor operation is fast, you probably can get accept by optimizing your code a little.
But if you're looking for a better time complexity to solve this, you can use the solution of this similar problem : 662C - Binary Table.
The problem you recommended is a bit too hard for me right now. I couldn't get any idea how to approach it and the editorial was a bit hard as well. Could you suggest some ways for me to optimize the accepted code that I have posted ?
Do you have any feedback ?
Your code runs in 78ms now, Why you wanna make it faster?
What is the reason for the difference ?20ms is not that important, It's about the power of the judge and these things.
I am not able to understand the algorithm some other people who got faster solution usedPut their code here so we can tell you.
But, the same program shouldn't be running at two speeds, right ?
I have noticed some people got it in even quicker time. I want to understand what they did that I didn't do.
Even to 100ms could be judge error. You're not dealing with a perfect judge, it's a common thing and it's not even a problem.
I have posted the other program you asked for.
That code's time complexity is O(N*C(14,K)). Instead of checking for all pairs if their xor has k bits, that code pre-processed something and now is only processing pairs that their xor has exactly k bits.
What is C(14, K) ? Can you calculate my code's time complexity ? It looks O(N) to me but I'm not sure.
14!/(K!*(14-K)!)
Your code runs in O(N^2).(RANGE^2 actually)
Can you provide some feedback on improving ?
You can use the problem that I gave you. It's O(N*lg(N)^2). Or you can use the code you linked in the blog that is O(N*C(14,K)).
You should change your algorithm for better time complexity, What do you expect?
Auto comment: topic has been updated by ghoshsai5000 (previous revision, new revision, compare).
Auto comment: topic has been updated by ghoshsai5000 (previous revision, new revision, compare).