Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

PavelKunyavskiy's blog

By PavelKunyavskiy, history, 21 month(s) ago, In English

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 Nov/07/2022 07:17 (Moscow time) 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.

  • Vote: I like it
  • +377
  • Vote: I do not like it

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it -32 Vote: I do not like it

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)

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +50 Vote: I do not like it

    You may solve these problems even now:

    We will reuse some problems from previous Div3 rounds.

    I wish there were some difficult original problems though...

»
21 month(s) ago, # |
  Vote: I like it +21 Vote: I do not like it

I bet for Errichto

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! Something new.

»
21 month(s) ago, # |
  Vote: I like it +314 Vote: I do not like it

Bring a tourist vs jiangly 1v1 match.

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

    I would pay anything for that. Their fight will be legendary ...

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

    What about tourist vs jiangly vs Benq 1v1v1 match?It will be wonderful!

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How wonderful idea it is, I would pay anything for that.

»
21 month(s) ago, # |
  Vote: I like it +23 Vote: I do not like it

Hail Andrew!

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Ecnerwala will be winner.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it +120 Vote: I do not like it

Is it rated?

»
21 month(s) ago, # |
  Vote: I like it +33 Vote: I do not like it

Epic Kotlin Battles Of History : Andrew ecnerwala Versus Kamiiiiil Errrichtoooo

»
21 month(s) ago, # |
  Vote: I like it +224 Vote: I do not like it

Somehow I still think that tourist will win

»
21 month(s) ago, # |
  Vote: I like it -9 Vote: I do not like it

Wishing everyone positive delta

»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it -29 Vote: I do not like it

    at least you won't RTE due to OutOfBounds that way

    (also JetBrains is an ICPC/Codeforces sponsor as you may already know)

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

    It increases the constant factor and forces you to think more to get rid of the extra logs in complexity.

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

    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?

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

      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.

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

        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.

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

          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

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

            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

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

              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.

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

                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?

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

                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.

                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.

            • »
              »
              »
              »
              »
              »
              »
              20 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                20 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  20 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Afaik not literally, but it's been hyped up in that sense, as not just a good Java replacement but good for anything.

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

            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.

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

              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 -noboundscheck option from the DMD's command line? But you seemed to be in favour of disabling bounds checking for release builds in your older comment.

              • »
                »
                »
                »
                »
                »
                »
                »
                20 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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 -noboundscheck is 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.

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

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  20 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Sorry, what?..

                  Let me make this clear.

                  1. If Codeforces gets an LDC or GDC compiler, I'd love that.

                  2. 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!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  20 months ago, # ^ |
                  Rev. 2   Vote: I like it +18 Vote: I do not like 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

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          Btw, do you think most competitive programmers use address sanitizer by default when testing?

          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.

          just off the box, without the need to set up the correct flags.

          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.

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

            "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

            • »
              »
              »
              »
              »
              »
              »
              20 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

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

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

              • »
                »
                »
                »
                »
                »
                »
                »
                20 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                They simply turned out to be useful in competitive programming environments because you can't change the compilation flags on your own while submitting

                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 once instead 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 support optimize() for anything except O0?), but deals with a lot of situations the language didn't handle.

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

                  I was mainly referring to optimization pragmas when I wrote that comment, I should have been clearer.

                  I've used #pragma once and #pragma omp as 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 ivdep which indicates to the compiler that there are no dependencies that will prevent vectorization of the loop).

    • »
      »
      »
      20 months ago, # ^ |
      Rev. 3   Vote: I like it +13 Vote: I do not like it

      an understandable failure message is always better than undefined behavior

      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.

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Since competitive programming is a mind sport, will someone setup bets for this match?

»
21 month(s) ago, # |
  Vote: I like it +31 Vote: I do not like it

arvindf232 vs Errichto when?

»
20 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can I live-cast this on my stream in spanish?

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

Ez W for ecnerwala

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hail Errichto

»
20 months ago, # |
  Vote: I like it +84 Vote: I do not like it

both on stage

»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

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

    I said it: stop trying to make Kotlin happen, it's not going to happen.

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

      Agree. But don't take it wrong jetbrains, you are known for your awesome IDEs, just don't ruin that.

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

    You don't need to install anything when you have IntelliJ, it's already there.

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

      you don't need to install anything if you have already installed this other thing

»
20 months ago, # |
  Vote: I like it +139 Vote: I do not like it

You can't run dfs, great advertising xd

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

    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.

»
20 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

.

»
20 months ago, # |
  Vote: I like it +70 Vote: I do not like it

Ecnerwala vs Errichto vs Kotlin match, can’t wait to see it!

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I really want to see Jiangly vs. tourist too

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

It would be nice to have acces to the code of ecnerwala and Errichto

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it +55 Vote: I do not like it

    It'll be open soon. Don't use it, please, as an example of good Kotlin code, though :)

»
20 months ago, # |
  Vote: I like it +19 Vote: I do not like it

yooo sick 1v1 contests are happening. when will we see boxing ?

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

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

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it

    TL; DR I replaced all the MutableList<Int> with IntArray and it worked in 880 ms. 180240836

    I feel like kotlin's standard io (readln() and println(), 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 not int, but Integer (int is primitive type, the variables of the type are kept on the stack, and this is way more faster than boxing class Integer, 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 IntArray instead of List<Int>. However, replacing MutableList<Int> (variable sized) with IntArray is a bit more trickier, and I don't know how to get fast Set<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).