By JetBrains, 3 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 first Kotlin Heroes competition which was held back in May. Congratulations to the top 3 winners Petr, ecnerwala, and abacabadabacaba on their incredible achievement, especially considering they were up against 4,500 other registrants from over 63 countries. We’d also like to give a shout out to tourist for being the only other person, outside of the top 3, to manage to solve every problem set from this round. Well done all of you!

Ready to challenge yourself to do better? The second "Kotlin Heroes" competition will be hosted on the Codeforces platform on the 7th of September, 2019, at 14:35 UTC (17:35 MSK, 07:35 PDT, 22:35 CST). 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 will again be held in accordance with a set of 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). 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.

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

REGISTER →

If you are still new to 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 the solutions are open, which means that you can look at the solution even if you haven't solved the problem yet. The practice round is available by the link.

We wish you luck and hope you enjoy Kotlin.

UPD: Thank you for the participation. The editorials are published.

Announcement of Kotlin Heroes: Episode 2
 
 
 
 
  • Vote: I like it
  • +104
  • Vote: I do not like it

»
3 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

That input In your tutorial is slow, java's tokenizer is much faster though it breaks functional programming principles

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

    You can use java classes in kotlin, see how i use java's tokenizer in kotlin link

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

      Switching to the tokenizer saves some time, but I find using the BufferedReader makes the biggest savings.

      Some good puzzles to stress test IO solutions on:

      #1208E Let Them Slide

      #1207F Remainder Problem

      #1181D Irrigation

      There's also the classic INTEST and INOUTTEST from SPOJ

      My conclusion is that Kotlin's STL String#split is good enough for the "business logic" of solution codes (rather than trying to deal with the StringTokenizer for those cases), but every ms saved in IO is a ms that can be used solving the actual puzzle.

      For output, I found two solutions to avoid auto-flushing: accumulating everything into a StringBuilder, or using a PrintWriter with auto-flush set to false. Both solutions seem to have about the same speed. It's again similar to Java, but Kotlin allows you to define "block functions" that helps reduce the chance of annoyances like forgetting to flush.

      Examples:

      StringBuilder version:

      class Output {
          val outputSb = StringBuilder()
          fun print(o: Any?) { outputSb.append(o) }
          fun println() { outputSb.append('\n') }
          fun println(o: Any?) { outputSb.append(o).append('\n') }
          fun iprintln(o: Any?) { kotlin.io.println(o) } // immediate println for interactive
      }
      inline fun output(block: Output.()->Unit) { val o = Output().apply(block); print(o.outputSb) }
      

      PrintWriter version:

      inline fun output(block: PrintWriter.()->Unit) { PrintWriter(System.out, false).apply(block).flush() }
      fun PrintWriter.iprintln(o: Any?) { println(o); flush() } // immediate println for interactive
      
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        In java, using System.in.read and System.out.write to byte buffers is the fastest by a factor of 2 compared to BufferedReader/PrintWriter. Probably the same is the case for kotlin.

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

          Do you mean something like #4 in this tutorial? Parsing raw bytes might just be a bit more work than I'm willing to do right now though, but thanks for the tip

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

            Yeah, kind of like that. There are still some optimizations for that, I think. I changed buffer size to 16777216 and also use InputStream instead of DataInputStream and it shaved off 0.01 seconds (out of 0.23 best runtime) on a high-input problem. (Although maybe that is just random fluctuations). For writing just use the write function and it will just print all the bytes in the given array.

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

Will the account with no contests claim T-Shirt?

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

    All contestants who solved at least one task will have a chance to win a t-shirt.

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

Good time to start learning Kotlin again.

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

It's astounding how many newly created accounts are registering in the contest. Everything for a t-shirt huh

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

    This is advertised in other sites as well, so it is possible that some Kotlin developers registered just for this. Let's hope, that there aren't many people who will "compete" with multiple accounts...

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

Few days back I only knew naive C++. CF urged me to learn C++ STL, Python. And now even Kotlin!__

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

I don't see any restriction for the winners of first Kotlin Heroes. Will t-shirts be different?

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

    We have another set of tasks, so everyone is welcome to join. T-shirts are in the same series, but not the same.

»
2 weeks ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

