By Vladosiya, history, 6 weeks ago,

1980A - Problem Generator

Tutorial
Solution

1980B - Choosing Cubes

Idea: senjougaharin Prepared by: senjougaharin

Tutorial
Solution

1980C - Sofia and the Lost Operations

Idea: senjougaharin Prepared by: Gornak40

Tutorial
Solution

1980D - GCD-sequence

Idea: myav Prepared by: myav

Tutorial
Solution

1980E - Permutation of Rows and Columns

Idea: senjougaharin Prepared by: senjougaharin

Tutorial
Solution

1980F1 - Field Division (easy version)

Tutorial
Solution

1980F2 - Field Division (hard version)

Tutorial
Solution

1980G - Yasya and the Mysterious Tree

Idea: Gornak40 Prepared by: Gornak40

Tutorial
Solution
• +56

By Vladosiya, history, 7 weeks ago, translation,

Hello! Codeforces Round 950 (Div. 3) will start at Jun/03/2024 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks. After open hacks all accepted solutions will be rejudged on successful hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by our team: myav, Gornak40, senjougaharin and Vladosiya.

We would like to thank:

1. MikeMirzayanov for help with ideas and Polygon and Codeforces platforms.

2. Be_dos, Dominater069, 74TrAkToR, BucketPotato for red testing.

3. KseniaShk, cry, tolbi, ScarletS, nskybytskyi, sevlll777 for yellow testing.

4. mahdi.hasnat, Phantom_Performer, mainyutin for purple testing.

5. natalina, FBI, Kopite, MADE_IN_HEAVEN, mz1 for blue testing.

6. Romakolesn for cyan testing.

Good luck!

P.S.: We are aware of the error that occurred while updating the ratings for Educational Codeforces Round 166. It will be fixed before this round. UPD: We fixed it!

UPD: Editorial is out!

• +193

By Vladosiya, history, 2 months ago,

1974A - Phone Desktop

Idea: Aksenov239

Tutorial
Solution

1974B - Symmetric Encoding

Idea: MikeMirzayanov

Tutorial
Solution

1974C - Beautiful Triple Pairs

Idea: MikeMirzayanov

Tutorial
Solution

1974D - Ingenuity-2

Idea: MaxBuzz

Tutorial
Solution

Idea: RobinFromTheHood

Tutorial
Solution

1974F - Cutting Game

Idea: MikeMirzayanov

Tutorial
Solution

1974G - Money Buys Less Happiness Now

Tutorial
Solution
• +79

By Vladosiya, history, 2 months ago, translation,

Hello! Codeforces Round 946 (Div. 3) will start at May/20/2024 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Round is based on UKIEPC 2024: Spring Practice. Please refrain from participating in this round if you are familiar with the tasks of this competition.

I would like to thank:

1. Authors of the original competition: Aksenov239, MaxBuzz, RobinFromTheHood, darnley, izban, pkhaustov, lsantire, az453, fedor.tsarev, Shoaib Jameel.

2. MikeMirzayanov for help with ideas and Polygon and Codeforces platforms.

3. -is-this-fft-, peltorator, tute7627 for red testing.

4. senjougaharin, kaikey, gmusya, nskybytskyi, Giga_Cronos, diskoteka for yellow testing.

5. TypeYippie, kzyKT, tepamid, ahshafi for purple testing.

6. Abo_Samrah, Zandler, sam07a, YESMAKHAN, xygzy, Klaus26 for blue testing.

7. Morvolzz, dasha..zhilina, sutekine, Muhsen, Gojova, Acanikolic73 for cyan testing.

8. You for participation.

Good luck!

UPD: Editorial is out.

• +194

By Vladosiya, history, 5 months ago, translation,

1932A - Thorns and Coins

Idea: denk

Tutorial
Solution

1932B - Chaya Calendar

Tutorial
Solution

1932C - LR-remainders

Idea: MikeMirzayanov

Tutorial
Solution

1932D - Card Game

Idea: goncharovmike

Tutorial
Solution

1932E - Final Countdown

Idea: step_by_step

Tutorial
Solution

1932F - Feed Cats

Idea: denk

Tutorial
Solution

1932G - Moving Platforms

Idea: denk

Tutorial
Solution
• +33

By Vladosiya, history, 5 months ago, translation,

1931A - Recovering a Small String

Idea: myav Prepared by: myav

Tutorial
Solution

1931B - Make Equal

Tutorial
Solution

1931C - Make Equal Again

Idea: senjougaharin Prepared by: senjougaharin

Tutorial
Solution

1931D - Divisible Pairs

Tutorial
Solution

1931E - Anna and the Valentine's Day Gift

Idea: Gornak40 Prepared by: Gornak40

Tutorial
Solution

1931F - Chat Screenshots

