ROTATPOL What's wrong with this approach?

general
1

I have tried many approaches for the problem ROTATPOL. Some got 50 points, however the last one which I think was the most optimal, got 0 points. I wonder if there’s anything wrong with that approach or it was a precision problem.

My final solution (top 226 lines) is trying to find a line splitting the vectors into two groups that a vector perpendicular to this line satisfies the conditions. That line can’t be parallel to any given vectors, otherwise the S_i would be 0. Thus, to find that line, for every given vector I considered the line just below and just above it. By just below, I mean the angle of the given vector minus epsilon. For each such line, it can be validated in \mathcal{O}(logN) time. How I do it? First, I keep a sorted array of pairs - (angle, original_order) in an ascending order. Then for each vector with angle \alpha, find the indices of the minimum and maximum pairs which have their angles in the interval [\alpha, \alpha + \pi). Let \ell and r be those indices. To verify that the vectors that fall into this interval
have the indices consecutive in the given input, I check iff the max_original_index - min_original_index == r - \ell.

Kudos to the testers :clap: , because my randomized solution passed 9 out of 11 tests, the 2 failing were in separate subtasks resulting in 0 score points :smiley: .

1 Like
2

you might made some mistake while implementing, this was more or less also my approach and worked

It’s not enough to check just above and below, you need to check the entire range from current vector to next one (polar order)

3

In my opinion the sub tasks you have got wrong are the ones where some of your answers aren’t giving (0,0) when it must have given. Your approach is almost similar to what i have done while sweeping all epsilon + vectors and maintaining a set .

See my submissions :
(before fixing for cases having 0 , 0 as answer)
https://www.codechef.com/viewsolution/37866585

after fixing it
https://www.codechef.com/viewsolution/37873999

The idea to fix it is to update every element together when there are multiple points with same directional value.
Line 178 and 179 , they are the only changes i made

4

Thanks @gigaliths for your reply! I had thought of the opposite case for the failing tests. Because when my solution finds a nonzero vector, then it actually checks if it really satisfies the conditions, otherwise throws an exception: L103: throw new IllegalStateException("Found point should be ok");. I think it’s the case when my solution doesn’t find an answer when there’s one.

I spent so much time on this - made 3 pages of submissions :slightly_smiling_face: - so at the end didn’t bother to move to storing angles as rational numbers as opposed to floating numbers. Not sure if this would work. If it’d then it means it’s the underflow/overflow issue with decimal numbers which shouldn’t be the case because I used epsilon interval for double comparisons. :man_shrugging:

5

