Hello, codeforces!

Long time no see, right? So maybe it's a good idea to try to return to my blogs slowly. This time the blog will be about a trick, which usually isn't necessary to solve a task, but can be useful to make implementation much more comfortable.

Let's look at this problem. It is about some DP on a tree in which we have to use convex hull trick to improve the complexity. The task requires merging two convex hulls with "smaller to bigger" trick. I recommend you to read the statement before reading the rest of the blog (and the editorial if you don't know how to solve it).

Hello, Codeforces!

We are happy to announce that in partnership with Codeforces to promote Kotlin programming language we are launching a series of "Kotlin Heroes" programming contests.

Kotlin programming language was introduced by JetBrains in 2011 and reached its first stable version 1.0 in 2016. The current language version is 1.3.31. The language is focused on solving the needs of application developers in various domains. Kotlin is a statically typed language that is designed for writing concise code, with less ceremony and more substance in it, and to scale from applications of just a few lines long to multi-million-lines projects.

While not being specifically designed for competitive programming, it incidentally fits well in this domain, reducing the typical amount boilerplate that a programmer needs to write and read while working with the code almost to the level offered by dynamically-typed scripting languages, while having tooling and performance of a statically-typed language.

The first "Kotlin Heroes" competition will be hosted at Codeforces platform on May/28/2019 17:35 (Moscow time). The contest will last 2 hours 30 minutes and will feature a set of problems from simple ones, designed to be solvable by anyone, to hard ones, to make it interesting for seasoned competitive programmers. Top three winners will get prizes of $512, $256, and $128 respectively, top 50 will win a Kotlin Heroes t-shirt and an exclusive Kotlin badge, competitors solving at least one problem will enter into a draw for one of 50 Kotlin Heroes t-shirts.

The round is held in accordance with slightly modified ICPC rules:

• The round is unrated.
• The contest will have 6-10 problems of various levels of complexity.
• You are only allowed to use Kotlin to solve these problems.
• Participants are ranked according to the number of correctly solved problems.
• Ties are resolved based on the lowest total penalty time for all problems, which is computed as follows. For each solved problem, a penalty is set to the submission time of that problem (the time since the start of the contest). An extra penalty of 10 minutes is added for each failed submission on solved problems (i.e., if you never solve the problem, you will not be penalized for trying that problem).

Registration is already open and available via the link. It will be available until the end of the round.

To help you get familiar with Kotlin we have prepared a tutorial on competitive programming in Kotlin and a practice round, where you can try to solve a few simple problems in Kotlin. All solutions are open, it means that you can look at a solution even if you haven't solved a problem yet. The practice round is available by the link.

We wish you luck and hope you enjoy Kotlin.

UPD 1: Many thanks to the testers elizarov, Benq, cdkrot, nhho, ksun48. Also KAN helped a lot with suggestions to the problems. And to all the participants warm greetings from authors MikeMirzayanov, vovuh, adedalic and pashka — they invented and prepared the problems for you!

Hi!

I'm glad to invite you to take part in Codeforces Round 562 (Div. 1) and Codeforces Round 562 (Div. 2), they will be held in May/26/2019 18:35 (Moscow time). The round will be rated for both divisions (^人^).

Participants in each division will be offered five problems and two hours to solve them.

The problems were written and prepared by me. Thanks to KAN for his help with the round, to sunset, TLE, furry, isaf27, Lewin, Aleks5d and wrg0ababd for testing and task discussing! Also, thanks to MikeMirzayanov for amazing systems Codeforces and Polygon!

Congratulations the winners!

Div1:

1) DearMargaret

2) OnionPringles

3) Errichto

4) maroonrk

5) Um_nik

Div2:

1) Szoboszlai10

2) lelolas

3) ndmitrovic

4) prick

5) Stardust

Editorial

Hello everyone,

At May 19 there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Saturday, May 25, at 10:00 MSK.

Contest link
Virtual participation link

