https://codeforces.com/blog/entry/98200

同上, 组队的哥哥可以 PM 一下.

A. ABC Legacy

记 $c_A, c_B, c_C$ 分别表示每个字母的出现次数, $f_{AB}, f_{AC}, f_{BC}$ 表示每种匹配的出现次数, 那么显然有 $$ \begin{cases} c_A = f_{AB}+f_{AC}\\ c_B = f_{AB}+f_{BC}\\ c_C = f_{AC}+f_{BC}\\ c_A+c_B+c_C = 2n \end{cases} $$ 于是显然可以解出 $f_{AB}=n-c_C, f_{AC}=n-c_B, f_{BC}=n-c{A}$, 即每种匹配的数量是固定的. 考虑所有含有 B 的匹配, 注意到最后还要匹配 AC 型的pattern, 所以我们在选择匹配 B* 的时候, 肯定会尽量选择后缀一段 A 和前缀一段 C, 那么匹配的时候找到第一个能匹配的 B 显然是最优的. 如果最后配不出来, 就是无解.

B. New Queries On Segment Deluxe

留坑

C. Counting Phenomenal Arrays

首先说一下我们在现场的做法: 不妨设 $a_1\leq a_2 \leq \cdots \leq a_n$, 只计数有序的序列数量, 乘上对应的系数即可.

注意到 $a_1a_2\cdots a_n = a_1+a_2+\cdots+a_n \leq na_n $, 所以我们有 $a_1a_2\cdots a_{n-1} \leq n$, 即我们选出的数中, 去掉最大的数, 乘积不能超过 $n$.

而另一方面, 当我们确定了前 $n-1$ 个数后, 我们可以通过解方程 $Px = S + x$ 来求出 $x$ 的值, 因此我们不难设计出一个 dp: 设 $f_{i,j,\pi,\sigma}$ 表示已经填了 $i$ 个数, 上一次填的是 $j$, 目前乘积是 $\pi$, 总和是 $\sigma$ 的贡献总和.

但上述 dp 的复杂度过高, 我们完全无法接受. 但是注意到大多数状态是完全不可达的, 因此我们不妨将上述过程写成一个搜索的形式, 只搜索可能达到的状态. 通过暴力实现搜索, 我们可以轻松通过 $n \leq 1000$ 的数据, 但仍然无法通过本题.

注意到我们可以添加许多剪枝. 其中最重要的一个是, 我们考察当前填出来的状态, 并通过解方程解出此时最后一个数能填啥. 如果这个解出来的值已经小于目前的 $j$, 那么再填下去就没有意义了, 我们直接认为不合法. 同时, 再添加若干个不同的优化(例如不需要去枚举1的数量,最后算答案再计算), 我们便可以轻松通过本题.

上述算法看起来不太科学, 通过地比较侥幸, 那么有没有更靠谱的算法? 当然是有的. 我们还是计算有序序列的数量, 但这次我们规定 $a_1>1$. 我们不妨设 $\varphi(a) = \sum(a) - \prod(a)$, 则我们最终要求 $\varphi(a)=0$. 但注意到, 若 $b_i > 2$, 则必有 $\varphi(a_1 \cdots a_k) \leq \varphi(a_1 \cdots a_{k+1})$, 而初始时我们有 $\varphi(a_1)=0$, 因此我们只要开始填数, $\varphi$ 值就恒小于等于 $0$, 只能在最后填 $1$ 来补救.

由于一个 $1$ 只能恰好将 $\varphi$ 值加 $1$, 所以显然 $\varphi$ 值不能超过 $n$. 我们仿照上述过程实现一个 dfs, 当我们搜出一个 $b_1,b_2,\cdots,b_k(b_1>2, b_i \leq b_{i+1})$, 其积为 $\pi$, 和为 $\sigma$ 时, 我们有 $\varphi(b) = \pi - \sigma$, 显然我们只有在最后填恰好 $-\varphi(b)$ 个 $1$ 才能让他有可能有贡献, 所以我们任取一个不含 1 的序列, 其只有不超过 1 种方法使得其有贡献. 最后我们添加 $k$ 个 $1$ 的方案数即为 $\binom{k-\varphi(b)}{-\varphi(b)}$, 乘上对应贡献的系数即可.

所有元素大于 1, 且乘积不超过 $n$ 的序列非常的少, 通过暴力打表我们可以验证总的可能状态数可以接受, 且我们每次递归都能找到一个对应的解, 故整个过程的复杂度是有保证的.

D. LIS Counting

留坑

E. Flood Fill

首先注意到, 如果两个块 $A,B$ 是相邻的, 那么我们不可能同时将 $A,B$ 均反色. 因此, 我们的操作相当于选一个互不相邻的联通块集合 $S$, 使得最小化 $\sum_{i\in S}f(i) + \sum_{i \notin S}g(i) = \sum g(n) + \sum_{i \in S} (f(i)-g(i))$, 这是一个二分图最大权独立集问题, 所以直接写个网络流就好了.

F. to Pay Respects

首先注意到, 我们的操作可以分为两类, 一类减小 $r$, 另一类不减小.