Idea: senjougaharin Prepared by: senjougaharin

Tutorial
Solution

1931G - One-Dimensional Puzzle

Idea: senjougaharin Prepared by: senjougaharin

Tutorial
Solution
• +68

By Vladosiya, history, 5 months ago, translation,

Hello! Codeforces Round 925 (Div. 3) will start at Feb/13/2024 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by our team: myav, Gornak40, senjougaharin and Vladosiya.

We would like to thank:

1. MikeMirzayanov for help with ideas and Polygon and Codeforces platforms.

2. nigus for red testing.

3. vladmart, Gheal, KseniaShk for yellow testing.

4. htetgm for purple testing.

5. natalina, SashaT9, lockdown, bma20006 for blue testing.

6. RedDreams for cyan testing.

7. the_Incharge, Aurora__, Longqiang for green testing

Good luck!

P.S. Happy Valentine's Day!

UPD: Let's continue streak of announces with photo of the authors :)

UPD2: Editorial

• +385

By Vladosiya, history, 5 months ago,

1927A - Make it White

Idea: MikeMirzayanov

Tutorial
Solution

1927B - Following the String

Idea: MikeMirzayanov

Tutorial
Solution

1927C - Choose the Different Ones!

Idea: MikeMirzayanov

Tutorial
Solution

1927D - Find the Different Ones!

Idea: MikeMirzayanov

Tutorial
Solution

1927E - Klever Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1927F - Microcycle

Idea: MikeMirzayanov

Tutorial
Solution

1927G - Paint Charges

Idea: MikeMirzayanov

Tutorial
Solution
• +160

By Vladosiya, history, 7 months ago, translation,

1907A - Rook

Idea: pashka

Tutorial
Solution

1907B - YetnotherrokenKeoard

Idea: pashka, MikeMirzayanov

Tutorial
Solution

1907C - Removal of Unattractive Pairs

Tutorial
Solution

1907D - Jumping Through Segments

Tutorial
Solution

1907E - Good Triples

Idea: pashka

Tutorial
Solution

1907F - Shift and Reverse

Idea: pashka

Tutorial
Solution

1907G - Lights

Idea: pashka

Tutorial
Solution
• +27

By Vladosiya, history, 7 months ago, translation,

Hello! Codeforces Round 913 (Div. 3) will start at Dec/05/2023 17:45 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by pashka, MikeMirzayanov and me.

Part of the problems in this round were in the Cyprus Programming Challenge. If you participated in it, please refrain from participating in this round.

We would like to thank:

1. peltorator, FairyWinx for red testing.
2. Vladithur, Valters07 for yellow testing.
3. stefanbalaz2, FBI, SlavicG, flamestorm, SashaT9, mesanu, trainerherp, Ush1su for purple testing.
4. dan_dolmatov, Yousef.Osama for blue testing.
5. Sergey140146659, Pa_sha, gas for cyan testing.

Good luck!

UPD: Editorial

• +255

By Vladosiya, history, 8 months ago, translation,

Hello, Codeforces!

I wanted to add CERC 2021 to gyms, but I can't seem to find the tests, checkers, and solutions. If you know where they can be found or someone who might have them, please let me know.

UPD: Thanks everyone for help and xiaowuc1 who shared the archive to me!

• +61

By Vladosiya, history, 9 months ago, translation,

1881A - Don't Try to Count

Tutorial
Solution

Idea: Gornak40

Tutorial
Solution

1881C - Perfect Square

Tutorial
Solution

1881D - Divide and Equalize

Idea: myav

Tutorial
Solution

1881E - Block Sequence

Idea: MikeMirzayanov

Tutorial
Solution

1881F - Minimum Maximum Distance

Idea: senjougaharin

Tutorial
Solution

1881G - Anya and the Mysterious String

Idea: Gornak40

Tutorial
Solution
• +26

By Vladosiya, history, 9 months ago, translation,

Hello! Codeforces Round 903 (Div. 3) will start at Oct/12/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by our team: myav, Gornak40, senjougaharin and Vladosiya.

We would like to thank:

1. MikeMirzayanov for Polygon and Codeforces platforms.

2. SomethingNew, rniya, zwezdinv for red testing.

3. makrav, snowysecret, AlexanderL, KseniaShk, pavlekn for yellow testing.

4. gigabuffoon, EgorUlin, KerakTelor, Pa_sha, I_love_geom, petyb, MinaRagy06, toniskrijelj, FynjyBath for purple testing.

5. Abo_Samrah, dan_dolmatov, pedrosorio, ezdp, azureglow, Chrisedyong, Apachee, arseny2606 for blue testing.

6. t0rtik, Sergey140146659, hader239, Modern for cyan testing.

7. mkshh, petertromso for green testing.

