Hello, Codeforces!

SomethingNew and I are glad to invite you to CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!), which will take place on Sep/18/2023 17:35 (Moscow time). You will have 2 hours 15 minutes to solve 8 problems. The round will be rated for everyone.

We would like to thank:

• 74TrAkToR for coordinating this round.
• isaf27, ugly2333, JianfengZhu, Little09, bashkort, Kieray, fishy15, Vladithur, Dart-Xeyter, pakhomovee, makrav, meowcneil, 127.0.0.1, Nanani, nnv-nick, SomethingDifferent, vl342, shiv_codegen, M1lkas, allmath, sdyakonov for testing the round and providing useful feedback.
• MikeMirzayanov for Codeforces and Polygon systems.

Score distribution:

500 — 750 — 1500 — 1750 — 2750 — 3250 — 3250 — 4000

We hope that our problems will be interesting for you!

Editorial

Congratulations to the winners!

1. orzdevinwang
2. cnnfls_csy
3. jiangly
4. PubabaOnO
5. maspy
6. tourist
7. AoLiGei
8. Um_nik
9. noimi
10. Geothermal

And here is the information from our title sponsor:

Hello, Codeforces!

We, the TON Foundation team, are pleased to support CodeTON Round 6.

The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.

Since July 2022, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.

The winners of CodeTON Round 6 will receive valuable prizes.

The first 1,023 participants will receive prizes in TON cryptocurrency:

• 1st place: 1,024 TON
• 2–3 places: 512 TON each
• 4–7 places: 256 TON each
• 8–15 places: 128 TON each
• …
• 512–1,023 places: 2 TON each

We wish you good luck at CodeTON Round 6 and hope you enjoy the contest!

Hello, Codeforces!

SomethingNew and I are glad to invite you to Codeforces Round 814 (Div. 1) and Codeforces Round 814 (Div. 2), which will take place on Aug/16/2022 17:35 (Moscow time). Each division will have 6 problems and 2 hours to solve them.

We would like to thank:

• 74TrAkToR for excellent coordination and for the idea of a problem for Div. 2.
• pakhomovee for idea and preparation of one of the problems for Div. 1, and for testing other problems of the contest.
• Um_nik, 244mhq, turmax, fedoseev.timofey, errorgorn, FairyWinx, daubi, arbuzick, AlesyaIvanova, Dart-Xeyter, Alexdat2000, Vladithur, rafaelka, plagues, LeoRiether, satyam343, ilya.kligunov, 1024mb, 127.0.0.1, efimovpaul, Prokhor08, marzipan, kirill.kligunov, MirMak, dmitry.lisitsyn, MichsSS, PUFL, bpaT_Kapaca, RomkaRS for testing the round and providing useful feedback.
• MikeMirzayanov for Codeforces and Polygon systems.
• ilaburkov for existing.

Score distribution:

Div. 2: 500 — 1000 — 1250 — (1250 — 1000) — 2500 — 2500

Div. 1: (500 — 500) — 1250 — 1250 — 2250 — 2250 — 2750

We hope that you will enjoy solving our problems!

Editorial

Congratulations to the winners!

Div. 2:

1. billieeyelash
2. randboy
3. TasselFlower
4. AVRush
5. Shiroqwq_

Div. 1:

1. tourist
2. maroonrk
3. Petr
4. ksun48
5. Radewoosh

Problem

We will count the number of bad permutations, at the end we subtract it from $$$n!$$$ (modular $$$n!$$$ is simple — if $$$n < m$$$, then we count head-on, otherwise we take it equal to $$$0$$$). We will add numbers to the permutation in order ($$$1, 2, ..., n$$$). If we add the number $$$i$$$, then we have $$$i$$$ insertion options, since there are $$$i - 1$$$ numbers in the permutation now. A pair of neighboring elements is called good if it meets the requirement from the statement ($$$x$$$ and $$$x + 1$$$). Now let $$$k$$$ be the number of good pairs in the permutation. If we insert $$$i$$$ between the indices of a good pair, then their number will decrease by $$$1$$$, if we insert it after the number $$$i - 1$$$, then it will increase by $$$1$$$, otherwise it will not change. This means that to increase the number of good pairs by $$$1$$$ we have a $$$1$$$ insertion option, to decrease by $$$1$$$ there are $$$k$$$ options, if we do not change anything there are $$$n - k - 1$$$ options. After $$$n$$$ insertions, we want to get the number of good pairs equal to $$$0$$$, so the increases and decreases are split into pairs. We want to find the number of all correct variants of insertions, if we do not have any increases this number is $$$(n - 1)!$$$ (from number of not changing options). Consider the first increase, let it be for the number $$$x$$$. Before it, there were $$$0$$$ pairs, so the number of permutations is equal to $$$(k - 2)!$$$ (according to the number of insertion options that do not change anything). We have a $$$1$$$ option for this insert. Note that for the next insertion (if it does not change) we will have $$$k - 1$$$ options, for the second after us there will be $$$k$$$ options, and so on, that is, we continued to accumulate the factorial. Consider a pairwise decrease (just this pair was removed), let it be at the moment $$$y$$$. We will only have the $$$1$$$ insert option since we are deleting a specific pair. Note that due to the presence of a pair (we assume that there is only one, for a larger number, the proof is obviously constructed in the same way, we only need to carefully take into account that there will be other deletions) before deleting it, we had $$$y - 3$$$ options on the previous insert, $$$1$$$ on the current one, and on the next there will already be $$$y$$$, that is, the factors $$$y - 2$$$ and $$$y - 1$$$ have been removed. We are looking for the sum over all variants of the remaining product after some set of deletions of pairs of consecutive numbers. Since before $$$ y $$$ there is a $$$ y - 1 $$$ number, and any of them could be paired with $$$ y $$$, then products without $$$y - 2$$$ and $$$y - 1$$$ will be counted $$$y - 1$$$ times, that is, we just removed $$$y - 2$$$. Thus, we have reduced the problem to the fact that we can remove any subset of factors from $$$(n - 1)!$$$, while we cannot remove two consecutive numbers (pairs $$$y - 2, y - 1$$$ cannot intersect in different $$$y$$$), you need to find the sum over all the products after deletions. This is easily done using DP ($$$dp_0 = dp_1 = 1$$$, $$$dp_i = dp_{i - 2} * (i - 1) + dp_{i - 1} * i $$$, the answer is $$$dp_{n - 1}$$$) in $$$O(n)$$$ and earns $$$77$$$ points. Now note that after $$$m$$$ the modulo remainders are looped. We will divide the old $$$dp$$$ into $$$dp1$$$ ($$$dp1_i$$$ — $$$i$$$ must be deleted) and $$$dp2$$$ ($$$dp2_i$$$ — $$$i$$$ can be deleted or not deleted), we will calculate the values ​​of DP from $$$0$$$ to $$$m$$$. $$$dp1_i = dp2_{i - 2} * (i - 1) $$$, $$$dp2_i = dp2_{i - 1} * i + dp1_i$$$. Note that all terms in which one of $$$m, 2m, ...$$$ is not removed are equal to $$$0$$$ and do not affect the sum. It is not hard to prove that then the answer to the problem is $$$(dp1_m)^{\frac{n}{m}} * dp2_{n\pmod{m}}$$$. Using binary exponentiation, we get a $$$O(m + log_2(\frac{n}{m}))$$$ solution, which gains $$$100$$$ points. All formulas in the solution were required to be taken modulo $$$m$$$.

PS: My proof seems to me too complicated, it seems that ShinigamiCHOP has a simpler proof.