My rating has been in a free fall due to Scala solutions not running in Codeforces for the last couple of contests. Please see:

29977952

29890121

29874042

29999130

They work fine locally and they randomly fail with this error:

java.lang.NoClassDefFoundError: scala/collection/TraversableOnce$class
	at IO.<init>(_849A.scala:188)
	at IO.<init>(_849A.scala:189)
	at IO.<init>(_849A.scala:190)
	at CodeForcesApp$class.main(_849A.scala:16)
	at _849A$.main(_849A.scala:1)
	at _849A.main(_849A.scala)
Caused by: java.lang.ClassNotFoundException: scala.collection.TraversableOnce$class
	at java.net.URLClassLoader.findClass(URLClassLoader.java:381)
	at java.lang.ClassLoader.loadClass(ClassLoader.java:424)
	at sun.misc.Launcher$AppCla...

Can CodeForces please rerun my submissions and update the ratings?

Circular buffers are simple data structures that provide O(1) get, set, append, prepend, clear, dropFirst and dropLast operations. It can be implemented using 2 pointers (start and end) and an array and using modular arithmetics for indexing.

Here is a simple implementation in Java:

class CircularBuffer<T> {
  private T[] array = (T[]) new Object[1<<4];
  private int start = 0, end = 0;

  public T get(int i) {
    assert(0 <= i && i < size());
    return array[mod(start + i)];
  }

  public void set(int i, T elem) {
    assert(0 <= i && i < size());
    array[mod(start + i)] = elem;
  }

  public void append(T elem) {
    if (size() == array.length - 1) resize();
    array[mod(end++)] = elem;
  }

  public void prepend(T elem) {
    if (size() == array.length - 1) resize();
    array[mod(--start)] = elem;
  }

  public void dropFirst(int count) {
    assert(0 <= count && count <= size());
    start += count;
  }

  public void dropLast(int count) {
    assert(0 <= count && count <= size());
    end -= count;
  }

  public int size() {
    return mod(mod(end) - mod(start));
  }

  public void clear() {
    start = end;
  }

  private int mod(int x) {
    return Math.floorMod(x, array.length);
  }

  private void resize() {
    T[] array2 = (T[]) new Object[2*array.length];
    for(int i = 0; i < size(); i++) {
      array2[i] = get(i);
    }
    end = size();
    start = 0;
    array = array2;
  }
}

Source: https://gist.github.com/pathikrit/eac29538af53abf7e827a74e110fb0ac

I reported this bug earlier too: http://codeforces.net/blog/entry/21307

Basically Scala code is compiled against JDK8 but is run on JDK7. I was using TreeSet.getOrDefault() in 21087553 but I got this runtime error (did not get to see the error till contest was over):

java.lang.NoSuchMethodError: java.util.TreeSet.getOrDefault

