PCJ18C - Editorial

#1

PROBLEM LINK:

Practice
Contest

Author: Madhav Sainanee
Tester: Prakhar Gupta
Editorialist: Prakhar Gupta

DIFFICULTY:

SIMPLE

PREREQUISITES:

Arithmetic Progression, Sum of internal angles of a polygon, Arithmetic of fractions.

PROBLEM:

Given an n sided polygon with the first angle a, find out the k^{th} angle if all the angles are in Arithmetic Progression with the first angle being the smallest.

QUICK EXPLANATION

Find out the sum of AP from the sum of internal angles of the polygon. The common difference can be calculated from the sum of AP and can be used to find the k^{th} angle.

EXPLANATION:

The sum of internal angles of an n sided polygon, S = 180 \times (n - 2).

This also forms the sum of the AP, i.e. S = \frac {n}{2} (2a + (n - 1) d).

From the above equation, we can find out d as a fraction.

The K^{th} angle can then be can be found out as A_k = a + (k - 1) d.

Since the numerator and denominator A_k may not be co-prime by now, divide both of them by their gcd.

Complexity: The time complexity is O(1 + log(n^2)) per test case, due to the gcd.
Note: We also allowed naive O(N) gcd algorithm.

AUTHOR’S SOLUTION:

Author’s solution can be found here.

1 Like
#2

Since the numerator and denominator Ak may not be co-prime by now, divide both of them by their gcd.

Please explain this statement .

#3

@osho_garg When you find the numerator and denominator separately, you might notice that they might have some common factor dividing them both. So you take the gcd of the two and divide both the numbers by them, to make them coprime.

#4

whats wrong in this code

https://www.codechef.com/viewsolution/19783960

my test case :
input
5
3 30 2
4 60 3
5 30 4
5 50 1
5 40 5

output:

60 1
100 1
147 1
50 1
176 1

#5

This question has not been framed carefully. In the original question, it is written that the angle A is smallest. Further the range of A is given as [1, 10^9]. With these conditions, we can have several conflicting answers:

Consider N = 4 and A = 270. Taking one of accepted answers, the angles of this quadrilateral are given as (270, 150, 30, -90). Two things to note just with the accepted solution: A = 270 is clearly not smallest, and last angle is negative (may interpret -90 as 270 though)

I posted an answer which only took positive angles and so the angle sum was no longer (n-2)180 given the conditions of question. For N = 4, A = 270 answer can very well be (270,270,270,270)

#6

/…what is the mistake in my code.i am getting wrong answer…/

#include<bits/stdc++.h>
using namespace std;
int main()
{
int test;
cin>>test;
while(test-- )
{
int n,k;
float a;
cin>>n>>a>>k;
int sum=(n-2)*180;
float difference=(((2 * sum)/(float)n)-(2 * a))/(float)(n-1);
float result=a+(k-1) * difference;
long long int r=(int)result;
long long int y=1;
float x=result;
while((long long int)r!=(float)x)
{
x=result;
y++;
x * = y;
r=(long long int)x;
}

    cout<<(long long int)x<<" "<<y<<endl;
}
return 0;

}

#7

plss tell why it gives wrong answer on simple approach with AP…as explainded

tc = int(input())
for i in range(tc):
n,a,k = map(int,input().split())
sn = (n-2)180
x = (sn2)//n
y = x-(2*a)
d = y//(n-1)
ans = a+(k-1)*d
if(ans>0):
print(ans,1)
else:
print(360+ans,1)