BOP 2016复赛题目解析

复赛题
Microsoft Academic Graph (MAG) is a large heterogeneous graph containing entities such as authors， papers， journals， conferences and relations between them. Microsoft provides Academic Knowledge API for this contest. The Entity attributes are defined here.

Participants are supposed to provide a REST service endpoint that can find all the 1-hop， 2-hop， and 3-hop graph paths connecting a given pair of entity identifiers in MAG. The given pair of entity identifiers could be [Id， Id]， [Id， AA.AuId]， [AA.AuId， Id]， [AA.AuId， AA.AuId]. Each node of a path should be one of the following identifiers: Id， F.Fid， J.JId， C.CId， AA.AuId， AA.AfId. Possible edges (a pair of adjacent nodes) of a path are:

For each test case， the REST service endpoint will receive a JSON array via HTTP with a pair of entity identifiers， where the identifiers are 64-bit integers， e.g. [123， 456]. The service endpoint needs to respond with a JSON array within 300 seconds. The response JSON array consists of a list of graph paths in the form of [path1， path2， …， pathn]， where each path is an array of entity identifiers. For example， if your program finds one 1-hop paths， two 2-hop paths， and one 3-hop paths， the results may look like this: [[123，456]， [123，2，456]， [123，3，456]， [123，4，5，456]]. For a path such as [123，4，5，456]， the integers are the identifiers of the entities on the path. After receiving the response， the evaluator will wait for a random period of time before sending the next requests.

Evaluation Metric
The REST service must be deployed to a Standard_A3 virtual machine for the final test. There are no constraints on the programming language you can use.

The test cases are not available before the final evaluation. When the evaluation starts， the evaluator system sends test cases to the REST endpoint of each team individually. Each team will receive 10 test cases (Q1to Q10). The response time for test case Qi is recorded as Ti(1≤i≤10). The final score is calculated using:

where Ni is the size of the solution (the total number of correct paths) for Qi ， Ki is the total number of paths returned by the REST service， Mi is the number of distinct correct paths returned by the REST service.

思路

题意解析：
为了帮助理解，我把文章实体各个属性含义列在下面，这里只说明比赛中要用到的带id的属性。
其中CC属性让我怨念颇深……比赛的时候完全没注意到，傻傻的用了RId.length，但是排名靠前的队伍基本都用上了，所以还是不够细心啊……心塞

从上面规则描述中的hop的定义可以看出，路径的组成只有11种：Id-Id， Id-FId， FId-Id， Id-JId， JId-Id， Id-CId， CId-Id，AuId-AFId， AFId-AuId， AuId-Id， Id-AuId。那么针对不同的Id对儿，可以找出下面的规律。

1. Id-Id， 共计15种

   • 1跳，1种 直达
   • 2跳，5种 Id1-Id-Id2，这种情况单独处理，用RId=Id2的反向查询更快捷。
     Id1-AuId-Id2， Id1-FId-Id2， Id1-JId-Id2， Id1-CId-Id2，
   • 3跳，9种 Id1-Id-Id-Id2，这种情况比较麻烦，需要前向和反向查询，url编写复杂度较高
     Id1-AuId-Id-Id2， Id1-FId-Id-Id2， Id1-JId-Id-Id2， Id1-CId-Id-Id2，Id1-Id-AuId-Id2， Id1-Id-FId-Id2，Id1-Id-JId-Id2，Id1-Id-CId-Id2

2. Id-AuId，共计8种

   • 1跳，1种 直达
   • 2跳，1种 Id-Id-AuId，1次查询就好
   • 3跳，6种 Id-Id-Id-AuId， Id-AuId-AfId-AuId，Id-AuId-Id-AuId，Id-FId-Id-AuId，Id-JId-Id-AuId，Id-CId-Id-AuId

3. AuId-Id，共计8种

   • 1跳，1种 直达
   • 2跳，1种 AuId-Id-Id
   • 3跳，6种 AuId-Id-Id-Id， AuId-AfId-AuId-Id， AuId-Id-JId-Id， AuId-Id-CId-Id， AuId-Id-FId-Id，AuId-Id-AuId-Id

4. AuId-AuId 共计3种

   • 1跳，木有
   • 2跳，2种 AuId-Id-AuId， AuId-AfId-AuId，
   • 3跳，1种 AuId-Id-Id-AuId

   看起来这是比较复杂的，需要分别写出34种的情况，但是这些可能性中有不少可以复用的。比如，通过查询一次id1,id2的属性值，就可以写出Id1-AuId-Id2， Id1-FId-Id2， Id1-JId-Id2， Id1-CId-Id2这四种2hop的了。

其实，准确无误的完成上面的思路，才刚刚进入可以比拼的大队。如果思路够清楚，花费1-2天的专注编程就可以了。
剩下的大部分时间还是花在了各种各样减少时间消耗的trick上，然而这部分我做的并不好，太过于依赖缓存的Map，导致最后的失败。

对于这些各种各样的trick感兴趣的可以看我上一篇博客:2016 BOP 编程之美复赛心得，后面若是还有空的话，我会按照他们的语言种类做个整合对比。