I'm sure most of you know that all mainstream C++ compilers support inline assembly language. But did you know that you can actually embed Python in a similar way?

Here, for instance, I implemented gcd function in Python simply because it's easier and shorter. The rest of the code is in C++: 17084249. (By the way, kudos to Codeforces for correct highlighting of both Python and C++ parts!)

I'm not sure if it can be useful at all, but I thought that it's fun to share. Keep in mind it doesn't work in all compilers though!

Like CHelper for Java, caide automates certain common tasks that you do during programming competitions: parsing, running and debugging problem tests, inlining library code. It currently supports C++ and C# programming languages. The list of supported online judges is here.

Download here. You can also install VS extension directly from Visual Studio.

Documentation:

• command line application (Windows and Linux)
• VS extension
• TC plugin (cross-platform).

Codelite and command line caide in Linux: (full size)

Codelite in Windows: (full size)

Visual Studio:

tl;dr: Install VsCaide extension in extensions manager of Visual Studio 2013.

(NOTE: it's recommended to create caide project from scratch after update: use caide init from command line or "Create caide solution" button in Visual Studio.)

v1.2.1:

• Fix Codeforces contest parser, GCJ, HackerRank
• Support RCC contests, POJ
• C++ inliner: don't remove used typedefs defined at class scope.

v1.2:

• Fix Codeforces parser in russian interface
• C++: Remove inactive preprocessor blocks, unused macros, unused typedefs
• C# support in VS plugin
• Compatibility with CHelper extension (command line only)
• Support Google Code Jam, Russian Code Cup, HackerRank

Currently supported online judges: Codeforces, GCJ, CodeChef, Timus, HackerRank, POJ, RCC. (Topcoder is planned.) Currently supported IDEs: Visual Studio 2013, CodeLite. Currently supported programming languages: C++, C#.

caide automates certain common tasks that you do during programming competitions: parsing, running and debugging problem tests, inlining library code.

caide is inspired by such projects as chelper or jhelper. Its purpose is to automate the following tasks:

• Parsing problem statement and extracting test cases
• Generating solution scaffold
• Inlining library code and preparing a single source file for submission
• Running the tests on your solution
• Debugging the tests

Unlike other projects, caide is designed to support multiple programming languages and IDEs/editors.

caide is split into the following projects:

• libcaide is core command line application implementing all functionality. Windows and Linux are supported. Theoretically, it should also build on OS X, but I don't have access to a Mac.
• VsCaide is caide frontend (extension) for Visual Studio; currently supports only C++ programming language.

Documentation, issue tracker and code: https://github.com/slycelote/caide

Update: Turns out that both C# and Mono actually have the same problem as Java. I don't know C# though, so it would be great if someone reviewed the code of the benchmark (bottom of the post).

Recently I noticed that switching from HashSet to TreeSet in a Java program increased performance by several times. Since it didn't make any sense, I decided to investigate the issue, and here is what I found.

In my program I extracted an arbitrary member from a set in the following manner:

Integer elem = set.iterator().next();
set.remove(elem);

It turns out that implementation of HashSet.iterator() method in Java is poor: it always scans the bucket table from the very beginning. An excerpt from JDK code:

        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

In my situation the total number of buckets was 2¹⁸, and each time a new element was extracted some part of the table had to be traversed to find the first non-empty bucket... you get the idea. As far as I understand, the implementation is the same in Java 6, 7 and 8.

I did benchmarks for C++ and C# as well.

• Visual C++ 2012, Visual C# 2012 and Mono 2.10 all have the same problem.
• g++ 4.6.3 doesn't. Looking at the code, they maintain the index of the first non-empty bucket. In certain situations (e.g. if we have a long sequence of insertions followed by a long sequence of removals) it guarantees that each bucket will be traversed only once.

The code of benchmarks is below. What puzzles me further about Java version is that if HashSet is tested after TreeSet, the performance is even worse than when tested in isolation. I'm using OpenJDK 1.7 if that matters.

import java.util.*;

public class TestSets {
    public static void main(String[] args) {
        testSet(new TreeSet<Integer>());
        testSet(new HashSet<Integer>());
    }

    static void testSet(Set<Integer> set) {
        long start = System.currentTimeMillis();

        final int N = 100000;
        for (int i = 0; i < N; ++i)
            set.add(i);
        for (int i = 0; i < N; ++i) {
            Integer elem = set.iterator().next();
            set.remove(elem);
        }

        long end = System.currentTimeMillis();
        double elapsed = (end - start) * 0.001;
        System.out.println("Elapsed time: " + elapsed + "s");
    }
}

#include <chrono>
#include <iostream>
#include <set>
#include <unordered_set>

template<typename Set>
void testSet() {
    auto start = std::chrono::system_clock::now();

    Set set;
    const int N = 600000;
    for (int i = 0; i < N; ++i)
        set.insert(i);

    for (int i = 0; i < N; ++i) {
        auto elem = *set.begin();
        set.erase(elem);
    }

    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::cerr << "Elapsed time: " << elapsed_seconds.count() << "s\n";
}

int main() {
    testSet< std::set<int> >();
    testSet< std::unordered_set<int> >();
    return 0;
}

using System;
using System.Collections.Generic;

class TestSets
{
	static void testSet (ISet<int> set)
	{
		var start = System.DateTime.Now;
		
		const int N = 50000;
		for (int i = 0; i < N; ++i)
			set.Add (i);
		for (int i = 0; i < N; ++i) {
			var e = set.GetEnumerator();
			e.MoveNext();
			var elem = e.Current;
			set.Remove(elem);
		}
		
		var end = System.DateTime.Now;
		var elapsed = end - start;
		System.Console.Out.WriteLine ("Elapsed time: " + elapsed);
	}
	
	public static void Main (string[] args)
	{
		testSet (new SortedSet<int> ());
		testSet (new HashSet<int> ());
	}
}

(I don't know whether there is an official bug tracker, so sorry for making it a blog post.)

Submission 3748858 is reported as runtime error, while it should be compilation error.

A. Almost Prime

B. Regular Bracket Sequence

C. Parquet

D. Tickets

E. Multithreading

A. You're given a string...

(This FAQ may be outdated. Please refer to official help).

I'm sure we won't need this post after Codeforces comes out of beta, but meanwhile it could be useful :) Feel free to suggest what should be added here.

Competitions: general

Competitions: writing code

Using the site

A. Letter

Petr

• Contest rating: 2046
• Fluent in Java

A. Die Roll