Today I starred a dramatic/pure-adrenaline experience.

It was during TopCoder SRM 646, after a few months of no participation on SRMs, I started fresh, by configuring Greed (arena plugin) from zero on my shiny Mint box. It was 3:00AM 3, 2, 1 ... Go, SRM 646 started.

250 was rather easy I think, I managed to solve it in a few minutes. The 600 problem was another story, the idea was rather standard, compress the coordinates ... and BFS, but the implementation was, without doubt, the most difficult part. I coded and coded, and coded using the old C++ standard with make_pair, long-named iterators and no auto ... I'm quite rusty since I'm using mainly Scala now, and suddenly C++ seemed to be very verbose.

I finished coding 2 minutes before the end, but with only the first test case PASSED, I had no idea, my code was hairy, I double checked, triple checked, but nothing. The adrenaline kept me focused, and in the last 5 seconds I decided to submit with only one test PASSED, yes I know I'm crazy, but I was very confident..., no wait, I wasn't, but something (my internal purely-rational programmer) pushed my to submit my "wrong" solution in the last second, yes, in the last second!!!!. The "Contest ended" message box followed my submission instantly. I felt sad because in such cases the most probable outcome is obvious, but I still had some hope.

The challenge phase started, one by one, many solutions (of red coders) were mercilessly hacked, but not mine, I was intrigued, nearly the end of the challenge phase I suddenly remembered that the Greed tester code runs all the tests in a single run, it does not run your program for each test (I knew it, but I'm rusty). F#!U%*C@#*&%K!!!!!!, all the static variables were filled with garbage after the first test.

I regained confidence, I still had no guarantee at all, I was again in tension. System testing started, and YEEEEEEEEEESSSSSSSSSSSSSS, System Tests Passed on both problems, the adrenaline rush make me feel that I was the smartest human being ever lived. I finished 34th overall, and everything due to my self-confidence. I feel like a boss!!!

I hope that you enjoyed such a large post, it's a lesson about luck (yes, mainly luck), confidence and the risks and rewards that came attached.

Because HR doesn't have a public forum/blog like Codeforces I post this here, anyway the community is shared between both sites.

The issue is with rating calculation on HR. I've participated on 2 contests recently; in the Functional Programming Contest I've got full score 8th place overall and in the Weekly contests full score again 4th place overall, which I consider are quite good results, but my "rating" just increased a few points, and to my surprise I went down in the global Leaderboard, from 163 to 168, how is this possible? I tried to find some information in the Scoring page, but there is no clue about the "weight" of different kinds of contests, eg Functional, 101, 20/20, Weekly .... In Codeforces for a mere 107 place I got +88, which doesn't mean that is better or worse, on Codeforces I remember once that the rating system was changed when tourist got 1st and his rating decreased, indeed there was something wrong with the rating calculation (someone correct me if I'm wrong), TopCoder implemented a quite sophisticated rating system... Could someone explain how the global rating works on HR?

UPDATE: It seems like the global Leaderboard becomes crazy, users are placed multiple times with different ratings.

This is a story about HackerRank engaging contests, and about problem solving in extreme conditions (NEVER, NEVER use phone as a replacement for a computer).

You can skip the problem-related lines... and keep only with the story (there is even a pretty girl).

Here is the P-Sequences problem. The official editorial is here

But my story solving this problem is quite "unique", here we go.

Resumed versions: Given N and P, count how many sequences of N non-negative integers, satisfy that for any pair of adjacent elements, its product is <= P.

Constraints: N <= 10^3 and P <= 10^9.

After reading it, the problem seemed hard, almost instantly I got an O(N*P) algorithm, but no clue about how to improve it.

NOTE: HackerRank gave 24 hours to solve the problem.

Next day I woken up at 7am, and the very first thing that came to my mind was that the number of states with "different" values was only O(sqrt(P)) for a given N, eg. dp[N][P/2 + 1 ... P] contains the same value, the same for dp[N][P/3 + 1 ... P/2] and so on, I was enlighten, but have absolutely no idea how to use or implement it efficiently.

