Hello.

Now Codeforces will be more convenient to browse from mobile platforms. For the majority of them mobile view is available now. The menu goes to the left panel and sidebar — to the right. Both panels are available either on special icon at the top of the page, or by swipe left/right. You can hide them by touch in the main area of ​​the page, or by reverse swipe. In the mobile view fonts are enlarged, so on most screens it is possible to read the website without zoom.

So, for example, how the sidebar appears on my phone:

You can switch off mobile view (or to switch off) by clicking the special link in the bottom of any page.

P.S. In old browsers, and generally on a non-webkit it may work incorrectly. Not sure it is easy to fix :-(

Hello!

Here are some statistics about 2015. I'm glad to see our growth. Frankly, each year I'm afraid to see that we stop to grow, but each year I see 20-50% growth! Thank you for your interest :-)

In addition, I have written before about progress in the development and championships and rounds with partner companies in 2015. If you have not read, please read.

Here are the funny pictures with the statistics:

Growth of registerations. This year we overcame 300K users!

Hello!

I congratulate New Year to the entire Codeforces community! I wish you interesting problems, beautiful solutions and successful attempts in the last seconds! I wish not to lose interest in programming, to believe in themselves and regularly find confirmation of this belief. And do not get sick and more smile (even if your rating decreases). Hooray!

The profile settings appear magical section. Happy New Year!

Hurry! Only until the 10th of January, you can change your handle (but only once)! Note that it will be possible to roll back the changes or change the handle again only after a year. Be careful what you wish for.

You can change your handle to the new one which wasn't used before by anybody or which was used by you before. The links to a profile page with old handle would automatically redirect to the actual profile.

Talking about handles I always reminisce the following story. Once a user wrote me the message: "Please change my handle from I_love_Valya to I_love_Sveta, as I no longer love Valya ..."

Happy New Year!

Hello!

In 2015 we have not only engaged in the organization of rounds and championships. Every day we write the code, debug, test and explore a variety of tools and technologies to make Codeforces better. Even if in some periods you have not seen great changes on the website, it does not mean that the development was stopped — just some of the innovations relate solely to infrastructure, architecture or administrative interfaces and are not visible to the users.

I have collected in a list of all the innovations, which touch users in some sense. This faceless list includes results of many days of work of each member (sometimes with prefix ex-) of Codeforces technical team: MikeMirzayanov, MaximShipko, kuviman, fcspartakm, Avalanche. There are valuable helpers Edvard (helped with the introduction of educational rounds), stingray (constant help with the administration and configuration of servers is priceless), demlit and lthirteenthl (assistance with the administration and hardware). And I just listed those who assist in technical terms — there is an important list of all of those who contributed to the life of Codeforces in other aspects. Thank you!

Here is the promised list of completed (sometimes partially) cases in 2015, the year.

Hello everybody!

I hope you have the holiday spirit!

Later I will publish statistics for the year and tell you about our achievements of this year, and for now I will talk about championships and competitions that we made with our partners in 2015. My speech does not include any activities that we have conducted very far from the Codeforces site (e.g., Russian AI Cup).

This year is remembered by many interesting events that we did not by ourselves, but together with partners. I am particularly pleased that all companies who wished to fill the ranks of their employees found worthy candidates among our members. And someone said that the Olympiads are not needed! That is a lie. Here is the list of events:

VK Cup 2015

Team Championship for young participants, was conducted in Russian. 2349 registered teams of two (rarely of 1 participant). The coolest prize money and rich finals in St. Petersburg. Organizer is the VK company.

Rockethon 2015

Open individual competition by the original rules of the Rocket Fuel company. More than 3600 participants and 6565 registrations!

ZeptoLab Code Rush 2015

Individual competition by the classical rules of the ZeptoLab company. 3090 participants and 5504 registrations, excellent presents for the winners! And insanely beautiful drawings from ZeptoLab artists!

Looksery Cup 2015

! Looksery

Individual competition by the classical rules of the Looksery company. This company did not only congratulate us on our 5th anniversary, but conducted such a cool round. And the fund of the company's founder had very cool initiatives supporting the development of sports programming! 3528 participants and 5714 registrations. Yes, the gifts are yet on the way!

