【总决赛赛题】2017华为软件精英挑战赛

[复制链接]
如花非花   金牌会员  发表于 2017-5-5 15:50:52

最新回复:2017-05-05 15:50:52

比赛问题定义
▌本次赛题通用性描述
网络结构模型:给定一个由若干网络节点(例如路由器、交换机)构成的网络结构无向图,每个节点至少与另外一个节点通过网络链路相连(网络链路特指两个网络节点之间直接相连的网络通路,中间没有其他网络节点,相当于无向图中的一条边),一个节点可以将收到的数据通过网络链路传输给相连的另一个节点,节点本身的转发能力无上限。每条链路的网络总带宽不同(例如某条链路的总带宽为10Gbps)。而每条链路承载的视频传输需要按照占用带宽的多少按每10秒收取对应网络租用费,每条链路的单位租用费均不同(例如某条链路的租用费为5千元/Gbps/10秒)。某条链路上被占用的带宽总和不得超过该链路的总带宽。
消费节点:给定的网络结构中有部分网络节点直接连接到小区住户的网络,每个小区住户网络在这个给定的网络结构图中呈现为一个消费节点,并存在视频带宽消耗需求。
视频内容服务器:视频内容服务器存放视频内容(如:电影影片、电视剧等),视频内容服务器的视频数据流可以经由网络节点与链路构成的网络路径流向消费节点,一台视频内容服务器可以服务多个消费节点,而一个消费节点也可以同时从多台视频内容服务器获取视频流。购买一台视频内容服务器需要硬件成本,每台视频内容服务器的输出能力存在上限(例如200Gbps/台),并分为若干档次(如1,2,3三个档次),不同档次的输出能力上限与硬件成本均不同(例如档次1的服务器硬件成本为100千元/台)。此外对于某个网络节点,部署一台视频内容服务器需要支付额外的部署成本(例如某个网络节点的额外部署成本为30千元/台),不同网络节点的部署成本可能不同。因此部署一台视频内容服务器到某网络节点的成本为该服务器硬件成本与该节点部署成本之和。
▌行为规则:
视频服务商的行为规则:
1、有多家视频服务商在相同的网络上部署视频内容服务器,但他们之间的数据流互不影响,链路总带宽也相互独立并相同,即每家服务商在网络中不会感知到其他服务商的存在。
2、参赛的每个队伍将作为其中一家视频服务商,在比赛过程中动态更新最优部署方案,与其他队伍代表的服务商共同争抢消费节点,赚取服务费用于支付成本与设备更新升级。
3、每家服务商可实时知悉任何消费节点选择哪家服务商,但是不清楚该服务商提供给该消费节点的具体视频带宽是多少(除非该服务商是他自己)。
4、比赛开始时每家服务商将被分配一定数额的初始资金用于最初部署方案,之后所有花销均来自于消费节点支付的服务费。
5、每隔10秒,视频服务商可以改变一次部署方案。每台视频内容服务器可以折旧卖出,折旧价格按如下公式计算:服务器折旧价格 = 服务器原始价格 *0.8 *(600 – 使用秒数)/ 600
消费节点的行为规则:
消费节点存在一个最低的带宽消耗需求。在满足最低需求的前提下,消费节点会选择给自己提供最大视频带宽的服务商作为签约服务商,并按每10秒为周期支付视频观看服务费。每个消费节点每10秒支付的服务费相同。如果在相同时间点上存在多家服务商提供了相同的最大带宽,则消费节点将随机选择其中一家服务商。如果某家服务商想要从其他服务商手中夺得消费节点,他所提供的带宽必须大于其他服务商提供给该消费节点的带宽。
▌比赛胜负规则
每家服务商将如果比赛过程中服务商账户余额为0,则退出比赛,并记录时间。如果所有队伍均退出比赛或比赛计时终止,则比赛结束。比赛结束时,余额越高的队伍排名越高。对于退出比赛的队伍,坚持时间越长则排名越高。如果若干队伍的余额相同且均坚持完比赛,或者退出比赛且坚持时间相同,则算为平局。
补充说明:
1. 两个网络节点之间最多仅存在一条链路,链路上下行方向的网络总带宽相互独立,并且上下行方向的总带宽与网络租用费相同。例如对于网络节点A与B之间的链路,该条链路上的总带宽为10Gbps,每10秒单位租用费为5千元/Gbps,则表示A->B、B->A两个方向上的网络总带宽分别均为10Gbps,并且租用费均为5千元/Gbps。如果某条数据流在该链路A->B方向的占用带宽为3Gbps,那么该数据流该秒在该链路的租用费为3K,并且该链路A->B方向的剩余可用带宽为7Gbps。而B->A方向的剩余可用带宽不受该数据流的影响,仍为10Gbps。
2. 每个网络节点最多仅能连接一个消费节点,每个消费节点仅能连接一个网络节点。消费节点与连接的网络节点之间的链路总带宽无限大,并且网络租用费为零。
3. 网络节点数量不超过10000个,每个节点的链路数量不超过10000条,消费节点的数量不超过10000个。
4. 链路总带宽与网络租用费为[0, 100]的整数,视频内容服务器部署成本、消费节点每10秒的视频服务费与最低带宽消耗需求均为[0,1000000]的整数。
5. 部署方案中,网络路径上的占用带宽必须为整数。
6. 每个网络节点上最多仅可部署一台视频内容服务器。
7. 购买的视频内容服务器一旦部署到某节点上之后不得转移到其他节点使用。如果需要移除、升级、降级该节点的服务器,必须先将原有视频内容服务器折旧变卖。
8. 如果某网络节点上一轮(10秒前)没有部署服务器,则本轮部署服务器需要支付部署成本。否则如果该网络节点已部署了服务器,需要升级或降级服务器的档次,则无需支付部署成本。
9. 比赛时长为10分钟。
程序输入与输出
▌输入文件格式
程序输入为一个以空格分隔的文本文件,文件每行以换行符(ASCII’\n’即0x0a)为结尾。
文件格式为:
网络节点数量网络链路数量消费节点数量参赛队伍数量
(空行)
消费节点每秒视频服务费
(空行)
视频内容服务器档次ID 输出能力硬件成本
。。。。。。(如上视频内容服务器信息若干行)
(空行)
网络节点ID 部署成本
。。。。。。(如上网络节点部署成本信息若干行)
(空行)
链路起始节点ID 链路终止节点ID 总带宽大小每秒单位网络租用费
…………….(如上链路信息若干行)
(空行)
消费节点ID 直接相连的网络节点ID 最低带宽消耗需求该节点选择的队伍ID
…………….(如上消费节点信息若干行)
(空行)
本队伍ID 账户剩余金额
(文件结束)
说明:
1. 网络节点ID,消费节点ID,视频内容服务器档次ID,队伍ID均为以0为起始的连续整数。
2. 文本中出现的所有数值均为大于等于0的整数,数值上限为5000000。
3. 输入文件中消费节点信息与本队伍账户剩余金额每隔10秒会更新一次,然后由判题系统调用队伍的比赛程序读取该输入文件作为程序该次的输入数据。
▌输入文件示例
程序输出为一个以空格分隔的文本文件,文件每行以换行符(ASCII’\n’即0x0a)为结尾。
文件格式为:
网络路径数量
(空行)
网络节点ID-01 网络节点ID-02 …… 网络节点ID-n 消费节点ID 视频内容服务器档次ID 占用带宽大小
…………….(如上网络路径信息若干行,每条网络路径由若干网络节点构成,路径的起始节点ID-01表示该节点部署了视频内容服务器,终止节点为某个消费节点)
(文件结束)
说明:
1. 网络路径数量不得超过100000条。
2. 单条路径的节点数量不得超过10000个。
3. 不同网络路径可按任意先后顺序输出。
4. 网络节点ID与消费节点ID的数值必须与输入文件相符合,如果ID数值不存在于输入文件中,则将被视为无效结果。
5. 文本文件中出现的所有数值必须为大于等于0的整数,数值大小不得超过5000000。
6. 比赛程序可随时更新输出文件,每隔10秒判题系统会读取比赛程序的输出文件并更新部署方案,然后根据上一轮与本轮的部署方案更新队伍的账户剩余金额。如果出现判题系统读取方案失败或部署方案违规,则沿用上一轮读取的部署方案。
7. 如果比赛程序出现编译错误或运行错误,或在最初的3次调用后均未输出任何合规部署方案,则直接判为余额为0,坚持时间为0,并退出比赛。

总决赛时间安排
4.26 发布总决赛赛题
4.27 上线SDK包及练习用例
4.29 开放代码提交功能
5.12-5.15 现场总决赛@深圳
跳转到指定楼层
您需要登录后才可以回帖 登录 | 注册

如果附件按钮无法使用,请将Adobe Flash Player 更新到最新版本!
快速回复 返回顶部