Below is a list of students who successfully passed the third exam:

nifeshe, Chifwin, flammifer, nickyfoo, NintsiChkhaidze, DeanMenezes93, theboatman, Moomins, _OmarAbdo, Ahmed_Ashraf_f, Ultist, Aksakal, Abdalazim_Ahmed, rwowlasd, FTGUPP, RSHASHANK2006, enlorik, VoropaevDaniil, alkogolek228, Black_Swordsman, wiktorlewicki, yanazyab, mishail_b, RedEye8, Mohammad.gholamzade, thestonedape, arabboy27, MkcAllen, pointerupdate, yousefuwk20, Ahsan_, egor_1054, bahailu, MinaRaouf, AhmedElseyoufi, Mr_Flash, medveeedik, ThePeak, letuscode, ayushb03, Gor_04, Ibrahim_Hassan1, OmarAnalog, gavinmagnus, Waffle_, Dr.rabi3, LeCNo, CGemmy, WHOISMTRX, 66hz, Error_403, princedyrus, BelentbaySamat, .nagy., jaloliddinmurodullaev, ahmad_alghadban, _Abdell, vellalacheruvu.raviteja, Glitch00, brown-Rang, T0TA._., AmiraAshour.

Below is a list of students who successfully passed the second exam:

nifeshe, Proof_by_QED, napgod_pk, antoshkin, morz, DeanMMenezes, Baskot, metelkov, Too_Weak_To_Anything, elixir, FTGUPP, Eslam.Taha, AnasMaged, dualthread, 5ON, VON, m1ckyro5a, Tod, TahsinArafat, fattahovainur0, 3alam, kk_tarun, _mbi, AbduSaber, nazimsaifullah, pozorische, trmasha2002, Yousef.Fadl, ProofByContradiction_, _hoanglong_, randomrandomness, shshank_10, Mohamed_Saad62, yohanse_mehabaw, Mostafa_Mohamed, payday3, bashem, loli_lover, CGemmy, Tamerlan74, elen.v.grigoryan, srkd, alaaawad0100, Dada1312, Alaatnt, 666EGOR777, El_Gemmy, Mohammed_Elmahboob, sky_fish, Make_CYF_Great_Again, Neko_lover, HazemRawi, enlorik, sheikh, Bylbaw, gveli21, hunde11.

We will communicate further instructions to you after all three exams. Thank you for joining EPIC Institute of Technology!

Problem A. Graph of vertices

For each vertex, we count the number of outgoing edges and find the maximum number for all vertices. After that, it is enough to iterate over the vertices again and output them.

Problem B. Paris 2024 Olympics

To take first place, you need to have at least as many gold medals as Team $$$USA$$$. Another set of medals may be needed if Team $$$Code$$$ has fewer silver medals, or if there are fewer bronze medals in a tie for silver.

Problem C. XOR and SUM

$$$2x \oplus (2x + 1) = 1$$$ and $$$(2x - 1) \oplus (2x) \gt 1$$$. Therefore, we can separately calculate the number of pairs for which $$$\oplus$$$ is equal to $$$1$$$ and in which it is strictly greater than $$$1$$$ (these pairs will alternate).

Problem D. Rectangles

Let $$$c_i$$$ be the number of times the number $$$i$$$ appears in the array.

Let's count how many different squares we can construct. To do this, we need to determine the number of $$$c_i$$$ such that $$$c_i \ge 4$$$.

Let's separately count the number of different rectangles $$$a \lt b$$$ that can be constructed. Let's count the number of $$$c_i$$$ such that $$$c_i \ge 2$$$, let's denote this number as $$$t$$$. It can be shown that the number of different rectangles that can be constructed is equal to $$$\frac{t(t - 1)}{2}$$$.

Problem E. Graph compression

In this problem, we should note the following fact. If the graph has $$$n$$$ vertices and $$$m$$$ edges, then using the described operations we can construct any graph of $$$n$$$ vertices and $$$m$$$ edges. We will find a minimum $$$t$$$ such that $$$\frac{t(t - 1)}{2} \ge m$$$. In other words, we will find the minimum number of vertices in the graph that contains at least $$$m$$$ edges. The minimum value of $$$t$$$ will be the answer to the problem.

Therefore, how the vertices are connected in the initial graph does not matter at all.

Problem F. Make a palindrome

Since $$$a \ge 2b$$$, we can always use only operations of the second type. Suppose we are trying to do an operation of the first type (swap any two symbols). But then we can simply assign the values ​​of the symbols after the swap in these two positions and spend $$$2b \le a$$$ coins on this.

If $$$s_i = s_{n - i + 1}$$$, we will pay $$$0$$$ coins for this pair of symbols in the palindrome. Otherwise, we will pay $$$b$$$ coins for this pair of symbols (we will replace one of them).

Problem G. abcd

$$$\frac{a^2cd + ab^2d + abc^2 + bcd^2}{abcd} = \frac{a}{b} + \frac{b}{c} + \frac{c}{d} + \frac{d}{a}$$$.

To show that $$$s \ge 8$$$, apply the AM-GM inequality twice as follows:

$$$(\frac{a}{b} + \frac{c}{d}) + (\frac{b}{c} + \frac{d}{a}) \ge 2 \sqrt{\frac{ac}{bd}} + 2 \sqrt{\frac{bd}{ac}} = \frac{2(ac+bd)}{\sqrt{abcd}} \ge 2 \frac{4\sqrt{ac}\sqrt{bd}}{\sqrt{abcd}} \ge 8$$$

Problem H. Good arrays of numbers

The number of such permutations is $$$F_{n + 1}$$$, where $$$F_k$$$ is the $$$k^th$$$ Fibonacci number: $$$F_1 = F_2 = 1$$$, $$$F_{n + 1} = F_n + F_{n - 1}$$$.

We will leave the proof of this solution as an independent task, but here are some hints:

1. Analyze whether $$$|b_i - i|$$$ can be greater than $$$1$$$.

2. Suppose that $$$|b_i - i| = 1$$$, consider two cases $$$b_1 = 1$$$ and $$$b_1 = 2$$$ ($$$b_1$$$ cannot take other values). For each case, try to count the number of ways to arrange the remaining numbers.

Problem I. Dice 2

Let's calculate $$$f(i)$$$, with what probability all throws of the dice with the value $$$i$$$ will be written down on one sheet of paper. Let's assume that the number $$$i$$$ came up exactly $$$c_i$$$ times. Then $$$f(i) = \frac{2}{2^{c_i}} = \frac{1}{2^{c_i - 1}}$$$. Of all $$$2^{c_i}$$$ equally probable outcomes, only $$$2$$$ of them are suitable for us (all numbers will be written down on one sheet).

The entire value $$$i$$$ can be considered independently, so the answer to the problem is $$$f(1) \cdot f(2) \cdot ... \cdot f(6)$$$.

Problem J. Matrix of zeros and ones

This is an optimization problem and you can see that it is impossible to score $$$10$$$ points. This problem has several basic solutions that can be further improved using local optimizations. Several basic solutions are to fill all even rows with ones, fill all even columns with ones, split the matrix into frames and alternate the values ​​$0$ or $$$1$$$ in them.

Problem K. Convex quadriteral

Let $$$I$$$ be the center of the inscribed circle. Then:

1. $$$\angle BIC = 105^{\circ}, \angle ICB = 15^{\circ}, \angle AID = 75^{\circ}, \angle IDA = 45 ^{\circ}$$$.

2. $$$AD = \frac{BI}{BC} \frac{AD}{AI} = \frac{sin 15 ^{\circ}}{sin 105 ^{\circ}} \frac{sin 75 ^{\circ}}{sin 45 ^{\circ}} = \sqrt{2} sin{15^{\circ}} = \frac{\sqrt{3} - 1}{2} $$$.

Problem L. Correct permutations

Let $$$f_{i,j}$$$ be the number of ways to arrange the numbers from $$$1$$$ to $$$i$$$ so that exactly $$$j$$$ numbers are visible.

Let's consider two cases:

1. $$$1$$$ in these permutations will be in the first position. It will be visible in any case, so in this case we can add the value $$$f_{{i - 1}, {j - 1}}$$$ to $$$f_{i, j}$$$ (a similar problem if we decrease the entire value of the numbers in the permutation by $$$1$$$).

2. $$$1$$$ in these permutations is not in the first position. Then it will never be visible and it does not matter in what position we put this number. Therefore, we can add $$$(i - 1)f_{i - 1, j}$$$ to the answer $$$f_{i, j}$$$ (there are $$$i - 1$$$ positions in total where we can put a one and move on to smaller dimensions).

Problem M. Interesting numbers

Such numbers are those of the form $$$153846153846153846...153846$$$.

Obviously, since the number has the same number of digits when multiplied by $$$3.5$$$, it must begin with either $$$1$$$ or $$$2$$$.

Case 1: The number is of the form $$$10^N + A, A \lt 10^N$$$.

$$$\frac{7}{2} (10^N + A) = 10A + 1 \rightarrow A = \frac{7 \cdot 10^N - 2}{13}$$$. The powers of $$$10$$$ repeat with a period of $$$6$$$ mod $$$13$$$, $$$(10, 9, 12, 3, 4, 1)$$$, so $$$A$$$ will be an integer iff $$$N \equiv 5$$$ $$$($$$ mod $$$6)$$$.

Case 2: The number is of the form $$$2 \cdot 10^N + A, A \lt 10^N$$$. Then, as before, $$$A = \frac{14 \cdot 10^N - 4}{13}$$$. But as $$$A \lt 10^N$$$, this implies $$$10^N \lt 4$$$, which is impossible.

The dates for the second and third entrance exams are set!

• Second Entrance Exam: August 13, 12:00 CET
• Third Entrance Exam: August 19, 14:00 CET

For more details on how to get enrolled and information about the exam format, please refer to the previous posts:

• How to get enrolled
• About the exam

Good luck!

Below is a list of students who successfully passed the first exam:

martynas-sm, NullPoExc, HynDuf, seduneon, whuang369, AmmarDab3an, artem3605, IMRUN, AceKnight7, Penguin07, Lilypad, TahsinArafat, Reginleyv, otabek_kholmirzaev, abz-codes, N00BGH0ST, adi_isHere, shinbay, denk, beka_0123, fozboom, la_gatto, ksu_kotovaa, Mohammed_Elmahboob, faresedres, FTGUPP, MinhHoangLe, Joel_Uwu, zakharch1k, prohibere, neal27, Oak, MadhavCoding, d_nelepova, RaBeka, hopium, Matvey_Kos, Azimjon, Uzbek_6565, shaswat01, folder, Griffith, pp_, cos_1e20, Jori, Ahmed__Mostafa, KinDeR___, danilak85, ruslanraupoff, BlueRaven52, m1ckyro5a, gveli21, _convexhull, Nisikto, sashkamilashka, Fatoma, Kalpit1018, _YaoYao_, Veab, Yassmenhussin, anonymous_ali.

We will communicate further instructions to you after all three exams. Thank you for joining EPIC Institute of Technology!

Problem A. Digits of numbers

In this problem, you need to count for each digit how many times it appears in the number notation and take all quantities modulo 10. To do this, it is enough to divide each of the numbers into digits and count the number of occurrences of each of them.

Problem B. Power of 2

The number $$$x$$$ can be represented as two powers of 2 if the binary notation of the number $$$x$$$ contains exactly two ones. To build a matrix, you need to iterate over all the rows and columns and count the number of ones in the binary notation of the sum of the row id and the column id.

Problem C. Bundesliga 23-24 analysis

Correct answers to the questions in the task:

1. 81
2. "Bayer 04 Leverkusen"
3. "SV Darmstadt 98"
4. "14:30"
5. 225
6. 20
7. "SV Darmstadt 98"
8. "Bayer 04 Leverkusen"
9. 10
10. 7

To get answers to questions, it was possible to locally process the dataset and pre-calculate all the answers.

Problem D. Shifts

We will move along the string of Latin letters $$$S$$$ from left to right and for each position check whether we can put the letter 'a' in its place. If it is impossible to put the letter 'a', then the answer for this position will not change, otherwise we put the letter 'a' and subtract from $$$k$$$ the number of operations that were spent to bring the current letter to the letter 'a'.

The complexity of the solution is $$$O(|S|)$$$.

Problem E. It's all about laziness