That day I was traveling to Bern (I currently live in Lausanne) to solve important affairs. Anticipating a busy day I left my precious laptop, and take only an old notebook(the one made of paper, NOT the electronic device), a pen and the phone (no laptop, only a phone!!!). Even worse, my girlfriend came with me too, hoping to have a nice couple day... so the little free time I was counting on was almost reduced to zero.

In the 1h:45m that takes the train to get to Bern I sketched a recurrence, and defined a state of the DP as follows:

dp[N][i] = number of ways to build a sequence of N elements, with the last element <= i

dpPover[N][i] = number of ways to build a sequence of N elements, with the last element <= (P / i)

The answer would be dpPover[N][1] (the number of sequences of N elements where the last element is something <= (P / 1))

Then we arrived to Bern, and the time to submit was slowly expiring.

While having lunch at McDonald's I spent like 30 minutes coding my solution, ON THE PHONE!!! and I have to say it in capital letters, it was HORRIBLE, phones are evil machines for programmers. Symbols like []{}¦ were 3 keys away on the touch keyboard ... a really painful experience. Sites like ideone.com doesn't work fine in phones, and HackerRank code editor was also useless. I did all using Jota++ Editor, a simple notepad app. No syntax highlighting, no indentation, testing was almost impossible... When leaving McDonald's my program compiled but was still incorrect. My girlfriend insisted that we should walk and take some pictures, visit the most we could (including the Albert Einstein Museum), and enter in all the stores, so I put the phone on my pocket and follow her, trying to find in my mind what was wrong with my code.

