On April 4th, V (XVI) Volga Region Open Team Student Programming Contest was held in Samara State University. And now, we invite everyone who haven't already participated in the championship to join the Codeforces training contest version on June 21st (11:00 — 16:00 MSK, UTC+3). We believe that participants of any level will find problems that will be interesting for them. The contest will probably be mostly interesting to participants with violet and orange levels (difficulty is 4 stars).

This contest uses ACM ICPC rules.

Please, do not use the Internet, prewritten code and other sources: participants of the championship could not use any of these.

Contest was prepared by Dmitry Matov (Nerevar), Constantine Drozdov (I_love_natalia), Andrew Antipov (Sinner), Andrey Gaidel (Shlakoblock), Elena Rogacheva (elena), Sergei Shteiner (steiner), Alexander Efimov; Igor Baryshnikov (master_j) was of great help in English translation.

ICPC World finals are coming. We've noted that Samara SAU delegation contains five people hardly training playing DOTA 2 in their spare time.

Will there be more fans at the finals? If so, we can get together, play and show that dota is not a game for schoolboys!

On April 6th, III (XIV) Volga Region Open Team Student Programming Contest was held in Samara State University. And now, we invite everyone who haven't already participated in the championship to join the Codeforces training contest version on April 28th (11:00 — 16:00 MSK, UTC+4). We believe that participants of any level will find problems that will be interesting for them. The contest will probably be mostly interesting to participants with violet and orange levels (difficulty is 4 stars).

This contest uses ACM ICPC rules. Use text files input.txt and output.txt instead of stdin/stdout.

Please, do not use the Internet, prewritten code and other sources: participants of the championship could not use any of these.

Contest was prepared by Dmitry Matov (Nerevar), Constantine Drozdov (I_love_natalia), Andrey Gaidel (Shlakoblock), Elena Rogacheva (elena), Sergei Shteiner (steiner), Dmitry Novikov, Alexander Efimov, Gennady Gutman.

After a small discussion, we decided to publish the generator that causes #TLE of HashSet and HashMap in Java.

It is here — http://pastebin.com/qpyNcD3R

The main idea: let's force the hash collections to put all the items in one bucket.

A feature of HashSet and HashMap is a usage of a special linear hash transformation, and then use a reminder hash % bucketsCount as bucket number.

This is some quotes from original Java code:

    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) { 
        return h & (length-1); /*length is a power of 2 --- me*/
    }

The only difficulty is to generate an inverse transform — it is here:

    int hashinv(int h) {
        h ^= (h >>> 4) ^ (h >>> 7) ^ (h >>> 8) ^ (h >>> 14) ^ (h >>> 15)
                ^ (h >>> 18) ^ (h >>> 19) ^ (h >>> 20) ^ (h >>> 21)
                ^ (h >>> 23) ^ (h >>> 26) ^ (h >>> 28);
        return h;
    }

And then, just type the numbers in a such way:

    final int size = 100000;
    int[] s = new int[size];
    for (int i = 0, val = 0; i < size; i++) {
        s[i] = Integer.MAX_VALUE;
        while (s[i] > 1000000000)
            s[i] = hashinv(bitreverse(val++));
    }

Here, bitreverse inverses last 31 bits in number.

This works for Java 6 и Java 7 with almost all standard input transformation (sorting, random shuffling, etc).

Good luck in hacks!