Let's go through all pairs of possible days $$$j_1, j_2$$$ and for each pair calculate the minimum time that needs to be spent on completing all the work. For the fixed days $$$j_1, j_2$$$, the minimum time that needs to be spent on completing all the work is $$$\sum_{i = 1}^{n} min(a_{i, j_1}, a_{i, j_2})$$$.

For all pairs of days $$$j_1, j_2$$$ we select the minimum value of time that needs to be spent on completing all the work, this will be the answer to the problem.

The complexity of the solution is $$$O(nm^2)$$$.

Problem F. Dictionary of English words

In this problem, you need to build a chain of words of maximum length, so that each word (except the last one) can be built from the next one.

You can sort all the words in order of increasing length and use dynamic programming. Let $$$dp_i$$$ be the maximum chain of words that can be built if the last word in this chain has index $$$i$$$. To calculate $$$dp_i$$$, we iterate over all $$$j \lt i$$$ and check whether the $$$j$$$-th word can be built from the $$$i$$$-th. If it is possible, we try to update the answer $$$dp_i$$$ as $$$dp_j + 1$$$, also remembering the index $$$j$$$ as the previous word for the $$$i$$$-th.

For a given set of words, there are many sequences of length $$$12$$$, one of them is "t", "nt", "ent", "rent", "inter", "retain", "certain", "creation", "creations", "containers", "consideration", "considerations".

Problem G. Interesting triangle

We will iterate over $$$x$$$ and keep the maximum $$$y$$$ such that the point $$$(x, y)$$$ is inside the triangle. This can be checked in many ways, for example, by constructing the equation of a line at the points $$$(0, b), (a, 0)$$$ and checking on which side of the line the point $$$(x, y)$$$ is. It can be shown that as $$$x$$$ increases, the maximum allowable $$$y$$$ will remain the same or decrease, so as $$$x$$$ increases, we can decrease $$$y$$$ until the point $$$(x, y)$$$ is inside the triangle. Since we never increase the value of $$$y$$$, the iteration over all $$$x$$$ and allowable segments will have a solution complexity of O(a + b)$.

Now for each $$$x$$$ we know the allowable segment by $$$y$$$, let's denote this segment by $$$[0, r]$$$. The answer should be supplemented by the number of primes on the segment $$$x, x + r$$$. To do this, you can pre-calculate all prime numbers up to $$$a + b$$$ and determine the number of prime numbers on the segment.

The complexity of the solution is $$$O(a + b)$$$.

Problem H. Dice (Easy version)

Let $$$dp_{i, j}$$$ be the probability that a sequence of length $$$i$$$ with the last element equal to $$$j$$$ was constructed. Let's iterate over which number from $$$1$$$ to $$$6$$$ will be drawn next and denote it $$$k$$$. If $$$k \ge j$$$, then the sequence will still be non-decreasing, so using the technique of dynamic programming forward, we will update the answer for $$$dp_{i + 1, k}$$$ (we will add the value of $$$dp_{i, j}$$$ divided by $$$6$$$, since each number is drawn with the same probability).

The complexity of such a solution is $$$O(n)$$$.

It can also be shown that the answer is $$$\frac{C_{n + 5}^{5}}{6^n}$$$. We will leave the proof of this statement to you. Hint: in a sequence of length $$$n$$$, you need to put exactly $$$6$$$ separators.

Problem I. Dice (Hard version)

The complex version of the problem can be solved by any of the methods described in the problem above, but now we need to represent the answer as a fraction $$$\frac{a}{b}$$$.

To transfer all real calculations to modulo calculations, it is enough to use Fermat's little theorem.

$$$a b^{-1}$$$ mod $$$M = ab^{M - 2}$$$ mod $$$M$$$ (for prime $$$M$$$).

Problem J. 10x10

The minimum value of $$$S$$$ is $$$106$$$. We suggest you leave the proof of this fact as an independent work. Hint — try to prove it by the opposite, trying to construct an answer for $$$105$$$ or less. You can safely write your reasoning in the comments under this post :)

The answer can be constructed constructively. One of the possible answers may look like this:

• $$$100$$$ $$$1$$$ $$$99$$$ $$$2$$$ $$$98$$$ $$$...$$$
• $$$6$$$ $$$95$$$ $$$7$$$ $$$94$$$ $$$8$$$ $$$...$$$
• $$$90$$$ $$$11$$$ $$$89$$$ $$$12$$$ $$$88$$$ $$$...$$$
• $$$...$$$

Problem K. Express the sum (simple version)

$$$\sum_{k = 0}^{n} \frac{(-1)^k}{k^3 + 9k^2 + 26k + 24} C_n^k$$$ =

$$$\sum_{k = 0}^{n} \frac{(-1)^k}{(k + 2)(k + 3)(k + 4)} C_n^k$$$ =

$$$\sum_{k = 0}^{n} (-1)^k \frac{k + 1}{(n + 1)(n + 2)(n + 3)(n + 4)} C_{n + 4}^{k + 4}$$$ =

$$$\frac{1}{(n + 1)(n + 2)(n + 3)(n + 4)}\sum_{k = 4}^{n + 4}(-1)^k(k - 3)C_{n + 4}^k$$$

It can be shown that

$$$\sum_{k = 0}^{n + 4} (-1)^k (k - 3) C_{n + 4}^k$$$ =

$$$\sum_{k = 0}^{n + 4} (-1)^k C_{n + 4}^k - 3 \sum_{k = 0}^{n + 4} (-1)^k C_{n + 4}^k$$$ =

$$$\sum_{k = 0}^{n + 4} (-1)^k C_{n + 4}^k - 3 (1 - 1)^{n + 4}$$$ =

$$$\frac{1}{n + 4} \sum_{k = 1}^{n + 4} (-1)^k C_{n + 3}^{k - 1}$$$ =

$$$\frac{1}{n + 4} (1 - 1)^{n + 3}$$$ = $$$0$$$.

Having this result and substituting it into the first formula, we get that the answer to the problem is $$$\frac{1}{2(n + 3)(n + 4)}$$$.

Problem L. Express the sum (hard version)

In this problem you also need to use Fermat's little theorem to avoid division.

Problem M. Travel to Byteland

For $$$k \le 1000$$$, dynamic programming can be used.

$$$dp_{i, j}$$$ is the number of paths that can be constructed from vertex $$$s$$$ to vertex $$$i$$$, passing through exactly $$$j$$$ roads.

The complexity of such a solution is $$$O(n^2 k$$$).

To solve the problem for any $$$k$$$,

Let $$$A$$$ be the adjacency matrix of the graph. If we square this matrix (we get a matrix $$$A'$$$ with elements $$$a'_{i, j}$$$, then $$$a'_{i, j}$$$) is equal to the number of ways to get from vertex $$$i$$$ to vertex $$$j$$$ using exactly two roads. This can be easily shown, since any path between vertices $$$i, j$$$ such that $$$a_{i, k} = 1$$$ and $$$a_{k, j} = 1$$$ will be counted, and $$$a'_{i, j}$$$ will be added to $$$1$$$. If at least one of the edges $$$(i, k)$$$, $$$(k, j)$$$ did not exist, then one of the factors will be equal to $$$1$$$ and nothing will be added to the answer.

Similar reasoning can be used to show that to obtain the number of paths of length $$$k$$$, the initial matrix $$$A$$$ must be raised to the power $$$k$$$. To do this, use the binary matrix exponentiation.

The complexity of the solution is $$$O(log(k)n^3)$$$.

Problem N. Three arithmetic sequences

Let's sort the elements of the array. Let's assume that $$$a_1$$$ is included in the first arithmetic sequence.

Let's take a random element from $$$a_2, a_3, ..., a_{3n}$$$. With probability $$$\frac{n - 1}{3n - 1} ≈ \frac{1}{3}$$$, this element will be in the first arithmetic sequence.

Let's denote $$$D = a_x - a_1$$$, where $$$x$$$ is the index of the randomly selected element. Then $$$d_1$$$ will be a divisor of $$$D$$$. Let's go through all possible options for $$$d_1$$$ and try to construct all possible arithmetic sequences of length $$$n$$$ with known $$$a_1, d_1$$$. If the set of numbers is included in the array of numbers $$$A$$$, we delete them and solve the problem of finding two arithmetic sequences in a similar way.

It can be shown that the complexity of such a solution is $$$O(n^2)$$$.

Hello everyone!

We are happy to announce that the date of the first entrance exam is set for July 27, 15:00 CET. We’ve prepared a step-by-step guide on how to get enrolled:

1. Fill out the application form on our website. After successful registration, you should receive an email. If you haven’t received it — first check your spam box and if it is not there, fill the form once again.

2. Entrance exams will be held here in the form of Codeforces contests. We strongly recommend to share either your real name or your email (the same one you provided in the application form) in your Codeforces profile so that we can easily identify you if you pass the exam.

3. There will be three entrance exams in total. Registration for the exam opens 6 hours before it starts. Each exam will last 4 hours. In order to be accepted you have to get a passing score in at least one of them. The passing score for each exam will be published within a few days of the exam itself. We will also provide solutions to each exam after the exam so that you can prepare for the next one. If you don’t get a passing score for an exam you can still participate in the next one.

You won't miss any important information if you are subscribed to our announcement channel or our LinkedIn group. We will announce the dates of the other exams in advance and on the day of the exam. You can also ask your questions in the discussion channel.

If you follow all of the steps above, we will send you an email with further instructions if you achieve a sufficient score in one of the exams.

Good luck!

Problem A. New sorting algorithm (version 5)

Let $$$f(s)$$$ denote the minimum number of letters that must be removed from the string $$$s$$$ so that all remaining letters are different. It is necessary to sort the strings of the initial array in order of increasing value $$$f(s)$$$ without changing the relative order of the strings if $$$f(s)$$$ is equal.

Problem B. Array encryption (version 2)

Let's denote $$$a_i$$$ — the value of the $$$i$$$-th number in the initial array. $$$ans_i = a_i$$$ XOR $$$a_{n - i + 1}$$$ (1-array indexing).

Problem C. 12 3 13

$$$12$$$ $$$3$$$ $$$13$$$ is "LCM". Each number indicates the number of a letter in the Latin alphabet. LCM — Least common multiple. The answer to the problem is the LCM of all the digits of the number.

Problem D. 30-digit numbers

The number 10 suggests the answer. From 1 to 30 there are only 10 prime numbers. In this problem you need to write down all the digits in positions $$$i$$$ such that $$$i$$$ is a prime number.

Problem E. Numbers of even length

Let's split the initial number into two parts of equal length. Let's denote the first number $$$l$$$, the second number $$$r$$$. If $$$l \ge r$$$, write down the digits of the numbers $$$l$$$ and $$$r$$$ one by one (the first digit of the number $$$l$$$, the first digit of the number $$$r$$$, the second digit of the number $$$l$$$, the second digit of the number $$$r$$$, .. .), the final number will be the answer. If $$$l \lt r$$$, we exchange the numbers $$$l$$$ and $$$r$$$ and similarly write down the numbers according to the principle described above.

Problem F.+-()

Let us denote by $$$x_1$$$, $$$x_2$$$, $$$y_1$$$, $$$y_2$$$ the number of occurrences of the characters '+', '-', '(', ')' in the initial line. The answer to the problem will be $$$|x_1 - x_2| + |y_1 - y_2|$$$.

Problem G. Word encryption

You can notice that the given string in the test examples has an even length. Let's split the string into pairs of characters and in each of these pairs we will find the difference between the right and left letters modulo 26 (the size of the Latin alphabet). This difference will indicate the serial number of the encrypted letter in the Latin alphabet.

Problem H. +-

In this problem you need to count the number of squares consisting entirely of the '+' symbol.

Problem I. Maximum product of prime numbers

Each row of the matrix contains one natural number. $$$a_{ij}$$$ contains a '+' sign if the partition of the $$$i$$$-th number includes the $$$j$$$-th prime number in ascending order (as a divisor). Using a given matrix, you need to construct all the numbers and select the maximum of them, which will be the answer.

Problem J. Sequence of natural numbers

$$$a_1 + a_2 + a_3 = a_4 + a_5 + a_6 = a_7 + a_8 + a_9 = 99$$$.

$$$a_1 + a_2 + ... + a_9 = 99 + 99 + 99 = 297$$$, $$$a_{10} + a_{11} = 381 - 297 = 84$$$.

$$$a_9 + a_{10} + a_{11} = 99$$$, $$$a_9 = 99 - 84 = 15$$$.

Problem A. New sorting algorithm (version 4)

Consider the string $$$s$$$. Let's count the number of occurrences of letters in the string $$$s$$$. For example, for the string $$$s = "abacaba"$$$, the letter $$$a$$$ appears 4 times, the letter $$$b$$$ twice, the letter $$$c$$$ once. Let's build an array of these quantities in non-increasing order $$$f(s) = [4, 2, 1]$$$.

It is necessary to sort the strings of the initial array in ascending order of the function $$$f(s)$$$ without changing the relative order of the strings if $$$f(s)$$$ is equal.

Problem B. Pairs of numbers

For a given $$$n$$$, you need to find the $$$n$$$-th prime and $$$n$$$-th composite number. The answer to the problem is the sum of these two numbers.

Problem C. Favorite digit

In this problem you need to sort the digits of a number in ascending order and output the value of the 4th (1-indexing).

Problem D. Array encryption

For position $$$i$$$, we need to calculate the length of the largest non-increasing subsequence that can be constructed if we take only elements with indices from $$$i$$$ to $$$n$$$, taking element $$$a_i$$$ first.

Problem E. Permutation encryption

Position $$$i$$$ in the initial array contains the xor of all numbers from $$$1$$$ to $$$n$$$, except for the number that is in the $$$i$$$-th position in the permutation.

Problem F. Two characters

The conditions are specified in Morse code. The problem requires finding the LCM of all numbers from 1 to 100.

Problem G. Beautiful array

Let's denote $$$a_{ij}$$$ — the element that will be located in the answer at position $$$(i, j)$$$. $$$a_{ij} = gcd(i + j, i * j)$$$.

Problem H. Restoring the permutation

You can analyze from test cases which sets of numbers represent each of the permutation numbers.

Problem I. suseG teh ucnotyr

This problem contains a text that talks about Italian pizza. The title of the task asks to display the name of the country. The answer is Italy.

Problem J. Star Array

If $$$i$$$ mod $$$j = 0$$$ or $$$j$$$ mod $$$i = 0$$$, then the cell $$$(i, j)$$$ contains '*'.

Problem K. Ten-digit natural number

Let's count the number of times each digit from 0 to 9 occurs. Let's construct a new number from these numbers, taking the number of occurrences of digits from 9 to 0. We need to remove the leading zeros and print the result as the answer to the problem.

Problem A. New sorting algorithm (version 3)

Let's denote $$$f(s)$$$ — the number of different characters in the string $$$s$$$. The starting array of strings must be sorted by increasing value of $$$f(s)$$$ without changing the relative order.

Problem B. Encryption algorithm

You need to print all the characters in odd positions first, then in even positions (1-indexing of characters in a string).

Problem C. Beautiful matrix (version 2)

The resulting matrix will have dimensions of $$$2^n$$$ by $$$2^n$$$.

Looking at the test examples, you can see that all the numbers in the matrix do not exceed 4. What could 4 mean? In this problem there are four directions of movement — left, right, down and up. For each cell $$$(i, j)$$$ we calculate the distances to each of the four boundaries of the matrix. The final value in the cell $$$(i, j)$$$ is the number of primes from this set of numbers (from four distances).

Problem D. Again... (version 4)

In this problem there was no need to find the shortest path. The statements does not say that you need to enter the maze. Therefore, you can go around it with just two movement changes.

Problem E. 2, 3, ..., 541

The title of the problem contained a hint — 2, 3, ... 541. 541 is the 100th prime number, the values of all $$$a_i$$$ are up to 100. Therefore, for a given $$$a_i$$$ you need to find the $$$a_i$$$th prime number and sum it over everyone $$$a_i$$$.

Problem F. Periods

There was also a hint in the title of this problem. You need to print the $$$n$$$th number, the notation of which can be represented as a notation of some other number repeated several times. You can iterate over the period number and the number of its occurrences and construct all possible numbers up to $$$10^{10} + 10^5$$$. It can be shown that the answer is at most $$$10^{10} + 10^5$$$, since we can construct $$$10^5$$$ numbers by taking each natural number and writing it twice.

Problem G. Close, very close...

The problem legend contained a hint for solving the problem. Let us denote $$$n_{min}$$$ as the maximum number less than $$$n$$$ that can be obtained by rearranging the digits of $$$n$$$ (leading zeros are allowed). Similarly, $$$n_{max}$$$ is the minimum number greater than $$$n$$$ that can be obtained from rearranging the digits of $$$n$$$.

The answer to the problem $$$n_{max} - n_{min}$$$.

Problem H. GG

It was necessary to understand which countries are depicted in the photographs.

The correct answers are the USA, Poland, Germany, Japan (not France) and in the last image Andorra. This is a typical task from GeoGuessr :)

