Hello, codeforces.
To unveil the full power of Kotlin and JetBrains tools, as well as their advantages in algorithmic problem-solving, we’ve invited two competitive programming stars to match their skills in solving Kotlin problems on stage at the ICPC World Finals.
Andrew ecnerwala He, one of the top competitive programmers in the world, will compete in a match against Kamil Errichto Debowski, Codeforces "Legendary Grandmaster" and Topcoder "Target." The match will be commentated by none other than Roman elizarov Elizarov, Kotlin Lead Language Designer.
You can join the stream on Kotlin by JetBrains youtube channel at 07.11.2022 07:17 (Московское время) and view submissions in the special Codeforces round Ecnerwala vs Errichto Kotlin Match. Only ecnerwala and Errichto can participate in the round, while you will be able to join as spectators.
We will reuse some problems from previous Div3 rounds. We mostly used round #748. And also, one problem was from round #627. A lot of thanks to MikeMirzayanov vovuh and MrPaul_TUser.
Good luck to both participants, and thanks to MikeMirzayanov for the great codeforces platform.
Will we be able to solve the problems after the contest? (Well, I would've said upsolve, but we technically did not join the contest)
You may solve these problems even now:
I wish there were some difficult original problems though...
I bet for Errichto
Wow! Something new.
Bring a tourist vs jiangly 1v1 match.
I would pay anything for that. Their fight will be legendary ...
What about tourist vs jiangly vs Benq 1v1v1 match?It will be wonderful!
How wonderful idea it is, I would pay anything for that.
Hail Andrew!
Ecnerwala will be winner.
Is it rated?
Epic Kotlin Battles Of History : Andrew ecnerwala Versus Kamiiiiil Errrichtoooo
A man of culture
Somehow I still think that tourist will win
Wishing everyone positive delta
Can someine explain to me how a language that forces bounds checking on every array access is good for competitive programming? Thank you very much
at least you won't RTE due to OutOfBounds that way
(also JetBrains is an ICPC/Codeforces sponsor as you may already know)
It increases the constant factor and forces you to think more to get rid of the extra logs in complexity.
As someone who uses Rust (which does bounds check on every array access), I can tell it is very good for competitive programming! And I never saw a problem, which is solvable in C++, but Rust gets TL.
As for bounds checking — an understandable failure message is always better than undefined behavior, don’t you agree?
An understandable failure message in a submission does no good at all. For locally ran code, C++ does pretty well on that front: address sanitizer + debug flag(s) give you not just the line number of out of bounds access, but a bit of stack trace and also the line number of the corresponding allocation.
Using the production build for debugging is an error (or self-challenge) of the user, not of the language.
Getting RE is always better than getting WA. You can look for specific types of errors or generate random tests locally. Much easier to debug.
Btw, do you think most competitive programmers use address sanitizer by default when testing? Anyway, it is much better to get the line number, stack trace, and all other stuff just off the box, without the need to set up the correct flags.
Getting RE instead of WA at the cost of getting TLE instead of AC if your algorithm is not optimal, but would work in an unsafe language
Okay, don't use it then. There are people who like kotlin/rust/any other programming language for whatever reasons, why are you trying to humiliate their languages?
For example, I like using kotlin, because it makes me feel that it was designed for humans, but that doesn't mean that I will go and laugh at disadvantages of C++ to kotlin
I am not humiliating them, I just challenge their claim that it's a good CP language, for the aforementioned reasons. If a language wants to move in that direction, they should give their users a choice to avoid bounds checking and all other unnecessary stuff.
In my view, a good language for CP should have an unsafe foundation, and the safety we're talking about should always be an abstraction built on top of it, and it should always be optional.
I like that Rust has overflow checks in Debug mode but not in Release. Why not the same logic when accessing arrays?
And yes, there are many things I don't like in C++. Its foundation is great, but its syntax and the standard library are terrible compared to other languages. There should be a langauge designed specifically for CP.
I mean, most of the problems on codeforces can be done in Kotlin, and in many of them the solution in Kotlin looks clearer than the solution in, say C++ or python because of the tools Kotlin provides (I am not a Kotlin expert, so for me these tools are mostly convenient functions for pretty much anything I want to do with basic objects, and these functions are named so that I can guess that they exist by entering what I want to do in the Idea ide). Yes, I have seen problems that I couldn't do in Kotlin due to time limit, and yes, Kotlin probably does a lot of unnecessary stuff that only slows down my solution while doing nothing useful, but does it really make the language bad for CP? And if it does, have Jetbrains claimed otherwise? Only if they advertise it among competitive programmers, to me that doesn't mean that they claim that it is perfect for competitive programming, but that they are popularizing a young language.
Also, as far as I know, Kotlin indeed was not created for CP, but it had a purpose to be a Java-like kinda functional language, probably for android or anything. Have the idea of creating the ultimate CP language been discussed earlier?
D language has nicer syntax for templates and ranges compared to C++. I think that it is very good for competitive programming. D does have arrays bounds checking in debug builds, but omits them in release builds.
There's just one major problem: right now Codeforces offers a pretty bad compiler for D language (a 32-bit DMD). But a 64-bit LDC compiler is necessary to compete on equal footing with C++ and Rust languages.
Gassa or hos.lyric could probably ask Mike to provide a D compiler upgrade.
Anyone that feels humiliated by constructive criticism has bigger problems than competitive programming problems.
My colleagues use Kotlin as a Java alternative and are very happy with it. We also have a C++ engine I'm maintaining. There are no plans to freeze the engine and start using Kotlin for everything new, because performance matters too much and performance critical code tends to be simple enough to implement in C++. These are simply different use cases, which is the norm in software development. Any "my language can do it all better!" claims have been and will be challenged. That's also normal.
Did I miss Jetbrains stating that "their language can do it all better"? If they had, then I, indeed, misinterpreted the original comment of ivan100sic, and the whole discussion makes more sense to me.
Afaik not literally, but it's been hyped up in that sense, as not just a good Java replacement but good for anything.
I'd take that any day.
To me, a solution which is slow but right is worth much more than a solution that is fast but wrong. With a slow solution, I could locate the bottleneck (which is a few percent of the code), and optimize just that. With a wrong solution, the error could be just anywhere in it. In the former case, the way forward is much more deterministic.
A rather common view of a strong competitive programmer seems to be to disregard the human-faced complexity of finding bugs, training themselves to overcome it with their wits and brain. In this view, if you make many bugs, you have to train harder to make less. Yet, a more realistic approach is to embrace that people — including oneself — make bugs, and then look for the features that make them less probable: in the language, tools, coding style, etc. The cost one is willing to pay for that depends on how much they appreciate being helped to code without bugs.
Do you know that your submission 150267074 was likely to TLE if codeforces online judge compiled it with array bounds checking enabled? Should we ask Mike to remove at least the
-noboundscheckoption from the DMD's command line? But you seemed to be in favour of disabling bounds checking for release builds in your older comment.I debug locally, so no: personally, I'm all in favor of testing the release version in the system, as it is now. It seems against the usual competitive programming guidelines to test debug version when
-noboundscheckis available in the language.For people submitting to debug, such option alongside release build may have been nice, much as we have clang++17-diagnostics option for C++. With the current design of compiler list though, looks like it would be too much clutter anyway.
On the other hand, the "every other language is slower than C[++]" mantra doesn't prevent me from accepting 99% of my solutions in D, even with DMD. With the usual guarantees of having a jury solution (de facto C++) at least 2x faster than TL, it's enough for my language as well, even with a suboptimal compiler and for alternative solutions with the intended complexity.
With DMD compiler, I'm having a hard time trying to accept $$$O(n^2)$$$ instead of $$$O(n \log n)$$$ — where GCC's vectorization capabilities shine — but that's it. Would be fine with GDC or LDC compiler as well.
If you enjoy competing while being artificially handicapped, then I suggest you to try CodeChef. CodeChef's GDC compiler is used without any optimization options at all, which results in a nice 3x-6x performance penalty for those, who are looking for an extra challenge.
Still you are not the only D language user on Codeforces. And not everyone wants to be handicapped. Sometimes DMD is very close to LDC, sometimes it's a complete disaster (LDC: 266 ms vs. DMD: 1337 ms). The DMD performance disadvantage typically averages to 30-40%, but 40% is not the upper bound.
Right now it's difficult to recommend D language to new users when both CodeChef and Codeforces offer suboptimal or badly misconfigured compilers.
Sorry, what?..
Let me make this clear.
If Codeforces gets an LDC or GDC compiler, I'd love that.
I don't have a case-in-point to show and tell Mike "see, the current compiler is a complete disaster, here's a better one". Seems like you do — do go on and suggest it!
Obviously I don't have cases too, but I just found one interesting finding: when hos.lyric is solving contests at CF, she uses D for first problems, but for last problems (E,F,...) she is switching to C++. I don't know why — but maybe performance/memory usage could be the issue in those problems for her..
PS Congrats with good results of SPBGU at ICPC
I generate random tests locally independent on what verdict I get.
There's a tiny fraction of situations in which it'll cause a WA instead of RE that's actually leading towards wrong assumptions. Yes, it's a slight improvement in that sense.
There's a lot of such slight improvements but it's very debatable if they're worth focusing on because everything comes with tradeoffs. For example, I can write more cache efficient code automatically now than 4 years ago. What does it give me? Perhaps two more ACs in contest or a bunch of avoided TLEs, but perhaps at the cost of not subconsciously focusing on more important things.
Similarly, every crutch like error messages or sanitizer has a tradeoff of less developing debugging skills and understanding how things work and why they can go wrong the way they sometimes do ("RAII = stack allocation", "return value goes in register" etc). IMO everyone should practice hardcore without debug tools, only compete with them.
In summary, there are big things like learning segment trees that are 100% worth the effort, and lots of tiny ones. You're focusing on one such tiny thing.
Of course not. Most competitive programmers are complete noobs who know next to nothing. Few people know about optimize/target pragmas, much less sanitizer. Few people can write segment trees too.
Now, however, anyone can read this convo and find out that such a thing exists. We learn as we go, about everything.
Through providing libraries for various real life use cases, I found out very painfully that there's no such thing as off the box. Everything involves a bit of effort at the start. With sanitizer too, it's still just a bit of effort like installing the package containing it and copypasting flags.
"Few people know about optimize/target pragmas, much less sanitizer"
Imho pragmas are some shaman-like weird almost redundant tricks while sanitizers are basic life-saving features I can't imagine participating without
Being able to set things like higher optimisation or vectorisation can be pretty important sometimes. (I vastly prefer function attributes since Ofast on whole code can be disastrous compared to Ofast on 4 nested fixed-size loops, but that's a detail.) I actually haven't been using asan until fairly recently and at that point I don't think it gave me all that much compared to learned skills, just less time wasted. I'm glad I developed those skills, would recommend.
As someone who wanted to increase awareness about pragmas, I agree (both about pragmas and sanitizers). The pragmas are nothing but a way to tell the compiler to use certain flags while compiling the file. They simply turned out to be useful in competitive programming environments because you can't change the compilation flags on your own while submitting, so pragmas become useful in providing some control over the compiler.
By the way, I would like to see this changed in a limited manner on Codeforces (similarly, uploading custom libraries) — configurable compilation flags are very cool, but not without downsides — maybe compilation error or some other verdicts need some specific compiler output or program behavior, and allowing compilation with arbitrary flags could make for a DOS attack, like linking statically against huge shared objects.
I believe everyone who writes code should know some basic stuff about their tools to make their life simpler (especially their compiler and what kinds of debugging features it provides).
I've actually found pragmas (or attributes, as I said they're more specific) more useful in real software development than competitive setting. It sometimes turns out that you want to disable a warning in part of a code, or go for
#pragma onceinstead of custom header guards, or do simple multiprocessing with openmp... it can be difficult if you're using different compilers for different targets (did you know clang doesn't supportoptimize()for anything except O0?), but deals with a lot of situations the language didn't handle.I was mainly referring to optimization pragmas when I wrote that comment, I should have been clearer.
I've used
#pragma onceand#pragma ompas well, they're pretty useful. Some other uses a lot of people don't know about (but can be useful) are#pragma pack(for underaligning) and diagnostic pragmas (including message, error and warning pragmas). I haven't really used other pragmas (except#pragma GCC ivdepwhich indicates to the compiler that there are no dependencies that will prevent vectorization of the loop).On the C++ side,
.at(x)actually does check bounds properly, but it's much, much more ugly compared to a pair of square brackets.Since competitive programming is a mind sport, will someone setup bets for this match?
arvindf232 vs Errichto when?
Can I live-cast this on my stream in spanish?
Ez W for ecnerwala
Hail Errichto
both on stage
They are doing contest in Dhaka?
yes, on the stage of icpc
WA on 1, I agree that it's not worth to install kotlin's compiler/interpreter on your machine just for this one contest and nothing more in the future.
I said it: stop trying to make Kotlin happen, it's not going to happen.
Agree. But don't take it wrong jetbrains, you are known for your awesome IDEs, just don't ruin that.
You don't need to install anything when you have IntelliJ, it's already there.
you don't need to install anything if you have already installed this other thing
You can't run dfs, great advertising xd
You cannot run naive dfs in stack (stack size is not big enough by default) but you can easily move it to heap in Kotlin. That requires some more Kotlin knowledge than those guys had and it was not needed in this problem anyway.
.
Ecnerwala vs Errichto vs Kotlin match, can’t wait to see it!
I really want to see Jiangly vs. tourist too
I hope all wanna see that!
It would be nice to have acces to the code of ecnerwala and Errichto
It'll be open soon. Don't use it, please, as an example of good Kotlin code, though :)
yooo sick 1v1 contests are happening. when will we see boxing ?
What's the best Fast I/O template for Kotlin? I tried to check if the performance of 179873022 (2963 ms) can be improved by using Fast I/O from this blog. But the result is still far from perfect: 180214573 (2745 ms). Is this issue not related to slow I/O? Are there any other tricks to speed up Kotlin?
For comparison, here's a pretty much direct line by line conversion of this Kotlin code to C++ with and without the ios_base::sync_with_stdio trick: 180210043 (374 ms) / 180210378 (1169 ms).
TL; DR I replaced all the
MutableList<Int>withIntArrayand it worked in 880 ms. 180240836I feel like kotlin's standard io (
readln()andprintln(), the latter not to be used many times during one run) are fast enough.The real problem is
<Int>substring in the code (i. e.mutableListOf<Int>). In java equivalent it means notint, butInteger(intis primitive type, the variables of the type are kept on the stack, and this is way more faster than boxing classInteger, which is kept on the heap). Generics<...>are meant to work with classes (inheritance and interfaces) and boxing ints slows down the program a lot.One should always use
IntArrayinstead ofList<Int>. However, replacingMutableList<Int>(variable sized) with IntArray is a bit more trickier, and I don't know how to get fastSet<Int>in kotlin (probably don't use sets at all, try segment tree approach for example).On a side note, while competing in kotlin, I store graphs as
List<MutableList<Int>>and it's usually fast enough (at least here, on CF, the time limits are usually soft).