Автор JetBrains, 3 недели назад, ,

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.

• +104

 » 3 недели назад, # | ← Rev. 2 →   +7 That input In your tutorial is slow, java's tokenizer is much faster though it breaks functional programming principles
•  » » 3 недели назад, # ^ | ← Rev. 2 →   +9 You can use java classes in kotlin, see how i use java's tokenizer in kotlin link
•  » » » 3 недели назад, # ^ | ← Rev. 7 →   +12 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 IrrigationThere's also the classic INTEST and INOUTTEST from SPOJMy 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 
•  » » » » 3 недели назад, # ^ |   +6 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.
•  » » » » » 3 недели назад, # ^ |   0 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
•  » » » » » » 3 недели назад, # ^ |   0 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 недели назад, # |   +8 Will the account with no contests claim T-Shirt?
•  » » 2 недели назад, # ^ |   +3 All contestants who solved at least one task will have a chance to win a t-shirt.
 » 3 недели назад, # |   +6 Good time to start learning Kotlin again.
 » 3 недели назад, # |   +3 It's astounding how many newly created accounts are registering in the contest. Everything for a t-shirt huh
•  » » 3 недели назад, # ^ |   +25 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...
 » 3 недели назад, # |   +17 Few days back I only knew naive C++. CF urged me to learn C++ STL, Python. And now even Kotlin!__
•  » » 3 недели назад, # ^ |   0 But not java :(
 » 3 недели назад, # |   0 I don't see any restriction for the winners of first Kotlin Heroes. Will t-shirts be different?
•  » » 2 недели назад, # ^ |   +30 We have another set of tasks, so everyone is welcome to join. T-shirts are in the same series, but not the same.
 » 3 недели назад, # | ← Rev. 3 →   +16 Is Kotlin IntArray.sort() O(n^2) complexity? I got TLE here 59869165
•  » » 3 недели назад, # ^ | ← Rev. 6 →   +11 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 or MutableList for sortings. (Same goes for LongArray and DoubleArray.) Kotlin also supports List.sorted() for read-only lists, which will return a new list with the sorting applied.
•  » » 2 недели назад, # ^ |   0 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.
•  » » » 2 недели назад, # ^ | ← Rev. 3 →   0 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.
•  » » » » 13 дней назад, # ^ |   0 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.
•  » » » » » 13 дней назад, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » 13 дней назад, # ^ |   0 I mean insertion sort is linear for already sorted array
•  » » » » » » » 13 дней назад, # ^ | ← Rev. 4 →   0 Oh. In that case it's better than pick-first quicksort because it isn't consistently picking the worst pivotsUpdate; 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.
 » 3 недели назад, # |   0 Kotlin seems similar to Java 8?
•  » » 2 недели назад, # ^ |   +70 Pure coincidence.
•  » » » 2 недели назад, # ^ |   0 Is it somewhat similar to C++?
•  » » » » 2 недели назад, # ^ |   0 Somewhat to C++, somewhat to Java...
•  » » » » 13 дней назад, # ^ |   +1 Checkout this presentation from the lead language designer is if you are curison on where Kotlin language features came from: https://2018.geekout.ee/andrey-breslav/
•  » » » » » 11 дней назад, # ^ |   0 thank you
 » 2 недели назад, # |   -102 The correct method to gain upvotes quickly in CF: "Please give me some downvotes."
 » 2 недели назад, # | ← Rev. 3 →   +7  mapmp; mp[2]=3; mp[2]--; if(mp[2]>0) cout<<"yes"; else cout<<"no"; Can anyone convert this c++ code into kotlin?
•  » » 2 недели назад, # ^ |   +4 Something like this, off the top of my head: val mp = mutableMapOf() 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.
•  » » » 2 недели назад, # ^ | ← Rev. 2 →   -21 "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.
•  » » » » 2 недели назад, # ^ | ← Rev. 3 →   0 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)
•  » » » » » 2 недели назад, # ^ |   0 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.
•  » » » » » » 2 недели назад, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » » 2 недели назад, # ^ |   0 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.
•  » » » » » » 2 недели назад, # ^ |   +3 If I understand correctly, you never use assertions/throws in your competitive code? Why?
•  » » » » » » » 2 недели назад, # ^ |   +16 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).
 » 2 недели назад, # |   +6 Where can I find the solutions to the practice contest?