AIM Fund Round 2015

Individual competition in two divisions by the classical rules of the AIM Fund company. Prepared in the context of congratulating Codeforces on the 5th anniversary, thank you! 4064 participants and 6721 registrations. I've heard a lot about the after-party in Petrozavodsk. I wish I had been there!

Call To Code 2015

A competition for Irish schoolchildren by unusual rules. It was not conducted on the Codeforces site, but on our platform. Organized by the Google company.

Hello.

Now you do not have to go into Google if you need to search blog posts. You can do it directly on Codeforces. The implemented search is based on Apache Lucene . The index contains all open public posts, which are already more than 15,000 documents.

Temporarily search for tags are now available (tags will be added to the index soon), but instead you have the opportunity to find posts and even sort using different criteria. By the way, you can use complete syntax of Lucene queries to search. Here is a short description of main features.

You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author.

Some examples:

• 305 — search for 305, most probably it will find blogs about the Round 305
• andrew stankevich contests — search for words "andrew", "stankevich" and "contests" at the same time
• user:mikemirzayanov title:testlib — search containing "testlib" in title by MikeMirzayanov
• "vk cup" — use quotes to find phrase as is
• title:educational search in title

Regarding indexing comments, solutions and problem statements I have a feeling that it may be useless. Too difficult to find something relevant (or maybe not). What do you think: should we implement it?

Hello,

We are launching new feature on Codeforces, in early beta mode. I hope it will be useful to many active users of the web-site. Now you can create, manage and use the "user lists".

Partially, it is a kind of generalization of "friends." You can create a list of users interesting to you (you can create many lists) and, using the list, filter the results of rounds, quickly analyze what problems are solved in the problemset, etc. This feature is a helpful tool for coaching — I'm using it. By combining in a list of all practicing students, it is easy to pick up problems that have not been solved (and even not attempted) by any student.

A user list has name and a pair of two relatively secret keys & mdash; one for view/usage and one for editing. For example, here is the key to view a list of ACM-ICPC students at Saratov State U for autumn of 2015: 15c68c2cf878267d59373d1e56be8c9a

This means that on some pages, you can use the optional parameter ?list=key to apply the list. Here is an example of the screen by the link http://codeforces.com/problemset/page/3?list=15c68c2cf878267d59373d1e56be8c9a:

Yeah, in the recent training I can give the problems 538H - Summer Dichotomy and 538G - Berserk Robot . In additional information the first number indicates the number of users solved problem, and the second is the number users attempted problem. Codeforces searches solutions/attempts not only for this particular problem, but all the possibilities of its use (say, someone can solve it in other division or in a mashup).

There are additional controls to make it more comfortable to use lists:

At the moment, the lists can be applied:

• in the problemset (shown number of solvers/attempters for each problem)
• in list of rounds/trainings in Gym (shown number of solvers/attempters for each problem)
• on the standings page (to filter the rows)

I remind you that the functionality is in early beta mode & mdash; there may be some issues. We will return to development and bug fixing after ACM-ICPC Regional Contest NEERC 2015.

And what other use of the lists can offer you?

Educational Codeforces Round 1 is over. During 24 hours after coding phase many of you tried to hack other's solutions. And it were many successful hacks!

It was 573 successful hacks, made by 101 hackers. Here are most effective:

Thank you! Now I'm pretty sure that tests of this problems are really complete. Moreover hacks shown that writer's tests are often incomplete. In short, it seems it was really good idea to make open hacks phase.

I'd like to crowdsource editorial for such rounds. Please, write in comments if your are ready to write/improve a editorial for problems C-F. For sure, you should solve problem to help with editorial.

Please, write in comments your feedback. It is very important for us to get it. Thanks!

Hi everybody!

First, I invite you to take part in an official Testing Round 12. The fact is, the Codeforces team has made numerous changes to the platform (details are below), and we want to be sure that the basic functionality remained unchanged. This round will have a shortened duration of 1.5 hours, consist of 3 (maybe 4) problems that you might have already seen before. Its purpose is to test the system on the one hand, and on the other hand — to brighten up a Wednesday evening. Of course, the round will be unrated.