The answer to the problem is the telephone code of Andorra (376).

Problem I. Higher, maybe even higher?

In this problem, there was a minimal hint about “higher” in the title. In theory, if one were to solve problem $$$C$$$ or $$$I$$$, this could provide a clue to the second problem.

In this problem, you need to imagine that the values in the cells are the height of the buildings. Then for the cell — the number of buildings that are visible in four directions.

Problem J. Matrix of letters

Let us denote p as the maximum divisor of the number $$$x$$$, not equal to $$$1$$$ and $$$x$$$. Then $$$f(x)$$$ is equal to $$$p$$$ — 1 letter of the Latin alphabet. If $$$x$$$ is prime, then $$$f(x)$$$ is equal to '-'.

In cell $$$(i, j)$$$ you need to print $$$f(i + j)$$$.

Problem A. Prime task

In this problem you need to find and output the sum of the first $$$n$$$ prime numbers.

Problem B. Beautiful matrix

The cell $$$(i, j)$$$ contains '*' if the number $$$i + j$$$ is prime (1-indexing). If the number $$$i + j$$$ is composite, then the cell $$$(i, j)$$$ contains '.' The size of the sides of the answer matrix is $$$2^n$$$ (the matrix is square).

Problem C. Emormirp

In this problem, for a given $$$n$$$, you need to find a least possible natural $$$m$$$ such that $$$m \gt n$$$, $$$m$$$ is both prime and palindrome.

Problem D. Another prime numbers problem?

In this problem you need to calculate the product of the digits of a given number and count the number of 2, 3, 5, 7 (prime numbers up to 10) in the prime factorization. You will notice that there is no need to count the product of digits and you can divide each digit by the product of prime divisors.

Problem E. Five numbers game

An interesting fact is that all participants who chose a number in the interval $$$[32, 35]$$$ as the maximum number scored the required number of points to get into the top 3.

The winning strategy is to maximize the first three numbers out of five to increase the chances of winning on the first three numbers.

Problem F. Again...

In this problem you need to count the number of equilateral triangles in an image.

The answer to the problem is 31.

Problem G. Matrix of letters

The size of each side of the matrix is $$$(2^n - 1)$$$. From the test examples you can see the principle of constructing a matrix of letters.

You can notice that the letter 'a' always forms a cross that goes through the row and column with indices $$$2^{n - 1}$$$ (1-indexing). Then you can solve the problem recursively in each of the remaining four squares.

Problem H. New sorting algorithm (version 2)

Let us denote $$$f(s)$$$ as the sum of the ordinal numbers of the letters of the string $$$s$$$ in the alphabet of lowercase Latin characters. For example, for the string $$$s = "abc"$$$ the value $$$f(s) = 1 + 2 + 3 = 6$$$.

After this, the strings need to be sorted in increasing order of the $$$f(s)$$$ function, without changing the relative order for rows with the same $$$f(s)$$$ value.

Problem I. Sequence of numbers

You will notice that the indicated numbers from the condition can be replaced with letters. $$$M = 1000, I = 1, L = 50, E = 2.71828$$$. M, I and L represent latin numerals and e is mathematical constant. If we assume that all the letters should form a word, then the letters are missing in the middle of the word, giving us a clue that the encrypted word is "middle". D stands for 500 in latin numeral representation.

The answer to the problem is 500.

Problem J. Petya and beautiful numbers

In this problem, you need to construct the minimum natural number $$$m$$$, which is obtained from some permutation of the digits of the number $$$n$$$ and does not have leading zeros.

Problem K. segozfnsvteienrveifrieueeeotwtroxnhenoih

Each of the numbers from $$$0$$$ to $$$9$$$ can be represented as a record of lowercase Latin letters. For example, $$$5$$$ = "five".

The line from the condition is a union of records of a certain set of numbers from $$$0$$$ to $$$9$$$. The letters were mixed and for such a string the answer can be constructed in a greedy way. For example, the letter 'g' appears only in the digit $$$8$$$, so you can first find the number of occurrences of $$$8$$$.

Problem A. Beautiful numbers

The answer to the problem is $$$a$$$, $$$b$$$, where $$$a$$$ is the number of composite numbers from $$$2$$$ to $$$n$$$, and $$$b$$$ is the number of prime numbers from $$$2$$$ to $$$n$$$.

Problem B. XOR / SUM

There are several solutions to this problem. One of them is to calculate the SUM and XOR of all numbers on the segment in $$$O(r)$$$ and compare them.

There is also a simple solution in $$$O(1)$$$. If $$$l = r$$$ then the segment consists of one number for which SUM and XOR coincide. If $$$l + 1 = r$$$ and $$$l$$$ xor $$$r = l + r$$$, the segment consists of two numbers and also has the same XOR and SUM.

If the length of the segment $$$[l, r]$$$ is greater than two, then XOR and SUM will never coincide.

Problem C. Interesting Text

In this problem you had to count the frequency of occurrence of each Latin lowercase letter and output the letter that occurs most often.

Problem D. Again...

All letters except 'M' appear three times. The answer to the problem is 'M'.

Problem E. 511

In this problem you had to print the $$$n$$$-th natural number in ascending order whose digits are strictly increasing. There are exactly $$$2^9 - 1$$$ of such numbers. To iterate over all such numbers, you can iterate over all binary masks from 1 to 511, where the $$$i$$$th bit indicates whether the digit $$$i + 1$$$ should be included in the number's notation.

https://oeis.org/A009993 — the sequence of numbers that should be the result.

Problem F. Guess the number

This problem has many different solutions. Let's describe two of them.

1. Let's try 10000 first. Find the value of the first digit of the hidden number. We will increase the value of the first digit by 1 until the number of points increases. You need to do the same for all the remaining numbers.

2. Let's try 10000 first. After that, we'll ask the numbers 20000, 11000, 10100, 10010, 10001. Knowing how much the number of points has changed for each number, you can use the formula from the problem statements to calculate the value of each number independently.

Problem G. New sorting algorithm

Let us denote $$$f(s)$$$ as the string obtained after sorting the letters of the string $$$s$$$. For example, $$$f("abacaba")$$$ = $$$"aaaabbc"$$$, $$$f("babdeabac")$$$ = $$$"aaaabbcde"$$$.

The string $$$s$$$ will appear earlier in the answer than the string $$$t$$$ if $$$f(s) \lt f(t)$$$ or $$$f(s) = f(t)$$$ and $$$s$$$ is to the left of the string $$$t$$$ in the starting array of strings.

Problem H. Interesting matrix

In this problem you need to rotate the initial matrix by $$$0$$$, $$$90$$$, $$$180$$$ and $$$270$$$ degrees and sum all four matrices (all additions modulo 10).

Problem I. Truly EPIC

Game of Life.

In this problem, you need to implement an iterative algorithm that works as follows. At each iteration, for each position $$$(i, j)$$$, you need to count the number of '*' in four neighboring cells. If the number of '*' is odd, then in the position $$$(i, j)$$$ at the next iteration you need to set '*', otherwise '.'.

Problem J. Numbers from 1 to 100

More than half of the participants came up with all 100 numbers. Each of the numbers from $$$1$$$ to $$$100$$$ was chosen more than once, so all participants received 0 points. Therefore, there was no need to submit a solution for this problem :)

Problem A. EPIC+Institute+of+Technology

$$$n$$$ — character index in the string "EPIC+Institute+of+Technology" in 1-indexing (hidden in the task name).

Problem B. Binary Present Encoding

In this problem, the answer for $$$n$$$ is the $$$n$$$-th row of Pascal's triangle modulo 2.

Problem C. Elves' Jolly Decimal Secrets

If you analyze the test examples, you will notice that the answers to all test examples are numbers that are palindromes (read from left to right and from right to left the same way).

The answer to the problem is the minimum number $$$m$$$ greater than $$$n$$$ that is a palindrome. In other words, you need to find the nearest palindromic number that is greater than the given $$$n$$$.