对于不减小的那一类, 我们考虑最后一次这样的操作在时刻 $T$, 如果存在 $T_0 < T$ 且 $T_0$ 你没有操作, 那么你把这次操作转移到 $T_0$ 显然更优, 这是因为反正你也不能减小了, 不如先操作让对面增长地慢一些.这说明我们第二类操作一定占据了所有操作的一个前缀. 存在一个显然的贪心, 即考虑每个时刻 $i$ 对答案的贡献 $\Delta_i$, 如果这个时刻你操作, 那么如果对面操作, 你的贡献就是 $(n-i+1) \cdot (p+r)$, 否则是 $(n-i+1) \cdot p$, 这是因为你显然不会让对面有值的时候放过它到后面再操作, 所以只有对面是 $1$ 的时候才有可能减小. 这样我们直接排序并取前 $K$ 大, 时间复杂度为 $O(n \log n+K)$.

事实上, 根据进一步分析, 我们显然会从间断点后取一个 $1$ 的前缀操作, 所以我们可以直接做一个类似双指针一样的操作, 一开始取前 $k$ 个, 每次取后面第一个调整即可. 时间复杂度为 $O(n+K)$.

G. Replace Sort

首先将 $B$ 排序, 随后发现我们替换的时候位置显然是单调的. 设 $f_{i}$ 表示将 $A$ 的前 $i$ 个数排序, 且最后一个数不变的最小代价, $g_{i,j}$ 表示将 $A$ 的前 $i$ 个数排序, 且最后一个数替换成了 $B_j$ 的最小代价, $p(x)$ 表示最大的一个 $k$ 使得 $B_k \leq x$.

转移时, 对于 $f$ 直接枚举前面放没放:

• $f_{i} \leftarrow f_{i-1} (A_{i-1} \leq A_i)$
• $f_i \leftarrow \min_{1 \leq j \leq p(A_i)} g_{i,j}$

对于 $g$, 我们注意到如果前面替换成了 $B_k$, 那么这次一定替换成 $B_{k+1}$, 因为填更大的只会让后面的限制变得更严格, 所以:

• $g_{i,j} \leftarrow f_{i-1} + 1 (A_{i-1} \leq B_j)$
• $g_{i,j} \leftarrow g_{i-1,j-1} + 1$

直接做复杂度显然是 $O(n^2)$ 的, 注意到我们可以使用线段树来优化 $g$ 对 $g$ 的转移与 $g$ 对 $f$ 的转移 (只需要区间取min, 区间求min即可. 平移操作没什么用, 加的1全都是全局加). 总的时间复杂度为 $O(n \log n)$.

H. Werewolves

注意到如果一个联通块有贡献, 那么造成贡献的颜色只有恰好一种, 所以我们可以枚举这种颜色, 然后数有多少个有贡献的联通块, 这可以通过一个简单的树上背包 ( $dp_{i,\delta}$ 表示考虑以 $i$ 为根的子树, $i$ 必须选, 出现次数最多的元素减去总元素为 $\delta$ 的方案数 ), 总的时间复杂度为 $O(n^3)$.

注意到 $\sum_{i=1}^n c_i = n$, 而我们枚举颜色 $i$ 做树上背包的时候, size 显然是不超过 $c_i$ 的, 所以我们只需要做大小不超过 $k$ 的树上背包, 它的时间复杂度是 $O(nk)$ 的, 具体之前我讲杂题的时候讲了就跳过了.jpeg

综上, 总的时间复杂度为 $O(n^2)$

I. Colourful Permutation Sorting

留坑

J. Jason ABC

注意到两次操作是一定够的, 我们设 $f_{c,i}$ 表示 $\sum_{i=1}^n [s_i=c]$, 求最小的 $j$ 使得 $\max_{i \in \Sigma} f_{i,j} \geq n$, 随后两次操作把剩下两种不够的字符补齐即可.

所以只需要特判零次和一次操作. 零次操作显然, 一次操作的话, 我们枚举这种操作的是什么字符, 然后在枚举左端点, 右端点显然是单调的, 于是就稍微维护一下就做完了. 时间复杂度 $O(n)$

K. Amazing Tree

首先注意到第一个元素一定是某一个叶子, 不妨设编号最小的叶子为 $x$, 则我们序列的第一个元素必定为 $x$.

不妨设我们 dfs 时的根为 $r$, $x$ 的唯一邻居为 $y$

1. 若 $r = y$, 则我们在访问完 $x$ 后, 相当于从 $y$ 开始依次遍历每一个子树(除了 $x$), 显然我们还是会走到最小的叶子所在的子树内, 就变成了一个根确定的子问题.
2. 若 $r \ne y$, 则相当于要选择一个 $y$ 的子树, 当作根所在的联通块, 显然我们取最小叶子最大的那个子树当根是最优的, 随后 dfs 的时候, 非最大子树的相当于根已确定, 直接走完所有的子树, 剩下的那一个还是需要做类似的过程确定最优的 $r$

L. Primes and XOR? Nonsense

留坑

M. Many LCS

留坑

N. Max Pair Matching

不妨设 $a_i \leq b_i$, 那么 $w(i,j) = \max(b_i-a_j,a_i-b_j)$. 那么最大匹配的权值就是选出恰好 $n$ 个点当作 $b_i$, 另外 $n$ 个点当作 $a_i$, 最大化他们相减的值. 我们可以假设 $2n$ 个点全都选 $b_i$, 那么把一个 $b_i$ 改为 $a_i$ 的代价即为 $a_i+b_i$, 按照代价排序选 $n$ 个最小的减去就是答案.

http://blog.qingyu.us/2021/11/moscow-international-workshops-2021.-day-1./

