Friday, May 24, 2024

A return@week

Kotlin Heroes Episode 10 on Codeforces was the main event of last week (problems, results, top 5 on the left, analysis). Only solutions in Kotlin programming language could be submitted. Long gone are the days of IDEA's Java-to-Kotlin converter, at least nobody in the top 20 seems to use it, and I think the Kotlin Heroes series is quite a success in introducing people to Kotlin and getting them to like it. At the same time, Kotlin knowledge is still not at 100% in the community, so other translation tools are on the rise :)

The top 2 were the same as in the previous edition, and they were the only participants to solve all problems. However, this time arvindf232 was faster and earned a well-deserved victory. Congratulations to arvindf232 and tourist on the great performance!

Tourist's wrong submissions on E and F have seriously damaged his winning chances. The wrong submission on E (link, compare to correct) stems from a wrong understanding of an advanced language feature, return@repeat, which turned out to mean continue and not break :) And the wrong submission on F (link, compare to correct) stems from not using a prewritten code library, more specifically a modint class. The winner's submission to the same problem does use prewritten code to deal with modular arithmetics, but interestingly it is not done through operator overloading, but rather through defining new infix operations that also refer to a global variable, leading to weird-looking code like ret[paths] = ret[paths] mp (count mm FACT.choose(options, k-1)), where "mp" and "mm" stand for modular addition and multiplication. arvindf232 or others reading this, what is the reason for this approach?

Thanks for reading, and check back next week!

2 comments:

  1. A prewritten modular arithmetic class could potentially be slower than unboxed operations with Ints, although I hope this is not the case with inline classes. I think arvindf232 implemented ModInt in such a way to avoid strong typing, which is one of the aspects of Kotlin (i.e., you can't compare Int and Long for equality). It could be useful to use Ints from the input or calculated in other parts of the algorithm as ModInts, and this requires explicit conversion, while his approach avoids it.

    ReplyDelete
    Replies
    1. Nice, thanks for the clarification! Reading various sources on the subject, it seems that equality checking is indeed the main/only issue: you can still do things like "inline operator fun Int.plus(modInt: ModInt) = modInt + this" to make "+" work for mixed types, but equality is already defined for Any in Int, and a class method always wins over an extension.

      Delete