Angle - editorial

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Trigonometry and Basic Data Structures.

PROBLEM:

Given a sequence A of length N, choose any three distinct elements A_x, A_y and A_z such that

  • |XY| = A_z, |XZ| = A_y, |YZ| = A_x
  • The angle ∠YXZ = θ satisfies \cos θ \geq P/Q

If there are multiple triangles satisfying above, choose the one which results in maximum angle θ. Find such a triangle or determine that it does not exist.

SUPER QUICK EXPLANATION

  • Law of cosines state that if |XY| = z, |XZ| = y, |YZ| = x, then z^2 = x^2 + y^2 - 2*x*y*\cos θ.
  • Since we need \cos θ \geq P/Q, we rearrange law of cosines to get z^2*Q \leq (x^2+y^2)*Q - 2*x*y*P. We also need to check if the sum of two sides is greater than the third side.
  • We fix two elements x and y and try to find z using binary search (preferred) or lower bound on sets. If multiple triangles we find, we take the one with the minimum value of \cos θ as \cos θ and θ are inversely related.

EXPLANATION

First of all, I am explaining the Law of cosines, which states that

If |XY| = z, |XZ| = y, |YZ| = x, then z^2 = x^2 + y^2 - 2*x*y*\cos θ.

Since we have N \leq 1000, we can fix two sides of triangle XYZ, say XY and XZ, and try to find a side for which \cos θ \geq P/Q.

Let us write the inequality in terms of \cos θ.

\cos θ = \frac {x^2+y^2-z^2}{2*x*y} \geq \frac{P}{Q}

After reaarranging the terms of inequality, we get

z^2*Q \leq (x^2+y^2)*Q-2*x*y*P

We have all terms except z in above inequality. Also, notice, that since Q \geq 1 and z \geq 1, Q*z^2 is an increasing function of z and thus, if we sort the sides by non-decreasing order of length, only segments from the start upto a particular segment will satisfy above inequality, depending upon values of x, y, P and Q.

This gives way to Binary Search if we sort the given sides, we can use binary search to find the side. Additional check is required to make sure that we do not select the same side twice (in case we had chosen the side we found already as x or y.) or checking if this combination of sides (x, y, z) satisfies Triangle Inequality Theorem which states that sum of any two sides should be greater than third side. You may read about triangle inequality here if you want to.

Now, suppose we have multiple answer, so, how to find which triangle results in larger value of θ. For this, we need to understand the behaviour of \cos θ as θ increases, in range [0, 180). We can find, that the cos function is strictly decreasing function in this range, hence, we can just see, that to maximize θ, we need to minimize \cos θ.

Every time we hit a valid triangle, we can just apply Law of Cosine again to find the value of \cos θ, and choose the one with minimum value of θ.

In case we do not find a valid triangle, we simply print -1.

To print indices, we can make values as (value, index) pairs sorted by value so that we can find index of values easily.

Alternative Implementation

We can just use multiset, iterate over every pair (x,y), remove both from set and make lower_bound query to find the third side. After query, we add the removed elements back and continue.

Note that the insert and delete operations increase the constant factor a lot, and thus, may work slower than binary search. Just mentioned this, as a side thought. :stuck_out_tongue:

Another Rant from Editorialist

Though it is rare to see such type of problems, it never hurts to know basics of trigonometry, about increasing and decreasing functions, concept of local maxima and local minima and so on. These are usually worth a read.

Time Complexity

Time complexity is O(N^2*logN) per test case. Log factors due to multiset operations.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2

I used the same method as the alternate implementation here but it gives WA… is there anything else that needs to be considered or am i missing something ?

3

I am getting WA. I have done everything you mentioned in the editorial.

Here is my code.

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mod 1000000007
int main() {
int t;
cin>>t;
for(int x1 = 0; x1 < t ; x1++){
    int n;
    double p,q;
    cin>>n>>p>>q;
    vector<pair<int,int>> a;
    for(int i = 0 ; i < n ; i++){
        int temp;
        cin>>temp;
        a.push_back(make_pair(temp,i));
    }
    double costheta = p/q;
    sort(a.begin(),a.end());
    double mincostheta = 1;
    vector<int> ans;
    for(int i = 0 ; i < n ; i++){
        for(int j = i+1; j < n-1 ; j++){
            double ax = a[i].first;
            double ay = a[j].first;
            //binary search
            int low = j+1;
            int high = n-1;
            double val = sqrt((ax*ax) + (ay*ay) - (2*(ax*ay)*costheta));
            while(low <= high){
                int mid = low + (high-low)/2;
                double az = a[mid].first;
                if(ax+ay <= az){
                    //move left
                    high = mid-1;
                   // cout<<"dwd";
                }
                else if(az <= val){
                    //found but minimse it
                    low = mid+1;
                    //cout<<"dwd";
                    //calculate costtheta
                    double temp = (((ax*ax)+(ay*ay)-(az*az))/(2*ax*ay));
                    if(temp <= mincostheta && temp >= costheta){
                        mincostheta = temp;
                        ans.clear();
                        ans.push_back(a[i].second);
                        ans.push_back(a[j].second);
                        ans.push_back(mid);
                    }
                }
                else if(az > val){
                    high = mid-1;
                   // cout<<"dwd";
                }
            }
            //binary search done
        }
    }  
    if(n < 3){
        cout<<"-1"<<endl;
        continue;
    }
    if(ans.size() == 0){
        cout<<"-1"<<endl;
    } 
    else{
        cout<<ans[0]+1<<" "<<ans[1]+1<<" "<<ans[2]+1<<endl;
    }
  }
  }
4

First thing, you are taking indices of sorted array for output while in problem, you have to print indices as per input.

Second thing, You are using floor division. Avoid division, but use cross multiplication to get only addition, subtraction and multiplication terms.

Last thing, Even if you find the correct triangle, you are print indices in wrong order. Order should be z1 x1 y1.

Hope this helps. :slight_smile:

5

Didn’t go through your code thoroughly, but Seemingly, you missed the case, where the binary search may find the element which we have already used. Already used i mean elements at position a[i].second and a[j].second in original array.

You can add a check, if current element has index same as a[i] or a[j], move mid to left. See setter’s implementation, quite similar.

6

Thanks a lot… The mistake is the one mentioned in the first one. I didn’t notice i am taking the indices of the sorted array.

Although, The second thing isn’t a problem since i used long double. I got AC now after fixing it: https://www.codechef.com/viewsolution/21507462

7

I can’t find the cases where my solution fails. Could you please provide some test cases?

8

Can someone please suggest what is wrong in my code, I coded it as per the editorial but am getting WA.

My solution

9

Link to the tester’s solution has a O(N^3) solution. It should time out.
So it just to test the correctness?
http://www.codechef.com/download/Solutions/SNCKPE19/tester/ANGLE.cpp

10

Yes, It is just checking correctness.