The contest took place in Sydney, Australia on November 26, 2016. The top 12 teams in the region competed in the ACM-ICPC South Pacific Regional Contest 2016.

Practice & VP available here: Codeforces Gym

Virtual Participated on May 4, 2020.

• Results
  • Summary
  • Virtual Participation
  • Member Distribution
• Solutions
  • A: Anticlockwise Motion
    • 题意
    • 解法
  • B: Balloon Warehouse
    • 题意
    • 解法
  • C: Crazy Rotations
    • 题意
    • 解法
  • D: Dendroctonus
    • 题意
    • 解法
  • E: Election Frenzy
    • 题意
    • 解法
  • F: False Intelligence
    • 题意
    • 解法
  • G: Graphics Design
    • 题意
    • 解法
    • Code
  • H: Hilbert’s Hash Browns
    • 题意
    • 解法
  • I: Intuidiff II
    • 题意
    • 解法
  • J: Just Terraffic!
    • 题意
    • 解法
  • K: Kiwis vs Kangaroos
    • 题意
    • 解法
• Timeline
• Reflections

• Solved 9 out of 11 problems
• Rank 2/12 in official records
• Solved 10 out of 11 afterwards

(√ for solved during vp, ○ for after vp, - for tried but not solved)

• Solved by Pantw

从原点开始往方格里填正整数，按照逆时针螺旋顺序。

给两个数 $a, b$，问两者位置的曼哈顿距离。

$a, b$ 范围 $10^9$。

水。简单推点式子。

• Solved by Withinlover

一个初始值全部为0的无限长数列，$n$次操作$(x,y)$表示在当前所有的数字$x$后面插入一个数字$y$，询问$n$次操作后区间$[l,r)$的值为多少。

对于第i次操作，建立带权边(x, y, i)，从点0开始，对于每个点，按照从小到大的顺序枚举边，且走过的边的权值必须严格递增。如此遍历一遍原图，便可以得到最终数列的一个循环节。之后找答案就很简单了

• Solved by Gary

给定长度为$n$的红黄蓝三色序列，令给定$1 \sim (n-1)$的一个排列$Q$，$Q_i$表示将颜色序列左移$Q_i$位（每次平移第一位挪至第$n$位），将每次操作后颜色改变的位置数记做$craziness$,问所有保证$craziness$单调不减的排列中，第$P$位的最小值。

$n\le 5e5$

单独考虑三种颜色，如考虑蓝色，将所有蓝色点记为$1$，非蓝色点记为$0$，每次操作后相当于一次对两个$01$串的匹配过程，可以通过$FFT$实现，具体操作为将$01$串再向后延续$n$位记为A,将01串翻转记为$B$,左移$i$位的$craziness$即为$(A*B)_{n+i-1}$，三种颜色分别统计后排序即可。

• Idea by Withinlover & Pantw
• Code by Pantw
• Debug by Withinlover

二维平面上给一堆整点，分为红色点和蓝色点。

问能否仅用一个圆覆盖所有红色点且不覆盖蓝色点。

点恰在边界上时既可认为覆盖也可认为不覆盖。

点数不超过 $100$，坐标绝对值不超过 $250$。

刚开始觉得枚举任三个红色点的外接圆可行，然后发现三点共线被叉爆了，加上了枚举两点的直径圆，还是被菱形 Case 叉爆了。

然后这时候灵机一动想到既然边界上也可以算也可以不算那么可以直接把蓝色点也包括进枚举，枚举任三个点的外接圆，同时依旧枚举两点的直径圆，然后就过了。

判断点是否在两点的直径圆内可以直接用点积来着，今天没睡醒，还求了个角度。

判断点是否在三点的外接圆内可以直接用角度结合叉积，不用求出那个圆的圆心和半径。

• Solved by Withinlover

按以下方式给定一张图：对于每个点，给定其相邻的所有点或不与其相邻的所有点。对图进行黑白染色，每个黑点周围需要至少一个白点，每个白点周围需要至少一个黑点。根据输入判断是否有解，若有解输出任意解。

易知原题等价于求图的生成森林。当且仅当图中出现孤立点的时候无解。若有解，用邻接矩阵存边，DFS生成树，标记一下边的终点是相邻的还是不相邻的，如果相邻则直接DFS，如果不相邻则从小到大依次枚举不在邻接矩阵中的点DFS，枚举的过程可以利用并查集跳过已经被染色的点。这样可以保证每个点只枚举一次。

• Code by Withinlover
• Debug by Pantw

定义真值集合为$\{0/\mathrm{False},1/\mathrm{Uncertain},2/\mathrm{True}\}$的真值函数，给定四个基本的二元连接词$\mathrm{AND}, \mathrm{OR}, \mathrm{IMPLIES}, \mathrm{EQUALS}$，输入 $n$ 个二元连接词，判断输入的二元连接词是否可以由给定的四种连接词组合得到。

暴力求出所有解，然后 Hash 判断即可