Now the main thing. This coming Friday (yes, the 13th of November) Codeforces starts another line of rounds. We called them Educational Rounds. Using my students at the Saratov State University Programmings Competitions Training Center as an example, I regularly notice that even those who have a considerable progress in the results on the rounds often have narrow purview in terms of standard topics and ideas, they are not familiar with many well-known problems and methods. The fact is, the rounds often avoid any folk or classical subjects, thus underdeveloping the purview of young generation of the participants.

We are pleased to announce the start of a series of educational rounds! They will take place with the regularity of a round 2-4 times per month.

Their characteristics are like that:

• The duration is classic — 1.5 — 2.5 hours;
• The goal is rather to practice and to educate, than to compete;
• Not only problems, but also exercises can be used;
• Useful, even well-known ideas will be reused in order to introduce them to a wide range of participants;
• Often the formal text of the statements;
• Unrated (perhaps for now);
• We will try to conduct them in the ACM-ICPC mode (if there are long waiting lists, we may change the approach);
• The results that are obtained after the end of the round, are preliminary;
• After the end of the round will be a 24-hour period of open hacks — any visitor of Codeforces may try to hack any complete solution to a problem of the last round (either from a contest, or from practice), the source code of hacking solution is available (you can copy the text and, for example, stress it);
• All successful hacks from the previous item will be added to the official test set and after as long as 24 hours after the end of the round retesting of all complete solutions will be made;
• Only after the final standings based on improved test data, the results are final;
• The results of a round are calculated separately by division;
• Our ability to process such problems are limited, so actually the test suites from the jury are expected to end up incomplete — we are looking forward to your hacks!

Basically, we will be oriented towards the members of the second division, but often these rounds will be of interest to more experienced participants.

For now preparing problems to these rounds will be concentrated at the Saratov State University Programming Competitions Training Center, most of the work with the problems will be accomplished by Edvard Edvard Davtyan. We wish him good luck, enthusiasm and energy!

See you at the Testing Round 12, and later at the Educational Codeforces Round 1.

Starting from October 2015 ratings formulas are open. They are given in the post. It is likely that from time to time we will change them slightly, it will be reflected here.

The basic idea of Codeforces rating system is to generalize Elo rating to support games with multiple participants.

Each community member is characterized by value r_i — integer number. Roughly speaking, the higher value means better results in the contests. Rating is calculated/recalculated so that the equality strives to be correct:

where P_i, j is probability that the i-th participant has better result than the j-th participant. Therefore for two participants the probability to win/lose depends on subtraction of their ratings. For example, if the difference of ratings is equal to 200 then stronger participant will win with probability ~0.75. If the difference of ratings is equal to 400 then stronger participant will win with probability ~0.9.

After a contest the values r_i change in a way to satisfy main formula better.

Let’s calculate expected place seed_i for each participant before contest. It equals to the sum over all other participants of probabilities to win (to have better place than) the i-th plus one because of 1-based place indices:

For example, before Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1) tourist had rating 3503 and his seed was ~1.7, and Petr had rating 3029 and expected place ~10.7.

General idea is to increase r_i if actual place is better than seed_i and to decrease r_i if actual place is worse than seed_i.

Having seed_i and actual place, let’s calculate their geometric mean m_i. You can think about it as an something average between seed_i and actual place shifted to the better place. Using binary search find such rating value R which the i-th participant should have to have a seed_i = m_i. Obviously the rating r_i should be modified to become closer to R. We use d_i = (R - r_i) / 2 as rating change for the i-th participant.

It's almost all except the phase of fighting against inflation. Inflation works as follows: the rich get richer. We will try to avoid it. If we assume that the rating was already calculated fair (i.e. everybody has perfect statistically based rating) then expected change of rating after a contest is equal to zero for any participant.

