50100. Impact Factor

I'm a slow walker, but I never walk backwards.

Write a function to compute impact factor for journals.

Task Description

The impact factor of an academic journal is a measure reflecting the average number of citations to the papers published in that journal. A paper belongs to a journal, and it can cite other papers, i.e., to mention other papers. Therefore the impact factor of a journal is the number of citations divided by the number of papers in that journal. You are given an array of paper structures. Compute the impact factor of each journal and print them in alphabetic (dictionary) order according to the names of journals.

We will store papers in an array. Every paper has an index, which is the its index within that array. Every paper has a list of papers it cites, stored in citedPaperIndex, and the number of cited papers is numCitedPaper.

1
2
3
4
5
typedef struct {
    char journalName[64];
    int numCitedPaper;
    int citedPaperIndex[1024];
} paper;

Let us illustrate this task with an example. Assume that there are six papers and their informations are as follow.

Paper 0 Paper 1 Paper 2 Paper 3 Paper 4 Paper 5
Paper id 0 1 2 3 4 5
journalName ICPP ACM IPDPS ICPP IPDPS IPDPS
numCitedPaper 1 1 1 3 2 1
citedPaperIndex 0 1 3 2, 4, 5 0, 3 4

According to this table, journal ICPP has two paper -- Paper 0 and 3. There are four citations to papers pubished in ICPP, i.e., from paper 0, 2, 4. Note that paper 4 cites two papers from ICPP (paper 0, and 3). As a result the impact factor of ICPP is 4/2. Similarly, the impact factor of ACM is 1/1 and that of IPDPS is 4/3. Note that you need to use “%d/%d” format to print the impact factor and do not reduce it.

The main function and the prototype of compute are as follow:

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#define MAXP 1024
#include "compute.h"
int main() {
    int N;
    paper P[MAXP] = {};
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%s%d", P[i].journalName, &P[i].numCitedPaper);
        for (int j = 0; j < P[i].numCitedPaper; j++)
            scanf("%d", &P[i].citedPaperIndex[j]);
    }
    compute(P, N);
    return 0;
}

compute.h

1
2
3
4
5
6
7
8
9
#ifndef COMPUTE
#define COMPUTE
typedef struct {
    char journalName[64];
    int numCitedPaper;
    int citedPaperIndex[1024];
} paper;
void compute(paper P[], int N);
#endif

Hint

You can compute the impact factor in two steps. In the first step you go through all papers and build a table of journal names and its number of papers. The way to build is to see if the name appears in the table. If it is in the table then increase the counter by one. If the name is not in the table then add one entry and set the counter to 1. In the second step you go through all papers and compute the number of citations each journal has. The way to do it is to go through all papers, find its journal name, and increase the corresponding counter by one.

Subtask

  • 10 points: There is only one journal.
  • 30 points: There are exactly two journals and every paper only cites papers from its own journal.
  • 60 points: There are multiple journals.

Input Format

The first line of input has the number of papers N. The following 2N lines are the paper informations. Each paper’s information has two lines. The first line has a string S indicating journal name, and an integer n for the number of papers this paper cites. The second line has n integers indicating the indices of cited papers.

  • 0 < N < 1025

Output Format

Print the names and impact factors of journals in alphabetic (dictionary) order according to the name of journals. Print the name in one line then the impact factor in the next line. Note that you need to use “%d/%d” format to print the impact factor and do not reduce it.

Sample Input 1

1
2
3
4
5
6
7
3
CCGRID 1
0
CCGRID 2
0 1
CCGRID 1
2

Sample Output 1

1
CCGRID 4/3

Sample Input 2

1
2
3
4
5
6
7
8
9
4
IEEE 2
0 2
ACM 1
3
IEEE 2
0 2
ACM 1
1

Sample Output 2

1
2
ACM 2/2
IEEE 4/2

Sample Input 3

1
2
3
4
5
6
7
8
9
10
11
12
13
6
ICPP 1
0
ACM 1
1
IPDPS 1
3
ICPP 3
2 4 5
IPDPS 2
0 3
IPDPS 1
4

Sample Output 3

1
2
3
ACM 1/1
ICPP 4/2
IPDPS 4/3

Discussion