Hello, Codeforces!

We are glad to announce that on 4th of June at 19:30 MSK Codeforces Round #306 will be held. Authors of this contest are me (Adilet Zhaxybay) and Timur Sitdikov (Timur_Sitdikov). The round will be rated for the second division, however, participants from the first division can, as usually, participate in it unofficially.

We want to thank all the people, who helped us to prepare the contest: Max Akhmedov (Zlobober), who helped us with the problems, Bekzhan Kassenov (BekzhanKassenov) and Sergey Lazarev (SergeyLazarev), who tested the round, and Maria Belova (Delinur), who translated problem statements. Also we want to say great thanks to Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon.

By the way, as far as we know, Timur_Sitdikov is the first participant from Uzbekistan, who took part in the preparation of Codeforces round. We hope that everything will go well :)

Good luck to all!

UPD The scoring will be dynamic

UPD2 Editorial can be found here

UPD3 Congratulations to winners!

1. mff

2. I_Love_Nodir.Daminov

3. tun

4. I_love_Ngoc_cmn_Thuy

5. goodhope

Round is over, thanks to everybody, who took part in it!

About two months ago we ran another regional intercollegiate team contest. The corresponding gym contest on Codeforces will be held on Sunday, June 7, 2015, at 13:00 UTC +3:00.

Contest was prepared by Sinner, dalex, Slamur. Also special thanks to craus, Shlakoblock and I_love_natalia.

Contest will be available on this page: Codeforces Gyms

The list of our previous contests:

• 2012, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2013, VI Samara Regional Intercollegiate Programming Contest
• 2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2014, VII Samara Regional Intercollegiate Programming Contest
• 2014, Samara SAU ACM ICPC Quarterfinal Qualification Contest

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.

Hello, Codeforces!

As you know the Linux package managers make life easier for users and administrators. In the Windows world, this is much worse, although there are some tools (in Windows 10 it will be much better): nuget, chocolatey, wpkg and others.

Maintaining Codeforces testing servers, computers of Programming Competitions Training Center of Saratov SU, installing workstations for different olympiads I finally got tired to write a variety of bat-files and decided to regularize the process.

Chocolatey makes good help, but in the details it turned out that it can't used in some cases: you can not specify the installation directory, there is no support for private repositories, lack of some packages, Chocolatey packages do not contain installers but only links for them (if package's official is down, one can't install the package).

That's why, in December 2014, I spent out several evenings to work on a package manager most convenient for our purposes (called PBOX, reads like a pi-box). I'm considering using PBOX to install specific software for Codeforces (concrete compilers and tools), but for programs of general purpose it is good idea to use Chocolatey.

In the coming months all the Codeforces testing servers (and many other computers of the CS department of Saratov State University), I plan to reinstall, and use in particular PBOX.

I have little use it for personal purposes, it seems to me, PBOX may be useful to someone from Codeforces users. The site http://pbox.me has usage examples. Below are a few explanations.

Installation

Visit http://pbox.me and in the administrative Windows console (search for cmd.exe, get the context menu by right mouse button, select Run as administrator) run the code from the website home page. PBOX written in Java, if you're not have it, then it will download JRE automatically. By the way, every time you start PBOX, it will try to self-update, so forget about updating it manually.

I usually turn off UAC, if you do not want you will always need to use administrative console. You can disable UAC by typing pbox -uac.

Usage

Do you want to install exactly the same g++ as Codeforces has? Just run pbox install mingw-tdm-gcc. It will install it to %HOMEDRIVE%\Programs\mingw-tdm-gcc (by default), add to PATH some directories (including MSYS), add environment variable MINGW_HOME.

Generally, to see exactly what will happen on installation simply visit the site to find the package and click Show pbox.xml.

For now PBOX has only 73 packages. Visit http://pbox.me/packages to explore them.

I like the collection of useful utilities called tools, so just run pbox install tools to install sysinternals tools, windows resource kit, support tools, and others like curl, wget, imdisk (add all of them to PATH). BTW, useful utility runexe.exe will also be installed: it is good to run processes and see time/memory usage.

Most compilers and tools will be installed to C:\Programs (actually to %HOMEDRIVE%\Programs). Quite convenient to have a path to them short and with no spaces unlike "Program Files".

You can use additional options like pbox install far --homedir=C:\Far --arch=32 --version=3.0.4040. To uninstall a package you can run: pbox uninstall far. Here are more examples of usage:

Download a package and explore it

It is really easy. Just try: http://repo.pbox.me/1.0/jdk8/1.8.0_45/jdk8$1.8.0_45.pbox.7z

Source code

Visit: https://github.com/MikeMirzayanov/pbox

Codeforces round #305 is gonna take place soon and I'm the writer.

After my previous contest that many people think it was a hard contest, I prepared an easy contest to cheer you up!

I want to thank Haghani for testing this round, Zlobober for help me prepare this round and his great advises, Delinur for translating problem statements into Russian, mruxim and Yasser Ahmadi Phoulady (Rasta) for their advises and ideas, HosseinYousefi for helping me choose legends and graphics and MikeMirzayanov for great Codeforces and Polygon platform and guys from Physics Olympiad that kept disturbing me while preparing this round.

This is my second official round and I hope you enjoy it.

The main character of this round is gonna be Mike (I didn't say MikeMirzayanov :D).

Also you'll meet Xaniar and Abol.

I wish you all Successful hacks and Accepted solutions and high ratings.

Scoring will be posted soon.

GL & HF!

UPD: Scoring is:

• Div.2: 500-1000-1750-2000-2750
• Div.1: 750-1000-1750-1750-2500

UPD2: Due to technical reasons we moved the round by 5 minutes.

UPD3: Contest has just ended. You can find the editorial here.

UPD4: System testing is done.

Congratulations to the winners, specially dreamoon_love_AA that got to his goal !

Div.1 winners:

1. dreamoon_love_AA
2. HYPERHYPERHYPERCUBELOVER
3. jqdai0815
4. YuukaKazami
5. subscriber

Div.2 winners:

1. fromWork
2. IloveGoodness
3. norge
4. rumman_sust
5. williamzpf

See you in the next rounds.

This is my first attempt at writing something useful, so your suggestions are welcome.

Most participants of programming contests are familiar with segment trees to some degree, especially having read this articles http://codeforces.net/blog/entry/15890, http://e-maxx.ru/algo/segment_tree (Russian only). If you're not — don't go there yet. I advise to read them after this article for the sake of examples, and to compare implementations and choose the one you like more (will be kinda obvious).

Segment tree with single element modifications

Let's start with a brief explanation of segment trees. They are used when we have an array, perform some changes and queries on continuous segments. In the first example we'll consider 2 operations:

1. modify one element in the array;
2. find the sum of elements on some segment.

I've just discovered this question on Quora: What is the story behind your username at CodeForces?. I guess it'd be pretty interesting to hear stories from top participants. For instance, my handle's history is already described there.

This blog is dedicated to everyone who don't have Quora account, so you can share your histories and comments here.

I personally would love to hear stories from tourist, rng_58 and YuukaKazami from current top-10.