Hello, Codeforces!

First and foremost, we would like to say a massive thank you to everyone who entered and submitted their answers to the five Kotlin Heroes competitions which were held previously: Episode 1, Episode 2, Episode 3, Episode 4, Episode 5: ICPC Round, and Episode 6.

Ready to challenge yourself to do better? The Kotlin Heroes: Episode 7 competition will be hosted on the Codeforces platform on Jun/29/2021 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.

**Prizes:**

**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 sticker, competitors solving at least one problem will enter into a draw for one of 50 Kotlin Heroes t-shirts.**

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

The round will again be held in accordance with a set of slightly modified ICPC rules:

- The round is unrated.
- The contest will have 9 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). If two participants solved the same number of problems and scored the same penalty, then those of them who had previously made the last successful submission will be given an advantage in the distribution of prizes and gifts.

If you are still new to Kotlin we have prepared a tutorial on competitive programming in Kotlin and Kotlin Heroes: Practice 7, where you can try to solve a few simple problems in Kotlin. The practice round is available by the link.

We wish you luck and hope you enjoy Kotlin.

Please update Kotlin version

do we have to write code in kotlin language

yes.. only Kotlin will be available for the contest... watch this contest you may understand about the contest rules and language Kotlin Heroes: Practice 7

I thought the practice session had hints and open solutions available. Where are the solutions?

The practice problems are from past Codeforces contests, you can search them online to find the solutions.

Kotlin takes ~15 secs to compile in my pc as well as in some online IDEs I've tried like Ideone etc. Is there something to speed up the process? Am I missing something here?

Kotlin was taking a while to compile when I tried it in VSCode. I switched to IntelliJ, and that sped up the compiling significantly.

Will any measures be taken to prevent people from creating multiple accounts to increase their chances of winning a t-shirt? I recall there were some issues with that last time, but it looks like the blog calling those people out has since been deleted.

For what it's worth, it seems over a third of the registrants for the contest at time of writing are unrated accounts, which is a much higher percentage than the most recent Div. 2 round. Of course there are probably multiple factors contributing to this (perhaps some of the unrated accounts feel more comfortable participating in an unrated round, or they just want to try their luck to get a t-shirt?) but the amount of unrated accounts currently registered is nearing the amount of unrateds that registered in the last Div. 2. That contest had over 20k registrants and this one does not yet have 5k.

Perhaps it would be worth limiting t-shirt lottery participants to only those who solve at least one problem

andwere rated before the contest? That would be a simple way to prevent account spam and it would at least force the cheaters to think ahead a little more.Yes, I acknowledge that I would definitely have a better chance of winning a t-shirt if this happened, but at the same time, the system seems easy for somebody to exploit (at least to me) and I think that should be fixed regardless of what personal benefit I might get out of it.

Most of the owners of these unrated accounts might be android developers, who never heard of codeforces before. Like me, they just might have come across Roman Elizarov's tweet or one of the Jetbrains' announcements about this contest and decided to register to participate.

Sure there might be, but there also many cases of people using alts to win these prizes. Each time a Kotlin Heroes contest happens, I can see at least 3 or 4 well known alts winning the prizes.

It'll never get fixed sadly. People comment on every Kotlin Heroes post to do this but MikeMirzayanov and BledDest seem to enjoy ghosting them. As long as they get their sponsorship money, they don't really care.

As far as I understand, JetBrains want to use these contests to try promoting both Kotlin in the world of competitive programming and vice versa (competitive programming among people who just use Kotlin to write code and are not familiar with ICPC or anything like that), that's why they expect people who didn't know about CF to participate and offer them prizes. Unfortunately, I don't know how to limit the usage of alternative accounts without limiting the ability to win a T-shirt if someone didn't participate in a CF round earlier.

A better idea might be a requirement of 1 previous non-T-shirt-based round (obviously they should have solved at least 1 problem). The round itself can be unrated, but it might make people who make multis at the last moment realize they can't participate. Then again, people who have long-standing multis really can't be stopped.

Some multis I found, and why I feel like they are multis:

submitpurposework submitjavak submitkotlin

You found this too, just here are all the associated multis I could find. Each was created at the same time, and each left at the same time.

Why does Kotlin Heroes: Practice 7 not allow me to submit solutions in practice mode right now? It says "Contest is over". I would like to learn the language before the real thing.

If anyone cares, this issue has disappeared (or somebody fixed it) and now it's possible to submit solutions for Kotlin Heroes: Practice 7. The Problem A page now has "choose file" and "submit" buttons as one would expect.

Was this a one time glitch? Or does Kotlin judge always become dysfunctional roughly half an hour before Kotlin contests on the codeforces platform?

Why is there no C++ Heroes?

Because there's no need to promote C++. Without this, most people wouldn't even have heard of Kotlin, but almost every programmer has heard of C++.

Every contest is C++ Heroes

"If two participants solved the same number of problems and scored the same penalty, then those of them who had previously made the last successful submission will be given an advantage in the distribution of prizes and gifts."