•  » » 2 недели назад, # ^ |   0 BTW, if anyone was wondering you can just type the problem name into google and get the actual problem.
 » 2 недели назад, # |   0 why cf predictor shows rate changing
•  » » 2 недели назад, # ^ | ← Rev. 2 →   0 I think because it works on your rank, points .. so whenever a contest has a rank and points it will work ( Idk )
 » 2 недели назад, # |   0 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) )
•  » » 2 недели назад, # ^ |   0 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.
•  » » » 2 недели назад, # ^ |   -8 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
•  » » » » 2 недели назад, # ^ |   +3 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.
•  » » » » » 2 недели назад, # ^ |   0 Thx, that was very helpful
•  » » 13 дней назад, # ^ | ← Rev. 2 →   +2 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.)
 » 2 недели назад, # |   0 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?
•  » » 13 дней назад, # ^ |   +18 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.
•  » » » 13 дней назад, # ^ |   0 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.
 » 2 недели назад, # |   0 The contest is unrated?
•  » » 13 дней назад, # ^ |   +17 It's unrated due to the Kotlin-only restriction.
 » 2 недели назад, # |   0 Надеюсь не взломают)
 » 13 дней назад, # |   +16 I have written a Simple Guide for beginners please go through if anyone wants to.
 » 13 дней назад, # |   -22 Is it unrated?
•  » » 12 дней назад, # ^ |   0 Yes, it is unrated.
 » 12 дней назад, # |   +8 Each time I use JetBrains products I wonder why are they so slow. Any trick how to make it faster for competitive programming?
•  » » 12 дней назад, # ^ |   0 What part of it is slow?
•  » » » 12 дней назад, # ^ |   0 Building or running in debug mode,
•  » » » » 12 дней назад, # ^ |   0 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.
•  » » » » » 12 дней назад, # ^ |   0 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...
•  » » 12 дней назад, # ^ |   +14 I am waiting for the day when "CUSTOM INVOCATION" button will outperform all these slow IDEs))
•  » » 12 дней назад, # ^ |   +3 Buy a modern computer
•  » » » 12 дней назад, # ^ |   0 Does not help :-( i am i7 with 16 ram
 » 12 дней назад, # |   +18 How we will know if we won a kotlin t-shirt
•  » » 12 дней назад, # ^ | ← Rev. 2 →   +11
•  » » 12 дней назад, # ^ | ← Rev. 3 →   +18 #include "testlib.h" #include 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 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).
•  » » 12 дней назад, # ^ |   +35 Assuming 300 = penalty and 546 = total participants, winners are52 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
•  » » » 12 дней назад, # ^ |   +16 Yay!
•  » » » » 12 дней назад, # ^ |   -26 I managed to solve the problem with difficulty because I do not write kotlin I hope to get a T-shirt
•  » » » » » 12 дней назад, # ^ |   0 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...
•  » » » » » 9 дней назад, # ^ |   +5 It is because you are gray, not because you do not write in kotlin.
•  » » » 12 дней назад, # ^ | ← Rev. 2 →   +2 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
•  » » 12 дней назад, # ^ | ← Rev. 2 →   +4 a
 » 12 дней назад, # |   +7 How do we know whether we gain or not the T-shirt for solving at least one task?
»
12 дней назад, # |
+95
•  » » 12 дней назад, # ^ |   0 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? :)
•  » » » 12 дней назад, # ^ |   0 the tshirts are tied by last submission time.
•  » » 12 дней назад, # ^ |   +14 How do we know more about getting the shirt?I mean, where do we put our ship-address?
•  » » » 12 дней назад, # ^ |   +20 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.
 » 12 дней назад, # |   +21 Rank 62 last time and rank 53 this time. What a pity.
 » 12 дней назад, # | ← Rev. 2 →   0 Why Codeforces doesn't support writing main function in a class like Java? :/
•  » » 11 дней назад, # ^ | ← Rev. 3 →   0 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) { // code goes here } } } I won't recommend doing this for anything beyond academic purposes.
 » 8 дней назад, # |   +40 when will be hold Kotlin Heroes: Episode 3?