Is Kotlin IntArray.sort() O(n^2) complexity? I got TLE here 59869165

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

    IntArray maps to Java's int[], and IntArray.sort() maps to Java's Array.sort(), so yes, it does use the unfortunately hack-vulnerable quicksort. Better to use Array<Int> or MutableList<Int> for sortings. (Same goes for LongArray and DoubleArray.) Kotlin also supports List<T>.sorted() for read-only lists, which will return a new list with the sorting applied.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    IntArray.sort() is the same as Arrays.sort(). Java uses quick sort for array of primitive types, and merge sort for array of objects. As we all know quick sort runs in O(N^2) in the worst case when the array is sorted or almost sorted. I guess that's the reason why you get TLE. Try writing your own version of merge sort that sorts primitive types.

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Actually Java uses dual-pivot quicksort for primitive arrays, which does much better on pre-sorted/almost-sorted lists than traditional quicksort, as well as on patterns found in real-world datasets. Unfortunately, it's still vulnerable to a specially designed adversarial input.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I've had a look at the implementation and wouldn't say that it is much better. Just slightly better. Here is what I found in the code

        /**
         * If the length of an array to be sorted is less than this
         * constant, insertion sort is used in preference to Quicksort.
         */
         private static final int INSERTION_SORT_THRESHOLD = 47;
        

        If an array is sorted and its size is big enough, then there is a lot of work to be done until the size of the problem is reduced to the threshold after which the insertion sort does its job in linear time. Still, the same issue as with classic quick sort.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          It's "better" in the sense that the pattern required to trigger its worst case is less likely to arise naturally (unlike pick-first- and pick-last-as-pivot flavors of quicksort which dies on pre-sorted lists, or pick-middle which dies to a slightly more complex "pipe organ" pattern). It isn't too much better against an adversarial input.

          Insertion sort is actually $$$O(n^2)$$$, but has a very good constant factor for small sublists; that's why it's used as a fallback once the partition is small enough.

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I mean insertion sort is linear for already sorted array

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
              Rev. 4   Vote: I like it 0 Vote: I do not like it

              Oh. In that case it's better than pick-first quicksort because it isn't consistently picking the worst pivots

              Update; just read up more about dual pivot. Picking first+last doesn't improve much on the behaviour of presorted lists, so Java must be using a different strategy for pivot picking, as the tests I see it failing on have a more elaborate pattern than merely being presorted.

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

Kotlin seems similar to Java 8?

»
2 weeks ago, # |
  Vote: I like it -102 Vote: I do not like it

The correct method to gain upvotes quickly in CF: "Please give me some downvotes."

»
2 weeks ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it
 map<int,int>mp;
 mp[2]=3;
 mp[2]--;
 if(mp[2]>0) cout<<"yes";
 else cout<<"no";

