Hello!

Only a few hours before the start of ACM-ICPC World Finals 2015!

The ACM ICPC is considered as the "Olympics of Programming Competitions". It is quite simply, the oldest, largest, and most prestigious programming contest in the world.

The ACM-ICPC (Association for Computing Machinery — International Collegiate Programming Contest) is a multi-tier, team-based, programming competition. Headquartered at Baylor University, Texas, it operates according to the rules and regulations formulated by the ACM. The contest participants come from over 2,500 universities that are spread across 100+ countries and six continents.

This year the best 128 teams in the world will meet face to face in Marrakech on World Finals. Video coverage will start on 09:00 (UTC), and the contest will start on 10:00 (UTC).

• current standings (currently there are practice session results there), alternative standings table by Ahmed Aly
• video on youtube
• text coverage on tumblr
• offcial photos
• twitch channel 1, twitch channel 2
• Petr Mitrichev's blog

Good luck to all the teams!

UPD Added link to the text coverage on tumblr.

It is really great to spend holyday usefully. During the Victory Day I not only visited the Victory Park with family, congratulated people closed to me, watch the Victory Day Salute, but also I've started to get rid from codeforces.ru

Yes, it is not a mistake. We are moving forward to use the only domain codeforces.com. It will make many thing better: better navigation, better page statistics, better pagerank and other metrics.

Of course, all links to codeforces.ru is redirecting to the appropriate page on codeforces.com now. In addition, for now it applies only to GET-requests.

Observant visitors have noticed that recently changed how we deal with images. Now, if you insert a link to image into the text of a post/comment, then when you save it predownloaded and stored on Codeforces, and link is replaced by to use our domain. This solves several problems: missing or spoofed pictures in old posts/comments, the restriction on the number of views in original image server, we resize too large images to smaller size, now we be sure to use https for images, which means we are closer to use https.

April 18, 18:00 (UTC) the second Wild-card round of VK Cup 2015 will take place.