Warning: 这场比赛可能会被用作 XXII Open Cup 的 GP of Poland, 如果你到时候想参赛的话就别看这篇博客了~

A. AMPPZ in the times of disease

首先注意到, 如果我们对每个 $S_1,S_2, \cdots, S_k$ 都确定了一个元素, 那么其余点显然只能选择距离其最近的一个关键点, 并加入这个集合(若有多个则显然无解).

令 $P_1 \in S_1$, 随后我们考虑距离 $P_1$ 最远的点, 不妨假设其为 $P_2$. (若有多个, 我们随便取一个即可)

那么, 如果 $P_2 \in S_1$, 那么 $f(S_1) \geq \mathrm{dist} (P_1,P_2)$, 但另一方面, 限制要求我们有 $f(S_1) \leq \min _{x \in S_1, y \notin S_1} \mathrm{dist}(x, y)$, 因此除非 $U \setminus S_1 = \varnothing$, 否则一定无解.

不妨设 $P_2 \in S_2$, 那么我们同样找到一个 $P_3$, 使得 $\min(\mathrm{dist}(P_1,P_3), \mathrm{dist}(P_2,P_3))$ 最小, 同样我们有 $P_3 \in S_3$.

这样重复 $k$ 轮, 我们就为每个集合都找到了一个关键元素. 时间复杂度为 $O(nk)$.

B. Babushka and her pierogi

留坑.

C. Cake

这个旋转操作看起来比较强大, 但是注意到旋转前后两维的奇偶性都会改变, 所以如果设 $b_{i,0} = a_{i,i \; \bmod 2}, b_{i,1} = a_{i,(i+1)\;\bmod 2}$, 那么旋转操作等价于交换两个相邻的 pair, 问题转化成给你一个序列, 问最少交换相邻元素多少次变成目标序列. 在没有相同元素的时候就是逆序对数, 而有相同元素时, 容易发现我们直接按顺序匹配就是最优的. 时间复杂度 $O(n \log n)$.

D. Divided Mechanism

直接暴力模拟即可, 难度全在读题上. 时间复杂度 $O(\sum nmq)$.

实现的时候如果直接维护整个图形可能有点难写, 直接记一下差分了多少即可.

E. Epidemic

留坑

F. Fence

首先注意到, 对于一个 $(a_i,b)$ 的二元组, 我们可以 $O(1)$ 求出其生成序列的奇数位置和与偶数位置和.

注意到当我们将 $b$ 变为 $b+1$ 时, 只有 $a_i \geq b$ 的位置的值变化了, 而这样的变化总数是不超过 $\sum_{b \geq 0}\sum_{i=1}^n [a_i \geq b] = \sum_{i=1}^n a_i = S$ 的, 所以我们可以直接暴力修改.

由于修改一个位置会影响后面位置的贡献, 我们可以开一棵线段树, 支持一下单点修改和区间换标记即可, 由于只有两种标记, 直接暴力存两个区间和即可. 时间复杂度为 $O(n + S \log n)$, 足够通过.

注意到我们修改的时候, 凡是这一轮没修改过的位置, 以后都不会再改了, 所以我们其实没必要线段树, 直接暴力维护即可. 对于删除操作, 直接使用链表维护即可, 时间复杂度为 $O(n+S)$.

G. Gebyte's Grind

如果我们将每个点看作一个映射 $f: \mathbb Z \mapsto \mathbb Z$ 的话, 那么这三类节点分别相当于:

1. $f(z) = \begin{cases}z-b & z > b\\ -\infty & \mathrm{otherwise}\end{cases}$
2. $f(z) = \begin{cases} c & z \geq c \\ -\infty & \mathrm{otherwise} \end{cases}$
3. $f(z) = \max (z, c)$

首先注意到第三类节点可以写成 $f(z) = \begin{cases} z & z \geq c \\ c & \mathrm{otherwise} \end{cases}$, 那么注意到, 我们任意取出若干个映射, 他们的复合一定可以写成 $(f \circ \cdots \circ f_*)(z) = \begin{cases} -\infty & z \leq a \\ c & a < z \leq b & \\ z + d & \mathrm{otherwise} \end{cases}$的形式(更特殊的, 其实一定有 $d=c-b$), 所以我们可以开一棵线段树, 每个节点维护这个区间的复合对应的映射长什么样. 容易发现我们可以 $O(1)$ 求两个映射的复合, 所以我们可以轻松合并标记. 对于修改操作, 我们直接做即可. 对于查询操作, 我们先从 $l_i$ 往上 jump, jump 的时候把 parent 对应的右儿子复合起来, 如果发现此时 $f(z)$ 已经是 $-\infty$ 了, 就代表需要左拐, 直接进去右儿子并不断往左跳即可(整个过程类似线段树二分). 总的时间复杂度为 $O((n+q) \log n)$.

H. Hidden Password

签到题.

I. Interesting Numbers

不妨假设 $a_i \in [0,2^b)$.

