rajiv_kale's blog

How to calculate time complexity for sum of four (CSES problemset)
By rajiv_kale, history, 4 years ago, In English

I am solving a question from CSES sum of four values. I found out the time complexity to be O(n^3) and n is 1000. But most of the solutions are within 0.12 seconds. Where I am going wrong with the calculation of time complexity.

Question is :: You are given an array of n integers, and your task is to find four values (at distinct positions) whose sum is x. CSES question link

The approach i am using is to store index of each element in unordered_map and then traverse the array using three loops to find three elements a1 , a2 , a3 and then check if sum-(a1+a2+a3) exists in map. It seems to be O(n^3) or O(n^3 *log n) with map , but it is getting passed within .12 or max .4 seconds. Shouldn't it get TLE verdict when n is 1000. Making O(1000000000).

I would like to know where I am wrong with the calculations.

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

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

U can store a pairwise sum of elements in map.

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

    Thanks but my question is how to calculate the time complexity of solution I submitted. It isn't O(N^3) otherwise it would have TLE but when I calculate it comes out to be O(N^3). It will be helpful if you can tell me how to calculate complexity for these tricky cases

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      The complexity is probably more like $$$\frac{1000\cdot999\cdot998}{6}$$$ since you can assume that the index of $$$a_1>a_2>a_3$$$. In c++ this can be quick enough (and I don't know if the test cases are strong).

      But still, that solution was probably not intended to pass and the author wanted the meet in the middle solution with complexity $$$O(n^2)$$$

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        MZuenni i dont think meet in the middle would work. Can you prove me wrong please? I assume you are saying

        • we store all pairwise sums

        • sort the vector

        then we try meet in the middle for the new vector(say new_v) formed.

        why it wont work — suppose my one pointer is at s and another pointer is at e. Suppose new_v[s] + new_v[e] = required_sum BUT new_v[s] and new_v[e] have an element which is common to both e.g. new_v[s] was formed by a[5] + a[6] and new_v[e] was formed by a[5] + a[8]

        now what do you think is optimal? incrementing s or decrementing e? (i think neither). as it might happen new_v[s] + new_v[e - 1] was a possible answer. so can new_v[s + 1] + new_v[e]

        I may be wrong and i would really appreciate it if you could clarify this.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          First, we create two sorted vectors $$$A, B$$$ with pairs. Second, we know there is a solution with the indices in sorted order, thus we only create pairs a,b with $$$a<b$$$. to solve ties in $$$A$$$ we try to minimize $$$b$$$ and to solve ties in $$$B$$$ we maximize $$$a$$$. Now while doing the meet in the middle we only combine entries from $$$(a,b)\in A$$$ with entries $$$(c,d)\in B$$$ where $$$b<c$$$.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, your solution is O(N^3) with unordered map and O(N^3 * log n) with a tree map.

      → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I'm not sure why it would do that. On CF 10^9 would totally time out. That being said smarter loop indexing (i from 0->1000, j from i+1->1000, k from j+1 ->1000) can lead the complexity to be 1.66x10^8 (1000C3), with a very simple operation inside the loops. Other than that perhaps the judge is faster?

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

    Thanks. How did you reach upto this 1.66x10^8 value.

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

      If we make sure that when selecting 3 indeces, we only consider triplets such that i<j<k (by fixing our iteration as mentioned above) then the answer to how many sums we are calculating is the number of ways to pick 3 indeces from 1000, which is precisely 1000C3, which I evaluated on the calculator to be 1.66x10^8 or (1000*9999*9998)/6.

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

    we can assume that reduction in cases by smart loop indexing might have reduced the runtime after executing it. But how could we estimate that it'll work under time limit for n=1000 when n^3logn will clearly not work

    → Reply