Hours later, we arrived to the Cathedral, and found a nice bank, surrounded by kids, with a beautiful view to the river. My girlfriend was exhausted, so she used me as a pillow, so I continue to think, and finally found the bug, YESSSSS!!!!. I fixed my program and hit submit, and got AC with my girlfriend resting in my legs, the adrenaline rush make me feel that I was the smartest person in the world in that moment (but I'm not). I've solved a really challenging problem using a phone and the day was still a success. I wrote this entry after the OFFICIAL testing, but I was quite confident about it. A phone is a terrible tool for programming, but releases the full power of thinking, of crafting an idea in the best possible way. Here is my final solution, which seems a lot simpler than the official one:

#include <iostream>
#include <cmath>
using namespace std;

const int MOD = 1000000007;
const int SQP = (int)sqrt(1000000000) + 100;
int N, P;
int dp[2][SQP];
int dpover[2][SQP];

int main(){

  cin >> N >> P;
 
  int S = (int)sqrt(P);

  for (int i = 1; i <= S; i++) {
    dp[1][i] = i;
    dpover[1][i] = P/i;
  }

  for (int i = 2; i <= N; ++i){

    int cur = i & 1;
    int prev = 1 - cur;

    dp[cur][1] = dpover[prev][1];

    for (int j = 2; j <= S; j++) {
       dp[cur][j] = (dp[cur][j - 1] + dpover[prev][j]) % MOD;
    }

    dpover[cur][S+1] = dp[cur][P/(S+1)];

    for (int j = S; j > 0; j--) {
        dpover[cur][j] = (dpover[cur][j + 1] + (P/j - P/(j+1)) * 1LL * dp[prev][j]) % MOD;
    }
  }
  
  cout << dpover[N&1][1] << endl;

  return 0;
}

UPD: Added Scala futures approach.

Google CodeJam 2014 is coming, and it will be nice if someone could share a way to run multiple tests concurrently, all programming languages are welcome. I've seen very handy codes in D, but I still use mainly C++, Scala has some nice ways to do it also. Running programs concurrently can be useful in CF also, eg. offline output generation. I'll try to populate this thread with some examples. Right now is up to you.

Updated: 30 December 2013 3:27 CEST (Added a brief introduction to Lambda Functions).

The new C++ standard, also known as C++11 and also as C++0x is here, with some sugars for programming contest. I'll update this thread soon with new contents (and better structure). You can use C++11 on Topcoder, Codeforces, HackerRank ... This thread is based on my own experience, so you don't need to dig on the whole C++11 specification to find some useful feature you can use in programming contests.

The "auto" keyword:

Type inference is included in many modern programming languages, and C++ is not behind, the "auto" keyword works like "var" in C#, it only tells the compiler to infer the type for us: So,

map< string, pair< int, int > > somyLongTypeName = map< string, pair< int, int > >();

Can be shortened to, with no impact on speed, since the type is inferred at compile time:

auto longTypeNamesAreHistory = map< string, pair< int, int > >();

Of course that a typedef could do the same, but using auto is faster (to type).

Personally I think that one of the best use of auto is when dealing with iterators, for example:

for (map< string, pair< int, int > >::iterator it = m.begin(); it != m.end(); ++it)
{
    /* do something with it */
}

Becomes:

for (auto it = m.begin(); it != m.end(); ++it)
{
    /* do something with it */
}

Which is a great improvement, easier to write and read, and to maintain (imagine we change one of the template arguments of m).

Initializer lists:

This is also a nice addition, and makes easier to initialize stl containers, let's a basic example:

vector< int > primeDigits = {2, 3, 5, 7};
vector< string > days = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
pair< int, int > p = {1, 2}; // equivalent to make_pair(1, 2)

Maps also can be initialized:

map< int, string > numeral = {
    {0, "zero"},
    {1, "one"},
    {2, "two"},
    {3, "three"},   
    {4, "four"},
    {5, "five"},
    {6, "six"},
    {7, "seven"},
    {8, "eight"},
    {9, "nine"}
};

Range based for loops:

C++11 also introduced a new way to iterate thourgh STL containers:

The old way (using auto for simplicity):

for (auto it = container.begin(); it != container.end(); ++it)
{
    /* do something with it */
}

Becomes:

for (auto x : container)
{
    cout << x << endl;
}

We can even modify the elements (note the &):

vector< int > numbers = {2, 3, 5, 7};
for (auto& x : numbers)
    x *= 2;

for (auto x : numbers)
    cout << x << endl;

The above should multiply by 2 all the elements of container.

But we can go even further and pythonize the for loops as follows:

First let's define a number_iterator and number_range:

template<typename T>
struct number_iterator : std::iterator<random_access_iterator_tag, T>{
	T v;
	number_iterator(T _v) : v(_v) {}
	operator T&(){return v;}
	T operator *() const {return v;}
};
template <typename T>
struct number_range {
	T b,e;
	number_range(T b, T e):b(b),e(e){}
	number_iterator<T> begin(){return b;}
	number_iterator<T> end(){return e;}
};
/* make_pair like functions for our range type */
template<typename T> number_range<T> range(T e) {return number_range<T>(0, e);}

// inclusive range
template<typename T> number_range<T> range(T b, T e) {return number_range<T>(b, e);}

Now we can do something like:

for (auto i: range(1000))
    sum += i;

or

for (auto i: range(10, 20))
    cout << i << endl;

Nothing to worry about speed, is exactly the same when compiled with -O2 (tested on g++ 4.8), which is logical since all the operations of the iterators are delegated to underlying type T (int or long long). Until now, my experience tell me that the new range for loops are easier to write/read without any speed penalty. Note that this is not so practical since we need to implement our own iterator and range classes, but if we have a pre-written template, the code becomes very clean and readable.

Another common example, (no more -> for (int i = 0; i < G[u].size(); ++i)... :

void dfs(int u, int from) {
    for (auto v: G[u])
        if (v != from)
            dfs(v);
}

But we can go even further (with the help of lambdas) and implement binary search using the well known lower_bound and upper_bound functions:

Let's implement a simple binary search to find the square root:

int findSqrt(int n) {
    int lo = 0, hi = n;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (mid * mid <= n)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return lo - 1;
}

Using our number_iterator and lower_bound the above code becomes:

int findSqrt(int n) {
	int lb = lower_bound(number_iterator<int>(0), number_iterator<int>(n), 0,
		[&] (int value, int /* ignored */ ) {
			return value * value <= n;
		}
	);
	return lb - 1;
}

As you can see, no need to cast (or de-reference) the resulting iterator, we can also use long long (not doubles obviously).

New array type:

C++11 brings a new array type which offer complete integration with the STL (not too useful IMHO), the syntax is verbose for multidimensional arrays, but there is no penalty on speed:

auto arr = array< int, 10 >{5, 8, 1, 9, 0, 3, 4, 2, 7, 6}; // array of 10 ints

sort(arr.begin(), arr.end()); // yes, same as sort(arr, arr + n) for normal arrays

arr[0] += arr[5]; // normal [] indexing

for (auto i: range(arr.size()))
{
    /* do something */
}

auto matrix = array< array<double, 10>, 10>(); // 10 by 10 matrix (not the same as double[10][10])

Initialization can be somehow particular, please refer to this for further details.

Lambda functions:

Before the new standard, C++ used functors, which are classes that simulates functions, still functions were not 1st class constructs. The new standard introduced lambda functions (still not 1st class citizens), and make the use of functions more pleasant than before. Let's see a trivial example:

Generates a permutation sorted by heights[].

auto heights = vector< int >{ ...some values here... };

auto order = vector< int >(heights.size());

for (int i: range(heights.size()))
    order[i] = i;

sort(order.begin(), order.end(),
    [&] (const int& a, const& int b) -> bool {
        return heights[a] < heights[b];
    }
);

See also the binary search implemented using lower_bound in the "Range based for loops" section.

The above is a quite common use case, but one may wonder why use a lambda instead of a simple static function, the reason is quite simple, the cool part is that lambda functions can capture other variables (by value or by reference, is even possible to specify which variables to capture), allowing us to access to all visible variables in the scope. The old style functions can only access global variables. The compiler can infer the return type in most cases. My advice is to avoid recursive lambda functions. Lambdas are a huge advance, but definetely not the same as in functional languages were functions are real 1st class constructs.

C++

for_each(v.begin(), v.end(),
    [&] (int x) {
        cout << x << endl;
    }
)

Scala

v foreach println

TODO: Better/more examples

Move semantics:

What is it and how it works?

C++03 and previous standards had a serious penalty when returning non-pointer values, eg. vector< int >, map< string, int >, string?... since the whole value should be deep-copied by value, move semantics is an optimization that avoid the copy of the whole structure and integrates flawlessly to existing code. To explain better how it works (without entering in technical details) let's try with a concrete example, let's assume we are returning a vector< int > , instead of copy the vector when returning, it just "moves" (with the help of some additional construct) what we are returning, the "move" is achieved by copying only the necesary internal "data" of the vector, which consist in a pointer and a integer (size), that way the whole data is NOT copied, only the necessary to have. Note that "move" is different from copy, it just "moves" cleverly what is really important, resulting in a considerable boost. So you can safely return vectors, maps, strings with a no performance overhead in a more natural way that using pointers which can be harder to code, debug ...

Soon, benchmarks using the new move semantics feature...

More is coming, lambdas, benchmarks, regex, new pseudo-random number generators, bye bye rand() ...

For many years competitive programming have follow the old "sequantial" style, where a program is just an ordered sequence of instructions executed in a deterministic way, one after the other.

In the present, processors have reach the maximum clock speed (a least the current technology leaders no longer focuses on faster, but multi-core processors). There is a funny upper bound: Lets suppose that a processor cycle takes the same time that light takes to travel from one side of the processor to the other (square processor), then to achieve 3Ghz the processor (square side) should be smaller than 30 cm, not very tight, but enough to worry. There is also the (theoretical) physical limit of 12nm for the manufacturing process, most advanced processors today are built with 22nm technology (very close too). Today, the industry tries to overcome the processing speed limits with concurrent, multi-threaded programs. "Functional" languages are becoming popular because it's "scalability".

The question is, does competitive programming should keep the old format, or maybe in a not too far future, parallel programs would become the standard?

Right now write a multi-threaded algorithm is by far more painful than the good old sequential way, there are a lot of approaches, different languages provides different frameworks, libraries, or just doesn't.

Maybe competitive programming could enable some multi-threading capabilities, but that would be unfair with older (or not so well supported languages). Java is 2 or 3 times slower than C++, what if we could use 2 threads in Java?.

The ideal would be that our programs could be coded in a sequential manner, and compiled/executed in a multi-threaded one, sadly the technology of today imposes a barrier; writing parallel programs requires a change (often introducing additional complexity) in the sintaxis, or the use of some obscure frameworks ...

We all hope that competitive programming would stay as a pilar of tomorrow technology and development and not as a divergent branch. As happened with Formula 1 which is becoming less and less important to common cars development(taken from here), or bodybuilding (drugs, pills, steroids...) in the case of physical health (fitness).

After seeing CHelper plugin in action, I decided to write a clone for Eclipse (now for Java, maybe C++ later); but soon I realize that Eclipse JDT API is verbose and overcomplicated for a beginner. I have already implemented a rude "Inline Code" function that works fine (JDT API isn't evil after all) but I still have problems with Eclipse integration. If there is someone interested (maybe with some Eclipse plugin development experience, but not a must), please leave a comment, innovative ideas are also appreciated. I will submit the code to GitHub as soon as I make some cleanup.

I have tried many ways to compete, in a fast and painless way, from using a simple text editor and a console, Geany, DevCpp++ (I love this one), Visual Studio, and finally Eclipse. Eclipse supports Java, C++ and is powerful enough for my needs. "Workspaces" were a very painful way to organize all my stuff, until I discover working sets. I also found EclipseCoder wich is very nice for Topcoder SRMs. So if you use or know about some useful tricks, plugins for Eclipse that makes your contestant life easier, then share it here.

This is a simple, bus fast implementation, it builds both, the suffix array, and the LCP (Longest Common Prefix) table. Have fun with it.

/*
Suffix array O(n lg^2 n)
LCP table O(n)
*/
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

namespace SuffixArray
{
	const int MAXN = 1 << 21;
	char * S;
	int N, gap;
	int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];

	bool sufCmp(int i, int j)
	{
		if (pos[i] != pos[j])
			return pos[i] < pos[j];
		i += gap;
		j += gap;
		return (i < N && j < N) ? pos[i] < pos[j] : i > j;
	}

	void buildSA()
	{
		N = strlen(S);
		REP(i, N) sa[i] = i, pos[i] = S[i];
		for (gap = 1;; gap *= 2)
		{
			sort(sa, sa + N, sufCmp);
			REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
			REP(i, N) pos[sa[i]] = tmp[i];
			if (tmp[N - 1] == N - 1) break;
		}
	}

	void buildLCP()
	{
		for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1)
		{
			for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];)
			++k;
			lcp[pos[i]] = k;
			if (k)--k;
		}
	}
} // end namespace SuffixArray

Another using hashing

namespace HashSuffixArray
{
	const int
		MAXN = 1 << 21;

	typedef unsigned long long hash;

	const hash BASE = 137;

	int N;
	char * S;
	int sa[MAXN];
	hash h[MAXN], hPow[MAXN];

	#define getHash(lo, size) (h[lo] - h[(lo) + (size)] * hPow[size])

	inline bool sufCmp(int i, int j)
	{
		int lo = 1, hi = min(N - i, N - j);
		while (lo <= hi)
		{
			int mid = (lo + hi) >> 1;
			if (getHash(i, mid) == getHash(j, mid))
				lo = mid + 1;
			else
				hi = mid - 1;
		}
		return S[i + hi] < S[j + hi];
	}

	void buildSA()
	{
		N = strlen(S);
		hPow[0] = 1;
		for (int i = 1; i <= N; ++i)
			hPow[i] = hPow[i - 1] * BASE;
		h[N] = 0;
		for (int i = N - 1; i >= 0; --i)
			h[i] = h[i + 1] * BASE + S[i], sa[i] = i;

		stable_sort(sa, sa + N, sufCmp);
	}

} // end namespace HashSuffixArray