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 eatmore 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.
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.
That input In your tutorial is slow, java's tokenizer is much faster though it breaks functional programming principles
You can use java classes in kotlin, see how i use java's tokenizer in kotlin link
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:
PrintWriter version:
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.
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
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.
Will the account with no contests claim T-Shirt?
All contestants who solved at least one task will have a chance to win a t-shirt.
Good time to start learning Kotlin again.
It's astounding how many newly created accounts are registering in the contest. Everything for a t-shirt huh
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...
Few days back I only knew naive C++. CF urged me to learn C++ STL, Python. And now even Kotlin!__
But not java :(
I don't see any restriction for the winners of first Kotlin Heroes. Will t-shirts be different?
We have another set of tasks, so everyone is welcome to join. T-shirts are in the same series, but not the same.
Is Kotlin
IntArray.sort()
O(n^2) complexity? I got TLE here 59869165IntArray
maps to Java'sint[]
, andIntArray.sort()
maps to Java'sArray.sort()
, so yes, it does use the unfortunately hack-vulnerable quicksort. Better to useArray<Int>
orMutableList<Int>
for sortings. (Same goes forLongArray
andDoubleArray
.) Kotlin also supportsList<T>.sorted()
for read-only lists, which will return a new list with the sorting applied.IntArray.sort()
is the same asArrays.sort()
. Java uses quick sort for array of primitive types, and merge sort for array of objects. As we all know quick sort runs inO(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.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.
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 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.
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.
I mean insertion sort is linear for already sorted array
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.
Kotlin seems similar to Java 8?
Pure coincidence.
Is it somewhat similar to C++?
Somewhat to C++, somewhat to Java...
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/
thank you
The correct method to gain upvotes quickly in CF: "Please give me some downvotes."
Can anyone convert this c++ code into kotlin?
Something like this, off the top of my head:
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.
"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.
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 atry
-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 ormax()
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)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.
Kotlin does in fact have special access functions for returning a default value or setting an unset key upon access, e.g.
Map.getOrDefault()
orMap.getOrPut()
. Even arrays and lists havegetOrDefault
/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.Yeah, you want these functions and this behaviour.
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.
If I understand correctly, you never use assertions/throws in your competitive code? Why?
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).
Where can I find the solutions to the practice contest?
BTW, if anyone was wondering you can just type the problem name into google and get the actual problem.
why cf predictor shows rate changing
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) )
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.
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
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.
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.)
I'm wondering about the implementation and performance of nullable types. Is an
Int?
something likeint*
which can be compared withnullptr
and then accessed viaoperator*
? If so, using it would incur two memory accesses in the worst case: one for the location of thisint*
and one for the location it points to, plus possibly compare/branch with!!
. Does it work like that?Int?
is a class similar tojava.lang.Integer
whereasInt
corresponds to primitive typeint
. So you get an indirection forInt?
but not forInt
.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
bitbyte+ and having all information contiguous in memory.The contest is unrated?
It's unrated due to the Kotlin-only restriction.
I have written a Simple Guide for beginners please go through if anyone wants to.
Is it unrated?
Yes, it is unrated.
Each time I use JetBrains products I wonder why are they so slow. Any trick how to make it faster for competitive programming?
What part of it is slow?
Building or running in debug mode,
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.
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...
I am waiting for the day when "CUSTOM INVOCATION" button will outperform all these slow IDEs))
Buy a modern computer
Does not help :-( i am i7 with 16 ram
So, I guess part of the problem was the fact that code files for all problems were in the same module, thus it has to compile multiple files module. When I made one module per project it started to be a bit faster.
How we will know if we won a kotlin t-shirt
In Episode 1 https://codeforces.me/blog/entry/67162?#comment-514253
Here first argument will be 300 and second argument will be 496. (penalty of winner as seed and total participants except first 50).
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
Yay!
I managed to solve the problem with difficulty because I do not write kotlin I hope to get a T-shirt
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...
It is because you are gray, not because you do not write in kotlin.
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
a
How do we know whether we gain or not the T-shirt for solving at least one task?
Our congratulations to the t-shirt winners (top 50 + random 50)!
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? :)
the tshirts are tied by last submission time.
How do we know more about getting the shirt?
I mean, where do we put our ship-address?
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.
I filled in a form with all the needed information as soon as I got the notification. Time passed, I forgot to double-check on this website but it turns out that 2 weeks after that there was a yet-another urgent question regarding my T-shirt size because T-Shirt sizes differ by a whole lot of 5cm from what I specified. This form is no longer available and I guess this is the reason why I'll get no T-shirt. Not that I needed it or anything, but this situation is absurd.
actually i haven't got a t-shirt too despite i filled both forms; so no one has got it still
Did you already get it?
No unfortunately
Rank 62 last time and rank 53 this time. What a pity.
Why Codeforces doesn't support writing main function in a class like Java? :/
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:
I won't recommend doing this for anything beyond academic purposes.
when will be hold Kotlin Heroes: Episode 3?
Has anyone recieved their t-shirt?
No, and we're really sorry about that. T-shirts are still on production stage. :(
The package arrived today. I was thinking I'm still not good enough to get any award, so very happy.
In problem E, at first I got solution using segment tree, but didn't have segment tree library written in kotlin, so wrote sqrt decomposition on the fly and got AC. It was very exciting for me and learning a lot.
Thanks for the great contests and awards.