На олимпиаде Казахстана прошлого года была задача "Количество совместимых чисел", которая сводится к такой: даны 22-битные маски a₁, a₂, ..., a_n (n < 10⁶), нужно посчитать d[m] — количество таких i, что a[i] является подмаской m (т.е. a[i] & m == a[i]).

Официальное решение решает эту задачу так:

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];
		}
	}
}

Пытаясь решить эту задачу самостоятельно, я дошёл до этой идеи, но сразу отбросил, потому что мне показалось очевидным, что она какие-нибудь подмаски будет считать несколько раз. Сейчас я вроде бы почти убедил себя, что этого не происходит, но у всё ещё меня нет интуитивного понимания того, почему это должно работать. Может, это какой-то известный трюк, которого я не знаю? Или может просто кто-нибудь может объяснить логику этого подхода?

Спасибо!

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.

Если вдруг кто упустил, то уже в эту субботу в СПб, Барнауле, Ташкенте, Тбилиси и Алматы откроется XIII ВКОШП, а само соревнование (как и награждение) пройдёт в воскресенье.

Буквально сегодня на сайте олимпиады появилась новость о том, что на олимпиаду можно взять свою клавиатуру (если она подключяется по USB, не является беспроводной и т.п.).

В понедельник, 26 ноября 2012 года также пройдёт командная интернет-олимпиада ИТМО по задачам ВКОШП.

Всем привет!

Обнаружив, что CMS (тестирующая система, которая будет использоваться на IOI'12) имеет открытый исходный код, я решил, что хорошей идеей будет попробовать поставить её себе, чтобы потренироваться на ней ещё до Practice session и возможно даже самому написать для неё патчи и отправить их разработчикам.

Тем, кому интересно, что из этого получилось и/или хочется самому пощупать систему — добро пожаловать под кат.