Pantw: 时限 10s，同时四种联结词的真值表中 $T\;\mathrm{op}\;T$ 的结果均为 $T$，所以状态数最多 $3^8$，每次拓展时枚举所有状态，最多 $3^{16}‭=43,046,721‬$，时间绰绰有余。

• Solved in Practice by Pantw

教授给他的 $n$ 个学生们布置期末大作业，对第 $i$ 个学生的大作业有 $d_i$ 个子任务。

每个子任务有优先级 $p$ 和所需时间 $t$，以及资源需求。这些子任务必须按照给出的顺序完成。

资源有三种，Camera / Camcorder / Computer。

每个子任务可能需要这三种中的 0 至 3 样，每样恰好 1 个。

如果一个子任务之前的任务全部完成，并且该任务所需的资源的现存数量均不为零，那么该任务可以开始。

在每个时刻，如果有多个任务可以开始，那么其中优先级最高的任务先开始，并占用资源，接下来再取优先级最高的可以开始的任务开始。

任务在 $T$ 时刻开始后将于 $T+t$ 时结束，并返还所有资源。

既然只有 3 种资源那么状态就是 8 个，将任务按照需求压入不同的堆中，这些堆按照优先级排序。取出时直接比较堆顶即可。任务开始之后将其压入所谓的进行堆，这个堆按照结束时间排序，每次从它里面取出已经结束的任务并释放资源。

这边由于忘了进行堆中的元素应该按照结束时间而非优先级排序所以 WA 了好几发。

struct Work {
    int pri, tim, use, stu, sid;
    long long T;
    bool cam, cor, com;
};
 
bool operator < (const Work &a, const Work &b) {
    return a.pri < b.pri;
}
 
struct Work_T : Work {
    Work_T(Work w) : Work(w) {  };
    bool operator < (const Work_T &b) const {
        return this->T > b.T;
    }   
};
 
vector<Work> W[maxn]; 
 
...
 
priority_queue<Work> wait[8];
priority_queue<Work_T> doing;
for(int i = 1; i <= n; ++i) {
    wait[W[i][1].use].push(W[i][1]); // Mark 1
}
 
...
 
Work ww = V.top();
...
doing.push(ww); // Mark 2

由于 operator < 只能被重载一次，无法很方便地改变比较函数，这时我们可以用点 OO 特性方便我们解决问题。

我们用 Work_T 继承 Work，并重载 operator <，这样可以覆盖掉基类的比较函数。

同时我们写个构造函数继承基类的复制构造函数，方便我们类型转换。

可以看到两个 Mark 处函数参数均为 Work 类型，两个 priority_queue 模板的参数不一样，但是依旧可以顺利直接 push。

给 $p, q, n$，问模 $n$ 的 $p$ 次剩余类的大小。

$p, q, n$ 范围均 $10^9$。

不会。

• Solved by Gary

给出由某些字数不一的不同片段组成的文章，以及将这些片段重新组合（可不使用或多次使用）后的新文章，问新文章中顺序与原文章相同的片段的总字数最大值。

$n\le1e5$

依次遍历新序列，记选择新文章第$i$个片段（在旧文章中为第$j$个片段）后的最大值为$f_j$，则$f_j=max(f_k)+len_j ,(1\le k< j)$

经典的线段树$DP$问题，对片段离散化之后建线段树，维护区间最大值即可。

• Idea & Code by Pantw
• Debug by Gary

给一列 $n$ 个递增的正整数，要求对其进行分组。

组的大小只能是 2 或 3。

相邻两个数相差不超过 1000 则必须同组，相差不小于 2000 则必须不同组。

要求输出大小为 2 的组的数量和大小为 3 的组的数量。

要求判断无解、解不唯一（分组数量不同时才视为不同解）的情况。

如果在同一个断点处出现多解的情况那么后面用到这个状态的后续状态都会出现多解。

那么我们直接记 $F_2[n]$ 为前 $n$ 个元素分组方案中大小为 $2$ 的组的组数，$F_3[n]$ 类似定义。

然后 $(F_2[n], F_3[n])$ 可以从 $(F_2[n-2], F_3[n-2])$ 和 $(F_2[n-3], F_3[n-3])$ 转移，如果转移过来的数据有异，那么可以直接打上一个多解标记，后面使用这个状态的全部进入多解状态。

这边因为没考虑到一个状态的多解未必反映到最终答案里而 WA 一发。

• Solved by Pantw

给一个字符串，里面一些特定字符给一个阵营加分，另一些特定字符给另一个阵营加分，加分都是固定的，计算哪个阵营获胜。

串长不超过 $100$。

好水啊不想写，不写了。

• 其实事后看来不应该先写 D，应该把好做的 J 和 F 先写了
• G 没 rush 出来有点可惜，要是有人早点看到是个大模拟就可以在空闲时间写了
• C题看了半天没看出来FFT 有点生疏
• 感觉应该先顺一遍所有题的题意
• 看题还是有点不仔细，B题把数据范围看漏了。F题抄错了Or真值表。
• 感觉读题速度还是有点慢，看了好久才理解C题的意思。