ghoshsai5000's blog

How can I make this program faster — K Interesting Pairs ?
By ghoshsai5000, history, 8 years ago, In English

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.

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

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

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.

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

    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 ?

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

    Do you have any feedback ?

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

      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 used

      Put their code here so we can tell you.

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

        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.

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

          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.

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

            I have posted the other program you asked for.

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

              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.

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

                What is C(14, K) ? Can you calculate my code's time complexity ? It looks O(N) to me but I'm not sure.

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

                  14!/(K!*(14-K)!)

                  Your code runs in O(N^2).(RANGE^2 actually)

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

                  Can you provide some feedback on improving ?

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

                  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?

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

Auto comment: topic has been updated by ghoshsai5000 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by ghoshsai5000 (previous revision, new revision, compare).

→ Reply