Dot Product Optimization

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

I have been trying to solve this problem on SPOJ-- (http://www.spoj.com/problems/DPMAX/)
After 6hrs of trying and 16 wrong submissions, I have finally decided to seek some help.
Brief Overview
We are given n vectors. The problem asks us to calculate the maximum dot product of every vector with any other vector including itself. The absolute value of x and y coordinates is less than equal to 10^5. And there are 2*10^5 vectors to process.

My approach
1.Take these vectors as points. Find their convex hull.
2. The answer for all vectors will be the dot product with another vector with its end as a point of convex hull found
3.Hypothesis--The maximum dot product for a vector lying in first quadrant should be with a vector which forms the upper right hull of the convex hull, similarly for a second quadrant vector it should be with a vector which forms the upper left hull and so on.
4.So vectors in the four different quadrants are separated into 4 different groups and the vectors are sorted to be in anti-clockwise order for each group.
5.Indices of Right-most, top-most, bottom-most, left-most points of hull are found.
6. Two-pointer approach is applied with one pointer being the starting of the sorted group and the other being points on the hull.(left-most,bottom-most...) Pairing will be of the form--First quadrant vectors with right-most point, Second quadrant vectors with the top most point and so on.
7.For the vector in consideration we move to the next point in counter-clockwise direction only if the dot-product of the next point with the vector is greater than the dot-product with current point, otherwise we move to the next vector.

This approach worked for this problem-Biathlon 2.0

My solution-- (http://mirror.codeforces.com/gym/100886/submission/28148901) However the vectors were only lying in first-quadrant for this question.

I have generated lot of random test cases and checked with brute-force solution and it had no diff at all.
Here is my solution--(http://ideone.com/RU9cZ8)

It would be great if you could tell me if my approach is wrong or some test case where my solution fails.

Thanks a lot for helping

Comments (18)

Show archived | Write comment?

ujzwt4it

7 years ago, # |

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

→ Reply

mathusalen

The hypothesis 3 is not true. Take for instance just two vectors (1,2) and (-1,1000). The first lies in the first quadrant but the maximum scalar product is attained against the second vector which is not in the first quadrant instead of the product against itself.

7 years ago, # ^ |

Isn't (-1,1000) a part of upper-right hull.

Yes I missunderstood you.

geniucos

+18

Not all the points are in the first quadrant here. My approach would be something like: consider the lines Fi(x)=a + bx for each point (a, b). Now, if we want to find the minimum dot product of a vector (c, d) with some other, we need to minimize ac + bd = c (a + b * (d/c)). So, depending on the sign (and here is the part I think you didn't take care of), you should either minimize the function Fj (d / c) for some j or maximize it. I'd also take care at cases that contain 0s if I were you because you're talking about quadrants and those points are at their margins

Thanks geniucos for answering my question. I was able to comprehend your approach. Will try to implement it and get AC. BTW my approach is a little different and is borrowed from the solution of 535E - Tavas and Pashmaks. It would be really helpful if you could also tell me what is wrong with my approach.

Klein

Isn't the maximum point one of the end points of the line segment on the convex hull that intersects the vector we're considering when we extend it as a line (in its direction)? With this approach you don't need to bother with quadrants and you can still use your two pointer approach.

Possible special cases:

The vector (0, 0).
When N < 3.

If I understood correctly what u meant. Take as vectors (1,1),(2,3),(5,1),(5,0),When we extend (1,1), it will intersect with only (1,1), whereas the maximum for it is (1*5)+(1*1). Correct me if I understood wrongly.

That falls under the second case I mentioned, but it will intersect the line segment between (2,3) and (5,1), and one of that segment's end points is the optimal choice.

I m sorry, I intended to make the second vector as (3,2) not (2,3).

Now there seems to be just one intersection with (1,1)

← Rev. 2 →

Oh I see, good catch. The vector with the biggest projection onto our vector isn't necessarily one of the intersecting segment's end points.

The question however is, does it affect the proposed solution? We actually never calculated any intersection, but only the optimal vector for some vector, and then processed the vectors in sorted order by angle and updated the optimal vector as described above. I guess the assumption we're making is that the optimal vector lies on the convex hull (or is this assumption even necessary?) and that it moves "as described above". Because if the best option for (1,1) is (5,1) then (5,1) should also be the best option for all vectors with an angle between (1,1) and (5,1).

Edit: The last statement is wrong, reason why is left as an exercise for the reader. :)

Regarding the assumption of optimal vector lying on convex hull---535E - Tavas and Pashmaks is where I got this idea from.

ujzwt4it's blog