### Aksenov239's blog

By Aksenov239, history, 12 months ago,

Hello, everybody!

We would like to invite you to participate in the Mirror of The ICPC World Finals Moscow Invitational Contest. The original contest was made for the teams who cannot come to The World Finals in Moscow. They were competing for the medals and glory. The Invitational contest has already passed and the results will be revealed on October 5th.

The mirror contest will be held by almost standard ICPC rules with 10 to 14 problems. The difference from the traditional ICPC format is that your team can use three computers instead of one. The problems are expected to be of The World Finals difficulty. Also, the round will be unrated!

The problemset was prepared by NERC Jury Team with the help of many other people. The chief judge is Roman elizarov Elizarov. The jury members are Pavel PavelKunyavskiy Kunyavskiy, Georgy kgeorgiy Korneev, Evgeny eatmore Kapun, Ilya izban Zban, Niyaz niyaznigmatul Nigmatullin, Vasiliy SirShokoladina Mokin, Daniil danilka.pro Sagunov, Gennady tourist Korotkevich, Oleg snarknews Hristenko, Egor Egor Kulikov, Borys qwerty787788 Minaev, Pavel pashka Mavrin, Mike MikeMirzayanov Mirzayanov, Anton Paramonov, Bruce bmerry Merry, Zachary Friggstad Friggstad, Jakub Wojtaszczyk, David Van Brackle, and myself. (I hope I haven't missed somebody. :P)

I hope you will like the contest! Good luck and have fun!

UPD: The editorial is available here.

• +300

By Aksenov239, history, 16 months ago,

Hello everybody!

After a long break I would like to announce the fourth Bioinformatics contest organized by ITMO University, Bioinformatics Institute, Rosalind and Stepik. The contest is sponsored by JetBrains, Yandex, Serokell, and Genotek.

The contest is hosted on Stepik platform. To participate you have to sign the rules.

The contest consists of two rounds:

The contest is prepared by the following team: Alexey Sergushichev, Nikita Alexeev, Nebuchadnezzar, demon1999, tourist, cdkrot, GShark, doreshnikov (all ITMO University), German Demidov (Center for Genomic Regulation), Andrey Prjibelski (CAB SPbU).

Are there any prizes?

• 1st place – Whole Genome Sequencing
• 2nd and 3rd – Whole Exome Sequencing
• 4th and 5th – 23andMe or Genotek DNA Service
• 1st–30th – Honorable Bioinformatics T-Shirt

Do I need to know biology?

The knowledge of biology is not necessary to solve the problems!

We wish that you will like the problems!

Good luck!

• +254

By Aksenov239, 2 years ago, translation,

Hello Codeforces!

My name is Vitaly Aksenov and I present you the new lesson in English EDU section as a part of "ITMO Academy: pilot course". I will talk about Disjoint Sets Union (DSU).

A little bit about myself, I cannot brag about being red (International Grandmaster), however, I was twice and each time afterwards there was a revolution of colours on Codeforces. :-) Right now I am the Researcher in ITMO University in parallel and distributed computing (link). Also, I am in Jury Committee of several olympiads such as NERC, Bioinformatics Contest, Russian Code Cup and etc.

This is my first time to write a lecture so do not judge harshly. I hope you will like it!

I want to thank pashka for video editing, and thanks to pashka, MikeMirzayanov and niyaznigmatul for sharing the problems.

Go to EDU →

• +751

By Aksenov239, history, 4 years ago,

Hello everybody!

I would like to announce the third Bioinformatics contest organized by ITMO University, Bioinformatics Institute, Rosalind and Stepik. The contest is sponsored by JetBrains, Yandex and Serokell.

The contest is hosted on Stepik platform. To participate you have to sign the rules.

The contest consists of two rounds:

The contest is prepared by the team from ITMO University: Alexey Sergushichev, Nikita Alexeev, Sergey Aganezov, GShark, YakutovDmitriy, Maria Atamanova, izban, VArtem, chavit and me.

Are there any prizes?

Do I need to know biology?

