№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
The 2022 ICPC Seoul Regional Mirror Contest has ended (link), and since no one made a post for discussion, let's discuss below. How to solve A, B, G and H?
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
#
0
''
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
input(), input()
print(input())
This problem was inspired from a local Croatian competition.
Problem C: idea: nor, preparation: nor
for i in range(int(input())):
input()
print(2 ** input().split().count('2'))
Problem D: idea: Ari, preparation: Ari
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')
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
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
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
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')
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')
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
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')
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
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)
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)
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)
Hi Codeforces!
We are pleased to invite you to [contest:383377], which will take place on [contest_time:383377]. You will be given 9 problems and 2 hours to solve them. Please follow this link in order to register for the contest. Note that this contest is not an official Codeforces round.
The round will be unrated for all participants. It will be held according to modified ICPC rules.
All problems in this round were written and prepared by dorijanlendvaj, errorgorn, Ari, nor and ToxicPie9. We have worked on this round for quite a short time and hope you find every problem so easy that even your five year old sibling could solve it interesting.
This round is sponsored by errorgorn and Ari with the following prizes:
We would like to thank:
Good luck and have fun! See you in the standings. Make sure to read the statements and conversion rate very carefully.
Reminder: The registration has just started!
Reminder 2: The contest starts in 15 minutes! Good luck, have fun!
UPD: Congratulations to the winners:
We would also like to congratulate the top $$$104$$$ participants for solving all the problems in-contest!
The editorial along with some more interesting stuff can be found here.
Название |
---|