Fourth time in a row it is a personal contest. So we ask everyone to participate solo. The contest is the most interesting for blue and violet coders.

Hi Codeforces!

We are happy to invite you to take part in Codeforces Round 561 (Div. 2). The contest will be held on May/17/2019 18:05 (Moscow time).

You will be given 6 problems and 2 hours to solve them. The round will be rated for all contestants with rating below 2100. As usual, participants from the first division are welcome to join out of competition.

The problems were written and prepared by Jefe and me. We owe a huge thanks to KAN for coordinating the round, to Lewin and mohammedehab2002 for testing, and of course, to MikeMirzayanov for the great Codeforces and Polygon platforms.

Good luck and have fun!

UPD: A huge thanks to neal, dreamoon_love_AA, and antguz for help with additional testing.

UPD2: Thanks for participating! System tests have finished. Congratulations to our winners!

Div. 2

1. iristran911

2. Sigyn

3. HaylayWilliams

4. albertg

5. Tianhen

Div. 1 + Div. 2:

1. 244mhq

2. Um_nik

3. uwi

4. iristran911

5. HIR180

Editorial will be available soon.

UPD3: Editorial is up!

Hello Codeforces!

On May/15/2019 17:35 (Moscow time) Educational Codeforces Round 65 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Hello Codeforces!

We are collaborating with an external sponsor who is offering a unique scholarship opportunity for women who want to study Cybersecurity or Fintech, both for Bachelors and Masters level.

The scholarship includes:

• An up to $10,000, one-time financial award, paid to the University
• An all-expenses-paid trip to the EMEA Summit 28-30 October, 2019 in Berlin
• A Cybersecurity professional to serve as an industry mentor

Apply before May 30th and Harbour.Space will also consider you for a scholarship from our own funds.

Don't miss this chance to study with us in Barcelona!

If you have questions about the scholarship, please contact us at [email protected]!

Congratulations to the winners:

Congratulations to the best hackers:

And finally people who were the first to solve each problem:

UPD: Editorial is out

Hi all!

The main phase of VRt Contest 2019 has ended. In the preliminary standings, five contestants managed to obtain a score of more than 60,000 points. The fight continued to the last day. Who will emerge as the winner after the final testing? We will know after it ends. (Update: results in a separate comment.)

I invite the contestants to share their solution ideas in the comments below, or in separate posts if their writeup is too large for a comment.

I have nothing to say this time, so meet yet another Div. 3 round :)

<almost-copy-pasted-part>

Hello! Codeforces Round 560 (Div. 3) will start at May/14/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) 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 participants of the third division, you must:

• take part in at least two 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 my work. Thanks to my good friends Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD: I also would like to thank nhho, chenjb and ksun48 for testing the round.

UPD2: I also would like to thank my friend Adilbek adedalic Dalabaev for valuable suggestions about the contest and testing it!

UPD3: Editorial is published!

UPD4:

Congratulations to the winners:

Congratulations to the best hackers:

And finally people who were the first to solve each problem:

Hello, Codeforces!

I'm glad to invite you to Codeforces Round 559 (Div. 1) and Codeforces Round 559 (Div. 2), which will be held on May/12/2019 17:35 (Moscow time). The round will be rated for both divisions (I hope).

All problems were written and prepared by me. Thanks to Aleks5d, TLE, sunset, furry, peltorator for testing problems and good advice, 300iq for round coordination and help with preparation and MikeMirzayanov for great systems Codeforces and Polygon.

You will be given 6 problems in both divisions and 2 hours to solve them. Please, read all the problems. Good luck, have fun and I wish everyone high ratings!

The scoring distribution will be announced closer to the beginning of the round.

UPD

The contest finished, contgratulations to the winners:

Div1:

1. mnbvmar
2. ecnerwala
3. ainta
4. ksun48
5. ekzhang

Div2:

1. hbi1998
2. Nutella3000
3. calabash_fool
4. ahgus89
5. 1207koo

Editorial