The knowledge of biology is not necessary to solve the problems!

We wish that you will like the problems!

Good luck!

• +35

By Aksenov239, 5 years ago,

Hello everybody!

I would like to announce the second BioInformatics Contest organized by Bioinformatics Institute, Rosalind and Stepik.

The contest is hosted on Stepik platform. You can already register and become familiar with the rules and the testing system. Note, that you have to sign the rules, otherwise, you will not be able to participate.

The contest consists of two rounds:

The contest is prepared by the team from ITMO University: Alexey Sergushichev, Nikita Alexeev, Alexander Tkachenko, chavit, izban, GShark, VArtem and me.

For now, you could train on the problems of the previous year.

Are there any prizes?

Yes, there will be. As in the previous year we will announce them later.

Do I need to know biology?

This year we will try to make problems more real-life, so some knowledge of biology is necessary. But do not worry this amount of knowledge is not deep and could be learned during the contest.

What kind of problems to expect?

There will be two kind of problems: exact (ACM) and approximate. We encourage you to take a glance on the problems of the previous year.

Good luck!

UPD1: The Qualification Round has started!

UPD2: We added the description of prizes!

UPD3: Approximately, one day left for Qualification Round.

• +71

By Aksenov239, 5 years ago,

Better late than never.

World Champions Programming School (wcps.ifmo.ru) announces the third training camp in France on ACM ICPC. It will be held in Universite Toulouse III Paul Sabatier from October 30 to November 3. The school page is https://www.irit.fr/olymp_prog2017/. The coaches for this session are Vladimir Smykalov (enot110, ICPC World Champion 2017) and Grigorii Shovkoplyas (GShark).

Note, that there are no registration fees, but the registration is obligatory.

Hope to see you there!

• +47

By Aksenov239, 6 years ago, translation,

Hello, everybody.

Probably, you know that we will have a broadcast of the ACM ICPC World Finals this year. (As in previous years. :-)) We want to make some flash interviews with participants and other people related to the contest. BUT, we are quite bored with the standard interviews and the standard questions that are asked. We will give some boring examples: What is the first step to become a successful competitor? When did you start to code? How much do you practice? How your team is training? I understand that for someone they are still interesting questions, but on the other hand, they are very impersonal.

We would like YOU to HELP us create funny or interesting questions! (You could still pose the standard question and, probably, we will use it. But it is better to think out of the box)

Here are several examples: - AMD or Intel? - What music do you prefer? - How much the Chinese football team should pay you per year, so you would agree to play with them? - Your first/most memorable trophy/achievement in life? - If you have to teach programming to a (non-programming) celebrity, who would it be? And why?

Note: it is better not to post the questions inside the comments, so the inteviewees could not prepare. :-)

Thanks!

• +51

By Aksenov239, history, 6 years ago,

Hello everybody!

I would like to announce the first BioInformatics Contest organized by Bioinformatics Institute.

The contest is hosted on Stepik platform. You can already register and become familiar with the rules and the testing system. Note, that you have to sign the rules, otherwise, you will not be able to participate.

The contest consists of two rounds:

There will be prizes for Top 10-20, but they are currently kept in secret. (Note, there will be no money prizes. :-))

All other information related to rounds is located at FAQ.

Why bioinformatics?

We think, that this is one of the most important fields of modern applied Computer Science and we would like to introduce this field to everybody who is interested in something new aside from Olympiad Programming and Software Engineering :-). Probably, somebody will find it interesting and will want to choose this path in his career.

If there will be such a person in Saint Petersburg, Russia, you could apply for a one year course at Bioinformatics Institute.

What type of problems will be there?

We have ACM-style (exact) and Challenge24-style (approximate) problems. This is our first try to do contest with approximate problems, so we could not be sure that everything will go smoothly but we hope so. At least, we tried to prepare interesting problems. Do not worry, most of the problems should be solvable without a knowledge of biology.

Who prepares the contest?

The contest is prepared by the team from ITMO University: Alexey Sergushichev, chavit, Anna Malova, izban, GShark, VArtem and me.