Choose a group of the most rated (before the round) participants and decide that their total rating shouldn’t change. We use heuristic value as a size of such group. Let’s find the sum of d_i over participants from group and adjust all values d_i (for all participants) to make the sum to be zero. In other words, r_i = r_i + inc, where inc =  - sum_s / s, sum_s is sum of d_i over s participants from chosen group.

After the round 327 we restricted the effect in following way. Firstly, we do r_i = r_i + inc, where inc =  - sum(d_i) / n - 1, sum(d_i) is sum of all d_i. It makes the sum of all d_i to be near zero and non-positive in the same time. Secondly, we apply idea from the previous paragraph, but inc = min(max( - sum_s / s,  - 10), 0). Thus, the effect of modification can not reduce rating for more than ~10 points.

By the way, for any consistent rating the following assertions should be true:

• if the participant A had worse rating than the participant B before the contest and finished the contest on the worse place then after recalculations the the rating of A can’t be greater than the rating of B
• if A finished the contest better than B but A had worse rating before the contest then A should have equal or greater rating change than B.

In particular, formulas are tested to satisfy the both items on each ratings recalculation.

You may read the actual Codeforces code to recalculate ratings here: 13861109.

You may print PDF-statements: http://assets.codeforces.com/statements/589.pdf

Recently 2015-2016 ACM-ICPC, NEERC, Southern Subregional Contest has been finished. On behalf of jury and hosts I congratulate winners and advancers to the semifinals. Prize places are (horray!):

• 1 place: Nizhny Novgorod State University #1 (Vladislav vepifanov Epifanov, Nikolay KAN Kalinin, Mikhail mike_live Krivonosov)
• 2 place: Innopolis University #1 (Evgeniy savinov Savinov, Sergey sokian Kiyan, Alexander map Mashrabov)
• 3 place: Saratov State University #1 (Edvard Edvard Davtyan, Vitaliy kuviman Kudasov, Danil danilka.pro Sagunov)

On Saturday (October, 17) в 08:00 (UTC) we will host unofficial online mirror. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams. This will be a team/personal contest on Codeforces, with teams consisting of up to three people or individual participants. The contest will not affect Codeforces ratings.

For sure, it will be unrated contest. We recommend you to take part in teams. I think, the contest will be moved to Gym later.

Good luck!

MikeMirzayanov, head of judges.

P.S. We are aware that this mirror will overlap with some other online tournaments, but unfortunately we are unable to change the current time slot, due to the online mirror of the Moscow Subregional of NEERC scheduled on Sunday. All school teams are recommended to pay attention to Online-mirror of the Ural regional team championship.

Over the last several months the Codeforces team has been looking anxiously at the inflation in the rating caused by both an influx of new users and the imperfect calculating formulas.

In the end it lead to noticeable shifts in colors and titles. For example, getting red in 2015 became much easier than in 2013.

We conducted a survey about the way to introduce the color bounds. We are happy to announce the updated colors and titles!

A summary of the main changes goes like that:

• a new color: greenish-blue color or cyan — just like the name implies, this color takes its place between green and blue, now the participants of the second division will be better differentiated;
• all the colors shift upwards along the rating scale — see the table below. Now reaching the top positions will be harder;
• the legendary grandmaster — the new title and color for those who reached the sky high rating 2900.

The cold colors (gray, green, cyan and blue) still correspond to the second division and the other ones correspond to the first one.

The requirements to the coach rights haven't changed — you've got to have 2200 or 1900 and a rich history of participations in order to become a coach. Problem tags and groups can be added by the participants from the first division.

The table below illustrates the new values of the color and rank borders:

Active users (who took part in last 6 months) on the moment of October, 1 are counted.

I will write about the changes in the rating formulas as soon as possible, And yes, the formulas will be open!

Hooray! Soon there will happen several updates on Codeforces affecting rating and colors. The second Revolution of Colors and Titles is coming!

You will soon find out a new rating with public formula, new color bounds and even something more...

New bounds will fix the rating inflation of last year, it will return exclusivity of high rating and titles. Don't worry if you end up with lower color; it's a new reason for you to move forward!

While discussing the ongoing change we faced an issue about how to apply new colors with two possible solutions.

First solution: forward without looking back.