Problem D. Be Modest and Wise, You'll Get Your Prize

Here are all the numbers that were selected in task D — 1, 1, 1, 2, 2, 3, 4, 7, 7, 8, 11, 11, 12, 13, 23, 24, 26, 29, 29, 31, 34, 311, 342, 120132, 84394, 841657.

Problem E. Santa's First Stops Around the Globe

$$$n$$$ is the year number. For the winning team of the UEFA Champions League in a given year, you need to print the name of the country that this team represents.

UEFA Champions League.

Problem F. Elves' Divisibility Debate

The problem has two obvious solutions.

The first solution is to calculate the product of the first 100 prime numbers and output the answer.

The second solution is to output 0.

Problem G. What?

The answer to a problem is the number of words in the problem statement. The answer to the problem is 579.

Problem H. Santa's Reindeer Sleigh Selection

The answer to the problem is "True" if the given number $$$n$$$ can be represented as $$$p^x$$$, where $$$p$$$ is a prime number, $$$x \gt 1$$$.

Problem I. Santa's sorting

You need to reverse all the numbers (for example, the number 12345 would be 54321) and sort them in ascending order. If the numbers after reversion are the same, then the larger one is the one that was larger in the initial recording. For example, the numbers 100, 1, 1000, 10000 will go in the order 1, 100, 1000, 10000.

Problem J. Lucky Number Santa

The hidden number is 70.

It could be calculated, for example, using binary search. Or make 100 attempts :)

Problem K. Beautiful image

The answer to the problem is the number of letters in the image. This image contains exactly 123 letters.

Problem A. Unary Addition

There are many solutions to this problem, one of them is to count the number of occurrences of the number 1 in the string and output the same number of digits 1. You can also simply remove all '+' from the string.

Problem B. Array of numbers

This problem can be solved in the following way. Assume that the number $$$x$$$ occurs $$$a$$$ times. Then you need to remove $$$a - 1$$$ of its copy from the array to leave at most once this number. It is possible to sort an array of given numbers and divide them into segments of identical numbers, separately solving the problem for each of them.

Another solution — the answer to the problem is equal to $$$n - |S|$$$, where $$$S$$$ is a set built on a given set of numbers.

Problem C. Minimum partition (version 2)

Let's construct a binary notation for our number $$$n$$$. We will go from smaller bits to larger ones and find such a pair of adjacent bits where the value in the larger bit is 0, and in the smaller one — 1. Then, to build the minimum required number, we need to swap these elements and sort the entire considered part on the right in ascending order ( in fact, one iteration of the insertion sort algorithm can be applied). If such a pair of neighboring bits was not found, it is necessary to add 0 to the record of the number in the maximum bit and swap the new bit and the maximum bit containing one and also sort the remaining bits in ascending order (to obtain the minimum exceeding the given number $$$n$$$).

You can see that this is very similar to finding the next permutation in an array of numbers.

There is an interesting solution in C++. Let's build a binary notation for our number $$$n$$$ and add 0 to it at the beginning of the notation. It can be easily shown to find the next permutation for a given set of numbers. You can just call the C++ next_permutation method and build the next permutation.

Problem D. Rectangles (version 2)

The answer to the problem is $$$S_1 + S_2 - S_0$$$, where $$$S_1$$$ is the area of the first rectangle, $$$S_2$$$ is the area of the second rectangle, $$$S_0$$$ is the area of their intersection. The task of finding the area of intersection of rectangles was in the first exam.

Problem E. Multiset

Let's assume that we need to take into account all the numbers from $$$l$$$ to $$$r$$$ once. Let's get some array $$$A$$$, and set the value $$$a_{l} = 1$$$, and $$$a_{r + 1} = -1$$$. If we count partial sums on this array, then we can see that only for numbers with indices from $$$l$$$ to $$$r$$$ the value of the sum on the prefix will be equal to 1, for other numbers — 0.

Using this solution, we can apply similar logic to all requests and calculate a partial amount for each position.

Problem F. Beautiful triples of numbers

Suppose $$$x$$$ is the number of matching numbers from $$$1$$$ to $$$n$$$. Then the answer to the problem is $$$C_x^3$$$.

To count the number of suitable numbers from $$$1$$$ to $$$n$$$, you can use the recursive method. Suppose we have already built some number $$$k \lt n$$$ and it contains different digits. Then you can try to add to the end for it any of the digits from $$$0$$$ to $$$9$$$, which did not occur in it. Let's assume that we assigned a number to $$$t$$$, then we get the number $$$k \cdot 10 + t$$$. If it also does not exceed $$$n$$$, causes a recursion from the received number further.

Problem G. Universal numbers

Let us separately consider the cases for $$$k = 1$$$. In what follows, we will assume that $$$k \gt 1$$$.

Let us enumerate the possible variants of the degree $$$a, b, c$$$. It is easy to show that all power values do not exceed $$$60$$$, since substituting the minimum possible value of $$$k$$$ equal to two will result in a number greater than $$$10^{18}$$$.

Suppose that the degrees $$$a, b, c$$$ are fixed and there is some function $$$f(a, b, c, k)$$$ that calculates the value $$$k^a + k^b + k^c$$$. Then a suitable value $$$k$$$ for the equation can be found using binary search, since the value of the function $$$f(a, b, c, k)$$$ is monotonic in the parameter $$$k$$$.

Problem H. Binary Knapsack

The full solution to the problem will appear later.

A little hint to the full solution — since the weights of the items are powers of 2, we can iterate over the weights of powers of 2 and combine items of the same weight into one item of weight of the next power of 2.

Problem I. Greatest Common Divisor

The answer to the problem can be represented as $$$2^{p_2} \cdot 3^{p_3} \cdot 5^{p_5} \cdot ...$$$. In other words, each number can be represented in its canonical form, where each factor is a prime number.

Let's enumerate all prime numbers up to $$$max(n_1, n_2)$$$ and calculate with what degree this prime number will be included in the GCD of two values.

Suppose we have fixed some number $$$p$$$ and want to know how many times it will occur in the partition $$$C_{n_1}^{m_1}$$$ (for $$$C_{n_2}^{m_2}$$$ the calculation is done in a similar way). To do this, it is necessary to calculate the degree with which the number $$$p$$$ enters $$$n_1!$$$ and subtract the degree with which this prime enters $$$m_1!$$$ and $$$(n_1 - m_1)!$$$. To find out with what factors the prime number $$$p$$$ is included in the GCD, it is necessary to take the minimum value among the quantities for $$$C_{n_1}^{m_1}$$$ and $$$C_{n_2}^{m_2}$$$.

Let's learn how to calculate for $$$n!$$$ with what degree the prime number $$$p$$$ enters the partition. It can be shown that each $$$p$$$-th number among $$$1 2 3 ... n$$$ is divisible by $$$p$$$, each $$$p^2$$$ of the numbers is divisible by $$$p^2$$$, and so on. Thus, $$$p$$$ will be included in $$$n!$$$ with degree $$$\frac{n}{p} + \frac{n}{p^2} + ...$$$ (all divisions are integer).

Problem J. Pseudocode

You can see that you do not need to constantly re-sort the entire array and the relative order will change only for the two maximum elements.

Therefore, it is enough to sort the starting array and check whether the two maximum elements are in the correct order.

Problem K. Sum of distances

Denote $$$S_1$$$ — the sum of pairwise distances between all tree vertices.

We will also learn how to count $$$A_e$$$ — the number of pairs of vertices that are located in different components of the graph, if the edge $$$A_e$$$ is removed. Denote $$$S_2$$$ — the sum of the values of $$$A_e$$$ over all edges of the tree. It can be shown that $$$S_1 = S_2$$$. This also follows from the fact that each edge contributes to the sum of pairwise distances as much as the number of paths that pass through this edge.

Therefore, to solve the problem, you need to consider each of the given edges of the tree and, using easy calculations, determine the number of paths that pass through this edge.

Problem A. Number strength

In this problem, you need to determine which digits occur in the notation of a number. This problem has many different solutions, one of them is to read the input number as a string and check if each digit from 0 to 9 is in the read string.

Problem B. The Euler Tour Representation

In this task, you need to implement the Depth-first search (DFS) algorithm. For each vertice of the tree, you need to add it to the answer at any time when the DFS algorithm passes through it. One of the solutions is given at the following link.

Such a solution has an asymptotics $$$O(n)$$$, where $$$n$$$ is the number of vertices in the tree.

Problem C. Check the Answer

Initially, let's find $$$n$$$ — the number of vertices in the tree. To do this, it is enough to count the number of different values that occur in the input. It can be seen that the length of the input array must be $$$2n - 1$$$, since an Euler traversal of a tree of $$$n$$$ vertices always contains $$$2n - 1$$$ values.

This problem also has several solutions. One of them is as follows. We will consider all edges (pairs of neighboring vertices) for a given Euler tour. Consider a pair of neighboring vertices $$$(u, v)$$$, which means that during the DFS algorithm we walked along the edge $$$(u, v)$$$. Then if the edge $$$(v, u)$$$ has already been encountered before, then we can remove it from the set of active edges (the DFS algorithm traversed some edge, traversed the subtree, and returns back). If the edge $$$(v, u)$$$ has not been encountered, then we add the edge $$$(u, v)$$$ to the set of active edges (traversing it for the first time).

The Euler bypass is correct for such a solution if, after considering all the edges, the set of active edges is empty.

Such a solution has an asymptotics $$$O(n \cdot log(n))$$$, where $$$n$$$ is the number of vertices in the tree.

Problem D. Split the Number

It is proposed to solve this problem recursively. Suppose that $$$i$$$ of the first digits of a given number have already been considered and some set of numbers $$$A$$$ has been constructed. $$$i + 1$$$-th digit can be appended to the end of the last number in set $$$A$$$ or a new number can be added to set $$$A$$$, consisting only of this digit. After the record of the number $$$n$$$ is divided into parts, it is possible to check that the numbers in the set $$$A$$$ are different and do not contain leading zeros. Among all suitable sets $$$A$$$ choose the one that contains the largest number of different numbers.

Denote $$$l$$$ — the number of digits in the record of the input number $$$n$$$. Such a solution has an asymptotic $$$O(l^2 \cdot 2^l)$$$ if bubble sort is used (to check that all numbers are distinct).

Problem E. Filling the Matrix

Let us first propose a slow solution to the problem with the asymptotics $$$O(min(M, N))$$$. It is easy to calculate what will be equal to any of the numbers for which $$$min(i, j) \le 2$$$. If $$$min(i, j) \gt 2$$$, then we can skip the first two rows and columns and add to the answer the number of numbers in the first two rows and columns. Accordingly, we need to reduce $$$i$$$ and $$$j$$$ also by 2. Thus, we have reduced the problem to a problem with less restrictions, and moving in steps of two, we will come to the answer.

With the help of easy calculations, one can generalize the formulas for two rows and pass immediately to any value of $$$2k$$$ rows and columns ahead, where $$$k$$$ is a natural number.

Such a solution to the problem has an asymptote O(1).

Problem F. Lucky Tickets

The solution to the problem is simplified by the fact that only the products of the digits in the two halves of the number must match.

Consider the first $$$n$$$ digits of a number. Each of them can take only one of the given values. Let's construct all possible solutions for the first $$$n$$$ digits. Let $$$i$$$ be the number of digits already considered, $$$A$$$ be an array of pairs of numbers $$$(u, cnt)$$$, where $$$u$$$ is the product that could be obtained by placing the first $$$i$$$ digits, and $$$cnt$$$ is the number of ways to get product $$$u$$$. Let's try to add $$$i + 1$$$-th digit and go through all possible options for its value. Then we can build a new array $$$B$$$ in the same way for $$$i + 1$$$ digits, iterate over all the options of $i + 1$th digit and products before that. In other words, the numbers for which the products of digits are the same in the future are not distinguishable and can be considered as one group. It also simplifies the solution of the problem and the fact that the values of the digits from 0 to 9 and the number of different products is limited on the given restrictions only by numbers that have simple divisors 2, 3, 5, 7 in their divisors.

Thus, we will construct all possible products that can be obtained for $$$n$$$ digits and their number. For the second half of the number, obviously the quantities will match. Therefore, the answer to the problem will be the sum of the squares of the number of occurrences of all products.

Problem G. Math problem

In this problem, you can notice that all values of $$$a_i$$$ are located in the interval from 0 to 2020. Therefore, you can substitute all values from $$$1$$$ to $$$n$$$ into the function $$$P(x)$$$ and count the number of times that each of the numbers occurred from 0 to 2020.

