We ended up making a meme contest, here’s the editorial for the contest. The original editorial is here.
Thank you for participating in this round! We hope you found the problems interesting and/or funny.
Special thanks to dorijanlendvaj for helping with Polygon related issues. Preparing good tests for certain problems was in fact a good problem in itself (in fact, sometimes they were hard enough for usual CF rounds), and we will mention these problems for the interested reader.
If the editorials are not visible, try registering for the contest or something similar.
Problem A: idea: ToxicPie9, preparation: nor
Solution
[tutorial: 383377A]
Code (Python) for solution 1
#
Code (Python) for solution 2
0
Code (Python) for solution 3
''
Preparation trivia
Preparing this problem on Polygon was quite hard, and we ended up having to set this as an interactive problem in order to cut off solutions that take input. The constraint of having no input was necessary, since there is no way of giving AC if the program is “well formed” without running the program on some input, and we don’t know what input the program will accept.
Problem B: idea: dorijanlendvaj, preparation: dorijanlendvaj
Solution
[tutorial: 383377B]
Code (Python)
input(), input()
print(input())
Preparation trivia
This problem was inspired from a local Croatian competition.
Problem C: idea: nor, preparation: nor
Solution
[tutorial: 383377C]
Code (Python)
for i in range(int(input())):
input()
print(2 ** input().split().count('2'))
Problem D: idea: Sexpert, preparation: Sexpert
Solution
[tutorial: 383377D]
Code (Python)
input()
a = list(map(int, input().split()))
for _ in range(int(input())):
l, r = map(int, input().split())
if l == r - 1 or max(a[l : r - 1]) < min(a[l - 1], a[r - 1]):
print('YES')
else:
print('NO')
Preparation trivia
While making the test cases, we realized that there can be only \(O(n)\) pairs \((l, r)\) such that the answer to the corresponding query is “YES”. It is a fun exercise to bound it more exactly (and in fact find how many such queries can have answer “YES” in \(O(n)\)).
Problem E: idea: errorgorn, preparation: nor
Solution
[tutorial: 383377E]
Code (Python)
n, k = map(int, input().split())
if n * (n + 1) // 2 == k:
print(*range(1, n + 1))
else:
print(-1)
Problem F: idea: nor, preparation: nor
Solution
[tutorial: 383377F]
Code (Python)
for i in range(int(input())):
input()
print(len([x for x in list(map(int, input().split())) if x % 2 != 0]))
Problem G: idea: nor, preparation: nor
Solution
[tutorial: 383377G]
Code (Python) for solution 1
for _ in range(int(input())):
l = [tuple(map(int, input().split())) for i in range(int(input()))]
X, Y, Z = zip(*l)
if (max(X), max(Y), max(Z)) in l:
print('YES')
else:
print('NO')
Code (Python) for solution 2
for _ in range(int(input())):
l = [tuple(map(int, input().split())) for i in range(int(input()))]
x, y, z = max(l)
if all(x >= X and y >= Y and z >= Z for X, Y, Z in l):
print('YES')
else:
print('NO')
Preparation trivia
The original formulation considered a student worthy of a trophy if their scores were strictly greater than everyone’s scores in the corresponding subjects. However, this was deemed to be a bit harder to check, and it was also harder preparation-wise: apparently, by shuffling the elements, we can run a brute-force that breaks early, and the expected running time is \(O(n \log n)\) (for more details on why this is true, please read solution 2 to problem B here).
Problem H1: idea: nor, preparation: nor
Solution
[tutorial: 383377H1]
Code (Python)
for _ in range(int(input())):
n = int(input())
for i in range(2 * n):
x, y, z = input().split()
print(x, y, 'L' if z == 'R' else 'R')
Preparation trivia
Preparing good tests for this problem was quite an interesting exercise. There were two tasks involved: exhaustively enumerate all binary trees on \(n\) vertices, and generate a binary tree on \(n\) vertices fast enough (\(O(n)\) or \(O(n \log n)\)).
The first can be done by running a simple brute force on how many vertices are in the left subtree, and how many are in the right subtree.
The second is more interesting. My approach was to first figure out a way to construct uniformly random balanced bracket sequences, which was the hard part of the problem. I will leave this as an exercise for the reader, and feel free to discuss this in the comments. What remains is to use the bijection from balanced bracket sequences between binary trees.
This can be done by using the correspondence \(f\) defined by: the empty tree corresponds to the empty bracket sequence, and a node \(N\) with left and right subtrees \(L\) and \(R\) corresponds to the bracket sequence \(( \; f(L) \; ) \; f( R)\). To do this fast enough in \(O(n \log n)\), we can note that to find the closing bracket after \(f(L)\), we can note that if the “balance” after the opening bracket before \(f(L)\) was \(b\), then the balance drops below \(b\) for the first time at the bracket after \(f(L)\). This implies that we can use a prefix-sum array for balance, and construct an RMQ data structure (either sparse-table or segment tree) and find this position in \(O(\log n)\) using either binary search or walk on segment tree. We can also do this in \(O(n)\): match all the brackets first using a stack, and then perform the algorithm as usual.
Update: A simplified version of the generator can be found here.
Problem H2: idea: ToxicPie9, preparation: nor
Solution
[tutorial: 383377H2]
Code (Python) for solution 1
for _ in range(int(input())):
n = int(input())
vis = [0 for i in range(n)]
for i in range(n):
x, y = map(int, input().split())
if y > 0:
vis[y - 1] += 1
print(y, x)
print(vis.index(0) + 1, 0)
Code (Python) for solution 2
for _ in range(int(input())):
n = int(input())
p = [-1] * (n + 1)
for i in range(n):
x, y = map(int, input().split())
p[y] = x
if y:
print(y, x)
print(p.index(-1), 0)
Code (Python) for solution 3
for _ in range(int(input())):
n = int(input())
p = n * (n + 1) // 2
for i in range(n):
x, y = map(int, input().split())
if y:
print(y, x)
p -= x
print(p, 0)