When applying new bounds we will update colors everywhere according to a new schema. For example, somebody can possibly lose not only the read color, but he may also regain a new challenge "to become red" since he lost time when he was red before on his rating history. For the first time it doesn't seem as a good solution, but if you think deeper, there is nothing bad in it. Ratings will be whole without cases like "you were read before the revolution, that doesn't count!". In old ranklists there will be no mess within colors of modern contestants (from upsolving or virtual contests) and historical contestants. Irregular visitors of Codeforces won't be confused of the fact that somebody is red in the standings but shouldn't have been red before according to his rating.

We did like this before it worked not bad, if we have changed the color history back then, it would have added mess and confusing.

Second solution: keeping history.

When adding new bounds we will keep old ranklists, posts and comments "as is". This won't break comments like "Congratulations with a red color!" (not sure if they are that valuable) Such solution will keep your achievement "to become red" unlocked, i. e. this part of your biography remains still confirmed by your rating history.

We may even make a rating graph become cut on two parts with a vertical line at the moment of a revolution. The old colors will remain to the left of it, and the new colors will be placed to the right of it. Although this may lead to a confusing of newcomers unprofessionals and rare Codeforces visitors.

Overall

As you see, both solutions have their pros and cons. I don't even know what is better among this two possibilities. That's why I want you to vote for the better choice. If one of the solutions surely wins, we'll use it. Otherwise I'll do as I think it is best.

Please vote only after carefully reading both options. First two comments below correspond to the solutions. Negative voices won't be considered at all, positive will have weights 1-2-4-8-16-32 according to your color (grey-green-blue-purple-orange-red). The vote is secret, results will be available on October, 1st in the evening.

UPD: The voting is finished. We congratulate the first option with a confident victory: 6394 points vs 2320 points! The comments for voting have been removed not to affect comment votings statistics. You may expect changes in colors and ranks in the nearest future!

As I work with students I often face the situation when if a problem doesn't seem clear to a student at the first sight, it makes them unable to solve it. Indeed, you always hear about specific methods and techniques. But you don't hear about how to think in order to apply them. In this note I'll try to sum up my experience of solving programming contest problems. However, some pieces of advice will also be applicable for olympiads in mathematics and your first steps in academic research.

So you've read a problem and you don't know how to solve it. Try the following techniques, some of them can often come handy.

Technique 1: "Total Recall"

Try to remember some similar problems that you had to solve. Quite many problems do not have a brand new idea. So probably, you can use your experience of solving a similar problem to solve this one.

Technique 2: "From Specific to General"

Let's say that you've found the solution for the problem (hurray!). Let's consider some particular case of a problem. Of course, you can apply the algorithm/solution to it. That's why, in order to solve a general problem, you need to solve all of its specific cases. Try solving some (or multiple) specific cases and then try and generalize them to the solution of the main problem. Such specific cases can be regarded as the simplifications of the problem, i.e. we can reason by the following principle: "if I don't know how to solve a complex problem, I think I'll simplify it and find the solutions of the simplified version".

The popular examples of simplifications (specific cases):

• you get a problem for a tree. Consider its variant where the tree degenerates into a path;
• the problem has weights? Consider a variant where all the weights are equal either to one or to an arbitrary number, or there are only two distinct weights (and so on).

Note that the solution of a specific case almost always isn't easier than the solution of a general one, so you need to try and find a solution that would be as easy and effective as possible.

Technique 3: "Bold Hypothesis"

Don't be shy of making bold hypotheses that seem true to you. You do not have to prove your solutions during contests, tap your inner intuition. When you've come up with your hypothesis, try to prove it — it may either work out well or give you an idea of how to disprove it. Do test the hypothesis on a wide set of tests as it would be a pain to waste time on implementing a solution based on a hypothesis and only after that disprove the hypothesis.

Examples:

• the solution always exists;
• item the number of states isn't large.

Technique 4: "To solve a problem, you should think like a problem"

I'm serious, put yourself in the shoes of the character of the problem, imagine that it's your job to handle the input sets. Think about how you'd act in this case. Try to process some small samples on your own. If the problem is about a game, play it. Sometimes I try to visualize a process or a model for better understanding. It's a little like how movies show the way scientists think. Try to think in images, imagine the solution, see it unfolding.

Technique 5: "Think together"

This technique is only applicable to team contests. In group of two or three persons start saying some clear facts about the problem. For example: "if n is even, then the answer is always 0", "if n is prime, then the solution should go like that", and so on. Sometimes your teammates will pick up ideas and develop them and this strategy can get you through the problem.

Technique 6: "Pick a Method"

Try coming through popular algorithms or methods that can apply to the problem in any way. It is useful to see the problem limits. Having picked a method, try thinking on the solution assuming that the problem is solved using this method. Your reasonings should be somewhat like this: "Let's assume that the problem is solved by divide and conquer. Then let us solve this problem recursively for the left and right half. Now all that's left is to find a way to unite these solutions. I wonder how we can do that..."

Technique 7: "Print Out and Look"

Quite often (especially in problems with a small input: one/two numbers) there are some patterns in the composition of the solution. To see a pattern, you sometimes need to write some naive method of solving a problem, generate answers for a large number of tests on large limits and meditate on your answers for a while. In order not to keep the computer busy, a good strategy is to print out the acquired results and meditate this time on the print outs.

Sometimes it is a good idea to print not only the answer, but also some extra information, such as a manner of acquiring a solutions.

Technique 8: "Google"

This technique can only be used if the round/contest rules allow it. If the problem is about sequences, then you can look for solutions (see technique 7) on the site https://oeis.org/. It helps to understand the formal model of the problem and google the correct mathematical terms.

What are generators?

Generators are helper programs that output test. Most programming task usually has a large input (for example, an array of up to 2 * 10⁵ elements, a tree of up to 10⁵ vertices), so it's not possible to add all the tests manually. In these cases, generators come to the rescue.

If you are writing a generator in C++, it is recommended to use the testlib.h library.

Types of generators

There are two types of generators:

1. Single-test generator: output exactly one test in a single run. Usually, to generate several tests, one must run the generator several times with different command line parameters. Such generators output the test to the standard output stream (to the screen).
2. Multiple-test generator: output many tests in a single run. Such generators output tests to files (one file for each test).

An example single-test generator with testlib.h

The following generator output a pair of integers with each element from 1 to n — where n is a command line parameter passed to the generator.

#include "testlib.h"
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);
    int n = atoi(argv[1]);
    cout << rnd.next(1, n) << " ";
    cout << rnd.next(1, n) << endl;
}

Why testlib.h?

On the surface, it seems that testlib.h is not necessary to write a generator. This is not true. Almost all generators need to generate random values, and it is tempted to use rand(). However, this is a bad practice. A basic principle of writing generators is that: a generator must output the same test when compiled by any compiler on any platform if it is run in the same way (using the same command line parameters). When using rand() or C++11 classes like mt19937/uniform_int_distribution, your program will output different tests when compiled with different compilers.

The random value generator in testlib.h ensures that the same value is generated regardless of the (test) generator and platform. Besides, testlib.h has various conveniences for generating tests, for example, rnd.next("[a-z]{1,10}") will return a random word of length 1 to 10 from letters a to z.

Translator's note: There are more issues with using rand() aside from the above one. Refer to this blog for a detailed explanation about these issues.

Available method

To initialize a testlib generator, the first line of your generator must be of the form registerGen(argc, argv, 1); (where 1 is the version of the random number generator used). After that, it will be possible to use the rnd object, which will be initialized with a hash from all the command line arguments. Thus, the output of g 100 and g.exe "100" will be the same, while g 100 0 will be different.

rnd is of type random_t. That is, you can create your own generator, but this is not necessary in most of the cases.

rnd has many useful member functions. Here are some examples:

Also, please do not use std::random_shuffle, use the shuffle from testlib.h instead. It also takes two iterators, but works using rnd.

Translator's note: If my understanding is correct, rnd.wnext is defined as follows:

Example: generating an undirected tree

Below is the code of an undirected tree generator that takes two parameters — the number of vertices and the 'elongation' of the tree. For example:

• For n = 10, t = 1000, a path graph (degree of all vertices are at most 2) is likely to be generated
• For n = 10, t =  - 1000, a star graph (there's only one non-leaf vertex in the tree) is likely to be generated.

registerGen(argc, argv, 1);

int n = atoi(argv[1]);
int t = atoi(argv[2]);

vector<int> p(n);

/* setup parents for vertices 1..n-1 */
for(int i = 0; i < n; ++i)
    if (i > 0)
        p[i] = rnd.wnext(i, t);

printf("%d\n", n);

/* shuffle vertices 1..n-1 */
vector<int> perm(n);
for(int i = 0; i < n; ++i)
    perm[i] = i;
shuffle(perm.begin() + 1, perm.end());

/* put edges considering shuffled vertices */
vector<pair<int,int> > edges;
for (int i = 1; i < n; i++)
    if (rnd.next(2))
        edges.push_back(make_pair(perm[i], perm[p[i]]));
    else
        edges.push_back(make_pair(perm[p[i]], perm[i]));

/* shuffle edges */
shuffle(edges.begin(), edges.end());

for (int i = 0; i + 1 < n; i++)
    printf("%d %d\n", edges[i].first + 1, edges[i].second + 1);

How to write a multiple-test generator?

A multiple-test generator in one execution can output more than one test. Tests by such a generator are output to files. In the generator on testlib.h it is enough to write startTest(test_index) before the test output. This will re-open (freopen) the standard output stream to a file named test_index.

Please note that if you are working with the Polygon system, in this case, you need to write something like multigen a b c > {4-10} in the script (if it is assumed that starting the multiple-test generator will return tests 4, 5, 6, 7, 8, 9, and 10).

Other notes about generators

• Strictly follow the format of the test — spaces and line breaks should be placed correctly. The test should end with a line feed. For example, if the test consists of a single number, then output it as cout << rnd.next (1, n) << endl; — with a line feed at the end.
• If the test size is large, it is prefered to use printf instead of cout — this will improve the performance of the generator.
• It is better to use cout to output long long, but if you want printf, then use the I64 constant (for example, printf(I64, x);).
• Please be aware about various cases of C++ undefined behavior. For example, in the first example generator above, if the two cout commands are combined into one, the order of the rnd.next function calls is not defined.

Translator's note: about the third point, using lld constant with printf to output long long used to be problematic in the past, but is no longer an issue now.

Further examples

Further examples of generators can be found in the release notes or directly at the GitHub repository.

Section about testlib is temporary, at some day it will be merged into global documentation section when it appears.

If you are developing a programming contest problem and you are doing it with using C++ then testlib.h is a right choice to write all auxiliary programs. This library is a standard solution in a professional community of problemsetters around the world. Many contests are prepared using testlib.h: All-Russian and International olympiads in Informatics, ICPC regional contests, all Codeforces round and many other competitions.

You can find testlib.h on GitHub.

testlib.h library is contained in a single header file. In order to use it you should just put testlib.h in the same directory with a program you are writing (checker, generator, validator, or interactor) and add the following line to the beginning of your program: #include "testlib.h".

Here are the cases when testlib.h is really useful:

• In writing generators. These are the programs that create tests for your problem, since it is not always possible to type a whole content of the test by using the keyboard (at least because of their possible large size);
• In writing validators. These are programs that read the whole test and verifies that it is correct and that it satisfies the constraints of the problem. Validators should be maximally strict with respect to spaces, endlines, leading zeroes etc;
• In writing interactors. These are programs that are used in interactive problems, if your problem isn't interactive then just nevermind;
• In writing checkers. If your problem allows several possible answers for the tests then you should write a special program that checks participant's answer against jury's answer and the input data.

testlib.h is fully compatible with Polygon problem preparation system.

First versions of testlib.h appeared in 2005 as a result of testlib.pas porting on C++. Since then testlib.h has evolved, its features and performance were improved. Last versions of testlib.h are compatible with different versions of Visual Studio compilers and GCC g++ (in editions for many platforms), also they are compatible with C++20.

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