limed's blog

By limed, history, 7 years ago, In English

As Java 9 has been released few days ago, I went through the What's New to see if there is something useful in the context of Competitive Programming. And I didn't find much, just these few enhancements:

  • new static factory methods on the List, Set, and Map interfaces (returning immutable instances of those collections), for example: Set<String> alphabet = Set.of("a", "b", "c");

  • internal String representation as array of bytes (8 bit) instead of array of chars (16 bit) in case the string contains only Latin-1 characters (which is normally the case in Competitive Programming); this would reduce memory consumption almost by half in String problems, and I wonder what would be the impact on performance;

  • JShell (aka REPL in some other languages) for executing small pieces of code / bruteforce solutions (thanks bhishma for suggesting this).

Also, there are some new standard library methods not mentioned in "What's new" (thanks eatmore for pointing this out). Here's what I found:

  • Math.fma(a, b, c) to compute a * b + c on doubles/floats with better performance and precision;

  • A few new Math.multiplyExact/multiplyFull/multiplyHigh methods;

  • Arrays.equals to compare two subarrays;

  • Arrays.compare to compare two arrays/subarrays lexicographically;

  • Arrays.mismatch to compute common prefix length of two arrays.

(Array methods should have efficient implementations using vectorised CPU instructions).

As a personal note, I feel like Java is still light years behind Scala (which unfortunately is broken on CF for 2 months already) for writing CP code, even though both of them run on the same JVM. Just please, don't start language flame wars, unless you have tried both :)

P. S. If someone goes through "What's new" of Java 9 and notices some more relevant enhancements, please post them here. I could have missed something.

Full text and comments »

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

By limed, history, 7 years ago, In English

Few weeks ago, during round #429, I've run into a Runtime Error when submitting any valid Scala solution. Today I've tried to submit some solutions, and had the same issue again (30041665). Also, I found that more Scala users had the same runtime issue in the last few rounds (eg., 29977952, 29706237 and more).

The error message is java.lang.NoClassDefFoundError: scala/App$class. Probably this could be caused by Scala standard library missing from the classpath.

I (and, I believe, other Scala users) would appreciate if this could be fixed. Until then, unfortunately, Scala is not usable on Codeforces :(

Full text and comments »

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

By limed, history, 7 years ago, In English

Thought this would be interesting to many: https://arxiv.org/abs/1708.03486

Norbert Blum

(Submitted on 11 Aug 2017)

Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreevs function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P not equal NP.

Full text and comments »

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