Good luck!

UPD: Editorial

• +243

By Vladosiya, history, 9 months ago,

Hello, Codeforces!

We've compiled a list of command lines that Codeforces uses to compile and run solutions in various languages and compilers.

It is up-to-date as of today (2023-10-06), and we will make efforts to keep it current in the future, but this is not guaranteed.

• +316

By Vladosiya, history, 10 months ago, translation,

Hello, Codeforces! A month ago, I started working part-time with MikeMirzayanov. It's time to share the results of the first month!

Overall, I've been involved in several things:

• +244

By Vladosiya, history, 11 months ago,

Hello, Codeforces!

Today, MikeMirzayanov taught me how to add contests to the Gym, so we've started adding old Google Code Jam rounds. We think it's a good idea to create a comprehensive (or almost comprehensive) archive of all GCJ rounds in the Gym.

I've added 2015 Google Code Jam Round 1A (GCJ 15 Round 1A) and 2015 Google Code Jam Round 1C (GCJ 15 Round 1C) today. It seems that for the 2015 season, only the Finals are missing now. I'll be adding that soon as well!

While Google's archives don't include solutions, we did find a user-generated archive at https://github.com/kamyu104/GoogleCodeJam-2015. However, it would be great to have additional sources for verification.

Would any of you be able to help us find other reliable sources for correct solutions? This way, we can be absolutely sure that all uploaded problems are accurate.

Thank you!

• +54

By Vladosiya, history, 12 months ago, translation,

Hello, Codeforces! I made announces of rounds quite often, so some time ago I made a script that gives out the entire list of testers divided by colors. Of course, you can rewrite it a little, so that the order is whatever you want.

Script uses Codeforces API, so first of all you need to go to your account settings and generate API keys and put the open one in the "key" file, and the secret one in the "secret" file in the same folder with the script (or just assign them to the corresponding variables in the script). Now you just need to fill in the array contestids with ids of mashups that you used for testing and run the script. At the end of its work, the script will create file "en.txt " with thanks to all the testers.

I hope it will help you to quickly change the list of testers. Good luck to all and successful rounds!

Script
• +79

By Vladosiya, history, 12 months ago,

1851A - Escalator Conversations

Tutorial
Solution

1851B - Parity Sort

Tutorial
Solution

1851C - Tiles Comeback

Tutorial
Solution

1851D - Prefix Permutation Sums

Idea: Gornak40, prepared: senjougaharin

Tutorial
Solution

1851E - Nastya and Potions

Tutorial
Solution

1851F - Lisa and the Martians

Idea: Gornak40, prepared: Gornak40

Tutorial
Solution

1851G - Vlad and the Mountains

Tutorial
Solution
• +96

By Vladosiya, history, 12 months ago, translation,

Hello! Codeforces Round 888 (Div. 3) will start at Jul/25/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by our team: myav, Aris, Gornak40, senjougaharin and Vladosiya.

We would like to thank:

1. MikeMirzayanov for Polygon and Codeforces platforms.

2. tute7627 for red testing

3. oversolver, sevlll777, pavlekn, zwezdinv, Sokol080808, 74TrAkToR, vladmart, EJIC_B_KEDAX, Vladithur, KseniaShk, Be_dos for yellow testing

4. moonpie24, FBI, meowcneil, NintsiChkhaidze, Phantom_Performer, SashaT9, spike1236, Kalashnikov for purple testing

5. TheGoodest, Pa_sha, Sasha0738 for blue testing

6. Syuzi777, Tahseen for cyan testing

Good luck!

UPD: Editorial

• +265

By Vladosiya, history, 14 months ago,

1833A - Musical Puzzle

Tutorial
Solution

1833B - Restore the Weather

Idea: myav, prepared: myav

Tutorial
Solution

1833C - Vlad Building Beautiful Array

Tutorial
Solution

1833D - Flipper

Idea: Gornak40, prepared: Aris

Tutorial
Solution

1833E - Round Dance

Tutorial
Solution

1833F - Ira and Flamenco

Idea: Gornak40, prepared: Gornak40

Tutorial
Solution

1833G - Ksyusha and Chinchilla

Idea: Gornak40, prepared: Gornak40

Tutorial
Solution
• +64

By Vladosiya, history, 14 months ago, translation,

Hello! Codeforces Round 874 (Div. 3) will start at May/19/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin and Vladosiya.

We would like to thank: pavlekn, KoT_OsKaR, natalina, vladmart, Phantom_Performer, Be_dos, ctraxxd, diskoteka, lunchbox, kzyKT, MODDI, molney, FEDIKUS, Nickir, 74TrAkToR, kamishogun, KseniaShk, Sokol080808, NintsiChkhaidze, Asad5059, heon for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

• +194

