British Informatics Olympiad 2018

https://www.olympiad.org.uk/2018/index.html

Round One

BIO的一试，是笔试和机试结合起来。
题目
https://www.olympiad.org.uk/papers/2018/bio/bio18-exam.pdf

答案
https://www.olympiad.org.uk/papers/2018/bio/bio18-marks.pdf

Round Two

四道上机题

Byway

https://www.olympiad.org.uk/papers/2018/final/Byway.pdf
输入一个无向图，可以让一条边的距离变为原本的一半，问1到v的最短路。

解法：分层图最短路

Cables

https://olympiad.org.uk/papers/2018/final/Cables.pdf
输入$s \times l$个点，没有三点共线。
把这些点分成$l$个集合，每个集合里有$s$个点，然后把每个集合内的点连成一个环。
要求所有的线段只能在端点处相交。注意并不需要像题目中一样，嵌套起来。

解法：
把所有点按照$x$排序，如果$x$相同按照$y$排序，然后每$s$个分一组。
接下来要把一组中所有点连起来，不自交。
一个比较简单的做法是极角排序。

Detente

https://www.olympiad.org.uk/papers/2018/final/Detente.pdf
输入平面上$n(n < 8192)$个点，每个点要染成A色或者B色，要求染色之后，每行每列A和B的个数至多差$1$（个数差的绝对值小于等于$1$）

解法：
每行每列建一个点，这样对于原图的一个点，相当于这个新图中的一条边，这个图是二分图，然后要给每条边一个颜色。
如果新图中有一个环，当然这个环长度为偶数，只需要把这个环上的边交替染为A和B，就可以了。
这样可以删掉原图中所有的环，原图会变为一个森林。
对于一棵树来说，只要随便染一下就可以了。

Show / Bonus

https://www.olympiad.org.uk/papers/2018/final/Show.pdf
https://www.olympiad.org.uk/papers/2018/final/Bonus.pdf
输入一个竞赛图，求一个 哈密尔顿路 / 哈密尔顿回路

解法：
https://en.wikipedia.org/wiki/Tournament_(graph_theory)
http://www.math.toronto.edu/gscott/sept20_2016.pdf
对于哈密尔顿路，可以直接用数学归纳法证明。
可以参考第二个pdf。

https://math.stackexchange.com/questions/461818/hamiltonian-cycle-in-tournament
对于哈密尔顿回路，有解的条件是所有点在一个强连通分量里。
删掉任意一个点之后，可以省下若干的强连通分量，每个强连通分量求一个哈密尔顿回路。
加入这个点之后，可以把所有哈密尔顿回路串在一起。