问题设置
概述
- 概念: 在本次编程竞赛中,您将运行送货服务。客户将向您的商店下订单。每个订单都有一个独特的 \text{ID} 并应交付给相应的客户。您的送货服务拥有一辆车。汽车将从商店取出订购的商品并将其交付给顾客。
- 分数: 您的目标是在给定的时间内尽快交付尽可能多的物品 T_{\text{max}}。 (订单预计截止到 0.95 \times T_{\text{max}}).
- 约束: 在本次比赛中,您可以放入车内的物品数量没有限制。然而,物品只能在下订单后从商店取货才能装载到车上。
- 问题 A/B: 在问题 A 中,所有订单位置和时间都提前提供给参赛者,参赛者算法应优化汽车的动作,以尽可能快地完成尽可能多的交付。另一方面,在问题B中,订单出现在网上,即出现新订单,同时您移动汽车以尽可能快地交付尽可能多的货物。
时间和空间规范:
- 时间: 在本次比赛中,我们通过整数值对时间进度进行建模 0 \le t < T_{\text{max}}.
- 地图: 在本次比赛中,我们通过简单、无向且连通的图对地图进行建模 G=(V, E),由一组顶点组成 V 和一组边 E
- 商店和顾客地点: 顶点 u \in V 标记为 1 to |V| 和顶点 u=1 表示您的商店的位置,而顶点 u = 2,...,|V| 表示潜在客户的位置。在这里, |V| 表示集合的元素数量 V.
- 街道: 每条边 \left\{ u, v \right\} \in E 表示连接顶点的街道 u, v \in V。相应的长度由整数边权重给出 d_{u, v} \ge 1.
- 图表创建: 下面的伪代码指定了基于随机种子生成地图的算法。有关更多详细信息,请参阅下面的示例代码。
伪代码: 地图图形生成器
- 输入:|V|, |E|, \mathrm{MaxDegree}=5
- 2d 顶点网格:
- 首先求最大整数 R>0 这样 |V| = R^{2} + r,与 r 是可能的最小非负整数。
- 然后我们绘制点 (x, y) 在 2d 顶点网格上 (0 \leq x, y \lt R).
- 对于每个点 (x, y) 添加统一随机偏移 dx, dy \in [0, 1] ,给出最终顶点位置 (x + dx, y + dy)\in [0,R] \times [0,R].
- 最后,添加剩余的 r 顶点位于均匀随机位置 (x, y) 与 0 \leq x, y \leq R.
- 顶点标签 u \in V 通过随机洗牌来分配。店铺是顶点 u=1.
- 我们如何创建高速公路:
- 为了生成高速公路网络,我们创建一个完整的图 顶点集上的 G_{\text{comp}} 在顶点集上 u \in V,分配每个顶点对 u, v \in V \times V 欧几里得距离 W_{u, v} 作为边权重。
- 接下来,我们构造一个 最小跨度 树 G_{\text{comp}}。的 |V|-1 最小生成树的边是图的高速公路网络 G。我们分配每条边 \left\{ u, v \right\} 边权重 d_{u,v} \leftarrow \lceil 2 \times W_{u, v} \rceil .
- 我们如何添加支路:
- 为了创建支路网络,我们相继添加 |E|-(|V|-1) 图形的边 G 如下:
- 更新 \mathrm{cost}(u,v).
- 顶点对之间 \left( u, v \right) \in V\times V,尚未通过边连接,选择具有最小的一对 \mathrm{cost}(u,v).
- 分配边权重 d_{u,v} \leftarrow \lceil 4 \times W_{u, v} \rceil .
-
在这里, \mathrm{cost}(u,v) 本质上基于顶点的欧几里德距离,优先连接附近度数较低的顶点。此外,优先考虑沿矩形网格的支路,以避免过多的桥梁。详细定义如下:
- 定义 \mathrm{degree}(u),顶点的度数 u\in V 作为入射边的数量。
- 定义 \mathrm{color}(u) 对于每个顶点 u\in V 按照原来的位置
顶点网格上的 (x,y) 为:
- If x+y 是偶数: \mathrm{color}(u) = 0
- If x+y 是奇数: \mathrm{color}(u) = 1
- 对于剩余的 r 顶点:分配颜色 \mathrm{color}(u) \in \left\{0,1\right\} 随机。
- 定义一个因素 f(u,v) 如下:
- If \mathrm{color}(u) 和 \mathrm{color}(v) 相同:设置 \mathrm{f}(u,v) = 5
- If \mathrm{color}(u) 和 \mathrm{color}(v) 不同:设置 \mathrm{f}(u,v) = 1
- 定义一个因素 g(u) 如下:
- If \mathrm{degree}(u) \lt \mathrm{MaxDegree} :设置 g(u)=1
- If \mathrm{degree}(u) \geq \mathrm{MaxDegree} :设置 g(u)=\infty
- 最后,成本定义如下:
- \mathrm{cost}(u,v) = W_{u,v}\times \mathrm{degree}(u) \times \mathrm{degree}(v) \times f(u,v) \times g(u) \times g(v).
- 为了创建支路网络,我们相继添加 |E|-(|V|-1) 图形的边 G 如下:
- 我们如何分配订单频率:
- 分配每个顶点 u \in V 订单频率 f_u \in \left\{0,1,2\right\}.
- 初始化商店顶点的订单频率: f_1 \leftarrow 0.
- 初始化其他顶点的顺序频率: f_u \leftarrow 1
- 现在确定阶次频率为 2 的顶点。为此绘制一个均匀的随机中心点 c=(c_x,c_y)\in [R/4,3R/4]\times[R/4,3R/4] 然后对于所有顶点 u=2,...,|V| 做:
- If \mathrm{EuclideanDistance}(c,u)\le R/8 + \mathrm{uniformRandom}[0,R/8]: f_{u} \leftarrow 2
汽车位置和移动规范:
为了进行送货,您将操作一辆送货车,它可以按照以下指定的方式占据位置并进行移动。
-
车位: 汽车通常可以采取两种类型的位置:
- 在顶点上 u \in V.
- 在边缘 \left\{ u, v \right\} \in E。更具体地说,它位于一个距离 x (0 \lt x \lt d_{u, v}) 来自 u to v .
-
汽车移动: 每一步 0 \le t < T_{\text{max}} 您必须选择以下操作之一才能控制您的送货车。
stay:停留在当前位置。move w: 向顶点迈出一步 w \in V.
如果选择
move w, w 必须遵守以下约束。不遵守这些限制会导致错误的答案WA.- w 必须是一个顶点,即 w \in V.
- 如果汽车位于顶点 u \in V,必须有一条边连接 u 和 v,即 \left\{ u, w \right\} \in E.
- 如果汽车在边缘 \left\{ u, v \right\} \in E, w 必须是 w = u or w = v.
订单、交货和限制:
- 订单: 在整个比赛中,每个订单都具有三个数量的特征:唯一的订单 ID、顶点 v \in V 表示订单目的地和订单时间 t 订单出现的位置。详细格式见下文。
- 订单生成: 每次 0 \le t \le T_{\text{last}} = 0.95 \times T_{\text{max}} 最多可以出现一个新订单 p_{\text{order}}(t)。如果有订单,则订单目的地 i 从顶点集中选择 V 概率与订单频率成正比 f_i。有关详细信息,请参阅下面的伪代码或下面的示例代码。
伪代码: 订单生成
- 输入: 最后下单时间 T_{\text{last}} 和平均订单概率 p_{\text{order}}(t).
- 初始化: \mathrm{ID} \leftarrow 0.
- 对于每个步骤 t = 0, ..., T_{\text{last}} 做:
- 生成统一随机数 r \in [0,1] .
- If r \le p_{\text{order}}(t) :
- 选择顶点位置 u \in V 随机,概率与订单频率成正比 顶点的 f_{u} 。
- \mathrm{ID} \leftarrow \mathrm{ID} + 1
- 下单(新订单ID、下单时间 t,顶点位置 u \in V )
- 其他: 未下订单
- 注意: 平均订单概率定义如下:
- p_{\text{order}}(t) = \begin{cases} t / T_{\text{peak}}, & \text{if } 0\le t \lt T_{\text{peak}}, \\ (T_{\text{last}} - t) / (T_{\text{last}}- T_{\text{peak}}), & \text{if } T_{\text{peak}} \le t \lt T_{\text{last}}, \\ 0, & \text{if } T_{\text{last}} \le t, \end{cases}
- 其中 T_{\text{last}}:=0.95 \times T_{\max} 和 T_{\text{peak}} 是从区间中随机均匀抽取的 [0, T_{\text{last}}].
- 注:值 T_{\text{peak}} 将不会作为输入给出。
- 交货: 要交付订单,参赛者必须在下订单后执行以下步骤:
- (1st) 将车移至商店: 注意:将汽车移入商店时,所有订单时间小于或等于当前时间的订单都将转移到汽车中。另一方面,尚未出现的订单则无法放入车内。
- (2) 将车移至客户位置: 要完成交付,请将汽车移至客户位置的顶点。注意:尚未转移到车上的订单,即使您到达了顾客位置,也不会被交付。
- 限制: 在整个比赛中,我们假设每个订单都有一个唯一的 \text{ID} 并应交付给相应的客户。进一步假设车内可以下无限数量的订单。
评分
- 比赛期间,提交的总分是通过对 30 个输入案例提交的分数求和来确定的。
- 比赛结束后将进行系统测试。为此,参赛者 最后提交 将通过对 100 个以前未见过的输入案例提交的分数求和来评分。
- 对于每个输入案例,分数计算如下:
\text{Score} = \sum_{i \in D} {(T_{\text{max}})}^{2} - {(\mathrm{waitingTime}_i)}^{2},
这里我们使用以下定义:- D :交付的订单集,直到 t=T_{\text{max}}
- 的等待时间 i第订单: \mathrm{waitingTime}_i = \mathrm{deliveredTime}_i - \mathrm{orderedTime}_i.
- 请注意,输入情况给出输出
WA将收到 0 点。
问题A的详情
在问题 A 中,我们通过了在某个时间出现的所有订单 0 \le t < 0.95 \times T_{\text{max}} 作为参赛者代码的输入。任务是提供一种算法来优化汽车的移动,以使上述分数达到最大。
输入格式
输入按以下形式提供:
|V| |E|
u_{1} v_{1} d_{u_{1}, v_{1}}
u_{2} v_{2} d_{u_{2}, v_{2}}
:
u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}}
T_{\text{max}}
\mathrm{info}_{0}
\mathrm{info}_{1}
:
\mathrm{info}_{T_{\text{max}}-1}
- 在第一行 |V| 表示顶点数,而 |E| 表示边数。
- 以下 |E| 线表示图形的边缘。特别是,在 i第行 u_{i} 和 v_{i} 表示连接的边 u_{i} 和 v_{i} 和 d_{u_{i}, v_{i}} 对应的距离。
- 下面一行表示步数 T_{\text{max}}.
在下面的行中, \mathrm{info}_t 是有关某个时间发生的客户订单的信息 t. \mathrm{info}_t 的形式如下:
N_{\text{new}}
\mathrm{new\_id}_1 \mathrm{dst}_1
\mathrm{new\_id}_2 \mathrm{dst}_2
\vdots
\mathrm{new\_id}_{N_{\text{new}}} \mathrm{dst}_{N_{\text{new}}}
- N_{\text{new}} 代表该时间出现的新订单数 t.
- 下一个 N_{\text{new}} 行给出了新生成的订单信息。的 i第订单信息表示该订单ID 新订单的 \mathrm{new\_{id}}_i ,同时 \mathrm{dst}_i 表示客户希望将订单交付到的顶点。
- 注意:如果 N_{\text{new}}=0,没有新行。
要求
- 所有输入均为非负整数值。
- T_{\text{max}} = 10000
- 200 \leq |V| \leq 400
- 1.5 |V| \leq |E| \leq 2 |V|
- 1 \leq u_{i}, v_{i} \leq |V| (1 \leq i \leq |E|)
- 1 \leq d_{u_i, v_i} \leq \lceil 4\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
- 给定的图没有自环/多重边,并且保证是连通的。
- 0 \leq N_{\text{new}} \leq 1
- 1 \leq \mathrm{new\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{new}})。注:如果所有订单均按上述订单生成规则生成,则订单总数最多为 T_{\text{last}}+1。因此,可能的范围为 \mathrm{new\_id}_{i} 应该来自 1 to T_{\text{last}}+1.
- 2 \leq \mathrm{dst}_i \leq |V| (1 \leq i \leq N_{\text{new}})
- 订单 ID \mathrm{new\_{id}}_i 是独一无二的。
输出格式
输出预计 T_{\text{max}} 整数,格式如下指定。
\mathrm{command}_{0}
\mathrm{command}_{1}
:
\mathrm{command}_{T_{\text{max}}-1}
特别是, \mathrm{command}_{i} 应使用以下两个选项之一指定送货车的移动:
1) stay,如果汽车不动:
-1
2) move w,如果汽车应向相邻顶点移动一步 w
w
请注意,如果是 2) w 必须满足以下条件:
- w \in V
- 如果汽车位于顶点 u: \left\{ u, w \right\} \in E .
- 如果汽车在边缘 \left\{ u, v \right\}, w 必须满足 u = w or v = w.
输入示例
5 7 1 2 5 5 3 4 2 4 8 1 5 1 2 3 3 4 5 3 4 3 9 4 1 1 2 1 2 5 1 3 4 0
请注意,此输入是小尺寸的示例,不符合竞赛的限制。
输出示例
2 -1 1 5
说明
该示例在图表上运行 |V| = 5 顶点, |E| = 7 边缘,以及 T_{\text{max}} = 4 时间步长。我们现在描述已经发生的命令和汽车的运动。
时间 t=0
时间 t=0 在商店下了订单。该订单有ID= 1 并且应该传递到顶点 2。由于您的汽车当前位于顶点一,因此订单将自动转移到您的汽车中。这样,当您的汽车到达商店时,当前和之前下的所有订单都会自动加载到您的汽车中。
时间 0 → 1
你选择向顶点移动 move 2。现在,您将向顶点 2 移动一步。
时间 t=1
出现了新订单。它有身份证 =2 并应在顶点交付 5.
时间 1 → 2
你决定 stay。您现在可以保持在原地。
时间 t=2
出现了新订单。它有身份证 =3 并应在顶点交付 4.
时间 2 → 3
你决定搬家 move 1 回到顶点 1。
您正在向顶点 1 迈近一步。
以这种方式掉头是明确允许的。
时间 t=3
尚未出现新订单。现在你已经到了顶点 1 (商店),带有订单ID的订单 2, 3 已装载到您的汽车中。同样,每当您返回商店时,所有已下的订单都会自动加载到您的汽车中。
时间 3 → 4
位于您选择的顶点 1 move 5。您正在将汽车向顶点移动一步 5。你到达顶点 5.
时间 t=4
自从你到达顶点 5,订单ID为订单 2 可以交付。