1. 如果 $k < 2^{b-1}$, 那么显然选出的数的最高位必须全都相同, 我们将最高位为 $0$ 和为 $1$ 的分开做即可, 转化为 $a_i \in [0,2^{b-1})$ 的子问题.
2. 如果 $k \geq 2^{b-1}$, 那么我们考虑建出一张图, 如果两个数异或小于等于 $k$ 连一条边, 答案即为图 $G$ 的最大团. 注意到最高位相同的 $a_i$ 之间一定会连边, 因此图事实上是两个团之间连了一些边, 求最大团.
   • 注意到 $G$ 的补图为二分图, 所以可以直接跑二分图最大匹配, 如果使用 Dinic 算法, 总的时间复杂度会达到 $O(n^{2.5} \log V)$, 无法通过.
   • 整个图的结构非常优秀, 我们可以考虑 Trie 树优化建图, 这样的时间复杂度优化到 $O(n^{1.5} \log n \log V)$, 可以通过. 当然, 如果做的时候精细实现一下, 把每一层重复的部分压缩起来, 应该可以做到 $O(n^{1.5} \log n + n \log V)$ (没写过, 口胡的)
   • 事实上不用这么复杂, 我们仍然可以使用类似分治的方法解决. 我们继续将两个团 $A,B$ 划分为第 $b-1$ 位为 $0$ 的部分 $A_0,B_0$ 与为 $1$ 的部分 $A_1,B_1$, 那么我们考虑 $k$ 的第 $b-1$ 位:
     1. 如果这一位为 $0$, 那么答案显然就是 $\max (f(A_0,B_0), f(A_1,B_1))$, 直接递归即可.
     2. 否则, 注意到只有 $A_0,B_1$ 与 $A_1,B_0$ 的部分需要决策, 答案即为 $\max(|A_0|+|B_0|, |A_1| + |B_1| , f(A_0, B_1), f(A_1, B_0))$.
   • 总的时间复杂度为 $O(n \log V)$

J. Jungle Trail

若起点与终点间不连通, 则无解. 否则, 容易发现, 我们任取一条起点到终点的长为 $n+m-2$ 的路径, 每次移动都会走到一个新的行/列, 直接调整这些位置就是一组合法的方案.

K. Kitten and Roomba

我们在走路的时候, 维护一个 $p_i$, 表示此时你站在 $i$ 号点的概率, 那么整个过程的答案可以使用以下过程求出:

1. 初始 $E \leftarrow 0$
2. 对于每一步所走的 $x$:
   1. 令 $E \leftarrow E + p_x$
   2. 对所有 $(x,y) \in G$, 令 $p_y \leftarrow p_y + p_x / \deg (x)$
   3. 令 $p_x \leftarrow 0$.
3. $E$ 即为答案

由于图是一棵树, 我们直接随便钦定一个点当根, 然后对于修改一个点邻居的操作, 我们变成修改它的父亲并在自己位置打一个标记. 查询的时候直接询问真实的值与父亲的标记相加即可. 时间复杂度 $O(n+m)$

L. Lemurs

容易发现如果一个位置能放, 那么我们放了显然不会让答案变劣, 所以我们能放就放是最优的.

而对于一个位置 $(x,y)$, 其能放当且仅当对所有 $|x'-x|+|y'-y| \leq k$ 的 $(x',y')$ 都是 x, 这可以通过转 Chebyshev Distance 后询问矩形和实现. 而求出答案后, 做同样的操作即可.

唯一的问题是虽然 $1 \leq n,m \leq 1000$, 但最坏情况下有 $50$ 组测试数据, 上述算法的时间复杂度为 $O(T(n+m)^2)$, 于是以 4.5 秒(时限4.0秒)的好成绩 TLE 了.

考虑一个常数更小的算法: 对于一个 ., 本质上其限制了预期 Manhattan 距离 $\leq k$ 的位置不能放, 所以相当于这些位置都被 ban 了. 我们对每个点维护一个 $f_i$, 表示这个点的距离限制, 那么我们按照 $f_i$ 从大到小 BFS, 即可求出所有被 ban 的位置. 最后合法的位置同样可以求出, 这样的时间复杂度就优化到了 $O(Tnm)$, 可以通过.

M. Median

留坑.

Auto Post by QOJ Editorial bot

Next Stage: Grand Prix of Seoul (7.17), Grand Prix of Bytedance (7.24), TBD (7.31)

Past Contests

News