Participants are invited to achieve progress in solving an unusual problem. VK Cup teams which were advanced to the Round 2 (and didn't advance to the Round 3) will take part in VK Cup 2015 - Wild Card Round 2 officially. In addition, this round will be open to the public for unofficial participation for everybody. Registration will be open for the whole round duration.

The round will be one week long. After the end latest submission (with positive score) of each participant will be judged on system tests.

Good luck!

UPD.: System testing is done. Final tests are available by link: http://assets.codeforces.com/files/vkcup-2015-wildcard-2-tests.2.zip

You can appeal on tests and their answers until April, 28th, 23:59:59. After that we will finalize the results. After finalizing all found bugs will not affect the final standings.

Hello Codeforces.

This is a really good and pleasant day for us. We are happy to announce that the fundraising campaign on Codeforces is successfully completed and its results are even beyond our expectations. Thank you for your support, your trust and your kind words.

By the way, we have some more unprocessed PayPal transfers: for unknown reasons the notifications in some cases didn't contain some data needed to process them automatically. We will process them manually and update the data as soon as possible.

To all of you waiting for our present in the mailbox, please update your Codeforces profile information or make sure that it already is complete and up-to-date.

Thanks!
Mike Mirzayanov

Hi!

It is only a day before the end of the fundraising campaign dedicated to the 5th anniversary of Codeforces. We are glad and grateful for your help and support. We are working hard to justify your and our own expectations.

For those who are not accustomed to rush, remember that you still have a little time to join the remarkable list of our friends — help us and get a gift from the Codeforces team!

When summing up, of course, we mostly want not to count money, but to assess progress and the work done. I looked at all of our commits to Codeforces and Polygon, and made a digest of changes.

I did not include to the digest improvements in the depths of system's backend (although stability progress should be visible), infrastructure jobs, org. work around the championships — but, believe me, there were many items too.

And here is the list of our achievements for about two months after anniversary.

Hello!

VK Cup 2015 — Round 1 (unofficial online mirror, Div. 1 only) — is public unofficial replay of Round 1. It means that if you didn't take part in VK Cup (for example, you are not Russian-speaking), decided to cancel further participation in VK Cup or didn't pass a Qualification you can take part in VK Cup 2015 — Round 1 (unofficial online mirror, Div. 1 only). You should be in Div. 1 to take part in it.

Mostly it will be typical round with regular Codeforces rules. Persons (not teams) will take part in it. The problems will be in English and in Russian. It will be hacks and rating will be updated after it. It will be used recently implemented smoother dynamic problem scores with 250 points steps. You can read about it here.

There were many not Russian-speaking teams in VK Cup Qualifications. I encourage these teams to respect the position of the organizers and not to take part in official Round 1. Please, take part in VK Cup 2015 — Round 1 (unofficial online mirror, Div. 1 only).

Wish you good luck!

Doing VK Cup 2015 we faced with an interesting problem: how to calculate rating changes for team members?

In short, currently the ratings are calculated using the following rules: * each contestant has some ratings r_i before the round, * our goal is to follow Elo Rating System idea: participant a wins participant b with probability:

• as we know chances to win/loose for any pair of participants, we can calculate the expected place (seed) as a sum of winning probabilities,
• if participant took place better than expected then we need to increase rating, if worse then we need to decrease rating.

Above items are just some general rules, but we have some anti-inflation corrections and heuristics. BTW, we are moving forward to rethink rating formulas and open them. But the question now is not about that, but about how to calculate the rating of a team.

It is natural to generalize current ideas, but we need a method to calculate the rating of a team knowing ratings of members. If there is such function, say teamRatings(r₁, r₂) (for 2-member teams), it will be naturally to use it to calculate expected place of a team. And depending on actual place, member's ratings should be adjusted.

That's the idea came to mind of the Codeforces team during lunch.

For sure, the function teamRatings(r₁, r₂) should satisfy some constraints:

• teamRatings(r₁, r₂) ≥ max(r₁, r₂),
• if we compose a team of tourist and somebody not very skilled (say, green participant), rating of team should be close (a little more) to tourist's rating.

I was offered the following funny model. Image there is team AB composed to two members A and B. Let's try somehow to compare it with individual participant C. In my model instead of single contest "A+B vs C" we will make two contests "A vs C" and "B vs C". If at least in one contest of two won member of AB, then the team won. If both contests won C, them C won.

This model doesn't consider any team-work, but it fairly tries to consider chances of both participants A and B to overcome C.

Now we know rating of C and winning probability of AB over C, we can inverse Elo formula to find rating of AB.

There is a trick that calculation of team rating depends on opponent C. How to choose the most relevant opponent C? It is easy to show that changing rating of C the calculated team rating changes monotonically. I like an idea to choose such rating of C that calculated rating happens to be equal to C. In other words let's use such opponent that equally skilled compared to the team AB. Binary search helps to find such opponent's rating (closed formula also exists).

So we following code aggregates ratings of several individual participants to the single value:

long double getWinProbability(long double ra, long double rb) {
    return 1.0 / (1.0 + pow((long double) 10.0, (rb - ra) / 400.0));
}

long double aggregateRatings(vector<long double> teamRatings)
{
    long double left = 1;
    long double right = 1E4;

    for (int tt = 0; tt < 100; tt++) {
        long double r = (left + right) / 2.0;

        long double rWinsProbability = 1.0;
        forn(i, teamRatings.size())
            rWinsProbability *= getWinProbability(r, teamRatings[i]);

        long double rating = log10(1 / (rWinsProbability) - 1) * 400 + r;

        if (rating > r)
            left = r;
        else
            right = r;
    }

    return (left + right) / 2.0;
}

Once again, I understand that this model is not absolutely correct. But I don't think that absolutely correct model exists. I think that this model is reasonable and has a right to exist. What do you think?

Hello Codeforces!

I am happy to announce that the indicated $10000 support fund was raised in a little more than three days! Thanks you very much friends!

Now it became possible to pay the writers equivalent funds even they are in rubles. It was impossible because of great increase of the dollar exchange rate.

We tie the money paid in rubles to the Central Bank of Russia exchange rate, rounded to the closest sum in rubles divisible by 5 (according to the rules of mathematical rounding). The table shows the values that were up-to-date when this post was published. An asterisk marks the bonus that is given if the round is prepared perfectly.

And that is not all! As I said before, we now have the opportunity to adequately support the coordinator of the Codeforces problems Max Zlobober Akhmdov. He started working on his position in the fall of 2014 and more than two dozens of rounds have been conducted under his guidance. Preparing rounds takes a lot of work and he copes brilliantly. I hope to work with him efficiently for many more years to come.

I asked Max to write several words about himself for you to get to know him better and that's the result:

Hi! Some personal info: I graduated from the Advanced Educational Scientific Center of Moscow State University named after A.N. Kolmogorov. When I was a school student, I went to the IOI 2012, earned the gold medal and the absolute seventh place in the Russian National Team. My biggest achievements include the 5-th place at the Russian Code Cup 2014, the 10-th place in 2013 and the 3-rd place in 2014 on NEERC as a member of the Moscow SU Trinity team. I won the all-Syberian Pottosin’s Olympiad in 2013 and the ICL 2014 cup as the member of the same team.

I like music. I listen to all sorts of heavy and not so heavy rock, I go to concerts. I play several musical instruments. I am a jury member in many school programming Olympiads. The last book I've read is ‘Chapayev and Void’ by Pelevin. It's hard to choose a favorite movie — I like movies by Quentin Tarantino, Robert Rodríguez and Christopher Nolan.

That's about it.
Max.

The fund-raising campaign will continue for quite a while and I sincerely believe that there are other participants who will support us these days. We continue raising funds (that is a standard crowdfunding procedure) and we will be happy to to fulfill all obligations of award the supporters. For example, those who supported us and chose the 'badge in profile' reward option have recently got badges of honor in their profiles, the symbol of your taking part in and being part of the Codeforces development. Certificates and T-shirts will be sent after the fund raising stops. Please, be a little more patient.

All the raised extra funds will be used to develop and support Codeforces, namely (provided that we've got enough of the collected budget):

• increase the payments for Div1+Div2 rounds — may there be more of them!
• introduce a content manager into the team who will regularly add and systemize the trainings;
• we will soon definitely need new hardware and we will be able to get buy it;
• we will strengthen the team of developers to make you happier with more cool features!

Thanks for your support,
Mike Mirzayanov

Hello, friends!

Yes, this post is for friends of Codeforces. Recently Codeforces had 5 years birthday. And on this occasion we opened a campaign to raise funds for the operation and development of Codeforces.

We are eager to develop and move forward and look forward to your participation in the campaign.

We invite you to consider the possibility to support Codeforces. Details of the campaign can be found at its direct link.

Mike Mirzayanov

UPD: We have great news!

Hello, Codeforces!

In late December and early January, I wrote a proof-of-concept of separate service in C ++, to take out heavy data from the Codeforces Java-code to C++. Long time I have not written in C ++, experienced a funny sense of immersion into another world.

I was surprised to find the lack of open-addressing hashmap in the C++ standard library, and indeed in the boost, and in other popular libraries. It is strange somehow, because often open addressing should be better than separate chaining both in time and memory. And since I intend to keep small objects, then sure.

I quickly sketched a prototype that actually shows that open addressing in 2-3 times faster than the standard std::unordered_map. Here's the output of the benchmark on my laptop:

std :: map takes 15779 ms
std :: unordered_map takes 4698 ms
oaht :: hash_map takes 1473 ms

I think that there is no good implementation of such container in stl-style with the support of C++11 (move semantics). Maybe someone will show, but I have not found.

Here is my prototype on github: https://github.com/MikeMirzayanov/open_addressing_hash_table Unfortunately, I'm not cool C ++ expert, and I have no time to implement.

On the other hand, on Codeforces where were many C ++- discussions, and seems there many users who understand modern C ++. Also algorithms are water and air of Codeforces!

Hello 2015! Hello Codeforces!

It seems it is time to take stock. Frankly, I was almost feared to start summing statistics of 2014. In 2013 Codeforces showed rapid growth so that it would not be surprising to look bad on the background of 2013. Certainly not! I was pleasantly surprised by the statistics and reports!

Just below is a list of major events and achievements of Codeforces over the year. For you, it's just a list, but please note — every item includes hard work of multi-day Codeforces team, writers of problems, the organizers of contests and tournaments, problem testers and volunteers. Yay! Together we have done all of this:

• introduced Codeforces API
• added (and sometimes improved) all Andrew andrewzta Stankevich contests
• Codeforces supported mode to work as iframe-widget, and Codeforces helped Google to run https://www.calltocode.ie/ for Ireland high school children
• nearly 70 rounds have been hosted for our beloved users
• nearly 450 new and interesting problems were prepared for the contests on the Codeforces platform
• supported new programming languages
• together with CROC was held Coder-Strike 2014
• hosted April Fools Day Contest 2014 from magnificent Maria Nickolas Mykhailova

• together with the jury of Russian Code Cup 2014 held RCC Warmup, who opened the RCC for a wide range of Codeforces users
• Codeforces played a role of press-partner of RCC, ACM-ICPC Finals in Ekaterinburg, Yandex.Algorithm
• we held ZeptoLab Code Rush 2014 (Om Nomes!)
• helped wonderful company RocketFuel to run Rockethon 2014 (on Codeforces)
• hosted MemSQL Start [c] UP 2.0 with the finals the MemSQL office!
• had 11 episodes of Codeforces Trainings Season 02
• together with the jury Bayan Contest held Bayan Contest Warm Up
• updated Polygon (http://polygon.codeforces.com/) introducing an infinite number of small improvements
• supported tutorial in Polygon
• file system queries caching in Polygon has led to significant acceleration of most pages
• together with GridDynamics held GridGames (for Saratov university students)
• broke all records: 6274 registrations on Good Bye 2014!

In this cold January day, I send warm greetings to the Codeforces team and our friends: developers, problem coordinators, problem writers, testers, tireless bloggers and all of you — the knowledge-hungry competitors!

And here is a comparison with previous years of Codeforces. Clearly. In Pictures.

Recently magic item has been appeared in settings of a profile. Happy New Year!

UPD: New Year holidays are finishing, magic is disappearing... This year the magic features has been used 7482 times. Here are statistics about target handle colors.

Hurry! Only until the 10th of January, you can change your handle! Note that it will be possible to roll back the changes or change the handle again only after a year.

You can change your handle to the new one which wasn't used before by anybody or which was used by you before. Soon, the links like http://codeforces.com/profile/Alex_KPR 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!

Welcome to 2014-2015 CT S02E11: Codeforces Trainings Season 2 Episode 11 (2011-2012 ACM-ICPC Latin American Regional Contest + Extended). The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

It is not visible from user point of view, but we've introduced some changes in Codeforces backend to improve system performance. And now we want to test the system before Round 278.

I invite you to take part in Testing Round 11. It will start soon, on November, 20 21:30:00 (UTC). It will be unofficial unrated round.

Pretests are unusually weak to trigger more hack.

If you see any unexpected behavior or bugs, please inform us via comments.

Thanks.

UPD.: Thank you for participation.

Welcome to 2014-2015 CT S02E10: Codeforces Trainings Season 2 Episode 10 - 2014 Amirkabir University of Technology Annual Programming Contest (AUT APC 14). The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

489A - SwapSort

All you need is to swap the current minimum with the i-th element each time. You can do it with the code like:

    for (int i = 0; i < n; i++)
    {
        int j = i;
        for (int t = i; t < n; t++)
            if (a[j] > a[t])
                j = t;
        if (i != j)
            answer.push_back(make_pair(i, j));
        swap(a[i], a[j]);
    }

This solution makes at most n-1 swap operation. Also if (i != j) is not necessary.

489B - BerSU Ball

There are about 100500 ways to solve the problem. You can find maximal matching in a bipartite graph boys-girls, write dynamic programming or just use greedy approach.

Let's sort boys and girls by skill. If boy with lowest skill can be matched, it is good idea to match him. It can't reduce answer size. Use girl with lowest skill to match. So you can use code like:

sort(boys.begin(), boys.end());
sort(girls.begin(), girls.end());

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (abs(boys[i] - girls[j]) <= 1)
        {
            girls[j] = 1000;
            result++;
            break;
        }

489C - Given Length and Sum of Digits...

There is a greedy approach to solve the problem. Just try first digit from lower values to higher (in subtask to minimize number) and check if it is possible to construct a tail in such a way that it satisfies rule about length/sum. You can use a function `can(m,s)' that answers if it is possible to construct a sequence of length m with the sum of digits s:

bool can(int m, int s)
{
    return s >= 0 && s <= 9 * m;
}

Using the function can(m,s) you can easily pick up answer digit-by-digit. For the first part of problem (to minimize number) this part of code is:

    int sum = s;
    for (int i = 0; i < m; i++)
        for (int d = 0; d < 10; d++)
            if ((i > 0 || d > 0 || (m == 1 && d == 0)) && can(m - i - 1, sum - d))
            {
                minn += char('0' + d);
                sum -= d;
                break;
            }

The equation (i > 0 || d > 0 || (m == 1 && d == 0)) is needed to be careful with leading zeroes.

489D - Unbearable Controversy of Being

Let's iterate through all combinations of a and c just two simple nested loops in O(n²) and find all candidates for b and d inside. To find candidates you can go through all neighbors of a and check that they are neighbors of c. Among all the candidates you should choose two junctions as b and d. So just use https://en.wikipedia.org/wiki/Combination All you need is to add to the answer , where r is the number of candidates (common neighbors of a and c). The code is:

    for (int a = 0; a < n; a++)
        for (int c = 0; c < n; c++)
            if (a != c)
            {
                int r = 0;
                for (int b = 0; b < nxt[a].size(); b++)
                    if (nxt[a][b] != a && nxt[a][b] != c && g[nxt[a][b]][c])
                        r++;
                result += r * (r - 1) / 2;
            }

It is easy to see that the total complexity is O(nm), because of sum of number of neighbors over all junctions is exactly m.

P.S. I'll be grateful if some of you will write editorial of E and F in comments because of now I should leave Codeforces and will return back some hours later. Thank you for participation!