BOP 2016复赛题目解析

2024-02-06 12:59
文章标签 题目 解析 2016 复赛 bop

本文主要是介绍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,但是排名靠前的队伍基本都用上了,所以还是不够细心啊……心塞

NameDescriptionTypeOperations
IdEntity IDInt64Equals
CCCitation countInt32none
AA.AuIdAuthor IDInt64Equals
AA.AfIdAuthor affiliation IDInt64Equals
F.FIdField of study IDInt64Equals
J.IdJournal IDInt64Equals
C.IdConference series IDInt64Equals
RIdReference IDInt64Equals

从上面规则描述中的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 编程之美复赛心得,后面若是还有空的话,我会按照他们的语言种类做个整合对比。


这篇关于BOP 2016复赛题目解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/684394

相关文章

在C#中合并和解析相对路径方式

《在C#中合并和解析相对路径方式》Path类提供了几个用于操作文件路径的静态方法,其中包括Combine方法和GetFullPath方法,Combine方法将两个路径合并在一起,但不会解析包含相对元素... 目录C#合并和解析相对路径System.IO.Path类幸运的是总结C#合并和解析相对路径对于 C

Java解析JSON的六种方案

《Java解析JSON的六种方案》这篇文章介绍了6种JSON解析方案,包括Jackson、Gson、FastJSON、JsonPath、、手动解析,分别阐述了它们的功能特点、代码示例、高级功能、优缺点... 目录前言1. 使用 Jackson:业界标配功能特点代码示例高级功能优缺点2. 使用 Gson:轻量

Java如何接收并解析HL7协议数据

《Java如何接收并解析HL7协议数据》文章主要介绍了HL7协议及其在医疗行业中的应用,详细描述了如何配置环境、接收和解析数据,以及与前端进行交互的实现方法,文章还分享了使用7Edit工具进行调试的经... 目录一、前言二、正文1、环境配置2、数据接收:HL7Monitor3、数据解析:HL7Busines

python解析HTML并提取span标签中的文本

《python解析HTML并提取span标签中的文本》在网页开发和数据抓取过程中,我们经常需要从HTML页面中提取信息,尤其是span元素中的文本,span标签是一个行内元素,通常用于包装一小段文本或... 目录一、安装相关依赖二、html 页面结构三、使用 BeautifulSoup javascript

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

OWASP十大安全漏洞解析

OWASP(开放式Web应用程序安全项目)发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南,它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析: 1. 注入漏洞(Injection) 描述:攻击者通过在应用程序的输入数据中插入恶意代码,从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响:可能导致数据泄

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

从状态管理到性能优化:全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动