Great, I tied with later last submit time. For the 3rd Kotlin contest in a row. I should just solve 1 problem instead of 6, that would even increase my chances to get lucky with the 50 random tshirts :(

TL in H is so tight. I have $$$O(nm2^k)$$$ solution but it doesn't pass :( Guess it's because of using stack.

On E, I got 2 WA and wasted 30 minutes because apparently using

`for (x in a) { print(x); print(" ") }`

is 50x slower than`println(a.joinToString(" "))`

(roughly tested on my computer)java (and so kotlin) flush every time you call

`print()`

or`println()`

Oh I thought it only did for println (probably wrong judgement based off of other languages)

I think your guess is correct. I also got TLE with stack and got AC by replacing it with

`IntArray`

.After also getting TLE in H using a Stack, I replaced it with an ArrayDeque (which provides the same methods and some more) and got AC in ~1.2 seconds. Seems like ArrayDeque should just always be preferred over Stack.

It's pretty weird of the developers to make it like that. Isn't there some concept like 'simpler versions should run faster'? It's the reason that

`std::vector`

is faster than`std::deque`

, the former doesn't need to support push/pop at the front.It seems like Stack is written to be thread-safe, so it's not actually really simpler in terms of implementation.

$$$O(2^knm\log{n})$$$ passed in 1.5 seconds

120901124

Yes, Stack was the culprit. I implemented Stack using array in the last 2 min and managed to get AC in 780ms. Almost cost me a t-shirt today.

Have a look at my AC submission if you wish to.

Yeah basically don't ever use

`java.util.Stack`

. An`ArrayList`

/`MutableList`

would do the job, using`.removeLast()`

as the pop operationI use following code to find nearest less element on right in array $$$a$$$ :

It's short, fast and without stack.

Solution for F? I tried to think of something using a compressed version of the string (e.g. $$$1011100 \rightarrow 1, 1, 3, 2$$$) but couldn't get anything.

One observation that you can make is that greedily extending the string as far as possible is a correct solution. Because of this, the sum of answers is at most $$$\mathcal{O}(n\log{}n)$$$, so you just need to be able to calculate the answer for some $$$k$$$ in $$$\mathcal{O}(ans\log{}n)$$$ time. You can do this by constantly binary searching for the longest length that the next string could have. You can see my submission here: 120888512

I got that the sum of answers is at most $$$\mathcal{O}(n \log n)$$$ in a different way. For fixed $$$k$$$, the answer is at most $$$\left \lceil\frac{n}{k}\right \rceil$$$, which becomes the harmonic sum.

But I'll have to implement the binary search, thanks!

Notice that each part will have length at least $$$k$$$, so the answer for fixed $$$k$$$ is no more than $$$\frac{n}{k}$$$, so the sum of all answers if $$$O(n \log n)$$$, which means that you can explicitly build all partitions, you just need to find longest allowed segment starting at $$$i$$$ in $$$O(1)$$$ time. Notice that you can find first position $$$j_0$$$ such that there are $$$k+1$$$ zeros at $$$[i; j_0]$$$ and first $$$j_1$$$ such that there are $$$k+1$$$ ones at $$$[i; j_1]$$$. Then the longest segment is $$$[i; \max(j_0, j_1) - 1]$$$. Let's find $$$j_0$$$, for example. If you calculate number of zeros on each prefix, you want first prefix with $$$sum_0[j_0] = sum_0[i - 1] + k + 1$$$, and you can just precompute such $$$j_0$$$ for each sum on the right from $$$1$$$ to $$$n$$$.

elegant!

By the way can you explain your intuition behind E ?

Exchange argument. Any inversion in the matching can be eliminated without making the answer worse, therefore a sorted matching is always optimal.

Thanks, got it :)

Before the contest I had zero knowledge of Kotlin. I somehow managed to learn some basics and solved 2 problems during the contest. Now I am very much motivated to learn Kotlin. Thanks to this contest. Enjoyed a lot.

It was exactly the same for me. I surely heard about Kotlin before and wanted to try it some day, but never was motivated enough to actually do it. This contest gave me the so much needed push. And Kotlin syntax turned out to be very easy to learn. It's time to try some Android apps development now :-)

I'm also a bit surprised that so few people participated. But who cares, it's their loss.

I know that this is not the place to ask but I have to because I do not know where else I can ask so, this is the question https://codeforces.com/problemset/problem/1469/A and this is the solution(ACCEPTED) https://codeforces.com/contest/1469/submission/120939474 but there are some cases like for (()(??()() the answer should be YES but the answer is NO(according to the submitted code) likewise for ())??(() the answer should be NO but it is YES(according to the submitted code) and still ended up getting AC how?

There is an important detail in the problem statement. "

There is exactly one character (and exactly one character)in this sequence" Your counterexample does not satisfy the condition.Looking forward for an editorial...

:catThink:

Who all are the random giveaway winners?

Bump

Just wait for the result blog post. No need to bump.

Maybe BledDest sir can help us!

Mega bump

Is there any information about t-shirts?

It would be weird if they announce winners for this Kotlin Heroes round before they announce the winners for the previous Kotlin Heroes round :)

There is a separate blogpost detailing winners of the previous round.

Ah, I didn't notice that post. Thanks!

Everyone is so excited about

random t-shirt pricesknowing the fact that winning one of those has a probability of about .0000000000001% lol.The probability is about 7%. This is not a zero probability at all

Why isn't there any editorial for kotlin heroes contests ? :'(

:catThink:

Thank you, if it would have been linked with this post, it would have been great :)

Editorials for this round can be found here: Kotlin Heroes 7 — Editorial.

BledDest, please add the link to the announcement too.

When would the giveaway winners be announced :(