By BledDest, 5 weeks ago, In English

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 29.06.2021 17:35 (Московское время). 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.

REGISTER →

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.

Announcement of Kotlin Heroes: Practice 7
Announcement of Kotlin Heroes: Episode 7
 
 
 
 
  • Vote: I like it
  • +163
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

Please update Kotlin version

»
5 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

do we have to write code in kotlin language

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solutions of each participant will be available after contest ends

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

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 and were 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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +52 Vote: I do not like 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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -46 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +56 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
5 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

Why is there no C++ Heroes?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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++.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Every contest is C++ Heroes

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

"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 :(

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      java (and so kotlin) flush every time you call print() or println()

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It seems like Stack is written to be thread-safe, so it's not actually really simpler in terms of implementation.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    120901124

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah basically don't ever use java.util.Stack. An ArrayList / MutableList would do the job, using .removeLast() as the pop operation

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I use following code to find nearest less element on right in array $$$a$$$ :

    vector<int> next_l(n);
    for (int i = n - 1; i >= 0; --i) {
        next_l[i] = i + 1;
        while(next_l[i] < n && a[i] <= a[next_l[i]])
            next_l[i] = next_l[next_l[i]];
    }
    

    It's short, fast and without stack.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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$$$.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      elegant!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        By the way can you explain your intuition behind E ?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +32 Vote: I do not like 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.cc/problemset/problem/1469/A and this is the solution(ACCEPTED) https://codeforces.cc/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?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      but what does that suppose to mean? "There is exactly one character (and exactly one character) in this sequence" what does this imply?

»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Looking forward for an editorial...

»
5 weeks ago, # |
  Vote: I like it +63 Vote: I do not like it

Who all are the random giveaway winners?

»
4 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

Is there any information about t-shirts?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Everyone is so excited about random t-shirt prices knowing the fact that winning one of those has a probability of about .0000000000001% lol.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      The probability is about 7%. This is not a zero probability at all

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 days ago, # |
  Vote: I like it +9 Vote: I do not like it

When would the giveaway winners be announced :(

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you all for participating in Kotlin Heroes: Episode 7! Here are the winners announced: https://codeforces.cc/blog/entry/93293