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.
U can store a pairwise sum of elements in map.
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
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)$$$
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
sand another pointer is ate. Supposenew_v[s] + new_v[e] = required_sumBUTnew_v[s]andnew_v[e]have an element which is common to both e.g.new_v[s]was formed bya[5] + a[6]andnew_v[e]was formed bya[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 cannew_v[s + 1] + new_v[e]I may be wrong and i would really appreciate it if you could clarify this.
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$$$.
thanks!
Yes, your solution is O(N^3) with unordered map and O(N^3 * log n) with a tree map.
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?
Thanks. How did you reach upto this 1.66x10^8 value.
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.
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