I had no idea what was wrong with my submission so I submitted again essentially the same code but removed some debug statements in 21087993 and it again got runtime error again from the judge :(

But, then I saw it was failing on test 1 — which is impossible since I run that test myself before submitting!

But MikeMirzayanov had confirmed to me earlier that the bug was fixed:

So I submitted it again but replaced TreeSet.getOrDefault() with TreeSet.get() and it passed!! See: 21088330

Is it possible to recalculate my rating based on my first submission (21087553) of the problem which is indeed correct but was marked wrong because of a bug in CodeForces (which I was told was fixed a year ago)?

If you are binary searching over Ints (or Longs), there is a neat trick you can use to quickly find the answer in exactly 32 (or 64 for Longs) operations. This code is simple to write, less error prone than binary search (off by 1 mistakes) and in practice often faster.

import java.util.OptionalLong;
import java.util.function.LongPredicate;
import java.util.stream.LongStream;

/**
 * Find the largest long that satisfies the predicate f using exactly 64 bit-wise operations: O(64 * O(f))
 *
 * @param f Monotonous predicate
 * @return The largest number that satisfies f
 */
static OptionalLong binarySearch(LongPredicate f) {
    long p = 0L, n = Long.MIN_VALUE;
    for(long t = n >>> 1; t > 0; t >>= 1) {
      if (f.test(p|t)) p |= t;
      if (f.test(n|t)) n |= t;
    }
    return LongStream.of(p, n).filter(f).findFirst();
}

If you only want to search over non-negative numbers, its even simpler (showing with Ints instead of Longs):

static Integer binarySearch(IntPredicate f) {
    int p = 0;
    for(int t = Integer.MIN_VALUE >>> 1; t > 0; t >>= 1) {
      if (f.test(p|t)) p |= t;
    }
    return f.test(p) ? p : null;
}

How does it work: There are only 64-bits in a long. Just toggle them one by one from left to right depending on whether the predicate is satisfied or not.

Exercise for reader: Modify code to search for smallest instead of largest.

Reposted from here:

I was asked this in an interview. I am modifying the question a bit to preserve it from being explicitly Googleable but the gist is:

You are given an N x M grid. Some cells in the grid are "evil" (denoted by number 1) and rest are "good" (denoted by 0). You have lasers positioned across each N rows and across each M columns which when turned on kills all cells in their respective row or column e.g. if you have:

LL L1 L2 L3 L4
L5  0  1  0  0
L6  0  1  0  1
L7  0  1  1  0
L8  0  0  0  0

You can turn on either (L2, L3, L4):

LL L1 L2 L3 L4
L5  0  x  x  x
L6  0  x  x  x
L7  0  x  x  x
L8  0  x  x  x

Or you can turn on (L2, L6, L7):

LL L1 L2 L3 L4
L5  0  x  0  0
L6  x  x  x  x
L7  x  x  x  x
L8  0  x  0  0

A set of lasers turned-on is called "GoodConfig" iff it kills all evil cells. Note you can always turn on all lasers along a row or column and kill everything and it would be "GoodConfig" but turning on lasers is expensive and killing good cells is bad.

1. What is the smallest size of "GoodConfig" i.e. least number of lasers we can turn on till kill all evil cells?

2. What is a "GoodConfig" that minimizes the number of good cells killed?

I realized that part 1 is similar to a step in the Hungarian algorithm but I don't have a good intuition or implementation of it. Part 2 — I have no idea.

Hi guys, I maintain a repository of algorithms in Scala here that you may like: https://github.com/pathikrit/scalgos

Algorithms: https://github.com/pathikrit/scalgos/tree/master/src/main/scala/com/github/pathikrit/scalgos

Unit tests: https://github.com/pathikrit/scalgos/tree/master/src/test/scala/com/github/pathikrit/scalgos

I submitted 16248609 and it failed with a compilation error: Can't compile file: File should contain class/object named as the file.

I could not figure out what was wrong with my submission since it compiled fine locally; so I submitted it again and CodeForces complained that I am trying to submit the same file! So I removed an empty line and submitted it again and 16248804 got accepted!

629A - Дальние родственники и торт was a really unlucky problem for me as I also ran into a surprising Scala issue (besides the one I described above) which gave me a TLE:

1. TLE: 16248545
2. AC: 16248804

I am not sure why, so I asked on StackOverflow: http://stackoverflow.com/questions/35528057/scala-performance-difference-between-nested-for-loops

I suffered from a bug in the setup for Scala in the last round. Although Scala code is compiled against JDK8, it is run using JDK7. I got this as a runtime error (**NOT** compile error) during the contest which puzzled me (ofcourse I did not see the error till after the contest):

java.lang.NoSuchMethodError: java.io.LineNumberReader.lines()Ljava/util/stream/Stream;
	at Scanner.<init>(_591B.scala:73)
	at Scanner.<init>(_591B.scala:66)
	at Scanner.<init>(_591B.scala:67)
	at Scanner.<init>(_591B.scala:68)
	at CodeForcesApp.main(_591B.scala:36)
	at _591B.main(_591B.scala)

Submissions: 13843944 13843313

I was able to eventually figure it out by doing a practice problem and seeing the error and resubmit and get those 2 problems correct but I lost about 45 minutes. What is the best way to report such bugs to Codeforces? Maybe we should document here (http://codeforces.net/blog/entry/79) more clearly what is done for Scala...

In my previous post, I discussed a fast Scanner for Scala.

To benchmark it, I wrote the fastest possible Scanner I could in Java:

package better.files;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.Arrays;

/**
 * Hand built using a char buffer
 */
public class ArrayBufferScanner extends AbstractScanner {
  private char[] buffer = new char[1 << 4];
  private int pos = 0;

  private BufferedReader reader;

  public ArrayBufferScanner(BufferedReader reader) {
    super(reader);
    this.reader = reader;
  }

  @Override
  public boolean hasNext() {
    return pos != -1;
  }

  private void loadBuffer() {
    pos = 0;
    while (true) {
      int i;
      try {
        i = reader.read();
      } catch (IOException e) {
        throw new UncheckedIOException(e);
      }
      if (i == -1) {
        pos = -1;
        break;
      }
      char c = (char) i;
      if (c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != '\f') {
        if (pos == buffer.length) {
          buffer = Arrays.copyOf(buffer, 2 * pos);
        }
        buffer[pos++] = c;
      } else if (pos != 0) {
        break;
      }
    }
  }

  @Override
  public String next() {
    loadBuffer();
    return String.copyValueOf(buffer, 0, pos);
  }

  @Override
  public String nextLine() {
    try {
      return reader.readLine();
    } catch (IOException e) {
      throw new UncheckedIOException(e);
    }
  }

   @Override
  public int nextInt() {
    loadBuffer();
    final int radix = 10;
    int result = 0;
    boolean didRun = false;
    for (int i = buffer[0] == '-' || buffer[0] == '+' ? 1 : 0; i < pos; i++, didRun = true) {
      int digit = buffer[i] - '0';
      checkValidNumber(0 <= digit && digit <= 9);
      result = result * radix + digit;
    }
    checkValidNumber(didRun);
    return buffer[0] == '-' ? -result : result;
  }
  
  private void checkValidNumber(boolean condition) {
    if(!condition) throw new NumberFormatException(String.copyValueOf(buffer, 0, pos));
  }
}

Is this the best I can do?

It is barely faster than Java's StreamTokenizer (NOT StringTokenizer) inspite of being much simpler than it: http://docs.oracle.com/javase/8/docs/api/java/io/StreamTokenizer.html

Java source: https://github.com/pathikrit/better-files/blob/master/benchmarks/src/main/java/better/files/ArrayBufferScanner.java

Other Scanners: https://github.com/pathikrit/better-files/blob/master/benchmarks/src/main/scala/better/files/Scanners.scala

Benchmark results: https://github.com/pathikrit/better-files/tree/master/benchmarks

We all know that java.util.Scanner is slow.

Here is a version in Scala that is idiomatic (you can do all the Collections API e.g. .take, .map, .filter etc) and supports line numbers too and is much faster than the Java Scanner:

import java.io._
import java.nio.file.{Files, Path}
import java.util.StringTokenizer

import scala.io.Codec

/**
 * Scala implementation of a faster java.util.Scanner
 * See: http://codeforces.net/blog/entry/7018
 */
class Scanner(reader: LineNumberReader) extends Iterator[String] with AutoCloseable {
  def this(reader: BufferedReader) = this(new LineNumberReader(reader))
  def this(reader: Reader) = this(new BufferedReader(reader))
  def this(inputStream: InputStream)(implicit codec: Codec) = this(new InputStreamReader(inputStream, codec.charSet))
  def this(path: Path)(implicit codec: Codec) = this(Files.newBufferedReader(path, codec.charSet))
  def this(file: File)(implicit codec: Codec) = this(file.toPath)(codec)
  def this(str: String) = this(new StringReader(str))

  private[this] val tokenizers = Iterator.continually(reader.readLine()).takeWhile(_ != null).map(new StringTokenizer(_)).filter(_.hasMoreTokens)
  private[this] var current: Option[StringTokenizer] = None

  @inline private[this] def tokenizer(): Option[StringTokenizer] = current.find(_.hasMoreTokens) orElse {
    current = if (tokenizers.hasNext) Some(tokenizers.next()) else None
    current
  }

  /**
   * Unlike Java's scanner which returns till end of current line, this actually returns the next line
   * @see line() if you want the Java behaviour
   */
  def nextLine(): String = {
    current = None   // reset
    reader.readLine()
  }
  def lineNumber: Int = reader.getLineNumber
  def line(): String = tokenizer().get.nextToken("\n\r")
  def nextString(): String = next()
  def nextChar(): Char = next().ensuring(_.length == 1).head
  def nextBoolean(): Boolean = next().toBoolean
  def nextByte(radix: Int = 10): Byte = java.lang.Byte.parseByte(next(), radix)
  def nextShort(radix: Int = 10): Short = java.lang.Short.parseShort(next(), radix)
  def nextInt(radix: Int = 10): Int = java.lang.Integer.parseInt(next(), radix)
  def nextLong(radix: Int = 10): Long = java.lang.Long.parseLong(next(), radix)
  def nextBigInt(radix: Int = 10): BigInt = BigInt(next(), radix)
  def nextFloat(): Float = next().toFloat
  def nextDouble(): Double = next().toDouble
  def nextBigDecimal(): BigDecimal = BigDecimal(next())
  override def next() = tokenizer().get.nextToken()
  override def hasNext = tokenizer().nonEmpty
  override def close() = reader.close()
}

Source: https://github.com/pathikrit/ScalaForces/blob/master/src/main/scala/Scanner.scala

Benchmarks: https://github.com/pathikrit/better-files/tree/master/benchmarks