Can anyone convert this c++ code into kotlin?

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

    Something like this, off the top of my head:

    val mp = mutableMapOf<Int, Int>()
    mp[2] = 3
    mp[2] = mp[2]!! - 1 // !! is non-null assertion operator, will throw exception if value is null;
                        // but we know it can't be null here as we just set it
    if((mp[2]?:0) > 0) println("yes") // ?: is null-coalescing operator
    else println("no")
    

    Kotlin can be slightly annoying with nullability checking when dealing with maps, since the behavior is to return null when the key doesn't exist. Usually, with variables, a feature called "smart-casting" will handle it within an if-block that tests for nullability, but, with maps, the compiler can't guarantee that successive invocations to Map.get() did not change its value.

    • »
      »
      »
      13 days ago, # ^ |
      Rev. 2   Vote: I like it -21 Vote: I do not like it

      "Throw exception" is a phrase that should never appear in competitive programming.

      UPD: I see people like to waste time with something that will still end up as RE.

      • »
        »
        »
        »
        13 days ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        I mean, I guess I get your point, if it's from the school-exam doctrine of "any answer is better than no answer", but I think the only way that can be practically implemented is to wrap the entire main() function in a try-block that prints a default value upon any unexpected error.

        Because, if avoiding exceptions means we shouldn't use !! for things like maps with known keys or max() on known non-empty arrays, then the same could be said about using any division operator (because possible divide by zero) or array access operation (because possible index out of bounds)

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In this case, when you see an unset key, rather than throw an exception, you should set that key and proceed as planned. At least that's equivalent to map access in C++.

          Yes, you shouldn't check these other things for exceptions either. If they don't signify a bug, they need to be handled in normal ways. It depends on the algorithm, but usually, out-of-bound access would be a no-op, division by zero would be handled as a special case (or avoided if possible!) and max([]) would be a default value smaller than all possible array elements.

          Error handling can be useful for debugging, but writing correct code quickly is more useful.

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            Kotlin does in fact have special access functions for returning a default value or setting an unset key upon access, e.g. Map.getOrDefault() or Map.getOrPut(). Even arrays and lists have getOrDefault / getOrElse; I use those all the time if it makes sense for "A[-1]" to notionally have some kind of default value (e.g. prefix sum arrays)

            The null-coalescing operator ?: is also often a good alternative to the double-bang, but occasionally there isn't any sensible default value to return.

            • »
              »
              »
              »
              »
              »
              »
              13 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah, you want these functions and this behaviour.

              occasionally there isn't any sensible default value to return

              That's also something you need to handle as part of your algorithm: "if(map[index] != null) do something". You can't make a language that automatically correctly handles this because it all depends on what you intend your code to produce.

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

            If I understand correctly, you never use assertions/throws in your competitive code? Why?

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

              I never use throws. I sometimes use asserts, when I notice that they'd give me useful info basically for free, like reaching the end of a function when I should return earlier or checking some identity that should obviously hold; the throw/catch mechanic is completely unnecessary. When I just want to check if my code doesn't silently crash locally, I prefer custom invocation. When I want to check correctness, stresstesting or printing out extra info is better.

              I can't think of a single situation where explicitly handling exceptions wouldn't have a simple alternative (like asserts).

»
13 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Where can I find the solutions to the practice contest?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    BTW, if anyone was wondering you can just type the problem name into google and get the actual problem.

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

why cf predictor shows rate changing

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

    I think because it works on your rank, points .. so whenever a contest has a rank and points it will work ( Idk )

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

I keep getting TLE in problem C test 11 because I used sort(), then I changed it to a quick sort but still TLE ( The rest of the code O(1) )

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Quick sort can be $$$O(n^2)$$$ , make sure you use Kotlin's sorting algorithms. For example, after reading the variables into array,or list $$$a$$$, use $$$a.sorted()$$$ to get a sorted copy of it.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I did use sort() at first and I got TLE, that's why I tried quick sort but also TLE ... I tried Bubble sort(O(n* log n) ) and it works , I got AC ... but thx

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

        For future reference, you should stay away from Quicksort because of worst case O(N^2). In order to avoid this you can turn your array into an arraylist and do Collections.sort() which uses merge sort which is only O(NlogN) worst case. Or if you want to use the array only you can shuffle the array before hand, so that when the quicksort uses the partition, it has a better chance of not being one-sided.

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    Lol. How many times have greens and grays run into this problem? For your own good, learn some Computer Science and read the documentation of programming libraries before you use them. Competitive Programming may be a fun sport. But it kinda teaches people bad habits here and there, like treating stuff you don’t understand/don’t wish to understand as a black box. Now that’s BAD. If you really want to be good, you need to study some formal academic material in detail and not blindly use code/algorithms which you don’t understand (spoiler: CP sites are BAD for learning specific domains (like math or algos) because they are not formal academic websites and some smarty pants who write tutorials think that everything is trivial. So they omit important details and assumptions and leave everything as exercise to the reader.)

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

I'm wondering about the implementation and performance of nullable types. Is an Int? something like int* which can be compared with nullptr and then accessed via operator*? If so, using it would incur two memory accesses in the worst case: one for the location of this int* and one for the location it points to, plus possibly compare/branch with !!. Does it work like that?

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

    Int? is a class similar to java.lang.Integer whereas Int corresponds to primitive type int. So you get an indirection for Int? but not for Int.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok. So if I use them, I have to be careful about using too many or I could end up torturing my cache. The most important thing I'm asking about is if it's two random memory accesses or something more efficient like allocating an extra bit byte+ and having all information contiguous in memory.

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

The contest is unrated?

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

