No.2873 Kendall's Tau
タグ : / 解いたユーザー数 79
作問者 :
寝癖
/ テスター :
yuusaan
👑 
seekworser
Problem Statement
Given $N$ data points $(x_1,y_1),\cdots,(x_N,y_N)$, find Kendall's rank correlation coefficient.
Here, Kendall's rank correlation coefficient $\tau$ is defined as follows. \[\tau=\frac{P-Q}{\sqrt{R\times S}}\]
- $P$: the number of pairs of distinct indices $(i, j)\ (1\le i < j\le N)$ such that $(x_i-x_j)(y_i-y_j)> 0$
- $Q$: the number of pairs of distinct indices $(i, j)\ (1\le i < j\le N)$ such that $(x_i-x_j)(y_i-y_j)< 0$
- $R$: the number of pairs of distinct indices $(i, j)\ (1\le i < j\le N)$ such that $x_i\neq x_j$
- $S$: the number of pairs of distinct indices $(i, j)\ (1\le i < j\le N)$ such that $y_i\neq y_j$
Under the constraints of this problem, it is guaranteed that $R\times S\neq0$.
Input
$N$ $x_1\ y_1$ $\vdots$ $x_N\ y_N$
- $2\le N\le 2\times10^5$
- $|x_i|,|y_i|\le10^9$ for all $i$
- There exists a pair of distinct indices $(i,j)$ such that $x_i\neq x_j$
- There exists a pair of distinct indices $(i,j)$ such that $y_i\neq y_j$
- All input values are integers
Output
Print Kendall's rank correlation coefficient on a single line.
Your answer is judged as correct if its absolute or relative error from the expected answer is at most $10^{-6}$.
Sample
Sample 1
Input
3 1 4 1 5 9 2
Output
-0.8164965809277260
The values of $P,Q,R,S$ in the definition of Kendall's rank correlation coefficient are as follows.
- $P=0$, since no pair satisfies the condition
- $Q=2$, since the pairs $(1,3),(2,3)$ satisfy the condition
- $R=2$, since the pairs $(1,3),(2,3)$ satisfy the condition
- $S=3$, since the pairs $(1,2),(1,3),(2,3)$ satisfy the condition
Therefore, the required value is $\frac{0-2}{\sqrt{2\times3}}=-\frac{2}{\sqrt{6}}=0.816496...$.
Sample 2
Input
2 1 1 2 2
Output
1.0000000000000000
Sample 3
Input
5 4 4 5 7 0 4 2 10 -6 4
Output
0.3585685828003181
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。