I stumbled upon a problem that can be reduced to the following: given 22-bit masks a₁, a₂, ..., a_n (n < 10⁶), calculate d[m] = the number of i such that a[i] is a submask of m (i.e. a[i] & m == a[i]).

The jury solves it like this:

for (int i = 0; i < n; i++) {
	d[a[i]]++;
}

for (int i = 0; i < 22; i++) {
	for (int mask = 0; mask < (1 << 22); mask++) {
		if ((mask & (1 << i)) == 0) {
			d[mask | (1 << i)] += d[mask];
		}
	}
}

I came up with a similar idea while trying to solve the problem myself, but discarded it immediately because I felt like it ought to double-count some submasks. I seem to have managed to convince myself that it doesn't, but I still don't have an intuitive understanding for why this approach works. Is this some kind of a trick that I don't know? Or perhaps somebody could just explain the reasoning behind this solution to me?

Thanks!

Rules

The draft for this year's rules is available on the competition website.

As it is highlighted, there are two important changes. First of all, it is officially confirmed that Java is among the languages that can be used at IOI 2015. Secondly, since the JVM uses threads "under the hood", threads are now allowed for submissions in any programming language, but the runtime of a solution is counted as the sum of the runtime of all threads.

I don't think that these changes are really significant to any participants not using Java, because there is no point in using threads if the runtime for each thread is counted separately.

The rules promise "generous time limits", which is interesting, because experience shows that Java solutions tend to be slower even when simple wall time is considered, but counting all the JVM threads separately could result in an even more significant slowdown (compared to other languages).

I'm a little bit concerned that this might mean that we're going to see 20s time limits again (and, consequently, long testing queues, just like during IOI 2013). This happened at the Baltic Olympiad in Informatics this year, where the jury had "optimal" Java solutions working for ~10-15s on maxtests, while C/Pascal solutions spent less than 0.5s, and the TLs were nevertheless set at around 20s (which did make feedback unavailable for a short period of time during the contest, but the jury dealt with it quickly).

Another change in rules which surprised me a bit is that the graders are not guaranteed to use the same hardware as contestants' machines. But then again, with full feedback on 100 submissions per task, perhaps this is not a very serious issue.

Syllabus

The IOI syllabus is a document describing topics (most importantly, algorithms) which IOI participants are expected to know, as well as those that must not be necessary to solve an IOI task.

The new version of the IOI syllabus is already available, and a list of changes should be available soon on misof's IOI Syllabus page.

Meanwhile, most of the changes in the syllabus appear to consist of moving stuff from "Explicitly excluded" to other parts of it, most often "Excluded, but open to discussion". I understand this new category as "these are still excluded, but we should consider including them in IOI 2016 or later", although one should be cautious with this, since the syllabus is not binding for the task authors anyway, so, if someone comes up with a really cool task concerning an excluded topic, it could theoretically be allowed, especially if the topic is "open for discussion".

Another interesting change is that planar graphs were moved from "explicitly excluded" to "included, not for task description", although planarity testing is still excluded. Bipartite matching was also moved from "explicitly excluded" to "included, not for task description", and maxflows and strongly connected components are now "excluded, open for discussion". Balanced binary search trees are now included, and string hashing is "excluded, but considering inclusion".

I hope that this overview of the changes will be useful to other IOI participants (or teachers, or spectators), and I'm looking forward to hearing more information from the organizers.

The changes in the syllabus seem to reflect the fact that with every year, more and more algorithms are becoming "widely known", and the olympiad organizers are trying to reflect this, which means that the olympiad is getting harder over time. Perhaps the organizers have decided that now is the right time to formalise this by including more advanced algorithms in the syllabus (as hinted by the results of the participant surveys in 2013 and 2014). However, at this particular moment, most of the changes seem to be in the "excluded, but open for the discussion" category, and it is certain that many discussions will be held on this topic, both at IOI and outside. Perhaps a part of this discussion might happen right here, on Codeforces.