Invitation to ICM Technex 2021 — IIT (BHU) Varanasi (Rated for Div. 2 & Div. 3)

Do you have proof for this one?

1 Like

If the array can be sorted by any number of cyclic rotations, answer is yes, else no. For detailed explanation, we are going to release the editorial.

Not exactly but this may suffice
Area of polygon =A = (L^2 n)/[4 tan (180/n)] (Googled). L is length n is number of sides

. Ratio of the area of inner polygon to outer polygon depends upon. only L(Visible).
Also this l equals
sin(theta/2)= S/L (new polygon/ original polygon).
theta is equal to angle of polygon.

Now by some math we easily get that the expectation value is
1/ (1-(ratio in change in area)) . sum of decreasing GP.

which sums up the original formula.

1 Like

It’s a simple geometric progression. We can calculate the ratio of sides using trigonometry if we suppose the initial length of side is 1. Instead of raising to the power of n (in the formula), we can exclude that part because a fraction raised to some enormous number is close enough to 0 for it to be discarded. (I’ve calculated it raised to the power of 1e12 using binary exponentation, but that part was not necessary). The rest is just implementation.

EDIT: I was replying to dhruv788

Here’s my code which does all the necessary steps and doesn’t just take the formula (but essentially the same thing, just a bit easier to grasp, it took a good amount of guessing the exponent tho):

#include <bits/stdc++.h>
using namespace std;

long double binpow(long double n, long long k) {
	long double res = 1;
	while (k) {
		if (k & 1) res *= n;
		n *= n;
		k >>= 1;
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		long double res = 1;
		long double x = (n - 2) * 180.0 / n;
		x = x / 360.0 * M_PI;
		x = sin(x);
		long double cur = x * x; // ratio of areas
		cout << setprecision(13) << fixed << (1.0 - binpow(cur, 1000000000000LL)) / (1.0 - cur) << '\n'; // geometric progression
	}
	return 0;
}
2 Likes

You only need to know the definition of expectation to solve this problem.
Let X be the random variable corresponding to the number of players so

\mathbb{E}[X]=\sum_{i=1}^{\infty} i \times \mathbb{P}(X=i)

Few trivial results,
Area of N sided polygon of side length L_0 is given by

\displaystyle\ A_{L_0}=\frac{NL_0^2}{4 \tan(\frac{\pi}{N})}

Side of the polygon made by joining the midpoints of the sides

\displaystyle\ L_1=L_0 \cos(\frac{\pi}{N} ) \\ -\\ L_i=L_0 \cos^i(\frac{\pi}{N})

So all we need to do is find \mathbb{P}(X=i) for all i.
Let’s see what \mathbb{P}(X=1) is.

REFERENCE

\displaystyle\ \mathbb{P}(X=1)=\frac{A_{shaded}}{A_{L_0}} \\ \mathbb{P}(X=1)=1-\frac{A_{L_1}}{A_{L_0} }= 1-\frac{L_1^2}{L_0^2}=1- \cos^2{\frac{\pi}{N}}=\sin^2{ \frac{\pi}{N}}

Similarly, if you work out the math then

\mathbb{P}(X=i)=\frac{A_{L_{i-1}}-A_{L_i}}{A_{L_{0}}}=\sin^2({\frac{\pi}{N}}) \cos^{2i-2}(\frac{\pi}{N})

So we just have to find the following infinite series which is a trivial Arithmetic Geometric Progression.

\mathbb{E}[X]=\sum_{i=1}^{\infty} i \times \sin^2({\frac{\pi}{N}}) \cos^{2i-2}(\frac{\pi}{N}) \\ \mathbb{E}[X] \cos^2(\frac{\pi}{N})=\sum_{i=1}^{\infty} i \times \sin^2({\frac{\pi}{N}}) \cos^{2i}(\frac{\pi}{N})

\text{Subtracting both equations.}

\mathbb{E}[X](1-\cos^2(\frac{\pi}{N}))=\sum_{i=1}^{\infty} \sin^2({\frac{\pi}{N}}) \cos^{2i-2}(\frac{\pi}{N}) =\frac{\sin^2(\frac{\pi}{N})}{1-\cos^2(\frac{\pi}{N})}=1 \\ \boxed{\therefore \mathbb{E}[X]=\frac{1}{1-\cos^2(\frac{\pi}{N})}=\cosec^2(\frac{\pi}{N})}
6 Likes

Okkk thanks

Thanks

It was just a GP…
First term = 1
Common ratio = 1/(1-sin^2(theta)))
where theta = (n-2)pi/(2n)
mine code :
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define ff first
#define ss second
#define endl ‘\n’
int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
double r = sin(M_PI*(n-2)/(2n));
r
=r; // it is r multiplied by r[not visible bcoz of codechef font problem]
double ans= 1/(1-r);
printf("%.8lf",ans);
cout<<endl;
}
return 0;
}
If u hv doubt in any step, u can ask…

Sure, I liked your confidence

1 Like

:joy:

Try thinking in a reverse manner, that is from a non decreasing array, we will delete some prefix and append that prefix of numbers to end of the array and after doing this operation for certain number of times , you will find that you have the array like:-

[3 3 3 3 3 4 4 4 1 1 1 2 2] for our original array :- [1 1 1 2 2 3 3 3 3 3 4 4 4 ]

If you are able to notice the modified array, you can easily see the elements follow a pattern:-
(1) elements are in non decreasing order to certain extent, then
(2) it decreases to some value and then follow the same pattern of non decreasing sequence.

So, Overall for the given input array which we need to make it non-decreasing sequence by allowed operations(delete some suffiix and insert at the beginning of the array) , we can have following answers:-
(1) Answer is “YES” if:-
(i) Given array is already in non-decreasing order.
(ii) Given array has exactly on change point(arr[i]<arr[i-1] for valid ‘i’) and arr[n-1]<=arr[0]
(2) Else, answer is “NO”

Link to Code

Hope this helps.

1 Like

I think it was more geometric ,constructive and maths questions .
Can anyone explain what logic is used in this - ICM0003 Problem - CodeChef .

The questions were a bit difficult to be rated for only div2 and div3.

Few queries -
How does rating change work out with parallel contests? Which contest is considered first? If one’s division changes after the first contest, how does it affect the rating calculation in the second?
@admin @shikhar7s

I think P(X=i) would be sin(A) ^ (2i-2) * cos(A) ^ 2 and E(X) would be sec(A) ^ 2, where A = (N-2) * PI / N / 2.

Update -
Hey, I made a mistake. The explanation is correct. Thanks.

The contest which starts first is calculated first.
Division change after the first contest does not affect the second contest’s rating calculation.

1 Like

Thanks a lot, @admin!
In case of division change after first contest calculation, for the second contest calculation, is the contestant considered belonging to the changed division or the division in which (s)he participated? If latter, how are the rating changes combined?

The latter. There is no non-trivlal combination - it shows up in the user profile that they participated in the contest in whichever division they actually participated in, even if according to their (retrospective) rating then, they should have been in a different division.

1 Like

Thanks!

when will the ratings come??

2 Likes