Problem A
Average Rank

The National Weekly Escape Room Challenge (NWERC) is a long-running competition held in Eindhoven. Every week a new escape room is presented, and anyone who completes it in their first attempt gains one point.

At the end of each week, competitors are ranked by the total number of points accumulated so far, highest first. In case of a tie, they share the same rank. In other words, the rank of a competitor is one more than the number of people with a strictly larger number of points.

\includegraphics[width=1.0\textwidth ]{ranks}
Figure 1: Illustration of Sample Input 3.

In total there have been $n$ participants in the contest, and the contest has been going for $w$ weeks. For each week you are given a list of the competitors that gained a point that week. Your task is to calculate the average rank during the $w$-week competition for each competitor.

Figure 1 illustrates the score progression in the third sample.


The input consists of:

  • One line with two integers $n$ and $w$ ($1 \le n, w \le 3 \cdot 10^5$), the number of competitors and the number of weeks. The competitors are numbered from $1$ to $n$.

  • $w$ lines (one for each week), each containing an integer $k$ ($0 \le k \le n$) followed by $k$ distinct integers $c_1, \ldots , c_ k$ ($1 \le c_ i \le n$ for all $i$), indicating that the $k$ competitors $c_1, \ldots , c_ k$ each gained a point that week.

The total number of points awarded is at most $1$ million.


Output $n$ lines, the $i$th of which contains the average rank of the $i$th competitor during the $w$-week competition. Your answers should have an absolute or relative error of at most $10^{-6}$.

Sample Input 1 Sample Output 1
3 2
2 1 2
2 1 3
Sample Input 2 Sample Output 2
3 1
Sample Input 3 Sample Output 3
5 6
2 3 5
2 3 1
3 3 5 2
3 5 4 2
2 3 4

Please log in to submit a solution to this problem

Log in