I have tried to solve the problem of finding k-interesting pairs [here].(http://codeforces.me/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.](http://codeforces.me/contest/769/submission/25240490)↵
↵
[Here's](http://codeforces.me/contest/769/submission/26229806) my code. Please help me. ↵
↵
Also, one more question — The same program seems to be performing at [78 ms here](http://codeforces.me/contest/769/submission/26229806) and at [93 ms here](http://codeforces.me/contest/769/submission/26229961). What is the reason for the difference ? This may help me understand and speeden things up.
↵
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.](http://codeforces.me/contest/769/submission/25240490)↵
↵
[Here's](http://codeforces.me/contest/769/submission/26229806) my code. Please help me. ↵
↵
Also, one more question — The same program seems to be performing at [78 ms here](http://codeforces.me/contest/769/submission/26229806) and at [93 ms here](http://codeforces.me/contest/769/submission/26229961). What is the reason for the difference ? This may help me understand and speeden things up.
