Блог пользователя Spheniscine

Автор Spheniscine, история, 5 лет назад, По-английски

I pretty much exclusively use Kotlin for competitive programming, mostly because it's the language I'm currently most comfortable with. Here are some scattered notes and tidbits about my experience which I think might be useful to others; if you have any tips/suggestions, feel free to let me know.

Primer

  • Kotlin has an official primer for competitive programming. However, the IO code suggested there is only so-so; it's definitely better than Scanner, but you definitely can save a lot of runtime in heavy input problems by using the classic Java combination of BufferedReader + StringTokenizer
My current IO template

Useful features

  • A lot less boilerplate than Java. Members are public by default. Type inference means a lot less "Pokémon speak". Variables and functions can be declared straight in the top-level of the file. (basically the equivalent of static functions). Fields have implicit getters and setters that can easily be overridden when necessary.

  • PHP-like string templates, e.g. "$id $cost"

  • Extension functions – syntactic sugar for static functions; gives more natural "afterthought" syntax, as well as allowing direct access to public members of the receiver

  • data classes – basically custom tuples. Allows convenient destructuring declarations too.

  • Has access to the data structures in the Java standard library (TreeMap, HashMap, PriorityQueue etc.), and also can use BigInteger and BigDecimal if needed

  • Functional idioms for collection manipulation – map, fold, filter, etc.

  • Sequences – lazy sequence generators, potentially infinite, has standard collection manipulation functions too. Using the sequence { ... } block function allows building a sequence using a scoped yield(value) function, reminiscent of Python

  • inline classes – allows the creation of a new type that wraps over a base type, but that is represented by an underlying type at runtime. Especially useful for "modulo $$$10^9 + 7$$$" problems, as I keep code for a ModInt class that overloads the arithmetic operators appropriately, but is represented as a plain int in JVM runtime. Keep in mind that they are experimental as of Kotlin 1.3, but that's fine for CP in my opinion

  • unsigned integer types in the standard library that use the inline class feature. Not used very often, but handy if needed

  • inline functions – tells the compiler to inline the function to call sites. Useful for higher-order functions (JVM won't need to create a new object for the lambda) as well as small functions that are called very often; basically, anything you might use a macro for in C++, you probably want to use an inline fun or inline val for

  • tailrec fun – tail recursion optimization

  • run block function – great way to write code that needs to shortcut (e.g. return@run "NO") without having to write a new function and pass every relevant argument

  • functions in functions – functions can be defined within e.g. the main function, so again, no having to pass lots of arguments or global variables. Keep in mind that these are represented as objects during runtime. It's too bad they can't be inline as of yet

Potential pitfalls

  • Generic wrappers for JVM primitive types can cause TLE for some problems. Use primitive arrays (IntArray etc.) whenever possible to avoid this, but see next point

  • Inherits the hack-prone quicksort from Java for primitive arrays. Easiest solution is to use generic arrays or lists instead, but due to the performance benefit of primitive arrays, I've took the trouble to write code that shuffles them randomly before sorting.

  • For Kotlin versions < 1.3.30, there is a bug that will throw an exception when using .asJavaRandom() on instances of kotlin.random.Random, including Kotlin's default instance. Either use Java's own Random class, or steal this wrapper:

class JavaRandom(val kt: Random) : java.util.Random(0) {
    override fun next(bits: Int): Int = kt.nextBits(bits)
    override fun setSeed(seed: Long) {}
}
  • Проголосовать: нравится
  • +70
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

What does "Pokémon speak" refer to?

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Spheniscine (previous revision, new revision, compare).

Added new pitfall due to buggy asJavaRandom() function in STL

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Wonderful post! I was wondering if there's a way compare two different IntArray or ArrayList as we can do in Python. For eg:

list1 = [2, 3]
list2 = [2, 4]
print(list1>list2)
# False
  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    It doesn't look like there are standard library functions to compare lists lexicographically, unfortunately. On the plus side though, you can actually implement the extension function operator fun <T: Comparable<T>> List<T>.compareTo(other: List<T>) and thereby use the comparison operators. (Unfortunately though, since there's currently no way to make List implement Comparable, it can only go one level. It's one of those tradeoffs of having a type system)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

any sample usage/application of your template in a CodeForces problem — http://codeforces.net/contest/1298, perhaps?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Still at the very beginning with codeforces, so maybe I'm not seeing the obvious.

How do you set up your environment to use the testset data provided by codeforces?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hack-prone quicksort from Java

What is this?

.asJavaRandom()

Why do we need to convert Kotlin Random to Java one?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    The default sorting algorithm for primitive arrays is quicksort with deterministic pivot selection, as such an adversarial dataset can be constructed to cause it to run in $$$O(n^2)$$$ time.

    The Java Random is needed for some rare applications, like when generating a random BigInteger.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Is sorting a real issue or rather an unlikely event? Constructing an adversarial dataset for a dumb quicksort with pivot a[(i+j)/2] seems to be a Div1B/C problem, and Java's DualPivotQuicksort seems much much harder to ruin.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        It is very real if you go through the archives for sorting problems. I haven't learned how to hack it myself, but there are generators around. Many problems in the archives either already have an anti-quicksort dataset in its test cases, or had one added there by a hack.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I was comparing the run time of a kotlin solution with a similar java solution. The Java solution took around 1ms whereas kotlin solution took 300ms. Are you aware of the multiplier used for the kotlin solutions?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Codeforces does not have a multiplier implemented (at this point of time). I've not really tried submitting Java solutions to CF before, but I find that for most problems the time limit is not a big issue, especially if you use the IO techniques I've outlined in this article.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can we use chelper plugin for kotlin as well ?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I haven't tried it yet

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Then can you tell me how do you use the same template for every problem? Do you copy the template every time ?

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            The basic template (IO and sorting) I leave in for every problem

            Other things I keep in a project of code snippets that I copy-paste in

            I think I'll give it a try and see if I can work with it; if not I'll stick with what I'm already doing

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.net/contest/1436/submission/96587787 got fst by StackOverflow... How to solve it?,

  • »
    »
    4 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

    I've not tried to solve that problem yet, but larger graphs do have that problem when using recursive DFS. In fact, large-enough graphs (about $$$|V| \geq 10^6$$$ or so) could cause stack overflow even in C++ programs.

    You can either refactor the DFS to be iterative using an explicit stack (ArrayList), or since CF now uses Kotlin 1.4, you can use the DeepRecursiveFunction API, which uses coroutines to simulate a recursive function without using the call stack. I've not tried to use the latter myself however, so I don't know if it's fast enough for this purpose.

    Update: My solution with iterative DFS: 96961954. In general this pattern of iterative DFS (either using the bitwise inverse trick I used, or an explicit visited array) can solve most graph problems of this type where you need to compute the "sum" of each node's subtree, since there isn't much state needed beyond that which can be put in the result arrays. I might make a blogpost about it if I can get my thoughts organized.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you share your modint kotlin class ?