Good luck!

UPD: The Qualification Round has started!

UPD2: Less than two days left till the end of the Qualification Round!

UPD3: Final round will start in 15 minutes!

UPD4: The standings could be found here.

• +90

By Aksenov239, history, 6 years ago,

Hi, everybody.

We would like you to join Live broadcast from ACM ICPC World Finals 2016. The broadcast will start at 8-00 ICT 19 May 2016, while the contest will start at 9-30 ICT. get more statistics afterwards.

The broadcast consists of two parts:

• Main broadcast with comments from our analytic Egor. There will be presented all information about the contest, interviews and other interesting videos! Broadcast will be available in youtube and twitch.

• Additional broadcast with videos from teams screens and web-cameras. This year you can influence what teams will be shown. For that, you should send the tweet in twitter, which contains #ICPC2016 and hashtag of the team. (The hashtags could be found in the page of each team under link social from MyICPC) If you prefer webcam to the screen, you could specify it with #camera. Examples of tweets: #ICPC2016 #ITMO, #ICPC2016 #ITMO #camera. We will show team if it gets enough votes. (Also, we count only one tweet per user per minute, so there is no need to spam votes) Broadcast will be available in youtube as second screen and twitch.

Also, we want to test our system tomorrow (18 march 2016) at 8-00 ICT. Dress rehearsal contest will start at 9-30 ICT, so all videos from teams and the second screen should be available starting from this time. Could you help us? :-)

At the end I want to mention everybody who is working on this broadcast:

• Director: elizarov.

• Script and beverages: lperovskaya.

• Design of infographics and hardware: pashka.

• Design of everything else: Mikhail Kutsov.

• Video preparation: Viktoria Volochay.

• Analytics and Creeping line manager: niyaznigmatul.

• Analytics and commentator: Egor.

• Flash zone interviewer: Charles Nevile.

• Software developers: pashkal, Anna Malova and me.

Don't forget to subscribe on channels and tell everybody! See you on broadcast!

P.S.: We encourage you to use youtube rather than twitch. (Even if the twitch chat is more comfortable to use. ;-)) This will help us to get more statistics afterwards.

• +117

By Aksenov239, 7 years ago, translation,

Hi everybody from the ICPC Live team (elizarov, pashka, niyaznigmatul, Egor, lperovskaya and me).

We want to inform you, that broadcast of the World Finals will take place on Wednesday, 20th of May.

The broadcast will be on the two websites (youtube and twitch). The links will be posted tomorrow, but you could subscribe to our channel.

We will have the following schedule:

Don't forget to subscribe on our channels on youtube and on twitch: icpclive1 and icpclive2.

While you wait, on Tuesday, May 19 Dress rehearsal will take place. The broadcast will be available on the youtube channel ICPC Live and on the twitch channel ICPC Live. The idea of this broadcast is to check, if everything is fine, so, please, be nice and report availability or performance issues. We can't guarantee the good broadcast.

Regards, Team ICPC Live

UPD4: Thanks to alexyz for the link: multitwitch

• +211

By Aksenov239, 8 years ago, translation,

I want to say thanks to whom can help me to make this round: for testing pashka and cerealguy, for problems chavit and enot110 and andrewzta for supervising.

417A - Elimination. Author and realization Aksenov239.

The first thing, that you need to mention, is that if k ≤ n·m, then the answer is equal to 0. After that you need to take at least n·m - k people. There's three possibilities to do that:

• To consider only main rounds: .
• To take additional rounds to the number, which is divisible by n: .
• To take only rounds of the second type: d(n·m - k).

Also in this problem it is possible to write the solution, which check every possible combinations of the numbers of main and elimination rounds.

Solution: 6396283

417B - Crash. Author and realization Aksenov239.

Let us create array a with 105 elements, which is filled with  - 1. In the cell a[k] we will contain the maximal number of the submissions of the participant with identifier k. We will process submissions in the given order. Let us process submission x k. If a[k] < x - 1, then the answer is NO, else we will update array a: a[k] = max(a[k], x).

Solution: 6396297