Well i assumed there is a 2e9*2e9 square around the xy plane , and the vector will meet at some point in this square boundary. Now just find the nearest integer coordinate to it , and that will act as your (epsilon vector which can be obtained in O(1) . hence there would be no unnecessary complications with float values.

6

Can you explain your approach for this problem in simpler language so that i can upsolve it…

7

Firstly we find all the vectors by doing Pn - Pn-1.
I will reduce the question to this statement : Find a line such that i can group a set containing all elements in [ L , R ] in one side of the line and rest will be in other side of the line.
the elements are basically the vectors. Geometrically a dot product will act as a projection , same side is '+" and opposite side is ’ - '.

Now the real question is how will i find such lines?
we could do a trick here , Lets imagine a (2e9 * 2e9) square .(thats the max constraint)
obviously the vectors obtained with respect to origin will meet the square at some point.
Find the nearest clockwise left of the points.
( I will call this line as Epsilon vector)

For example :
vector (1 , 1) meets the square at (2e9 , 2e9) , hence the nearest clockwise left point lying on the square is (2e9 - 1 , 2e9).

vector(2 , 1) meets the square at (2e9 , 1e9) , so the point is (2e9 , 1e9 + 1).

As i took Clockwise left Line of this vectors , if i use epsilon vector( vector B ) , i will have B on clockwise right side of my line. So , intuitively the Dot product with right perpendicular of this line will always give me ‘+’ for B and left perpendicular will give ‘-’ for B.

For Sub-task 1 , you could just check dot product of each vector with each perpendicular of(epsilon vector) . So that would be O(N*N).
N perp(epsilon vectors) being checked with all N vectors.
Dot product takes O(1) and checking for required condition to have continuous elements to have dot product as ‘+’ value takes O(N).

Code snippet for subtask 1.

        ans = {0 , 0};
        for(auto p : bl) //bl has all pairs of epsilon vectors (pairs)
        {
            int dot[n];
            // perpendicular(x,y) = (-y , x)
            pii pp = {-p.second , p.first}; //pp = perpendicular of the taken vector.
            int pos=0; //Total Positive Dot products
            for(int i=0 ; i<n ; i++)
            {
                dot[i] = pp.first*v[i].first + pp.second*v[i].second;
                if(dot[i] >0)pos++;
            }
            int continuous_pos=0;
            int tracker=0;
            for(int i=0 ; i<n ; i++)
            {
                if(dot[i] == 0)break;
                if(dot[i] > 0)
                {
                    tracker++;
                }
                else
                {
                    continuous_pos = max(continuous_pos , tracker);
                    tracker=0;
                }
            }
            continuous_pos = max(continuous_pos , tracker);
            if(continuous_pos == pos)
            {
                ans = pp;
                break;
            } 
        }
        cout<<ans.first<<" "<<ans.second<<endl;

For Subtask 2 , we can have an observation that if we find all the epsilon vectors and move in clockwise or anti-clockwise manner.
Assign epsilon(A) as +A and assign -epsilon(A) as -A when we encounter.
We could actually use this to maintain a set and update accordingly.
Your set maybe assigned as the elements in the right of the rotating line.
now to check if we have continuos sequence of numbers in the set , A small trick can be used.

if set has {3,4,5} i could just check is Sum(set) = ( PP+1 - CC-1)/2
where P = (first_element + set.size() - 1)
and C = (first_element).

Comparator to sort coordinates in clockwise fashion.

bool cmp( const pair<pii , int> &a , const pair<pii , int> &b)
{
    ld angle1 = atan2(a.first.second , a.first.first);
    ld angle2 = atan2(b.first.second , b.first.first);
    if(angle1 > angle2)return 1;
    else return 0;
}

Now the rest part is exercise for you.

9

In this problem, I was unable to find exact mid point after getting starting and ending point. I just tried (2x±1,2y±1) and one more way. And verified in O(n). Here (x,y) are 90 degrees rotated points from starting point.

10

nice explanation but i i didnt get that why you took 2e9 max constraint is 5e8 in question??

11

I did some major overthinking on this problem. I was thinking about dual cones and checking their intersection and found it difficult to implement. This was still O(n^2). Need to work more on implementation skills. I was confused about handling angles modulo 2\pi and never got to actual implementation. :frowning:

1 Like
12

The max constraint i can keep for a V is 2e9 ( stated in the question) and the max constraint for a given point is 5e8. Hence keeping the maximum will ensure it doesnt mingle with some other over existing point.

13

and what is exact meaning of nearest clockwise left point?? and what is significance of it ??

14

the exact meaning will be to find a vector which can be represented rationally ( y/x integral form and lies inside the max range for V(2e9)) which comes just clockwise left of the vector.
Eg :- Lets denote a vector (1, 2) , we could write it in the form ( x , 2x ) because vector is just a ratio of (y/x) or vica-versa.
we could similarly write (1,2) as (1e9 , 2e9) which is also the point where 2y = x meets the square i mentioned in my method above.
now clockwise left point can be taken as (1e9-1 , 2e9) which can be represented as vector
( 1 , 2.000000/0.999999) == (1 , 2.000001) , so clearly this vector is the nearest vector you can achieve to (1,2) and we call it the epsilon vector.
hence i call epsilonLeft( 1, 2) == (1e9 - 1 , 2e9)

The significance is that using these epsilon vectors you can include and exclude individual elements as you cant have any other vector between vector and epsilon vector.
You will have to try the testcases by drawing the above stuff to get a clearer idea.

15

I have figured what I missed in my implementation. Apparently, when I found a splitting line, I was only checking the set of points on one side of that line, not both sides :man_facepalming:. Adding that check passed all tests :smirk:
Anyway, I found my answer :white_check_mark: