Hello Codeforces community !

I am glad to announce Codeforces Round 307 (Div. 2) on 12th of June at 19:30 MSK. Authors of this contest are Nikola Mandic (nikola12345) and Aleksa Plavsic (allllekssssa). This is our first round and we really tried to make interesting and solvable problems. Traditionally Div.1 participants can take part out of the competition ( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes ). This is the first Serbian round and we want to invite our friends from Serbia to take part in this round and maybe prepare some of next rounds.

The main character of this round is gonna be GukiZ ( our proffesor of computer science ). He really helps us to become better people and developers !

We want to thank Zlobober for help in preparing contest and great advices, Delinur for translating problems statements into Russian and MikeMirzayanov for fantastic Codeforces and Polygon platform !

We wish you great fun, a lot of Successful hacks, Accepted solutions and high rating !

UPD: Scoring distribution: 500 — 1250 — 1750 — 2000 — 2500.

UPD2: Due to technical reasons round was delayed by 10 minutes. Stay tuned!

UPD3: +5 minutes. Thanks for your patience!

UPD4: System testing is complete, but the rating update won't be that fast since we are working on improving our cheater catching system. Thanks for your understanding!

Congratulations to winners!

DIV 1:
1.MrDindows

2.kennethsnow

3.ecnerwala

4.I_love_Tanya_Romanova

5.Hasan0540

DIV 2:
1.hrzhrz_hrzhrz

2.slo

3.wangjing

4.cyber_tourist

5.Moose_Lee

Thanks to all participants. We hope you have a good time and learn something new.

UPD5: Link of editorial !

If you have written some programming problems, and have prepared test cases, you will probably experience the terrible feeling that some test cases may be invalid (meaning it does not agree with the constraints in problem statement): upper bound can be violated, your graph not satisfied connectivity requirements or is not at tree... It is reasonable to feel that way. Even experienced problem setters make mistakes sometimes (for example, in the prestigious ACM ICPC World final 2007).

It is strictly recommended to write a special program (called validator) to formally check each test to satisfy all requirements from problem statements. Validators are strictly required for problems on Codeforces. Polygon has built-in support of validators.

It is really easy to write a validator using testlib.h.

Example

Following is a validator that could be used for problem 100541A - Stock Market:

#include "testlib.h"

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);
    int testCount = inf.readInt(1, 10, "testCount");
    inf.readEoln();
    
    for (int i = 0; i < testCount; i++) {
        setTestCase(i + 1);
        int n = inf.readInt(1, 100, "n");
        inf.readSpace();
        inf.readInt(1, 1'000'000, "w");
        inf.readEoln();

        inf.readInts(n, 1, 1000, "p");
        inf.readEoln();
    }

    inf.readEof();
}

#include "testlib.h"

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);
    int testCount = inf.readInt(1, 10, "testCount");
    inf.readEoln();
    
    for (int i = 0; i < testCount; i++) {
        int n = inf.readInt(1, 100, "n");
        inf.readSpace();
        inf.readInt(1, 1000000, "w");
        inf.readEoln();

        for(int i = 0; i < n; ++i) {
            inf.readInt(1, 1000, "p_i");
            if (i < n-1)
                inf.readSpace();
        }
        inf.readEoln();
    }

    inf.readEof();
}

The wonderful thing about this validator is that it is very simple and it is very difficult to write something incorrect.

More examples can be found at the Github repo

Available methods

The first line of your code should be registerValidation(argc, argv) which does some magic in the background, so that you can use the necessary methods.

Hi, Codeforces!

I am glad to announce Looksery Cup 2015, that is prepared by our developers, each one of them has made a great impact: Sfairat, olpetOdessaONU, Sklyack, MrDindows, Rubanenko, Krasnokutskiy, 2222, Maxim, Avalanche, Igor_Kudryashov, Kepnu4 and I. Special thank to coordinator Zlobober for the help with problems and advices and to Delinur for the translation.

We've prepared 8 problems for you, that will have random order at the contest. Round will last 2 hours 30 minutes under the standard Codeforces rules with smooth dynamic scoring. We hope, that you will enjoy competition, and we will receive small amount of clars :)

Top-200 competitors will get t-shirts with the handle at Codeforces:

Winner will get opportunity to have a prepaid trip to San-Francisco.

Besides, top-15 competitors will get Oculus Development Kit 2.

And competitors from 16 to 50 — gadget Ollie.

Also I would like to thank MikeMirzayanov and everybody, who works on Codeforces and Polygon — your contribution in education and IT is hard to be overestimated.

UPD. Round will be rated for both divisions.

Looking forward to seeing you tomorrow,

Looksery Inc.

UPD3. Editorial

UPD2. Rating will be recalculated today, but it could be changed a little till final results.

UPD. Round is over. Thank to everybody, who took part. Congratulations to winners! The final results will be announced in a day, after catching all cheaters. Current top-15:

1. tourist
2. scott_wu
3. Petr
4. Haghani
5. jqdai0815
6. PavelKunyavskiy
7. W4yneb0t
8. vepifanov
9. LHiC
10. Gullesnuffs
11. simonlindholm
12. subscriber
13. Shik
14. izban
15. data_h

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