本帖所有内容均来自 Open Cup News 频道(https://t.me/opencup_ru) 与官方网站 (http://opencup.ru), 若信息有冲突请以频道内容为准.

本帖所提及的发帖时间均指莫斯科时间 (UTC +3)

• 09/02/2021 15:49: The first three stages of new season will be based on Petrozavodsk contests: 12.09 will be Grand Prix of Dolgoprudny, 19.09 - Grand Prix of IMO, 26.09 - Grand Prix of XiAn (if there will not be an actual onsite/online to base the new GP, in that case the GP of XiAn will be moved to next Sunday). The GP's will start at usual time.
• 09/02/2021 15:49: The final of XXI season of OpenCup is planned approximately at November 2021.
• 09/02/2021 16:42: Due to troubles with new interface of Yandex.Contest admin console for the sector coordinators, the start of XXII season is moved for one week. So the first GP (GP of Dolgoprudny) is planned to Sep 12, GP of IMO - to Sep 19, GP of XiAn - to Sep 26.
• 09/02/2021 16:43: Probably the new registration for sectors / ext logins will be needed. The information (if any) will appear here.
• 10/07/2021 13:45: The Widesiberian Olympiad changed the rules for the selection contest from ACM to mixed ACM+marathon with variable scoring, so it cannot be used as the OpenCup stage at the current season. In next seasons the non-ACM scoring stages may be considered, but major last-minute changes are not acceptable. So the Grand Prix of Eurasia at Oct 10 is cancelled.
• 10/22/2021 14:23: The GP of Korea will take place at Oct 24, usual time.
• 10/24/2021 16:54: The summary standings for 4 stages are published now.
• 11/05/2021 15:34: The GP of Siberia will take place at Nov 7, usual time. The GP's are planned for Nov 14, 21 and 28, all usual time. The names for the GP will be announced later.
• 11/07/2021 11:18: The standings on Yandex are broken
• 11/07/2021 11:18: http://opentrains.snarknews.info/~ejudge/res/res10555
• 11/07/2021 11:18: Div 1 standings
• 11/07/2021 11:24: http://opentrains.snarknews.info/~ejudge/res/res10565
• 11/07/2021 11:24: Div 2 standings
• 11/07/2021 12:35: Builtin standings are working now
• 11/07/2021 15:16: The results of the Siberian Grand Prix will be added to the rating after 10:00 GMT Nov 8, after the Widesiberian Olympiad closing ceremony, where the last hour for the base contest teams will be opened.
• 11/11/2021 09:33: The GP of EDG will take place at Nov 14, usual time
• 19/11/2021 22:01: The GP of Southeastern Europe will take place at Nov 28, usual time. The Nov 21 will be the day off, no Grand Prix is scheduled for that day.
• 14/02/2022 16:31: The Grand Prix of Kyoto will take place at Feb 20, usual time. The Grand Prix of Daejeon will take place at Feb 27, usual time. The Grand Prix of Gomel will take place at Mar 6, usual time. The Grand Prix of Belarus will take place at Mar 13, usual time. The results of Petrozavodsk camp will be counted in those 4 GP's.
• 26/02/2022 14:17: The Grand Prix of Daejeon is postponed at least till Mar 6. The Grand Prix of Belarus is postponed till Mar 13, the Grand Prix of Gomel is postponed till Mar 20. The GP of Daejeon, however, is still open for the early participation by ext teams, the link is http://official.contest.yandex.com/opencupXXII/contest/35265/enter
• 05/03/2022 20:50: The Grand Prix of Daejeon is postponed at least till Mar 20. Further information will follow. The link for participation of the ext teams is still working. Additionally, here is the link for the partcipation of the ext teams for the next GP: http://official.contest.yandex.com/opencupXXII/contest/35268/enter
• 19/03/2022 20:39: The final date of the Grand Prix of Daejeon is Mar 27, original time.
• 27/03/2022 10:03: GP of Daejeon link: http://official.contest.yandex.com/opencupXXII/contest/35265/enter
• 27/03/2022 10:04: There will be no Div 2 today, for further GP Div2 is under consideration.
• 02/04/2022 13:38: The link on 12'th stage of the OpenCup - GP of Grushevka Div 1 contest: http://official.contest.yandex.com/opencupXXII/contest/35268/enter
• 06/04/2022 00:41: The 13'th stage of the OpenCup will be at Apr 10, usual time. The teams participating Petrozavodsk camp will have their results included in the final standings.
• 28/04/2022 11:44: The 14'th stage of the OpenCup, GP of BSUIR, will be at May 1,, usual time. The teams participating BSUIR Open Finals will have their results included in the final standings. The 15'th stage is planned on May 8, usual time.
• 28/04/2022 11:45: The OpenCup season will be prolonged approx to end of July, because some planned GP are postponed due to COVID issues in China.
• 29/04/2022 13:45: http://official.contest.yandex.com/opencupXXII/contest/37753/enter - Division 1 Link for Grand Prix of BSUIR
• 01/05/2022 09:59: http://official.contest.yandex.com/opencupXXII/contest/37754/enter - Division 2 Link for Grand Prix of BSUIR
• 04/05/2022 18:52: The 15'th stage, the GP of Yuquan, is planned on May 8, usual time. Teams that were participated in Prefinals MW will have their results included in the final standings. http://official.contest.yandex.com/opencupXXII/contest/37831/enter - Division 1 Link
• 26/05/2022 13:42: The 16'th stage, the GP of Urals, is planned on June 5, usual time. Teams that were participated in Championship of Urals, will have their results included in the final standings.
• 02/06/2022 14:17: The 16'th stage, the GP of Urals, is planned on June 5, usual time. http://official.contest.yandex.com/opencupXXII/contest/38278/enter - Division 1 Link
• 05/06/2022 10:55: There will be Division 2 contest today, the link is: http://official.contest.yandex.com/opencupXXII/contest/38279/enter
• 12/07/2022 16:55: The Bytedance camp finally started, so there will be Stage 17, GP of Seoul at Jul 17, usual time, and Stage 18, GP of Bytedance at Jul 24, usual time. The results of the camp participants will be integrated. And at Jul 31 will be stage 19.

本帖最后更新于 02/06/2022 16:22 (UTC +3)

以下为 opencup.ru 中给出的时间表. 本表最后更新于 06/12/2021.

The information about future stages will appear later.

Announcement

В XXII Открытом Кубке им. Е.В. Панкратьева по программированию, который планируется провести с сентября 2021 по май-июль 2022 года, предполагается проведение от 14 до 24 этапов. Первый этап Кубка состоится 12.09.2021. В этом сезоне традиционно основной системой для первого дивизиона Кубка будет Яндекс.Контест. Основной системой для второго дивизиона Кубка будет ejudge, для команд второго дивизиона организован спонсорский зачёт Moscow Workshops. Спонсорского зачёта от компании Яндекс в текущем сезоне не будет.
В этом сезоне планируется полная перерегистрация всех секторов (с перегенерацией паролей). Перерегистрация будет идти до 1 октября 2021 года. При перерегистрации будет проведена синхронизация данных в обеих используемых системах (ejudge и Яндекс.Контест), что позволит использовать единую консоль администратора сектора для обоих дивизионов. До окончания перерегистрации все логины не перерегистрировавшихся секторов остаются as is. Для команд, использующих логины с префиксом ext, синхронизация будет проведена позднее.
При перерегистрации сектора (и для регистрации нового сектора) необходимо отправить заявку на адрес site-register(сoбakа)opencup(тoчka)org. В теме письма указать "Перерегистрация" или "Регистрация нового сектора". В самом письме указать следующую информацию:

Для ввода имён команд и получения условий задач координаторы должны использовать консоль администратора. Ссылки на консоль администратора для системы ejudge и для системы Яндекс.Контест находятся в меню слева.

Updated I:

Первый этап XXII Открытого Кубка по программированию - Гран-При Долгопрудного - состоится 12.09.2021 в 11:00.
Командам, участвовавшим в сборах в Петрозаводске, в зачёт идёт результат, показанный в Петрозаводске.
В связи с проблемами с доступом к серверу opentrains.snarknews.info и недостаточным количеством перерегистрированных секторов команды второго дивизиона будут участвовать в предстоящем этапе в системе Яндекс.Контест. При этом наборы задач совпадают лишь частично (как обычно в Div 2).
В связи с пандемией коронавируса командам рекомендуется писать через удалённый доступ из дома (для коммуникации можно использовать программные средства типа skype, discord, zoom и им подобные). В функции координатора сектора входит только высылка паролей командам своего сектора, у которых есть проблемы с доступом (у новых или забывших пароль).
Первоначальную регистрацию производят координаторы секторов и подсекторов. Команды, которые хотели бы принять участие в Кубке в составе того или иного сектора, но ещё не сообщили о своём намерении участвовать в текущем сезоне Кубка координатору сектора, могут до 11:00 11.09.2021 отправить по e-mail координатора заявку. В заявке для каждой команды указывать название команды, имена и фамилии участников, учебное заведение, курс или класс для каждого из участников (если таковые определены).
Координаторы секторов и подсекторов обязаны заполнить окончательные составы участвующих в Гран-При команд не позднее 16:00 11.09.2021. Предварительные составы желательно заполнять до начала Гран-При.

Update II:

Седьмой этап XXII Открытого Кубка по программированию - Grand Prix of Southeastern Europe - состоится 28.11.2021 в 11:00. Командам, участвовавшим в MW International 2021, в зачёт идёт результат, показанный на сборах. В связи с переносом сервера ejudge и недостаточным количеством перерегистрированных секторов команды второго дивизиона будут участвовать в предстоящем этапе в системе Яндекс.Контест. При этом наборы задач совпадают лишь частично (как обычно в Div 2). В связи с пандемией коронавируса командам рекомендуется писать через удалённый доступ из дома (для коммуникации можно использовать программные средства типа skype, discord, zoom и им подобные). В функции координатора сектора входит только высылка паролей командам своего сектора, у которых есть проблемы с доступом (у новых или забывших пароль). Первоначальную регистрацию производят координаторы секторов и подсекторов. Команды, которые хотели бы принять участие в Кубке в составе того или иного сектора, но ещё не сообщили о своём намерении участвовать в текущем сезоне Кубка координатору сектора, могут до 11:00 28.11.2021 отправить по e-mail координатора заявку. В заявке для каждой команды указывать название команды, имена и фамилии участников, учебное заведение, курс или класс для каждого из участников (если таковые определены).

Past contests:

• Grand Prix of Dolgoprudny: Div.1, Div.2, Discussion
• Grand Prix of IMO: Div.1, Div.2, Discussion
• Grand Prix of Xi'an: Div.1, Div.2, Discussion
• Grand Prix of Eurasia: CANCELLED
• Grand Prix of Korea: Div.1, Div.2, Discussion
• Grand Prix of Siberia: Div.1, Div.2, Discussion
• Grand Prix of EDG: Div.1, Div.2, Discussion
• Grand Prix of Southeastern Europe: Div.1, Div.2, Discussion
• Grand Prix of Poland: Div.1, Div.2, Discussion
• Grand Prix of Nanjing: Div.1, Div.2, Discussion
• Grand Prix of Kyoto: Div.1, Div.2
• Grand Prix of Daejeon: Div.1 (No Div. 2 Contest)
• Grand Prix of Belarus Grushevka: Div.1 (No Div. 2 Contest)
• Grand Prix of Gomel: Div.1 (No Div. 2 Contest)
• Grand Prix of BSUIR: Div. 1
• Grand Prix of Yuquan: Div. 1
• Grand Prix of Urals: Div. 1, Div. 2

比赛可以鸽，暂别不行。

我们几个管理员 Qingyu, Qingyu, Qingyu 和我在过去的半年中，组织和举办了不少的比赛，也还算及时地将官方比赛题目上传到了 QOJ 中。

我一直非常喜欢 UOJ，在去年收到 Qingyu 的邀请后，我思考了一段时间，并决定来当 QOJ 管理，我想为这个美好的 OJ 献出自己的一份力量，让这个 OJ 变得更加好，如今看来，当时的目标也基本实现了。

在当管理的一年中，还是有很多事让我记忆深刻的，还记得 XXI Open Cup named after E.V. Pankratiev, Grand Prix of Siberia; XXI Open Cup named after E.V. Pankratiev, Grand Prix of Eurasia; 7 February, 2021 — Waterloo local contest; NOIP 2020; Petrozavodsk Winter 2021. Day 9. Grand Prix of Suwon; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Suwon; Petrozavodsk Winter 2021. Day 8. Belarusian SU Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Belarus; Petrozavodsk Winter 2021. Day 7. North American Contest 1; Petrozavodsk Winter 2021. Day 6. PKU Contest 2; Petrozavodsk Winter 2021. Day 5. Almost Retired Dandelion Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Nizhny Novgorod; Petrozavodsk Winter 2021. Day 4. PKU Contest (Common Contest 1); Petrozavodsk Winter 2021. Day 3. Nordic+ Contest 2020 (NCPC-2020 with some BAPC/UKIEPC 2020); Petrozavodsk Winter 2021. Day 2. UPC Contest; Petrozavodsk Winter 2021. Day 1. Jagiellonian U Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of Krakow; Nordic Collegiate Programming Contest 2020; Potyczki Algorytmiczne 2020; Runda 5; Potyczki Algorytmiczne 2020; Runda 4; Potyczki Algorytmiczne 2020; Runda 3; Potyczki Algorytmiczne 2020; Runda 2; Potyczki Algorytmiczne 2020; Runda 1; Potyczki Algorytmiczne 2020; Runda próbna; 2019-2020 ICPC Northwestern Europe Regional Contest; 2018-2019 ICPC Northwestern Europe Regional Contest; USACO 2020 January Contest (Platinum); USACO 2019 December Contest (Platinum); The 2020 Benelux Algorithm Programming Contest; USACO 2019 February Contest (Platinum); USACO 2019 January Contest (Platinum); USACO 2018 December Contest (Platinum); 2017-2018 ICPC Northwestern Europe Regional Contest; Nordic Collegiate Programming Contest 2019; 2019-2020 ICPC Southwestern Europe Regional Contest; 2020 Canadian Computing Olympiad Day 2; 2020 Canadian Computing Olympiad Day 1; International Olympiad in Informatics 2020 Day 2; International Olympiad in Informatics 2020 Day 1; Petrozavodsk Summer 2020. Day 6. Korean Contest; Petrozavodsk Summer 2020. Day 5. JAG Summer 2019+; Petrozavodsk Summer 2020. Day 4. Xi Lin Contest 6; Petrozavodsk Summer 2020. Day 3. Songyang Chen Contest; Petrozavodsk Summer 2020. Day 2. SPb SU LOUD ENOUGH Contest; XXI Open Cup named after E.V. Pankratiev; Grand Prix of SPb; Petrozavodsk Summer 2020. Day 1. Warsaw U Contest; USACO 2018 February Contest (Platinum); USACO 2018 January Contest (Platinum); USACO 2017 December Contest (Platinum); 2020-2021 ICPC North America - Pacific Northwest Regional Contest - Division 2; 2020-2021 ICPC North America - Pacific Northwest Regional Contest - Division 1; 2020-2021 ICPC North America - Mid-Atlantic USA Regional Contest; 2020-2021 ICPC North America - Mid-Central USA Programming Contest; 2020-2021 ICPC North America - East Central NA Regional Contest; 2020-2021 ICPC North America - Rocky Mountain Regional Contest; 2019-2020 ICPC North America - Rocky Mountain Regional Contest; Russia Open 2020 High School Team Programming Contest 2020-09-08 08:30:00 3 hours 30 minutes No ×0 IOI 2018 中国国家队清华集训 Day 4 (CTT 2017 Day 4); IOI 2018 中国国家队清华集训 Day 3 (CTT 2017 Day 3); IOI 2018 中国国家队清华集训 Day 2 (CTT 2017 Day 2); IOI 2018 中国国家队清华集训 Day 1 (CTT 2017 Day 1); 前 D 题发生了一系列事故，导致比赛前一天 Qingyu 哥哥晚上一点多写好 std，我三多造好数据，然后还发现了同样没睡在内卷的 hy，第二天起来一看 Qingyu 说他第一步假了，暴力和 std 都是错的，换上了现在的题意，11 点 Qingyu 写完 std 然后我造数据传好就弃疗了。以及后来的 QOJ Training Series 和 Qingyu 哥哥熬夜造 E 题等等 （主要原因还是我们太鸽），不过相信下一届管理员会比我们做得更好！

现在 NOI 也顺利结束了，又一批 OIer 完成了他们最重要的一战，而 QOJ 也到了换届的环节，下一届将有四个管理员，他们是：

Qingyu、Qingyu、Qingyu、Qingyu

祝你们一切顺利，QOJ 越办越好！

Online Contests

Opentrains

• Opentrains Logins
• Opentrains Contests
• A complete list
• Official contest list

Yandex

• Yandex Contests

Open Cup

• opentrains
• Official Website
• List of all Open Cup contests

AtCoder

• AtCoder test cases
• Kenkoooo

TopCoder

• Contest Archive
• Problem Archive

Polish Contests

• Olimpiada Informatyczna
• Szkopuł
• OIOIOI

Training Camp

• List of all Petrozavodsk Contests

OI Contests

ICPC Contests

http://oj.qingyu.us/archive/icpc/

为了避免自己的账户泄露，建议不要在大机房中使用浏览器的“保存密码”功能！！

若认为自己的密码已经泄露，需要在修改密码后使用 登出所有活跃会话 功能，否则此前认证过的会话可能不会失效。

同时，为了避免权限组的题目泄露，hydd 大神指示各位 hy 的粉丝 使用强度较高的密码，请不要使用诸如 123456、114514、19260817、hyakcts、ilovechino 的弱口令。

FTP 所有账户已重置，请有 FTP 权限的群友查看系统消息获取最新的用户密码。对于 Archive 中一些公开的测试数据，建议大家转至 Google Drive 镜像进行下载。

不建议在博客中写模拟赛题的题解，如果需要写内部题的题解，一定注意添加权限。所有内部题目的讨论博客需要拥有 access-secret-blogs 权限与校内团队（目前有 $12,16,17,19,22$ 五个团队）权限才可以查看。

本公告的最终解释权归 hydd 所有。

Last Updated: June 2026

Judgehost Specification

The judgehosts of QOJ are all hosted on Microsoft Azure. All judgehosts have the identical specifications:

• OS: Ubuntu 26.04.1 LTS
• RAM: 8 GiB
• CPU: Intel(R) Xeon(R) Platinum 8573C

Language Details

Unless specified in the problem meta page, you may submit your solution in any of our supported languages. Note that IOI and most other Olympiads support C++ exclusively, so problems with graders typically only support C++. Always check the problem meta information before starting!

• C
• C++
• D
• Fortran
• Go
• Haskell
• Java
• Kotlin
• Lean 4.23.0
• Pascal
• Python 3 (CPython 3.13 or PyPy 3.11)
• Ruby
• Rust

C++ (C++98, C++11, C++14, C++17, C++20, C++23, C++26)

All C++ submissions are compiled using GCC 15.2.0. The detailed compilation tag is as follows:

g++ -o answer -x c++ answer.code -lm -O2 -DONLINE_JUDGE -std=c++XX

The -std=c++XX flag will be set according to your chosen standard (98, 11, 14, 17, 20, 23, or 26).

C (C99, C11)

All C submissions are compiled using GCC 15.2.0. The detailed compilation tag is as follows:

gcc -o answer -x c answer.code -lm -O2 -DONLINE_JUDGE -std=cXX

The -std=cXX flag will be set to either c99 or c11 based on your selection.

Java (Java 8, Java 11, Java 17, Java 21)

Note: As of January 13, 2025, Java 7 and Java 14 are no longer supported by QOJ.

We use Open JDK for all Java submissions.

• Java 8: openjdk version "1.8.0_462"
• Java 11: openjdk 11.0.28
• Java 17: openjdk 17.0.16
• Java 21: openjdk 21.0.8

Flags -Xmx2048m, -Xss1024m, and -XX:ActiveProcessorCount=1 will be added when running Java programs.

Python (CPython 3.13 / PyPy 3.11)

Note: As of Dec 20, 2023, Python 2 is no longer supported by QOJ.

The Python Interpreters we used are CPython 3.13.7 and PyPy 3.11.

Rust

The Rust compiler we used is rustc 1.92.0 (ded5c06cf 2025-12-08). The detailed compilation tag is as follows:

rustc -o answer -C opt-level=3 --edition=2021 answer.code

D

The D compiler we used is DMD64 D Compiler v2.109.1. The detailed compilation tag is as follows:

dmd answer -O -release -inline -boundscheck=off

Pascal

The Pascal compiler we used is fpc, Free Pascal Compiler version 3.2.2. The detailed compilation tag is as follows:

fpc answer.code -O2

Haskell

The Haskell compiler we used is ghc, The Glorious Glasgow Haskell Compilation System, version 9.4.7. The detailed compilation tag is as follows:

ghc -O2 -rtsopts -XSafe -no-keep-hi-files -no-keep-o-files -static -o answer answer.hs

Kotlin

The Kotlin compiler we used is kotlinc-jvm 2.1.0 (JRE 21.0.5+11-Ubuntu-1ubuntu124.04). The JVM option we used to run Kotlin programs is the same as we used in Java programs.

Go

The Go compiler we used is go version go1.22.2 linux/amd64.

go build -o answer -ldflags -s -w -trimpath

Ruby

The Ruby version we used is Ruby 3.4.8.

Fortran 95 / Fortran 2018

The Fortran compiler we used is GNU Fortran 15.0.1. The detailed compilation tag is as follows:

gfortran -o answer answer.f90  -O2 -DONLINE_JUDGE -std=fX

The -std=fX flag will be set according to your chosen standard (95 or 2018).

Discovery Hailiang Logins

这个东西在若干个群友监督下随机生成的,他们都表示直接通过!

随机生成器是 @Qingyu 瞎写的,有问题就喷他.

在随机现场的 @hydd, @Lenstar 表示这个真的是一次随机生成的.

因为一些原因去随便找了个爬虫爬了下来所有比赛名称。

下面是部分内容展示，完整版请见附件下载：

Part I: contest.yandex.ru

最后更新：2021.02.19，更新至比赛 id 25209

……

下载附件