After that, you can go further and the quantity of these If this happens, then we have found the residue we need.

The solution of the problem has the asymptotics $$$O(n)$$$.

Problem H. Inversions

We will build a solution to the problem constructively. Let $$$n$$$ be the length of the permutation, $$$k$$$ be the required number of inversions. If $$$k = 0$$$, the answer to the problem is the permutation $$$1$$$ $$$2$$$ ... $$$n$$$. If $$$k \lt n$$$, then the answer to the problem is the permutation $$$2$$$ $$$3$$$ ... $$$k$$$ $$$k + 1$$$ $$$1$$$ $$$k + 2$$$ ... $$$n$$$ (it has exactly $$$k$$$ inversions) .

If $$$n \le k$$$, we put the number $$$n$$$ at the beginning of the permutation, subtract $$$n - 1$$$ from the number of inversions (because that many new iversions are formed) and go to the problem one element less.

Such a constructive solution has the asymptotics $$$O(n)$$$.

Problem I. Sums

Since we need to find the maximum difference between the sums, we can initially multiply by -1 all the numbers in even places and solve the problem of finding a segment with the maximum / minimum sum. You can solve the problem separately to find the maximum amount, for the minimum it is solved in a similar way (you can multiply all numbers by -1 and find the segment with the maximum amount).

In order to find the segment with the maximum sum, you can use the following solution. We will consider the numbers in turn and calculate the current sum of all numbers, and also store the minimum sum on the prefix that we once received earlier, the difference between them will be the maximum possible sum on the segment with the right border in the current number.

Such a solution to the problem has the asymptotics $$$O(n)$$$.

Problem J. Difficult task

If $$$n$$$ is odd, then the answer to the problem is $$$sqrt(n)$$$.

If $$$n$$$ modulo 4 gives a remainder of 0, then the answer to the problem is equal to $$$sqrt(2n)$$$.

If $$$n$$$ modulo 4 gives a remainder of 2, then the answer to the problem is $$$0$$$.

A detailed solution to the problem will appear later.

Problem K. Bison

Since the polygon is convex, you can recalculate the area of the polygon by moving along successive vertices using the formula for the area of a triangle.

Find the vertex $$$opt$$$ for the first vertex, drawing a diagonal through which the polygon is divided into two halves with a minimum difference in areas. This can be done by going through all the vertices of the polygon in linear time.

Next, we note the following fact. Assume that for some vertex $$$i$$$ we know a vertex $$$opt$$$ through which it is best to draw a diagonal from vertex $$$i$$$. Then it can be shown that if we move the left vertex of the diagonal from $$$i$$$ to $$$i + 1$$$, then the optimal vertex for drawing the diagonal $$$opt'$$$ will not be less than $$$opt$$$ (we leave the proof for self-study, you need to pay attention to how the value of the areas of the two halves changes).

Then we can move the vertex $$$i$$$ and keep the optimal value of the vertex $$$opt$$$, through which it is most profitable to make a diagonal.

Problem L. Game with Numbers

In this task, it was simply necessary to implement the iteration process described in the problem statement.

It can be seen that if the difference between the maximum and minimum is large, then we can immediately reduce the maximum number until such a moment when the relative order of the elements in the array changes (using GCD).

Problem M. Colored Leafs

In this problem, we will consider the simplest solution — for each vertice we will store what colors were found in the subtree of this vertice. Depth-first traversal visits some subtree and calculates all the colors that were used there and then adds them all to the set of the current vertice.

This approach can be optimized to a $$$O(n \cdot log^2(n))$$$ solution using the following trick. When it is necessary to add a set of values to some other set, we will move set of a smaller size to a larger one (for fewer operations). It can be seen that when using this method, each of the elements will be moved no more than $$$O(log(n))$$$ times (for the case when all the colors used are different), since with each move it falls into the set of the total size of at least twice as big.

In other words, for each vertice of the tree, we will be able to store the entire set of colors that occurs in the subtree. In this case, to find the number of different colors, you can sort the resulting set or store everything in advance in the set structure.

Problem A.Minimum partition

The answer to the problem is the number of 1s in the binary representation of the number $$$n$$$.

Popular mistakes:

• Always output 2. This is not true, for example, for $$$n = 7$$$.

Problem B. Rectangles

Note that if two rectangles intersect, then their intersection also forms a rectangle.

It should also be noted that in order to find the intersection of two rectangles, it is enough to solve the problem separately for the coordinate axes.

Suppose $$$x_1, y_1, x_2, y_2 (x_1 \le x_2, y_1 \le y_2)$$$ are the coordinates of the opposite corners of the first rectangle, $$$x_3, y_3, x_4, y_4 (x_3 \le x_4, y_3 \le y_4)$$$ are the coordinates of the opposite corners of the second rectangle. It can be shown that their intersection will be a rectangle with coordinates $$$max(x_1, x_3), max(y_1, y_3), min(x_2, x_4), min(y_2, y_4)$$$. It is worth considering the case that if $$$max(x_1, x_3) \gt min(x_2, x_4)$$$ or $$$max(y_1, y_3) \gt min(y_2, y_4)$$$ then the rectangles do not intersect.

To find the intersection of all three rectangles, you can first find the intersection of the first two and intersect the result with the third rectangle. The problem is similarly solved in the general case and for an arbitrary number of rectangles.

Popular mistakes:

• Int overflow in C++ (because the coordinates are up to $$$10^9$$$ and the product of side lengths can reach $$$10^{18}$$$);
• The case when the rectangles do not intersect was not checked.

Problem C. Obtuse triangles

To solve this problem, you need to use the law of cosines.

Suppose that $$$a, b, c (a \lt b \lt c)$$$ are the sides of a triangle. A triangle is obtuse if $$$c^2 \gt a^2 + b^2$$$.

Let's enumerate the values of the sides $$$a$$$ and $$$b$$$. Then it is obvious that $$$c \lt a + b$$$, since otherwise the triangle would be degenerate. Also, $$$c$$$ must be greater than $$$\sqrt{a^2 + b^2}$$$. Thus, you get several restrictions on the value of the side $$$c$$$ (including that $$$c \le n$$$), and using all of them we can calculate for the pair of sides $$$a, b$$$ the number of suitable values for $$$c$$$.

Such a solution has the asymptotic $$$O(n^2)$$$.

Popular mistakes:

• C++ int overflow (the answer for $$$n = 5000$$$ is $$$5943065628$$$);
• Incorrectly used the above conditions, as a result, the final result included degenerate or right-angled triangles.

Problem D. Bundesliga Results 2022-2023

This problem could be solved in several ways. One is to parse the data in Python or C++, precalculate the results for each football round, and write that as a constant in your code. Using this constant, you can display the result for each of the football rounds.

Popular mistakes:

• The final names of the teams must be displayed without umlauts;
• In this problem you don't need to know any algorithms and we hoped that all students will spend some time to solve this implementation problem :)

Problem E. Dice

Suppose we rolled a dice exactly $$$6N$$$ times. Then each digit from $$$1$$$ to $$$6$$$ must come up exactly $$$N$$$ times.

Consider a sequence of throws of length $$$6N$$$. In total there are $$$6^{6N}$$$ different sequences that can be obtained with the same probability.

Let's denote $$$C^{m}_{n}$$$ — the number to choose m different elements from a selection of n elements. It is known that $$$C^{m}_{n} = \frac{n!}{m! (n - m)!}$$$.

We call a sequence of throws correct if each digit in it occurs exactly $$$N$$$ times. We fix $$$N$$$ positions where the number 1 occurs. There are $$$C^{N}_{6N}$$$ ways to do this. Next, we fix $$$N$$$ positions where the number 2 will occur. There are $$$C^{N}_{5N}$$$ ways to do this in total (since $$$N$$$ positions are already occupied). Similarly, we fix positions for the remaining digits. We get that the number of correct sequences is $$$C^{N}_{6N} \cdot C^{N}_{5N} \cdot C^{N}_{4N} \cdot C^{N}_{3N} \cdot C^{N}_{2N} \cdot C^{N}_{N}$$$.

Considering that $$$C^{N}_{N} = 1$$$, we get the answer to the problem — $$$\frac{C^{N}_{6N} \cdot C^{N}_{5N} \cdot C^{N}_{4N} \cdot C^{N}_{3N } \cdot C^{N}_{2N}}{6^{6N}}$$$.

As $$$n$$$ increases, the final probability decreases and you could score at least 6 points by simply outputting always 0.

Popular mistakes:

• C++ int overflow.
• The output of the answer with the wrong precision.

Problem F. Graph Construction

It is proposed to solve the problem in a recursive way.

Suppose we need to build a graph that will have $$$k$$$ independent sets (taking the empty set, for this we can add one for the initial $$$k$$$).

If $$$k = 2$$$, then it is possible to build a graph from one vertice and get exactly two independent sets — the vertice of the graph can be taken into the set and not taken.

If $$$k$$$ is even, then we can construct the following solution. Let's construct an answer for $$$\frac{k}{2}$$$. Then we can add one vertice to the resulting graph that is not connected to any of the others, and thus multiply the number of independent sets by two (we can either add a new vertice to the independent sets, or not take it).

If $$$k$$$ is odd, we can construct a solution for $$$k - 1$$$ and add a vertice to it, which will be connected to all the others. In this case, we will add just one new independent subset, taking this vertice.

It is easy to show that $$$O(log(k)$$$) vertices are needed to construct a graph under such constraints, since we use a recursive construction dividing the number of required independent subsets by two.

Problem G. Paraboloids

After simplifying the equation, you can see that the problem has 0, 1, or an infinite number of solutions.

Suppose that $$$a \ne b$$$ (otherwise we can consider several special cases).

$$$a \cdot (x − x_0)^2+ a \cdot (y − y_0)^2 + z_0 = b \cdot (x - x_1)^2 + b \cdot (y - y_1)^2 + z_1$$$

$$$a \cdot (x^2 - 2 \cdot x \cdot x_0 + x_0^2 + y^2 - 2 \cdot y \cdot y_0 + y_0^2) + z_0 = b \cdot (x^2 - 2 \cdot x \cdot x_1 + x_1^2 + y^2 - 2 \cdot y \cdot y_1 + y_1^2) + z_1$$$