By Vladosiya, 15 months ago, translation,

1811A - Insert Digit

Idea: senjougaharin, prepared: senjougaharin

Tutorial
Solution

1811B - Conveyor Belts

Tutorial
Solution

1811C - Restore the Array

Idea: MikeMirzayanov, prepared: myav

Tutorial
Solution

1811D - Umka and a Long Flight

Idea: Gornak40, prepared: Gornak40

Tutorial
Solution

1811E - Living Sequence

Idea: Aris, prepared: Aris

Tutorial
Solution

1811F - Is It Flower?

Tutorial
Solution

1811G1 - Vlad and the Nice Paths (easy version)

Tutorial
Solution

1811G2 - Vlad and the Nice Paths (hard version)

Tutorial
Solution
• +52

By Vladosiya, 16 months ago, translation,

Hello! Codeforces Round 863 (Div. 3) will start at Apr/04/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin and Vladosiya.

We would like to thank: Sugar_fan, doreshnikov, powergee101, pashka, KseniaShk, 74TrAkToR, stefanbalaz2, playerr17, diskoteka, BF_OF_Priety, nigus, erankyun, plourde27, Be_dos, donghoony, lucasxia01, Jostic11, sansen, gigabuffoon, akulenok, pwned, vrintle for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

• +38

By Vladosiya, history, 17 months ago, translation,

1800A - Is It a Cat?

Tutorial
Solution

1800B - Count the Number of Pairs

Idea: myav

Tutorial
Solution

1800C1 - Powering the Hero (easy version)

Tutorial
Solution

1800C2 - Powering the Hero (hard version)

Tutorial
Solution

1800D - Remove Two Letters

Idea: MikeMirzayanov

Tutorial
Solution

1800E1 - Unforgivable Curse (easy version)

Idea: Aris, talant

Tutorial
Solution

1800E2 - Unforgivable Curse (hard version)

Tutorial
Solution

1800F - Dasha and Nightmares

Idea: Gornak40

Tutorial
Solution

1800G - Symmetree

Tutorial
Solution
• +46

By Vladosiya, history, 17 months ago, translation,

I found a small shortage of materials in English on this topic and I want to start with translated article of rationalex:

## The problem

We want to learn how to compare root trees for isomorphism (equality up to the renumbering of vertices + the root of one tree necessarily goes to the root of another tree).

## Hash of vertex

Note that since we cannot appeal to the vertex numbers, the only information we can operate on is the structure of our tree.

We will consider as a hash of a vertex without children some constant (for example, 179), and for a vertex with children we will use as a hash some function from the sorted list of hashes of children (since we do not know the true order in which the children should go, we need to bring them to the same form). The hash of the root tree will be considered the hash of the root.

By construction, the hashes of isomorphic root trees coincide (the author leaves the proof by induction on the number of levels in the tree to the reader as an exercise).

## Polynomial hash is not suitable

Consider 2 trees:

If we calculate for them to take a polynomial hash as a function of children, we get: $h(T1)=179+179p+179p^2=179+p(179+179p)=h(T2)$

## Which hash is suitable?

As a good hash function, for example, this is suitable

$h(v)=42 + \sum_{u \in sorted\_by\_hash(child(v))} log(h(u))$

For this hash function, it may seem that it is possible not to sort the hashes of children, but this is not the case, because when calculating floating-point numbers, we have an error, and in order for this summation result to be the same for isomorphic trees, it is also necessary to sum the children in the same order.

An example of a more complicated hash function:

$h(v)= \big[\sum_{u \in sorted\_by\_hash(child(v))} h(u)^2+h(u)p^i+42\big]\mod2^{64}$

## Asymptotics

All we need to do at each level is sorting the vertices by hash value and summing, so the final complexity is: $O(|V|log(|V|))$

## I want to continue on my own:

In the reality of Codeforces, these approaches have problems in the form of hacks (which can be seen, for example, by hacks of this task). Therefore, I want to talk about an approach in which there are no collisions.

## What is this magic hash function?

Let's sort the hashes of the children for the vertex and match the number to this array, which we will consider the hash of the vertex (if the array is new, then we will assign it the minimum unoccupied number, otherwise we will take the one that has already been given).

## Why does it work fast?

It is easy to notice that the total size of the arrays that we counted is $n - 1$ (each addition is a transition along the edge). Due to this, even using treemap for mapping, all accesses to it will require a total of $O(n \cdot log(n))$. Comparing a key of size $sz$ with another key works in $O(sz)$ and such comparisons for each key will occur $O(\log(n))$ times, and the sum of all $sz$, as we remember, is $n-1$, so it turns out a total of $O(n\cdot \log(n))$. (You might think that it is worth using hashmap, but this does not improve the asymptotics and causes the probability of a collision).

• +151