Hello!

Codeforces never sleeps, and I am going to tell you about our recent updates which weren't announced yet.

Testlib

• testlib moved to GitHub, and the version 0.9.9 with C++11 support has been released.

Polygon

• Added basic support for test groups. Now you can specify group for each test, run invocations by test groups, and you can view summary for each group on the invocation page. If group is specified for a test, it will be added to the problem descriptor (i. e. <test cmd="gen 1 2" group="testGroup" method="generated"/>).
• You can now view problem statements and validator for a problem/contest on the same page. This makes finding mistakes in translations and in validator much easier (before you had to open them on separate tabs and switch between them, which is not comfortable). On the problem statements page the "Review" link has been added:
  
  On the contest page the corresponding link appears in the sidebar:
  

Codeforces

• Missing an announcement during contest is now even harder — messages additionally are showed using Notification API.
• Fixed a bug in API: in contest.hacks method defender and hacker were confused.
• Fixed a bug about status filter reset. This was happening sometimes when request went to another Codeforces server.
• Fixed a bug about local storage overflow. If you had a problem with local storage overflow, you had to run localStorage.clear(); in browser console. Now Codeforces uses local storage more carefully.
• Syntax is now highlighted when you are hacking:
  
• Invisible characters are now shown when you view a submission. Before it was confusing why you get WA:

Before	Now

• You don't have to upload images to a third-party site anymore, you can do it while editing a topic. Right under the topic content you can select one or more images, for each of them there will be a link generated which you can use to insert it into the text:
  
• Improved topic categorization, for example soon you will not have to search for Codeforces important materials (documentation, rules, etc.) in blogs, they will be structured and available on a special page.
• Implemented a feature to add rights to edit the topic to a list of users. For now this opportunity will be available for reputable users, who will be able to edit topics with documentation, tutorials and similar materials themselves.
• Improved testing for determinism of generators: we remind you that generators have to be written so that they produce the same input each time, this is tested more reliably now. Do not initialize random number generators with current time!
• Implemented a feature to view revision history for a topic. History may be available either to all users or only to the editors. By default new topics will have history available to everyone. If you enable viewing history, then you will be able to publish auto comment when you have edited the topic, which will have links to the previous version, new version and the link to compare them.
• Now users which didn't take part in rated events for more than 6 months are hidden in the ratings pages. Also they do not affect a country/city/organization ratings.

And this is not all! Expect more improvements soon, for example we work on rating inflation problem and lots of other things.

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.com/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.