Do you think you can solve CP problems without reading the problem statements? Let's find out!
On August 28, 2022 (Sunday) 19:30-22:00 GMT+8, I will hold an unofficial fun contest called Statement Not Found. As you can deduce from the title, there will be no problem statements (except title and samples). Your goal is to collect as many points as possible within 2.5 hours :)
Obviously, this round is unrated. It is somewhere between April Fools contest and a legitimate contest.
The contest will be OI-style, meaning there will be no time penalty. You are allowed to use any resources online to help solve the problems. There will be 12 problems.
Scoring Distribution: 200-400-700-700-700-800-800-900-1100-1100-1100-1500 (Total: 10000)
Please read all problems as problem difficulty is very subjective and a 1100-point problem might be easy for you while a 700-point problem might be difficult. The last problem is meant to be a tiebreaker.
You can participate solo or in teams of up to 3 (I would allow more team members but apparently Codeforces doesn't support it). Teams are highly recommended if you intend to solve everything in 2.5 hours. Good luck and have fun!
Twitter Announcement (Japanese)
Contest Link
Season 1 Problems
Below are hints/key insights to all the problems. Of course, please don't open this if you still plan to attempt the problems/virtually participate.
Problem A Hint 1Output looks like Codeforces titles.
Problem A SpoilerCodeforces rating -> title
Problem B Hint 1The title and the fact that the input is represented by $$$c$$$ is a hint.
Problem B Hint 2What well-known function has a fixed point at $$$-40$$$?
Problem C Hint 1Sample 2 has output $$$28$$$, which is $$$\binom{8}{2}$$$.
Problem C Hint 2$$$28$$$ is the number of nonempty substrings of sample $$$2$$$.
Problem C SpoilerNumber of distinct nonempty substrings.
Problem D Hint 1We are looking for a word from the grids.
Problem D Hint 2Exactly one word appears in all the grids with answer YES and does not appear in all the grids with answer NO.
Problem D SpoilerOutput YES iff "vapid" can be found in the grid (vertically, horizontally or diagonally).
Problem E Hint 1The title is asking you to factor the sample outputs and spot a pattern.
Problem E Hint 2Look for factors coming from well-known sequences.
Problem E SpoilerThe answer is Fib(n)^2*Catalan(n). Originally I planned to use Fib(n)*Catalan(n) but unfortunately it appears in OEIS for some reason.
Problem F Hint 1The queries look like subrectangle queries. Play around with the samples. # contributes to the answer somehow. Answer is always even.
Problem F SpoilerCompute the "perimeter" of the # region in the query subrectangle.
Problem G Hint 1The input makes no sense and seems unrelated to the title. The title seems to be our only clue?
Problem H Hint 1Input $$$1$$$ is $$$\frac{1}{6} \pmod{998244353}$$$.
Problem H Hint 2We can guess that the output is a rational number mod $$$998244353$$$.
Problem H Hint 3By brute forcing all fractions with numerator and denominator $$$\le 3000$$$ (sth that can run in $$$\tilde{O}(n^2)$$$) tells us that the answer to sample $$$2$$$ is $$$\frac{691}{2730}$$$.
Problem H Hint 4Google $$$\frac{691}{2730}$$$.
Problem H SpoilerOutput the absolute value of the $$$(2n-2)$$$-th Bernoulli number (using the indexing from Wikipedia). For $$$n \le 15$$$ you can just hard code it. For $$$n \le 2 \cdot 10^5$$$, you can compute it using its EGF (Exponential Generating Function) in $$$O(n\log n)$$$.
Problem I Hint 1While Eulerian paths and the input format might suggest this is a graph problem, the ? in the title suggests that we should think twice (deja vu from season 1?).
Problem I Hint 2// is very weird. Why is it in the title?
Problem I Hint 4Output seems to contain two pairs of triangles.
Problem I Hint 5You can reinterpret the title as "Parallel Euler Lines".
Problem I SpoilerFind two pairs of triangles from the set of points with parallel Euler lines.
Problem J Hint 1You are playing a two-player game on a $$$n$$$ by $$$n$$$ grid where on each turn, you can color a $$$1 \times k$$$ or $$$k \times 1$$$ subrectangle. The game ends when all cells are colored, and you lose if you can’t make a move. From here, it is a normal CP problem.
Problem J SpoilerYou can always win as P1 when $$$n$$$ or $$$m$$$ is odd by starting with the center row/column and using a symmetric strategy. Similarly, you win as P2 if $$$n, m$$$ are even.
Problem K Hint 1What does $$$a,b,c$$$ stand for in math?
Problem K SpoilerGiven $$$X$$$, find a triangle with integer side lengths with area $$$\sqrt{X}$$$.
Problem L Criterion AThe score here only depends on $$$|s|$$$. $$$|s| = 81$$$ for full points. You get higher partials if the length is a square, otherwise the partial credit roughly indicates how close you are to the nearest square number below. Trying strings of different lengths will eventually lead you to this.
Problem L Criterion B & C PrerequisiteYou need to submit a string $$$s$$$ of perfect square length to get nonzero points in B or C. This suggests that we need to use the perfect square condition somehow.
Problem L Criterion B HintSince the length is a square number, we can arrange the digits in a square grid (for length=81, 9x9 grid).
Problem L Criterion BThis criterion counts the number of rows and columns which contain all distinct digits and gives a higher score if you have more such rows/columns. It also gives a higher score for larger grids. To get full score, you need a $$$9 \times 9$$$ Latin square.
Problem L Criterion C HintThis criteria is a bit more complicated. Having a lot of composite numbers will tend to give you a higher score.
Problem L Criterion CFirst, read each row and column as a (9-digit) number. Your score depends on the average number of (not necessarily distinct) prime factors is (higher if more prime factors). To get a full score, you need an average of $$$\ge \frac{100}{9}$$$.
Top Scorers
snuke, sugim48, hos.lyric 6470
Golovanov399 6032.144
.I., -is-this-fft- 4625
Gilwall, conqueror_of_tourist, Friday1 4556.109
hitonanode 4400
Bench0310 3900
rainboy 3600
sansen 3456.109
tute7627 3356.109
AndreySergunin 3300
Awesome contest idea! This sounds really fun!
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
is it rated?
Contest name suggestion: Statemen't
Starts in < 24 hours.
~30 minutes to start!
Wtf is this?
(I just tried to copy some old CodeChef code that calculates the Bernoulli numbers fast...)
Does it have some precomputed numbers maybe? Or, if there is something calculated in compile time in general, it may increase the size of the executable by an absurd lot
Yes, I see that this implementation of FFT contains some static arrays (for example,
static point A[maxn]
). Replacing them with non-static arrays or with vectors should workAuto comment: topic has been updated by zscoder (previous revision, new revision, compare).
Huh, i tried the same approach as in editorial, but searching "coloring trees codeforces" in Yandex showed me this problem (902B - Coloring a Tree) instead of needed one. Now I searched it in Google, and it showed me needed problem. Moral: always use Google
Thank you for the contest! GG to the winners
Is it possible to solve J with python? My code got TLE.