It can be seen that this can be reduced to a quadratic equation (by rearranging the terms and counting the coefficients at $$$x^2, x, 1$$$.

Further calculations are omitted as part of the problem for self-study.

Problem H. Palindrome

It is easy to see that in an even length palindrome each letter of the Latin alphabet occurs an even number of times, and in an odd length palindrome exactly one letter of the Latin alphabet occurs an odd number of times.

Let's count the number of times that each letter of the Latin alphabet occurs in the string. Given the fact described above, you can leave at most one letter that will occur an odd number of times.

Suppose $$$k$$$ is the number of letters that occur an odd number of times. Then, if $$$k = 0$$$ — a palindrome can be built from the string by permuting the letters, and the answer in this case is 0. If $$$k \gt 0$$$, then we can leave only one of these letters in the final palindrome, so the answer is $$$k - 1$$$.

Problem I. On Mercury

Let's denote $$$p_i$$$ — the sum of $$$n$$$ maximum numbers that can be taken from the first $$$i$$$ elements of the array, $$$s_i$$$ — the sum of $$$n$$$ minimum numbers that can be taken from numbers with positions from $$$i$$$ to $$$3n $$$.Then we can find such an $$$i$$$ for which the value of $$$p_i - s_{i + 1}$$$ is the maximum, which will be the solution to the problem. It is worth noting that $$$i$$$ must be such that there would be at least one option to take $$$n$$$ elements from the left and right.

Let's calculate the values of $$$p_i$$$ for all $$$i$$$, $$$s_i$$$ are calculated in a similar way. We will store a set of the maximum n numbers that we have taken so far. If $$$i \lt n$$$, the set size will be less than $$$n$$$. When adding a new element to the set, if its size becomes greater than $$$n$$$, we remove the minimum from it. Thus, for each $$$i$$$, the values of the $$$n$$$ maximal elements are known, and the sum of these numbers must be stored simultaneously with the set.

Problem J. Subset

Denote $$$f(x)$$$ — a function that checks whether for the current set of pairs $$$(a_i, b_i)$$$ it is possible to select $$$k$$$ pairs in such a way that the value of the fraction is not less than $$$x$$$.

Suppose $$$k$$$ pairs $$$a_i, b_i$$$ have been chosen. For the function $$$f(x)$$$, we need to check that $$$\frac{a_1 + a_2 + ... + a_k}{b_1 + b_2 + ... +b_k} \ge x$$$. Divide both parts by $$$x$$$, we get $$$a_1 + a_2 + ... + a_k \ge x(b_1 + b_2 + ... +b_k)$$$. We get $$$a_1 - x \cdot b_1 + a_2 - x \cdot b_2 + ... + a_k - x \cdot b_k \ge 0$$$.

Using the arguments above, we obtain the following solution for the implementation of the function $$$f(x)$$$. Each pair of initial numbers $$$a_i, b_i$$$ can be converted into a single number $$$c_i = a_i - x \cdot b_i$$$. Next, we need to check that it is possible to take $$$k$$$ values of $$$c_i$$$ such that they give a non-negative sum. To do this, we need to take $$$k$$$ maximum values of $$$c_i$$$.

It is easy to show that the function $$$f(x)$$$ is monotonic, and if a solution can be constructed for $$$f(x)$$$, then it can also be constructed for any $$$y \lt x$$$. Therefore, we can use binary search to determine the value of the maximum $$$x$$$ for which a solution can be built.

Problem K. Beautiful pairs of numbers

Let's denote $$$f(x)$$$ — the mask of digits that are used in the number $$$x$$$. Assume that the digit $$$y$$$ occurs in the number $$$x$$$. Then the mask will contain one in the $$$y$$$-th bit. For example, for the number $$$1029$$$ the value $$$f(1029)$$$ = $$$2^0 + 2^1 + 2^2 + 2^9$$$, the value of the function $$$f(10000002222229)$$$ is also $$$2^0 + 2^1 + 2 ^2 + 2^9$$$ since both numbers consist of the same set of digits. Thus, the value of the function $$$f$$$ will be in the segment [1, 1023].

It is easy to show that a pair of numbers $$$(x, y)$$$ is beautiful if $$$f(x) = f(y)$$$.

Let's calculate the value of $$$f(a_i)$$$ for each number from the input and calculate the number of times that each mask will occur from $$$1$$$ to $$$1023$$$. Let $$$m_i$$$ be the number of times the $$$i$$$ mask has been encountered. Then the answer to the problem is $$$ \sum_{i = 1}^{1023} \frac{m_i \cdot (m_i - 1)}{2}$$$.

Problem L. Median

To solve this problem, you need to use a dynamic segment tree (you can read it here or here). In the simple version of the segment tree, the tree structure can be precalculated in advance, in the dynamic segment tree, nodes are added if necessary.

For each request for adding numbers on the segment $$$l_i, r_i$$$, you need to perform an addition operation on the segment. Also, in each node of the dynamic segment tree, you need to store the sum on the segment. This will allow us to find the median element after the addition operation on the interval (search for the $$$k$$$-th order statistics).

Problem M. Segment Sum

This exam task is designed for lovers of data structures.

This problem can be solved using segment trees with lazy propagation. You can read about tasks and methods here, here, or here. In each node of the data structure, you need to store the sum of even and odd numbers, as well as the number that is added to all numbers on the segment to which this node is assigned.

It was also possible to use a Cartesian tree to solve the problem. You can read about it here or here.

Problem A. Beautiful numbers

Every positive integer $$$N \gt 1$$$ can be represented in exactly one way as a product of prime powers:

$$$N = p_1^{n_1}p_2^{n_2}...p_k^{n_k} = \prod\limits_{i=1}^k p_i^{n_i}$$$

This representation is called the canonical representation of $$$N$$$, or the standard form of $$$N$$$.

It is known that the number of different divisors for the number $$$N$$$ is equal to $$$(n_1 + 1)(n_2 + 1)...(n_k + 1)$$$.

The only way to get exactly three divisors is $$$k = 1$$$ and $$$n_1 = 2$$$. This means that only numbers that are squares of primes are eligible. Indeed, for any prime number $$$p$$$ there are exactly three different divisors of the number $$$p^2$$$ — this is $$$1, p, p^2$$$.

Thus, we need to consider all prime numbers up to $$$\sqrt{R}$$$ and check that the square of this prime number is in the segment $$$[L, R]$$$.

To find all prime numbers from $$$2$$$ to any $$$X$$$, you can use the sieve of Eratosthenes.

Problem B. Little kitty

Let $$$f_i$$$ be the minimum number of jumps you need to make to get to the $$$i$$$-th bump. Let's also denote $$$p_i$$$ — the nearest bump on the left for the bump numbered $$$i$$$, which has the same color. If there are no bumps with the same color, we will assume that $$$p_i = -1$$$.

It is obvious that $$$f_1 = 0$$$.

$$$f_i = min(f_{i - 1}, f_{p_i}) + 1$$$, for $$$p_i \ne -1$$$.

If $$$p_i = -1$$$, then $$$i$$$-th bump can be reached only from $$$(i - 1)$$$-th, so in this case $$$f_i = f_{i - 1} + 1$$$.

Problem C. Paper

In this problem, you need to find the rectangle of the maximum size that is formed after all the cuts.

Consider all horizontal cuts in ascending order $$$h_0 \lt h_1 \lt h_2 \lt ... \lt h_m \lt h_{m + 1}$$$, where $$$h_0 = 0, h_{m + 1} = B$$$. Similarly, consider all vertical cuts in ascending order $$$v_0 \lt v_1 \lt v_2 \lt ... \lt v_k \lt v_{k + 1}$$$, where $$$v_0 = 0, v_{k + 1} = A$$$. Denote $$$H$$$ — the maximum difference between all adjacent pairs of horizontal cuts $$$(h_i, h_{i + 1})$$$, $$$V$$$ — the maximum difference between all adjacent pairs of vertical cuts $$$(v_i, v_{i + 1})$$$, then the answer to the problem is equal to $$$HV$$$.

Problem D. Word game

In this task, it was necessary to download all the input tests and the dictionary. For each input test, you need to iterate over all the words from the dictionary and check if the word matches. To do this, iterate over the number of the letter in the word and check if such a letter can be in this position.

Answers to input tests: $$$17, 14, 39, 0, 345, 0, 15, 729, 187, 198, 145$$$.

Problem E. Square root

Integer root in the specified restrictions can take values from $$$1$$$ to $$$10^7$$$.

Let's go through all the values of the integer root. Suppose $$$x$$$ is the value of an integer root. It is easy to see that the numbers in the segment $$$[x^2, (x + 1)^2 - 1]$$$ will have an integer root $$$x$$$. We intersect the resulting segment with the input $$$[L, R]$$$ and add to the answer the size of the intersection multiplied by the value of the integer root.

Problem F. Magic Prime Square

It can be seen that if for each number from $$$1$$$ to $$$p^2$$$ we take the remainder modulo $$$p$$$, then each remainder from $$$0$$$ to $$$p - 1$$$ occurs exactly $$$p$$$ times.

Since there is a remainder $$$0$$$, the only case when all products in rows and columns will match — in each row and in each column there must be a number that is a multiple of $$$p$$$, and then all products will be equal to $$$0$$$.

There are $$$p!$$$ ways to arrange $$$p$$$ numbers with remainder modulo $$$p$$$ equal to $$$0$$$, one in each column and one in each row. There are also $$$p$$$ such numbers (with remainder $$$0$$$ modulo $$$p$$$) and they can be arranged in $$$p!$$$ different ways.

The rest of the numbers can be arranged in any way. There are exactly $$$p^2 - p$$$ of the remaining numbers, and they can be placed in $$$(p^2 - p)!$$$ ways in the remaining places.

In total there are $$$p!p!(p^2-p)!$$$ ways to arrange all the numbers from $$$1$$$ to $$$p^2$$$.

Problem G. Two bags

Consider some natural number $$$n$$$. Let's denote $$$f(n)$$$ — the mask of digits that occur in the number $$$n$$$. If the digit $$$i$$$ occurs in the number $$$n$$$, then the $$$i$$$-th bit of $$$f(n)$$$ will be $$$1$$$, otherwise it will be $$$0$$$. For example, $$$f(111) = 2, f(10) = 3, f(91414) = 530$$$.

Let's calculate for all values ​​of the array $$$a_1, a_2, ..., a_n$$$ the value of the function $$$f(a_i)$$$ and for the array $$$b_1, b_2, ..., b_m$$$ the value of the function $$$f(b_j)$$$.

Also, for each mask from $$$0$$$ to $$$1023$$$ (the maximum value of the mask that can be reached), we calculate how many numbers are in the arrays $$$a_1, a_2, ..., a_n$$$ and $$$b_1, b_2, ..., b_m$$$, respectively. Denote $$$c1(x)$$$ — the number of elemenths in the array $$$a_1, a_2, ... a_n$$$, for which $$$f(a_i) = x$$$, $$$c2(x)$$$ — the number of elemenths in the array $$$b_1, b_2, ..., b_m$$$ for which $$$f(b_j) = x$$$.

The answer to the problem is $$$\sum\limits_{i=0}^{1023} \sum\limits_{j=0}^{1023} c_1(i) c_2(j)$$$ for which $$$i$$$ & $$$j \gt 0$$$, i.e. the masks have although would have one common $$$1$$$ in binary notation. This means that the numbers under consideration have at least one common digit.

Problem H. Teams

Sort the numbers in non-increasing order $$$a_1 \ge a_2 \ge ... \ge a_n$$$.

Let's go through the numbers of two captains $$$id_1, id_2$$$. The numbers of the remaining players are divided into three segments $$$[1, id_1 - 1], [id_1 + 1, id_2 - 1], [id_2 + 1, n]$$$. All numbers in each segment with the same parity will be located in one of the two identical teams. To calculate the sum of all elements in a segment with the same index parity, you can precalculate the partial sums for the array $$$a$$$ with a step of 2. The total complexity is $$$O(n^2)$$$, since for each pair of captains the sums of the team strengths can be calculated in $$$O (1)$$$.

Problem I. Player strength

Sort the elements of the array $$$a_1, a_2, ..., a_n$$$ in ascending order.

Let's solve the problem for the case $$$k = 1$$$.

It can be seen that the maximum product will be achieved when the value of $$$a_1$$$ is increased. We will leave the proof of this fact as an independent task (a little hint — try to write down all the options for adding one to each of the factors and compare all the results).

Simply adding one to the minimum element $$$k$$$ times iteratively will take a very long time, so we will use the following approach. Since the numbers in the array $$$a_1, ..., a_n$$$ are small, we will add one to the minimum of all elements at each iteration until all numbers are equal. It can be seen that a maximum of $$$99900 (100 * 999)$$$ adding one operations will be performed in order for all elements to become equal.

Assume that there are $$$m$$$ additions left after that. Then add $$$\lfloor \frac{m}{n} \rfloor$$$ to each element, and add one to $$$m \mod n$$$ elements.

The product can be large, so for example C++ needs to implement long arithmetic.

Problem J. Partitions

If $$$\frac{k(k+1)}{2} \gt n$$$, then no partitions can be constructed, since the sum in the minimal partition $$$1, 2, ..., k$$$ is greater than $$$n$$$.

Consider any of the partitions. It is possible to move from the initial problem to another one by subtracting its index from each partition number. Then the problem is reformulated as follows — it is necessary to count the number of partitions of the number $$$n$$$ into $$$k$$$ non-negative integer terms in non-increasing order.

Denote $$$f(n, k)$$$ — the number of ways to represent the number $$$n$$$ as $$$k$$$ non-negative integer terms in non-increasing order.

$$$f(n, k) = f(n - k, k) + f(n, k - 1)$$$.

This formula is built as follows. Consider some partition of the number $$$n$$$ into $$$k$$$ summands. It will either have at least one term equal to 0, or all terms will be positive. If there is at least one term equal to 0, we can discard it and solve the problem for one term less than $$$f(n, k - 1)$$$. If all terms are positive, we can subtract $$$1$$$ from all terms and go to the subproblem in which the sum of all elements is equal to $$$n - k$$$, such partitions $$$f(n - k, k)$$$.

Problem A. Triangles

It can be seen that the points from the input set lie on two parallel lines $$$y = 0$$$ and $$$y = 1$$$ respectively.

In order to form a non-degenerate triangle, the selected points must not be located on the same straight line.

There are two ways to select three points for a triangle — two points on the line $$$y=0$$$ and one point on the line $$$y=1$$$ and vice versa, one point on the line $$$y = 0$$$ and two points on the line $$$y = 1$$$ .

Consider the first option, two points on the first line can be chosen in $$$C^2_{n+1} = \frac{n(n + 1)}{2}$$$ ways, so we can construct $$$\frac{n(n+1) (m+1)}{2}$$$ triangles for this option. Similarly, for the second option, $$$\frac{m(m+1)(n+1)}{2}$$$ ways are obtained.

Therefore, the answer to the problem is $$$\frac{(n+1)(m+1)(n+m)}{2}$$$.

Problem B. Pairs

You can see that pairs must be built according to the following principle. You need to sort all the numbers in the array in non-decreasing order and build the pairs $$$(a_1, a_n)$$$, $$$(a_2, a_{n-1})$$$, $$$...$$$, $$$(a_{\frac{n}{2}}, a_{\frac {n}{2} + 1})$$$. If the sum in each pair is the same, then the necessary partition has been constructed, otherwise it does not exist.

We leave the proof of the fact that pairs must be built in this way as an additional task. A little hint — you need to try to pair $$$a_1$$$ b and not $$$a_n$$$ and see what you can get after that.

Problem C. Simple graph

The maximum number of edges that can be left for a graph of $$$n$$$ vertices is $$$n - 1$$$ edges. In this case, a tree of $$$n$$$ vertices is formed, and no more edges can be added without forming a cycle.

Using this fact, we solve our problem separately for each connected component in the graph. Namely, for a connected component of size $$$x$$$ it is necessary to leave an edge $$$x-1$$$.

Splitting into connectivity components and tree selection for each component can be done in various ways, for example, DFS, BFS or DSU.

Problem D. Beautiful string

If some letter occurs more than half of the times, then the optimal string is constructed as follows. It is necessary to write down all occurrences of the most frequent letter and between pairs of adjacent letters, at the beginning and at the end of this line, insert the remaining letters in any order.

If there is no letter that occurs more than half of the times, then the final line can be built in the following way. Each time we will add a letter that occurs most often and does not coincide with the last one already written. Note that in this case it is always possible to construct a string $$$s$$$ with beauty equal to $$$|s| - 1$$$.

We leave the proof of the correctness of the proposed solution as an additional task. A little hint — show that knowing how many times each letter must occur with such a solution, you can never come to the state that some letter will occur more than half of the times.

Problem E. Words

Correct answers to the questions from the problem statement:

1. 203

2. 65905

3. 232

4. You need to output the strings "blepharoconjunctivitis", "formaldehydesulphoxylic", "pneumoventriculography", "pseudolamellibranchiata", "pseudolamellibranchiate", "superacknowledgment".

5. e

6. ing

There are many ways to solve the problem, one of them is using the Pandas library in Python. Using this library, you can read the input data and calculate the answers to questions from the condition. It was also possible to read data in C++, Python or any other programming language and parse it in any way.

Problem F. Dice

Suppose that a number from 1 to 6 is rolled exactly $$$c_1, c_2, c_3, c_4, c_5, c_6$$$ times respectively. Let us enumerate all possible sixes of numbers $$$c_1, ..., c_6$$$, which can be obtained with some probability after $$$n$$$ throws and they fit the condition $$$c_1 \ge c_2 \ge c_3 \ge c_4 \ge c_5 \ge c_6$$$. To do this, you can iterate over $$$c_6$$$ — the number of times the number 6 will fall out, then $$$c_5$$$ — the number of times the number 5 will fall out (this number must be at least $$$c_6$$$), etc. It can be shown that there are about 34 million such partitions.

It can be shown that there are exactly $$$C_n^{c_1, c_2, c_3, c_4, c_5, c_6} = \frac{n!}{c_1!c_2!c_3!c_4!c_5!c_6!}$$$ different ways to roll a die $$$n$$$ times and get $$$c_1, ..., c_6$$$. The probability of each of these events is equal to $$$\frac{1}{6^n}$$$. Therefore, for each such partition into $$$c_1, ..., c_6$$$, it is necessary to add to the answer the product of the number of ways to obtain such a partition and the probability of such an event.

Problem G. Palindromes

If more than two distinct letters occur an odd number of times, then no palindrome can be constructed.

If exactly one letter occurs an odd number of times, then the length of the string is odd and, accordingly, at the position $$$\frac{|s| + 1}{2}$$$ (1-indexing) this letter must occur in the string. For example, for the string "cbacabc" you can see that if the letter 'c' is not located in the center, then for one of the occurrences of the letter 'c' there will be no pair and, accordingly, no palindrome can be built. In this case, we will put a character that occurs an odd number of times in the middle of the string and we will solve the problem when each letter occurs an even number of times.

Each letter that occurs in a string will occur the same number of times in the left and right halves of the strings. Therefore, we divide the number of occurrences of each character and analyze what happens for each of the half strings. It can be seen that for any arrangement of letters in the left half of the string, the right half is always restored and restored uniquely. Thus, the letters in the left half of the word can be arranged in any way, and for each arrangement there is exactly one palindrome that can be obtained in the end.

Let's denote, $$$c_1, c_2, ... c_m$$$ — the number of times that some letters of the alphabet occur in the left half of the string. Then it can be shown that the total number of palindromes is equal to $$$\frac{l!}{c_1!c_2!...c_m!}$$$, where $$$l = c_1 + c_2 + ... + c_m$$$.

Problem H. XOR OR AND

Let's solve the problem separately for $$$XOR$$$ and $$$OR + AND$$$.

It is known that $$$XOR(0 .. 4k + 3) = 0$$$ for any non-negative integer $$$k$$$. This can be easily shown by dividing all pairs into quadruples $$$(0, 1, 2, 3)$$$, $$$(4, 5, 6, 7)$$$, ... and showing that $$$XOR$$$ is 0 in each of them. Thus it turns out that $$$XOR(0 .. 4k) = 4k$$$, $$$XOR(0 .. 4k + 1) = 1$$$, $$$XOR(0 .. 4k + 2)$$$ = $$$4k + 3$$$, $$$XOR( 0 .. 4k + 3) = 0$$$.

It is also known that $$$XOR(L .. R)$$$ = $$$XOR(0 .. R)$$$ ^ $$$XOR(0, L - 1)$$$. Therefore, $$$XOR$$$ on a segment can be calculated with just a few operations.

In order for $$$OR(L..R)$$$ $$$i$$$-th bit in the binary notation of the result to be equal to one, it is necessary that on the segment $$$L..R$$$ at least one number in the $$$i$$$-th bit contains unit. In order for $$$AND(L..R)$$$ the $$$i$$$-th bit in the binary notation of the result to be equal to one, it is necessary that the segment $$$L..R$$$ in all numbers in $$$i$$$-th bit one is located.

Let's iterate over the bits of $$$L$$$ and $$$R$$$ in descending order until we find the difference (namely, the number $$$L$$$ in the $$$i$$$-th bit will contain 0, and the number $$$R$$$ will contain 1). It is easy to show that for $$$OR$$$ all bits starting from the current one can be equal to 1 at least once, and for $$$AND$$$ it can be shown that at least once each of the bits will be equal to 0. Therefore, the solution is to find the maximum bit that differs in the numbers $$$L$$$ and $$$R$$$ and restore the answer.

Problem I. K-th Divisor

In this problem, you need to recursively build all divisors for each number and choose the $$$k$$$-th one in ascending order (for example, std::nth_element in C++).

To recursively construct all divisors, it was necessary to use the following idea. Initially, you need to decompose the number into prime divisors, for this you can precalculate all prime numbers up to $$$\sqrt{10^9}$$$ and take only them as prime divisors, this will allow you to find a partition into prime divisors faster than $$$O(\sqrt{n})$$$.

After that, using recursion, you can build all the divisors of the number, sorting out for each prime whether it is included in the divisor or not.

You can find more information about the number of divisors and finding them in this post. For example, in the constraints $$$n \le 10^9$$$, the number of divisors of a number does not exceed 1344.

Problem J. Matrix

This problem has several different solutions. One of them is as follows. Let's construct a random matrix in which the number of paths exceeds $$$K$$$. After that, we will randomly replace the characters '.' to '#' (blocking some paths) and '#' to '.' (returning some paths). The replacement position may be chosen randomly, or a position may be chosen that makes the number of current paths closer to the result. This is an iterative algorithm that does not always yield a result, so after $$$C$$$ iterations it can be restarted for a new random starting matrix.

It was also possible to build a result using pre-calculated patterns, in which a pre-known number of paths, by combining them on a matrix. For example, if the number $$$A$$$ can be represented as the product of two numbers $$$X$$$ and $$$Y$$$, you can construct the answers for $$$X$$$ and $$$Y$$$ on smaller matrices and combine the results.

If you have an interesting idea for solving this problem, you can write it in the comments.

Problem K. Two points

There are three different independent subproblems that you need to be able to solve — when the points are located on the same line of the rectangle, on adjacent sides and on opposite sides.

It can be shown that the expected distance for points on one side of the rectangle is $$$\frac{x}{3}$$$, where $$$x$$$ is the length of the side. We leave the proof of this fact as an independent task.

We fix a rectangle on the plane and assume that the corners of the rectangle are located at the coordinates $$$(0, 0), (0, a), (b, 0), (b, a)$$$.

Let's calculate the result for the case when the points are located on neighboring sides. Suppose that these points are located on the sides $$$(0, 0) - (0, a)$$$ and $$$(0, 0) - (b, 0)$$$, respectively. It can be shown that the expectation of the distance between points is calculated as follows:

$$$d = \frac{1}{ab} \int^a_0 (\int^b_0 \sqrt{x^2+y^2}dy)dx$$$

$$$\int \sqrt{x^2+y^2}dy = \frac{1}{2}(y \sqrt{x^2+y^2} + x^2 log (\sqrt{x^2+y^2} + y)) + const$$$

After we got rid of one integral, you can either solve the second integral (we leave it as an additional task, you can write your solution for verification in the comments) or, for example, calculate the result using Simpson's formula.

For the case when the points are located on opposite sides, the solution is similar (double integral with a similar approach to the solution).

Problem A. Bipartite graph

One of the definitions of a bipartite graph is as follows. A graph is bipartite if its vertices can be divided into two sets so that there are no edges inside each of the sets. For example, for a graph of 4 vertices and edges 1 — 2, 2 — 3, 3 — 4, 4 — 1, vertices 1 and 3 fall into one set, vertices 2 and 4 into the second set, and each of the edges connects vertices from different sets .

Suppose that one set of the bipartite graph contains $$$x$$$ vertices, then the second set contains $$$n - x$$$ vertices, where $$$n$$$ is the number of vertices in the graph. The maximum number of edges that such a graph can have is $$$x (n - x)$$$, this number can be obtained by linking all pairs of vertices from different sets.

The optimal value of $$$x$$$ could be chosen by enumeration of all options (since $$$1 \le n \le 300$$$), but we can notice the following fact that the value of $$$x$$$, for which the number of edges is maximum — $$$\lfloor \frac{n}{2} \rfloor$$$. You can prove this yourself as an exercise, link for help.

As an additional task, you can try to solve the following problem: given an undirected graph of $$$n$$$ $$$(1 \le n \le 10^4)$$$ vertices and $$$m$$$ edges $$$(0 \le m \le 10^5)$$$, it is guaranteed that he is bipartite. What is the maximum number of edges that can be added to it so that it remains bipartite and does not have multiple edges? Ways to solve this and the following additional tasks can be discussed in the comments.

Problem B. EPL 20/21

Correct answers to the questions from the problem statement:

1. FRA

2. 38

3. Manchester City

4. Harry Kane

5. Tottenham Hotspur

There are many ways to solve the problem, one of them is using the Pandas library in Python. Using this library, you can read the input data and calculate the answers to questions from the condition. It was also possible to read data in C++, Python or any other programming language and parse it in any way.

Problem C. Dice

Let us first calculate the probability that there were $$$n$$$ throws of the dice in total, and each throw would result in a number not greater than $$$d$$$. The probability of such an outcome is $$$(\frac{d}{6})^n$$$. If we subtract from this value the probability that for all throws a value is strictly less than $$$d$$$, we get the required probability. The probability that for all $$$n$$$ rolls a number strictly less than $$$d$$$ comes up is $$$(\frac{d - 1}{6})^n$$$.

Then the answer to the problem is $$$(\frac{d}{6})^n$$$ — $$$(\frac{d - 1}{6})^n$$$.

Another way to solve it is with dynamic programming. $$$dp[i][j]$$$ — the probability that $$$i$$$ rolls were made and the maximum rolled number is equal to $$$j$$$. Let's iterate over the value of the dice for the $$$(i + 1)$$$-th throw, let's assume it is equal to $$$d$$$. We need to update the dynamic programming state in $$$dp[i + 1][max(j, d)]$$$ by adding the value of $$$dp[i][j]$$$ divided by 6 (the probability of each number coming up is $$$\frac{1}{6}$$$).

Also in the task there was a group of tests, estimated at 1 point and with restrictions of $$$200 \le n \le 1000$$$. For such restrictions, for $$$1 \le d \lt 6$$$ one can output 0, and for $$$d = 6$$$ one can output 1. It can be shown that the responses tend to 0 and 1 under such constraints.

Problem D. Function graph

Response to the $$$i$$$-th query $$$-$$$ the value of the integral $$$\int_{L_i}^{R_i}4 - (sin(x) cos(\frac{x}{2})+cos(x) (cos(2x)+1)) dx$$$

$$$\int4 - (sin(x) cos(\frac{x}{2})+cos(x) (cos(2x)+1))dx$$$ = $$$\int4dx - \int cos(\frac{x}{2})sin(x)dx - \int(cos(2x)+1)cos(x) dx$$$

Let's use the following formulas:

$$$sin(\alpha)cos(\beta) = \frac{sin(\alpha + \beta) + sin(\alpha - \beta)}{2}$$$, $$$cos(\alpha)cos(\beta) = \frac{cos(\alpha + \beta) + cos(\alpha - \beta)}{2}$$$

Then, $$$\int4dx - \int cos(\frac{x}{2})sin(x)dx - \int(cos(2x)+1)cos(x) dx$$$ = $$$\int4dx - \int \frac{1}{2} sin(\frac{3x}{2})dx - \int \frac{1}{2} sin(\frac{x}{2})dx - \int \frac{3}{2} cos(x)dx - \int \frac{cos(3x)}{2} dx$$$ = $$$4x + \frac{cos(\frac{3x}{2})}{3} + cos(\frac{x}{2}) - \frac{3}{2}sin(x) - \frac{sin(3x)}{6} + constant$$$.

Denote $$$f(a)$$$ = $$$\int_{0}^{a}4 - (sin(x) cos(\frac{x}{2})+cos(x) (cos(2x)+1))dx = 4a - \frac{3sin(a)}{2} - \frac{sin(3a)}{6} + cos(\frac{a}{2}) + \frac{cos(\frac{3a}{2})}{3}$$$

Then the answer to the $$$i$$$-th query is $$$f(r_i) - f(l_i)$$$.

Problem E. Determinant

Since it is known that the missing number is in the segment $$$[-20, 20]$$$ and is an integer, we can go through all the options for the missing number and calculate the determinant of the matrix for each option. The matrix determinant can be calculated, for example, using Gaussian method.

Another solution to the problem is as follows. Following the Leibniz formula, you can go through all possible permutations and divide all terms, one can enumerate all possible permutations and divide all the terms, one of the factors of which is the missing number (let's denote the sum of these terms as $$$a$$$) and into terms that are counted without taking into account the missing number (let's denote this term as $$$b$$$). Denote the missing number $$$x$$$, then $$$ax + b = 0$$$, hence $$$x = -\frac{b}{a}$$$.

Problem F. abacaba

It can be seen that the first time the $$$i$$$-th letter of the Latin alphabet occurs at position $$$2^{i - 1}$$$ and will continue to occur with a step of $$$2^i$$$. For example, the letter 'b' will first occur at $$$2^1 = 2$$$ positions and will occur at positions 2, 6, 10, 14, ...

Thus, to answer the $$$i$$$-th query, you need to find the first and last occurrence of a character and, knowing the step for the character, calculate the total number of occurrences. The first and last occurrences can be done with simple arithmetic, we'll leave that as an exercise.

Problem G. Maximum flow

The main fact in the problem is that the given graph is a tree. As you know, in a graph that is a tree, there is exactly one path between any pair of vertices.

Then it is easy to see that the answer to the $$$i$$$-th query in the problem is the value of the minimum throughput on all edges of the path between the vertices $$$u_i, v_i$$$.

The minimum value on the path can be found using the DFS or BFS algorithms. Such a solution will have $$$O(n)$$$ asymptotics for each of the queries, the total asymptotics is $$$O(nq)$$$. This decision allows you to score 5 points in the specified restrictions.

For finding the minimum value in a path, there are several faster solutions, such as using Lowest common ancestor. This idea allows us to find the minimum throughput on the path in $$$O(\text{log n})$$$ or $$$O(1)$$$ operations (depending on the implementation). The following links may be useful for a $$$O(\text{log n})$$$ solution: link, link, link, link and link.

Problem H. Partitions

Let's denote $$$f_i$$$ — the number of ways the number $$$i$$$ as a sum of powers of 2, $$$f_0 = 1$$$. Let's consider two cases — when $$$i$$$ is odd and when $$$i$$$ is even.

For the case of odd $$$i$$$, one can notice that in all partitions of this number one of the terms will be equal to 1, so the number of partitions of the number $$$i$$$ in this case is equal to the number of partitions of the number $$$i - 1$$$. Thus $$$f_i = f_{i - 1}$$$ for odd $$$i$$$.

For the even case $$$i$$$, one can notice that all partitions can be divided into two parts — partitions in which all terms are even and partitions in which at least one term is equal to 1. Thus $$$f_i = f_{i - 1} + f_ {\frac{i}{2}}$$$.

The asymptotic behavior of the described solution is $$$O(n)$$$.

Problem I. Triplets of numbers

Denote $$$G(n)$$$ — the mask of digits that occur in the number $$$n$$$. The $$$i$$$-th bit of the mask is equal to one if the number $$$n$$$ contains the digit $$$i$$$ at least once. The value of the function $$$G(n)$$$ for natural numbers does not exceed $$$2^{10} - 1$$$.

Denote $$$F(n, mask)$$$ — the number of natural numbers from 1 to $$$n$$$ for which $$$G(n) = mask$$$. The value of $$$F(n, mask)$$$ can be calculated using digit dynamic programming as follows. Let $$$f_{l, mask, c}$$$ be the number of natural numbers of length equal to $$$l$$$ for which the value of the function $$$G(x)$$$ is equal to $$$mask$$$. $$$c$$$ takes values from 0 to 2 and denotes whether the number formed from the first $$$len$$$ digits of $$$n$$$ is greater than, equal to, or less than the numbers in question, respectively. For example, if $$$n = 12345$$$, then for the numbers $$$11$$$, $$$1099$$$ the value of $$$c$$$ is 0, for the numbers $$$1, 12, 123$$$ the value of $$$c$$$ is 1, and for the numbers $$$5, 55, 9, 124$$$ the value of $$$c$$$ is 2. The transitions in the described DP are as follows. It is necessary to iterate over the digit that will be set to $$$l + 1$$$, set $$$mask$$$ to one if the corresponding digit has not been encountered and update the value of $$$c$$$ (you can see $$$c$$$ can only change if it was equal to one). In other words, for some digit $$$d$$$ it is necessary to update the state of $$$f_{l + 1, mask', c'}$$$.

You can read about digit dynamic programming and examples of classical tasks, for example, at this or this links.

Once $$$F(n, mask)$$$ is known for all possible $$$mask$$$ values, the inclusion-exclusion principle can be applied to count the number of matching triples. The answer is constructed as follows. Let's count the number of ways to take exactly three numbers for which the digit 0 occurs at least once, the digit 1 occurs at least once, and so on. You may notice that numbers were added to the sum several times in which the digits 0 and 1 occur at the same time, so you need to subtract this amount, etc. To do this, it is necessary to iterate over all possible values ​​of $$$mask$$$, and if the number of units in the binary notation is odd, the summand must be included in the total sum with a plus sign, otherwise with a minus sign.

It is also worth mentioning that the number of correct triples of numbers in which a certain set of digits occurs can be calculated as follows. Let's denote $$$k$$$ — the number of numbers with a fixed set of identical digits. Then we can choose three numbers from the set in exactly $$$\frac{k(k-1)(k-2)}{6} = C_k^3$$$ ways.

Problem J. K-th path

You can see that each path will be $$$2n - 1$$$ long and each path can be represented as a $$$(2n - 1)$$$-digit number.

Denote $$$F(x)$$$ — the number of paths from the cell $$$(1, 1)$$$ to the cell $$$(n, n)$$$, the value of the number on which does not exceed $$$x$$$. It is easy to see that $$$F(x) \le F(x + 1)$$$. The value of the function $$$F(x)$$$ can be calculated using dynamic programming as follows.

Denote $$$f_{i,j,t}$$$ — how many ways there are to get from cell $$$(1, 1)$$$ to cell $$$(i, j)$$$, constructing a number of length $$$i + j - 1$$$ and which is less (if $$$t = 0$$$) or equal (if $$$t = 1$$$) to the number formed from the first $$$i + j - 1$$$ digits of $$$x$$$. There are two different transitions — to the cell $$$(i + 1, j)$$$ and to the cell $$$(i, j + 1)$$$. Since the number of ways can be huge, it is necessary to replace large values with some number, obviously greater than $$$k$$$ from the condition, so as not to catch the overflow.

Then, using binary search, we can find the answer, that is, the minimum number $$$x$$$ such that $$$F(x) \ge k$$$.

A similar problem for reflection — how to solve a similar problem, only if each cell of the matrix would be a letter of the Latin alphabet and it was necessary to find the $$$k$$$-th lexicographically string in ascending order?

Problem K. Tic-tac-toe game

The problem also has many different solutions.

One of the solutions involves generating a random matrix, in which there will be a specified number of crosses and a specified number of zeros, and using random symbol exchanges in the matrix, recalculate the number of correct submatrices, trying to improve the arrangement (approaching the correct answer). You can do several of these iterations to get the best solution. The local search method was described above, you can read about it https://en.wikipedia.org/wiki/Local_search_(optimization). Also, the problem could be solved with the help of a genetic algorithm, link or link for self-study.

Any questions about the tasks can be asked in the comments.

There is a trial competition that will allow you to get acquainted with the types of problems that can be encountered on the entrance exam. It's a good idea to try submitting each of the tasks and review the grading options. To participate in the competition, you need to go to the Contests tab, register for the competition, and after that you will be able to submit solutions in the competition.

We remind you that the first entrance exam will take place on June 11. We would like to ask you to fill out your personal information in your Codeforces profile for quick identification.

Please visit website to learn more about EPIC Institute of Technology and programs. If you have any questions, you can quickly ask them in our chat

Hello, Codeforces!

We are excited to announce the grand opening of EPIC Institute of Technology! EPIC Institute of Technology, a part of EPIC — EPAM Product Innovation Center, is truly a unique educational organization driven by the Deltix team under the EPAM Systems umbrella.

EPIC Institute of Technology is online and entirely free institute. We offer three programs: Complex Logic, Real-Time Backend, and Time-Series Analysis. The training will last one year and consist of two semesters. Groups for each program will be formed based on the results of the entrance exam, which will be held in the end of May/beginning of June 2022. The exact dates will be provided in the near future.

Successful graduates, and even current students, will have access to the power and resources of EPAM and an incredible chance to jumpstart their career by just using their talent and skill. We will offer our students a unique and straightforward path to the most challenging and exciting projects on a global scale, and an opportunity to learn from and work with industry-leading professionals.

Most recently, we told you that we can offer paid part-time jobs for those who are interested. To our and your happiness, the offer is still valid! Fill out the following form for teaching and we will contact you.

Please visit our website to learn more about EPIC Institute of Technology and our programs. Also, basic information about the institute will be published in our Telegram channel.

UPD: We are pleased to announce that the first entrance exam will be held at Codeforces on June 11th. The detailed information about the competition and access to it will be shared a few days before the exam.

We remind you to register on our website to take the exam. There you can also find some tasks to practice.

UPD: You can now join our group on Codeforces to stay in tune with all our activities, contests, and exams.

We would like to ask you to fill out your personal information in your Codeforces profile for quick identification. Register in the group. Confirmation of your registration is not automatic and may take some time. Please be aware, that all entrance exams will also be held in this group and you must be registered to take part.

In Contests tab, you can find a trial competition for you to get familiar with the testing system and the types of problems that may be a part of the entrance exam. Please register for the contest to be able to submit your solutions.

If you have any questions, you can quickly ask them in our chat.