I have written a Simple Guide for beginners please go through if anyone wants to.

»
9 days ago, # |
  Vote: I like it -22 Vote: I do not like it

Is it unrated?

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

Each time I use JetBrains products I wonder why are they so slow. Any trick how to make it faster for competitive programming?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What part of it is slow?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Building or running in debug mode,

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I find that only first execution is slow, each consecutive is very fast.

        What bugs me is that run window is not focused when the application is run.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That is what it should be like. But I feel like each pressing of debug button rebuilds. Probably, something with project definition, but they should be default...

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I am waiting for the day when "CUSTOM INVOCATION" button will outperform all these slow IDEs))

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

    Buy a modern computer

»
8 days ago, # |
  Vote: I like it +18 Vote: I do not like it

How we will know if we won a kotlin t-shirt

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it
  • »
    »
    8 days ago, # ^ |
    Rev. 3   Vote: I like it +18 Vote: I do not like it
    #include "testlib.h"
    #include <iostream>
    
    using namespace std;
    
    int main(int argc, char *argv[]) {
        int seed = atoi(argv[1]);
        int len = atoi(argv[2]);
        int nwinners = 50;
        rnd.setSeed(seed);
        
        set<int> winners;
        while (winners.size() < nwinners)
            winners.insert(50 + rnd.next(1, len));
        
        for (auto winner: winners)
            cout << winner << " ";
        cout << endl;
    }
    

    Here first argument will be 300 and second argument will be 496. (penalty of winner as seed and total participants except first 50).

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    Assuming 300 = penalty and 546 = total participants, winners are

    52 60 62 69 99 101 113 119 127 130 135 138 159 170 173 178 179 187 193 200 209 215 221 235 264 269 281 296 298 303 341 343 347 354 370 384 387 390 410 415 424 430 454 464 468 469 508 517 529 545

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

       Yay!

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it -26 Vote: I do not like it

         I managed to solve the problem with difficulty because I do not write kotlin I hope to get a T-shirt

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Man, half of the people here don't code in Kotlin in regular life. Nevertheless, these language-restricted rounds still have more or less the same set of winners. I think it's because language-restricted rounds actually measure "how well you solve problems" instead of "how good you know this language". Maybe, just maybe, such rounds are even better than regular rounds in determining how good people are at problem-solving because, you know, fewer people have prewritten code in Kotlin than in C++, fewer people have SublimeText snippets for Kotlin, etc.

          I wonder if maybe some day such rounds will get rated...

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

          It is because you are gray, not because you do not write in kotlin.

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

      If this is true, then thank you tourist for the tshirt. :)

      EDIT — thanks to everyone(including fake ids if any :P) too since it also depends on number of participants xD

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    a

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

How do we know whether we gain or not the T-shirt for solving at least one task?

»
8 days ago, # |
  Vote: I like it +95 Vote: I do not like it
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When loading the page, I am at 112th place. After several page updates, I am at 113th place. T-shirt gets a competitor in 113th place. Can I get a small T-shirt? :)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    How do we know more about getting the shirt?

    I mean, where do we put our ship-address?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      If you go to your profile then settings there is a tab where you can specify your shipping address for t-shirts. Not sure if they are going to send to that address, but it's better to fill it anyway.

»
8 days ago, # |
  Vote: I like it +21 Vote: I do not like it

Rank 62 last time and rank 53 this time. What a pity.

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why Codeforces doesn't support writing main function in a class like Java? :/

  • »
    »
    8 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    See this: https://discuss.kotlinlang.org/t/is-the-main-function-must-be-a-standalone-function/877

    TLDR: Kotlin doesn't natively support static functions in classes, thus the easiest way to define a static function, as the main function is required to be, is to put it in the top level of the file, outside any class declarations. (To the JVM, this is treated as a static function within a static wrapper class called e.g. "ContestKt" if your filename is "contest.kt") There is a way to expose a class function as static to the JVM, but it's kinda ugly, looking something like:

    class Solution {
        companion object {
            @JvmStatic fun main(args: Array<String>) {
                // code goes here
            }
        }
    }
    

    I won't recommend doing this for anything beyond academic purposes.

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

when will be hold Kotlin Heroes: Episode 3?