418A - Football. Author and realization Aksenov239.

Let's consider this tournir as graph. Each vertex should have out-degree k. Then the graph should contain exactly nk edges. But the full-graph contains , because of that if n < 2k + 1 then the answer is  - 1, otherwise we will connect the i-th vertex with i + 1, ..., i + k, taking modulo n if needed.

Solution: 6396331

418B - Cunning Gena. Author and realization Aksenov239.

Let us sort the friends by the number of the monitors in the increasing order. Afterwards we will calculate the dp on the masks: the minimal amount of money Gena should spend to solve some subset of problems, if we take first n friends. Then the answer we should compare with the answer for first i friends plus the number of the monitors, which the i-th friend needs. Is is not hard to see, that if we consider the friends in this order consequently, then we can recalc dp like in the knapsack problem. The running time of this algorithm is O(nlog(n) + n2m).

Solution pashka: 6396347

418C - Square Table. Author and realization Aksenov239.

Let's build array of the length n for each n, that the sum of the squares of its elements is the square:

• If n = 1, then take [1].
• If n = 2, then take [3, 4].
• If n is even, then take .
• If n is odd, then take .

We are given two numbers n and m. Let array a corresponds to n, and array b corresponds to m. The we will build the answer array c as follows cij = ai·bj.

Solution: 6396358

418D - Big Problems for Organizers. Author chavit, realization Aksenov239.

This problem has two solutions.

The first one. Let's hang the tree on some vertex. Afterwards, let us calculate for eah vertex it's height and 3 most distant vertices in its subtree. Also let's calculate arrays for the lowest common ancestors problem. For each vertex i and the power of two 2j we have p[i][j], up[i][j] and down[i][j]:

• p[i][j] is the ancestor on the distance of 2j,
• up[i][j] is equal to the longest path from i to the vertices, which are situated in subtrees of the vertices on the path between i and p[i][j].
• down[i][j] is equal the same, but from the vertex p[i][j].

And the last part of this solution. Let us be given the query u v. Firstly, we find w = LCA(u, v). Afterwards, we need to find vertex hu, which is situated on the middle of the path between u and v. Really, we need to split the tree by this vertex, count the longest path from u in its tree and count the longest path from v in its tree. If we can imagine in the main tree, we can not delete this vertex, but with our precalculated arrays recalc this two values.

First solution: 6396376

The second solution. In a few words. Let's find the diameter of the tree. Precalc the answer for each vertices on the prefix. Then on the query we find two distant vertices on this diameter and the path. Obviously, diameter should contain the middle of the path, when we find it, using precalculated results on the prefixes and suffixes we can obtain the answer.

Second solution cerealguy: 6396390

418E - Tricky Password. Authors enot110, Aksenov239, realization Aksenov239.

The key theoretical idea of this problem is that the $2$nd row is exactly the same as the $4$th row, $3$rd row is exactly the same as $5$th row and so on. Because of that we need only to answer queries on the first three rows.

Let's move on to the practical part. In the first place we will compress coordinates, that any value will not exceed 2·105. Afterwards, let's split the array into parts of the length LEN. On each part we will calculate the following values: cnt[k] — the number of occurences of the number k on this prefix, also f[k] — the total number of the values, which occur exactly k times on this prefix. Array f we will store in the Fenwick data structure.

It is not hard to see, that array cnt contains the answer for the queries to the 2nd row. To get the answer for the queries to the 3rd row we need to calculate f[cnt[k]... 105]. Also it's quite understandable how to recalc this dp.

In summary, we will get per query. And we take , then we will get per query. Solution: 6396412

• +37

By Aksenov239, 10 years ago,

Hello!

Tomorrow (the 3rd of November) will held the Nothern Subregion Quarterfinal 2012 in the Northeastern European Region.

I think, it will be very interesting to watch the "battle" between teams, because in our quarterfinal participate 3 persons from the top10 in Codeforces rating. And jury made all to make this quaterfinal very interesting and unpredictable.

Also, don't forget, that you can participate in Yandex.Contest.