#### 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](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Statement+Not+Found+-+Season+2&iso=20220828T1930&p1=122&ah=2&am=30), 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)](https://twitter.com/zscoder/status/1562593804388929536?s=20&t=ZRXqrDf2eqEd689K9BmruQ)↵
↵
[Contest Link](https://codeforces.net/contestInvitation/1817599dc3abcbbeeaec820c8a4fabd97d5f2a0d)↵
↵
[Season 1 Problems](https://codeforces.net/contestInvitation/3b8ec5cc8b3e47831312e23b00a2377151f5c84e)↵
↵
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. ↵
↵
<spoiler summary="Problem A Hint 1">↵
Output looks like Codeforces titles. ↵
</spoiler>↵
↵
<spoiler summary="Problem A Spoiler">↵
Codeforces rating -> title↵
</spoiler>↵
↵
<spoiler summary="Problem B Hint 1">↵
The title and the fact that the input is represented by $c$ is a hint. ↵
</spoiler>↵
↵
<spoiler summary="Problem B Hint 2">↵
What well-known function has a fixed point at $-40$?↵
</spoiler>↵
↵
<spoiler summary="Problem B Spoiler">↵
Celsius -> Fahrenheit↵
</spoiler>↵
↵
<spoiler summary="Problem C Hint 1">↵
Sample 2 has output $28$, which is $\binom{8}{2}$.↵
</spoiler>↵
↵
<spoiler summary="Problem C Hint 2">↵
$28$ is the number of nonempty substrings of sample $2$.↵
</spoiler>↵
↵
<spoiler summary="Problem C Spoiler">↵
Number of distinct nonempty substrings.↵
</spoiler>↵
↵
<spoiler summary="Problem D Hint 1">↵
We are looking for a word from the grids.↵
</spoiler>↵
↵
<spoiler summary="Problem D Hint 2">↵
Exactly one word appears in all the grids with answer YES and does not appear in all the grids with answer NO.↵
</spoiler>↵
↵
<spoiler summary="Problem D Spoiler">↵
Output YES iff "vapid" can be found in the grid (vertically, horizontally or diagonally).↵
</spoiler>↵
↵
<spoiler summary="Problem E Hint 1">↵
The title is asking you to factor the sample outputs and spot a pattern.↵
</spoiler>↵
↵
<spoiler summary="Problem E Hint 2">↵
Look for factors coming from well-known sequences.↵
</spoiler>↵
↵
<spoiler summary="Problem E Spoiler">↵
The 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.↵
</spoiler>↵
↵
<spoiler summary="Problem F Hint 1">↵
The queries look like subrectangle queries. Play around with the samples. # contributes to the answer somehow. Answer is always even.↵
</spoiler>↵
↵
<spoiler summary="Problem F Spoiler">↵
Compute the "perimeter" of the # region in the query subrectangle.↵
</spoiler>↵
↵
<spoiler summary="Problem G Hint 1">↵
The input makes no sense and seems unrelated to the title. The title seems to be our only clue?↵
</spoiler>↵
↵
<spoiler summary="Problem G Hint 2">↵
Notorious coincidence.↵
</spoiler>↵
↵
<spoiler summary="Problem G Spoiler">↵
Google “Coloring Trees codeforces” (or something similar) will lead you to https://codeforces.net/problemset/problem/711/C↵
</spoiler>↵
↵
<spoiler summary="Problem H Hint 1">↵
Input $1$ is $\frac{1}{6} \pmod{998244353}$.↵
</spoiler>↵
↵
<spoiler summary="Problem H Hint 2">↵
We can guess that the output is a rational number mod $998244353$. ↵
</spoiler>↵
↵
<spoiler summary="Problem H Hint 3">↵
By 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}$.↵
</spoiler>↵
↵
<spoiler summary="Problem H Hint 4">↵
Google $\frac{691}{2730}$.↵
</spoiler>↵
↵
<spoiler summary="Problem H Spoiler">↵
Output 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)$. ↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 1">↵
While 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?). ↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 2">↵
// is very weird. Why is it in the title?↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 3">↵
It's a geometry problem.↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 4">↵
Output seems to contain two pairs of triangles.↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 5">↵
You can reinterpret the title as "Parallel Euler Lines".↵
</spoiler>↵
↵
<spoiler summary="Problem I Spoiler">↵
Find two pairs of triangles from the set of points with parallel Euler lines. ↵
</spoiler>↵
↵
<spoiler summary="Problem J Hint 1">↵
You 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. ↵
</spoiler>↵
↵
<spoiler summary="Problem J Hint 2">↵
Symmetric Strategy↵
</spoiler>↵
↵
<spoiler summary="Problem J Spoiler">↵
You 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.↵
</spoiler>↵
↵
<spoiler summary="Problem K Hint 1">↵
What does $a,b,c$ stand for in math?↵
</spoiler>↵
↵
<spoiler summary="Problem K Hint 2">↵
Side lengths of triangle↵
</spoiler>↵
↵
<spoiler summary="Problem K Spoiler">↵
Given $X$, find a triangle with integer side lengths with area $\sqrt{X}$.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion A">↵
The 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.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion B & C Prerequisite">↵
You 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.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion B Hint">↵
Since the length is a square number, we can arrange the digits in a square grid (for length=81, 9x9 grid).↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion B">↵
This 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.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion C Hint">↵
This criteria is a bit more complicated. Having a lot of composite numbers will tend to give you a higher score.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion C">↵
First, 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}$.↵
</spoiler>↵
↵
Top Scorers↵
------------------------------↵
↵
1. [user:snuke,2022-08-28], [user:sugim48,2022-08-28], [user:hos.lyric,2022-08-28] 6470↵
↵
2. [user:Golovanov399,2022-08-28] 6032.144↵
↵
3. [user:.I.,2022-08-28], [user:-is-this-fft-,2022-08-28] 4625↵
↵
4. [user:Gilwall,2022-08-28], [user:conqueror_of_tourist,2022-08-28], [user:Friday1,2022-08-28] 4556.109↵
↵
5. [user:hitonanode,2022-08-28] 4400↵
↵
6. [user:Bench0310,2022-08-28] 3900↵
↵
7. [user:rainboy,2022-08-28] 3600↵
↵
8. [user:sansen,2022-08-28] 3456.109 ↵
↵
9. [user:tute7627,2022-08-28] 3356.109 ↵
↵
10. [user:AndreySergunin,2022-08-28] 3300↵
↵
↵
↵
↵
On [August 28, 2022 (Sunday) 19:30-22:00 GMT+8](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Statement+Not+Found+-+Season+2&iso=20220828T1930&p1=122&ah=2&am=30), 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)](https://twitter.com/zscoder/status/1562593804388929536?s=20&t=ZRXqrDf2eqEd689K9BmruQ)↵
↵
[Contest Link](https://codeforces.net/contestInvitation/1817599dc3abcbbeeaec820c8a4fabd97d5f2a0d)↵
↵
[Season 1 Problems](https://codeforces.net/contestInvitation/3b8ec5cc8b3e47831312e23b00a2377151f5c84e)↵
↵
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. ↵
↵
<spoiler summary="Problem A Hint 1">↵
Output looks like Codeforces titles. ↵
</spoiler>↵
↵
<spoiler summary="Problem A Spoiler">↵
Codeforces rating -> title↵
</spoiler>↵
↵
<spoiler summary="Problem B Hint 1">↵
The title and the fact that the input is represented by $c$ is a hint. ↵
</spoiler>↵
↵
<spoiler summary="Problem B Hint 2">↵
What well-known function has a fixed point at $-40$?↵
</spoiler>↵
↵
<spoiler summary="Problem B Spoiler">↵
Celsius -> Fahrenheit↵
</spoiler>↵
↵
<spoiler summary="Problem C Hint 1">↵
Sample 2 has output $28$, which is $\binom{8}{2}$.↵
</spoiler>↵
↵
<spoiler summary="Problem C Hint 2">↵
$28$ is the number of nonempty substrings of sample $2$.↵
</spoiler>↵
↵
<spoiler summary="Problem C Spoiler">↵
Number of distinct nonempty substrings.↵
</spoiler>↵
↵
<spoiler summary="Problem D Hint 1">↵
We are looking for a word from the grids.↵
</spoiler>↵
↵
<spoiler summary="Problem D Hint 2">↵
Exactly one word appears in all the grids with answer YES and does not appear in all the grids with answer NO.↵
</spoiler>↵
↵
<spoiler summary="Problem D Spoiler">↵
Output YES iff "vapid" can be found in the grid (vertically, horizontally or diagonally).↵
</spoiler>↵
↵
<spoiler summary="Problem E Hint 1">↵
The title is asking you to factor the sample outputs and spot a pattern.↵
</spoiler>↵
↵
<spoiler summary="Problem E Hint 2">↵
Look for factors coming from well-known sequences.↵
</spoiler>↵
↵
<spoiler summary="Problem E Spoiler">↵
The 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.↵
</spoiler>↵
↵
<spoiler summary="Problem F Hint 1">↵
The queries look like subrectangle queries. Play around with the samples. # contributes to the answer somehow. Answer is always even.↵
</spoiler>↵
↵
<spoiler summary="Problem F Spoiler">↵
Compute the "perimeter" of the # region in the query subrectangle.↵
</spoiler>↵
↵
<spoiler summary="Problem G Hint 1">↵
The input makes no sense and seems unrelated to the title. The title seems to be our only clue?↵
</spoiler>↵
↵
<spoiler summary="Problem G Hint 2">↵
Notorious coincidence.↵
</spoiler>↵
↵
<spoiler summary="Problem G Spoiler">↵
Google “Coloring Trees codeforces” (or something similar) will lead you to https://codeforces.net/problemset/problem/711/C↵
</spoiler>↵
↵
<spoiler summary="Problem H Hint 1">↵
Input $1$ is $\frac{1}{6} \pmod{998244353}$.↵
</spoiler>↵
↵
<spoiler summary="Problem H Hint 2">↵
We can guess that the output is a rational number mod $998244353$. ↵
</spoiler>↵
↵
<spoiler summary="Problem H Hint 3">↵
By 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}$.↵
</spoiler>↵
↵
<spoiler summary="Problem H Hint 4">↵
Google $\frac{691}{2730}$.↵
</spoiler>↵
↵
<spoiler summary="Problem H Spoiler">↵
Output 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)$. ↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 1">↵
While 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?). ↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 2">↵
// is very weird. Why is it in the title?↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 3">↵
It's a geometry problem.↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 4">↵
Output seems to contain two pairs of triangles.↵
</spoiler>↵
↵
<spoiler summary="Problem I Hint 5">↵
You can reinterpret the title as "Parallel Euler Lines".↵
</spoiler>↵
↵
<spoiler summary="Problem I Spoiler">↵
Find two pairs of triangles from the set of points with parallel Euler lines. ↵
</spoiler>↵
↵
<spoiler summary="Problem J Hint 1">↵
You 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. ↵
</spoiler>↵
↵
<spoiler summary="Problem J Hint 2">↵
Symmetric Strategy↵
</spoiler>↵
↵
<spoiler summary="Problem J Spoiler">↵
You 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.↵
</spoiler>↵
↵
<spoiler summary="Problem K Hint 1">↵
What does $a,b,c$ stand for in math?↵
</spoiler>↵
↵
<spoiler summary="Problem K Hint 2">↵
Side lengths of triangle↵
</spoiler>↵
↵
<spoiler summary="Problem K Spoiler">↵
Given $X$, find a triangle with integer side lengths with area $\sqrt{X}$.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion A">↵
The 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.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion B & C Prerequisite">↵
You 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.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion B Hint">↵
Since the length is a square number, we can arrange the digits in a square grid (for length=81, 9x9 grid).↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion B">↵
This 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.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion C Hint">↵
This criteria is a bit more complicated. Having a lot of composite numbers will tend to give you a higher score.↵
</spoiler>↵
↵
<spoiler summary="Problem L Criterion C">↵
First, 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}$.↵
</spoiler>↵
↵
Top Scorers↵
------------------------------↵
↵
1. [user:snuke,2022-08-28], [user:sugim48,2022-08-28], [user:hos.lyric,2022-08-28] 6470↵
↵
2. [user:Golovanov399,2022-08-28] 6032.144↵
↵
3. [user:.I.,2022-08-28], [user:-is-this-fft-,2022-08-28] 4625↵
↵
4. [user:Gilwall,2022-08-28], [user:conqueror_of_tourist,2022-08-28], [user:Friday1,2022-08-28] 4556.109↵
↵
5. [user:hitonanode,2022-08-28] 4400↵
↵
6. [user:Bench0310,2022-08-28] 3900↵
↵
7. [user:rainboy,2022-08-28] 3600↵
↵
8. [user:sansen,2022-08-28] 3456.109 ↵
↵
9. [user:tute7627,2022-08-28] 3356.109 ↵
↵
10. [user:AndreySergunin,2022-08-28] 3300↵
↵
↵
↵
