Do you already have a New Year's mood?

And we have traditional gifts!

Change Handle Feature

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 an old handle would automatically redirect to the actual profile.

Again, this year if you took part in at least 10 rounds you can request a handle of an inactive participant. It means that the participant should have a period of activity on Codeforces of at most 180 days, this period should be in 2016 or earlier. The inactive participant can't have posted comments, messages and so on. It can't take part in more than 2 contests. It will be automatically renamed and informed by email. A user has the opportunity to request back his/her handle: in this case, we will roll back the change and return your previous handle to you. If you can't change your handle to another, it means that some requirement doesn't meet. Please do not ask me to do something with it. I'm not Santa Claus.

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 ..."

New Year's Masquerade of Colors and Ranks

The traditional magical tab has appeared in the profile setting. Happy New Year!

Many thanks to cannor147 and geranazavr555 for the help with the translation into English.

1259A - Happy Birthday, Polycarp!

Problem Writer: MikeMirzayanov

1259B - Make Them Odd

Problem Writer: MikeMirzayanov

1259C - As Simple as One and Two

Problem Writer: MikeMirzayanov

1259D - Let's Play the Words?

Problem Writer: MikeMirzayanov

1259E - Two Fairs

Problem Writer: MikeMirzayanov

1259F - Beautiful Rectangle

Problem Writer: MikeMirzayanov

1259G - Tree Elimination

Problem Writers: Endagorion

1276E - Four Stones

Problem Writers: Endagorion

1276F - Asterisk Substrings

Problem Writers: voidmax

This weekend, on Dec/14/2019 14:05 (Moscow time) we will hold Codeforces Round 606. It is based on problems of Technocup 2020 Elimination Round 4 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fit into this category, please register at Technocup 2020 website and take part in Technocup 2020 - Elimination Round 4.

Problem authors are me, Endagorion and voidmax. Many thanks to the testers: Kostroma, never_giveup, Supermagzzz, AdvancerMan, Stepavly, unreal.eugene, cannor147 and geranazavr555!

Div. 1 and Div.2 editions are open and rated for everyone. As usual, the statements will be provided in English and in Russian. Register and enjoy the contests!

Good luck on the round
— MikeMirzayanov

UPD 1: The scoring:

• D1: 500-1000-1250-2000-2250-3000
• D2: 500-1000-1500-1500-2000-2500

Hello,

Initially, the problem 1255B - Fridge Lockers was with no constraint $$$m \le n$$$ (just $$$m \le 2000$$$). Almost all participants (and me) invented wrong solution like: "make a cycle plus take the cheapest edge $$$m-n$$$ times". The counter-example is $$$n=5$$$, $$$m=6$$$ and prices are $$$3, 4, 1, 4, 5$$$. Look into the picture:

It was really unexpected for my intuition (and, of course, failed a proof).

Do you know the solution for this case?

Hello!

ICPC Southern and Volga Russian Regional Contest (Northern Eurasia) 2019 has ended on October 15. There were 76 teams onsite in Saratov, most of them were invited because of their result on the qualification stage.

On Oct/27/2019 12:35 (Moscow time) will start online-mirror 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred).

In this contest I play a role of Cheif Judge and the jury teams consists of ex-participants of ICPC from Saratov and jury members from other cities. Many thanks to all of them! I hope you will like the problems!

I invite ICPC teams and individual participants of Codeforces competitions to take part! Sure, the contest will be unrated.

— MikeMirzayanov

Hello!

Codeforces supports a wide range of languages. Just yesterday I supported Java 11.

On the other hand, my website is not only just open public rounds and trainings, but also an advanced system of groups, custom domains and mashups. This ecosystem makes it possible to conduct private trainings, local contests/olympiads, provides the work of computer science clubs, and so on.

Sometimes you ask me to somehow limit the languages that can be used in a particular contest. For example, an official competition is held that does not support Rust. Or this contest is a practical session specifically for classes in Python.

Now you can configure allowed programming languages (more precisely, their groups) for your mashups and private trainings. Thanks for the help to geranazavr555 who helped to realize this opportunity!

Here are some screenshots of how it looks in action.

Edit a contest settings to specify the list of allowed languages.

You can choose program languages groups your contest supports.

Hope you enjoy the feature,
— MikeMirzayanov

Hi Codeforces!

Unfortunately, ill-wishers thwarted the round by making DDOS on our infrastructure. Neither the coordinator nor the writers of the round are subjects to blame for the failure. Please do not downvote the announcement of the round. I think that this situation is an additional reason to support the writers. They worked hard and prepared good problems!

Apparently, such an attack should be regarded as a symptom of the fact that Codeforces outgrew the youth phase and entered serious adult life. Of course, we will respond with adequate measures to protect ourselves from such incidents. Fortunately, for almost 10 years of work, a large community has formed around those who care about Codeforces. We are not worried about possible additional expenses or efforts. We can do this. The rounds must go on.

— MikeMirzayanov

UPD 1: All three of today's rounds will be unrated.

UPD 2: Hooray! Today we've survived another DDOS attack. The round was not perfect, but it was not ruined!

Hello.

It is not an official announcement of the events. Just information: The contest on Sep/22/2019 12:05 (Moscow time) will be only for onsite finalists. The mirror round will be the next day on Sep/23/2019 17:05 (Moscow time).

Hope to see many participants. Guess, who are the main writers of the Final?

Hello Codeforces!

I hope you enjoyed the problems. I forgot to mention the contribution of testers to the preparation of problems in the round announcement. I apologize and correct myself. Many thanks to the testers: elizarov, ashmelev, KAN, arsijo, adedalic and Roms. Also many thanks to my co-authors: 300iq and geranazavr555. Special thanks to cannor147 who helped with translations.

1211A - Three Problems

Problem writer: MikeMirzayanov

1211B - Traveling Around the Golden Ring of Berland

Problem writer: MikeMirzayanov

1211C - Ice Cream

Problem writers: MikeMirzayanov, geranazavr555

1211D - Teams

Problem writer: MikeMirzayanov

1211E - Double Permutation Inc.

Problem writers: MikeMirzayanov, geranazavr555

1211F - kotlinkotlinkotlinkotlin...

Problem writer: MikeMirzayanov

1211G - King's Path

Problem writer: MikeMirzayanov

1211H - Road Repair in Treeland

Problem writer: MikeMirzayanov

1211I - Unusual Graph

Problem writer: 300iq

Hello!

We are very pleased to cooperate with XTX Markets, thanks to whom we are able to hold the Global rounds. Four of the six of them are already passed and here are the current results.

In short, XTX Markets is a leading quantitative-driven electronic market maker Launched in 2015, XTX Markets has rapidly become the number 1 FX spot liquidity provider by volumes globally, surging ahead of global banks.

Thanks for supporting our community!

We are happy to announce that XTX recently launched the XTX Markets Global Forecasting Challenge, powered by Correlation One.

The XTX Markets Global Forecasting Challenge is an online competition for aspiring quantitative professionals, where contestants are tasked to develop a predictive model based on training data provided by XTX.

Competition highlights include:

• Over $100,000 in total cash prizes.
• $7,500 for the best submission from a participant aged under-25 (as of 1st July 2019).
• Exciting job opportunities in London.
• Opportunity to compete against the best quantitative minds from around the world.

The competition is open to all data-minded contestants from 1st of July to 30th of September, 2019.

To get started, please sign up below.

We hope you'd be interested!

Hi Codeforces.

Recently there have been several improvements on the website. A little later, I will write a short note about them. Here I want to tell about a noticeable new functionality that has recently been implemented by kuviman.

Sometimes after the end of a round there are requests in comments to add a particular test. And problem writers or coordinators add it manually. Now this process is automated.

Meet the uphacking phase!

Now, after the end of almost any contest, participants from Div.1 have the opportunity to hack any solution in this contest during the week. Yes, including official solutions from rounds. In case of successful hacking:

• Your test will be automatically added to the problem and will be used in the future when testing new solutions for this problem;
• If a hacked solution is a practice (i.e. upsolving), then its verdict will change to “hacked” otherwise its verdict will remain unchanged;
• The participant whose solution has been hacked will be notified via system private message;
• Each solution can be successfully hacked only once.

In order to add only adequate and reasonable tests, it is forbidden to hack solutions that intentionally contain a mistake. Please strictly follow this rule. It is because of the possibility of inadequate behavior that we cannot open uphacking for everyone.

I hope that this innovation will be useful and tests for problems will become even better!

• MikeMirzayanov

UPD: Probably, later we will extend uphacking phase and reduce the rating bound.

Hello,

Do you remember my post New: Diagnostics of Solutions in C++? If not, please read it.

Recently, I've implemented better UI to show you diagnostics. Now in on the status pages sometimes you can notice something like this:

Click to the and you'll see the code with the highlighted problematic line and description with the possible reason of the mistake.

Do you like it?

In 2019, with the support of XTX Markets, 6 rounds of the new Codeforces Global Rounds will be held. These will be common rounds for both divisions of 7–9 problems each. The duration of the rounds will be 2-3 hours, depending on the number and complexity of the problems. All such rounds will be rated for all participants. At each such round, 50 brand T-shirts will be handed out, and we will be happy to give T-shirts to all authors and problem testers.

The prizes for the 6-round series in 2019:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over all series get sweatshirts and place certificates.

Current standings after two rounds:

During the past few days, we have done some internal optimizations (thanks, kuviman). Before the start of Codeforces Global Round 3, I want to be absolutely sure that everything works correctly. I ask you to help us to test the system. Please, take part in Testing Round 15 (Unrated). It is unrated, contains 1-2 easy well-known problems. The pretests will be extremely weak to increase the number of hacks. Thanks!

UPD: It seems everything works great. Thanks!

Hello, Codeforces!

Today I’ve released an important update of the Polygon — partial support for advanced properties of resources. The main task that is being solved by this update is to support the development of problems with graders.

In most competitions, participants need to submit a complete solution code, including reading an input reading and an output writing. For example, in Codeforces rounds you solve such kind of problems. However, in some competitions another approach is using: a participant needs to implement the required function or interface.

For example, in a problem statement can be written that in a C ++ solution you need to implement a function that has prototype int sum (int a, int b) and submit the implementation. In this case, a participant has to submit a source code that contains the implementation of this function. Then, in the process of judging this solution for such a problem, an online judge should compile and link into a single executable file the file sent by the participant and a special jury-prepared file that contains the rest of the necessary code (in particular, there will be the function main).

In the case of problem ``A + B’’, such file, which is called a grader, might look like (grader.cpp):

#include <iostream>
int sum(int a, int b);
int main() {
	int a, b;
	std::cin >> a >> b;
	std::cout << sum(a, b) << std::endl;
}

A solution might look like:

int sum(int a, int b) {
    return a + b;
}

Therefore, a grader cannot be independently compiled into an executable file: it also needs a solution to the problem.

And now basic support for such problems in Polygon has been implemented (thanks to PavelKunyavskiy and cannor147 for the help!). I've started with C++ support only.

In order to add grader files, you must upload them as resources, specifying additional advanced properties: that resources are applicable to cpp.* language group, that they are compile-time resources and that solutions need to be compiled with them.

After adding such resources, while compiling solutions, they will be in the same folder with the solution, and those resources that are C++ files will be appended to the compiler command line.

Please note that all additional information for resources is available in the problem descriptor file problem.xml. Also, API is updated (see the documentation for the methods problem.files and problem.saveFile).

Later, the support of some other languages will be added. Also, I’ll add a feature to attach resources in a similar way not to solutions only, but also to validators/integrators/checkers. Of course, you can expect support for such kind of problems on Codeforces. I note that such problems can be used not only in olympiads/contests but also in the educational process. For example, I can easily imagine an exercise on Java, where you need to implement a given interface, and all other routines (unit tests and other things) are hidden in resources files.

P.S. The support of graders appeared for a special reason: today in Russia begins the IOI training camp. The best high school students will compete for the right to represent Russia on International Olympiad in Informatics. I hope, this feature will help the scientific committee to write new problems. And I wish participants every success and luck!

Many thanks to problem authors — Tech Scouts instructors. Please, review the author's solutions. They are beautiful and short. Our community has many to learn from mathematicians!

What do you know about real Mathforces? This is a world full of numbers, theorems and formulas. Are you ready for the adventure full of challenges and dangers in a new world?

Our friends from Harbour.Space University, the International Tournament of Young Mathematicians (ITYM) and St. Paul's International School Barcelona for the second time organize Tech Scouts — two week International summer camp for high school students. I really think it is a valuable and useful initiative.

For some participants the organizers cover participation fee, the decision is based on the results in special online math test and phone interview.

I invite you to take part in Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated). It was offered to candidates a year ago, in 2018. This year participants can use it as a practice. I think for many of you it will be interesting to compare your math skills. It starts on May/05/2019 11:05 (Moscow time).

The duration of the test will be 2 hours. You will be offered about 20 math questions. Each of them are expected to be solved using math skills. Please refrain from writing code and try to solve problems without any programming.

You can skip questions or re-submit answers during the test. All the answers will be judged after the test ends. Each question costs 1-3 points in case of the correct answer. Please, do not share your answers before the end of the test.

For sure, the test will be unrated.

Please refrain from participation if you have already participated in this test last year.

UPD 1: The problems will be in English.

UPD 2: The tutorials are published.

Hello,

Three days ago I was forced to come back to ITMO (at midnight!) to turn on the server. I was just happy that the night security at the university understood everything and I got into the server room without any issues. It seems the server was overheated and and shut down. Today, I and cdkrot are planning to update a thermal grease in it. We have not done this before (but I watched the video on YouTube). Wish us good luck!

Hi!

I didn't find any blog post about the round. So, let's discuss it. I'm a little bit upset, because I didn't solve C. Actually, on last minutes I wrote the solution which should pass if replace linear searches with binary.

Am I right that now Google doesn't publish tests?

P.S. And eatmore is right. The standings are completely unusable (

ICPC World Finals 2019 will begin on April 4, 2019 at 11:00 (UTC). This event is the main event of the year in the world of sports programming!

In the past 20 years alone, ICPC participation has increased by more than 2000%. The contest evolved into its present form as a multi-tier competition in 1977, with the first finals held in conjunction with the ACM Computer Science Conference. Last year, ICPC Regional participation included 52,709 of the finest students and faculty in computing disciplines from 3,233 universities in 110 countries. We remind you that in the current world champion is the team of Moscow State University.

Codeforces wishes the teams to show a vivid and interesting contest. We wish to find beautiful solutions, write without bugs and enjoy many accepted problems!

Links:

• Current results
• Official website of the championship
• ICPC News (photo, video about the Finals)
• ICPC Live (broadcast and not only)
• List of the Teams (with Codeforces handles)
• Online Mirror Contest

Hi Codeforces!

Here are some recent improvements here and in Polygon.

Weak and Leaked Passwords

We often hear about password leaks from various services. Considering that having common passwords is a common (but insecure) practice, we've improved Codeforces and Polygon to identify weak or leaked passwords. If on the top of the website you see a message that your password is not secure, then just change it immediately.

Type of the round when creating a contest proposal

This item improves our work with the writers. When creating a contest proposal, please indicate the type of a round. Leave the field empty only if you don't know the type of the round (it is strange).

Calendar

We've fixed errors when synchronizing official Codeforces rounds with the calendar. Now everything should be correct.

I trust this user

Currently, Codeforces provides a mature infrastructure for organizing contests, olympiads and trainings. With the help of domain groups and mashups, competitions of various levels were hosted on Codeforces. The organizers are sometimes not regular users of Codeforces rounds and do not have rights to some of the actions. Now, any red user can confirm his trust in another account, and he will get the right to: write comments/posts, create private groups, create mashups. I hope this will save me from a certain routine of processing such requests.

Confirmation via email when entering Polygon

When you sign in Polygon, your IP-address and browser will be verified. If you didn't use them in the recent past, then you may be asked to sign in with a confirmation email. In this case, just follow the secret link that comes to your email.

Thanks for taking part in the round. I hope you enjoyed the round. It happens that the statements were really easy to understand (thanks to testers). We've got only 38 questions during a round!

int n, m;
cin >> n >> m;
int result = -1;
if (m % n == 0) {
    result = 0;
    int d = m / n;
    while (d % 2 == 0)
        d /= 2, result++;
    while (d % 3 == 0)
        d /= 3, result++;
    if (d != 1)
        result = -1;
}
cout << result << endl;

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
    cin >> a[i];
int result = 0;
int len = 0;
for (int i = 0; i < 2 * n; i++) {
    if (a[i % n] == 1) {
        len++;
        result = max(result, len);
    } else {
        len = 0;
    }
}
cout << result << endl;

int n;
cin >> n;
vector<int> q(n - 1);
long long sum = 0;
long long min_val = 0;
for (int i = 0; i + 1 < n; i++) {
    cin >> q[i];
    sum += q[i];
    if (sum < min_val)
        min_val = sum;
}
vector<long long> p(n);
p[0] = 1 - min_val;
forn(i, n - 1)
    p[i + 1] = p[i] + q[i];
bool ok = true;
for (int i = 0; i < n; i++)
    if (p[i] < 1 || p[i] > n)
        ok = false;
if (ok)
    ok = set<long long>(p.begin(), p.end()).size() == n;
if (ok) {
    forn(i, n)
        cout << p[i] << " ";
} else
    cout << -1 << endl;

#define forn(i, n) for (int i = 0; i < int(n); i++)
const int A = 26;
...
int n;
cin >> n;
string l;
cin >> l;
vector<vector<int>> left(A);
vector<int> wl;
forn(i, n)
    if (l[i] != '?')
        left[l[i] - 'a'].push_back(i);
    else
        wl.push_back(i);
string r;
cin >> r;
vector<vector<int>> right(A);
vector<int> wr;
forn(i, n)
    if (r[i] != '?')
        right[r[i] - 'a'].push_back(i);
    else
        wr.push_back(i);
vector<pair<int,int>> p;
vector<int> cl(A), cr(A);
forn(i, A) {
    forn(j, min(left[i].size(), right[i].size()))
        p.push_back(make_pair(left[i][j] + 1, right[i][j] + 1));
    cl[i] = cr[i] = min(left[i].size(), right[i].size());
}
forn(i, A)
    while (cl[i] < left[i].size() && !wr.empty()) {
        p.push_back(make_pair(left[i][cl[i]] + 1, wr[wr.size() - 1] + 1));
        cl[i]++;
        wr.pop_back();
    }
forn(i, A)
    while (cr[i] < right[i].size() && !wl.empty()) {
        p.push_back(make_pair(wl[wl.size() - 1] + 1, right[i][cr[i]] + 1));
        wl.pop_back();
        cr[i]++;
    }
forn(j, min(wl.size(), wr.size()))
    p.push_back(make_pair(wl[j] + 1, wr[j] + 1));
cout << p.size() << endl;
for (auto pp: p)
    cout << pp.first << " " << pp.second << endl;

long long H;
int n;
cin >> H >> n;
vector<long long> a(n);
long long sum = 0;
long long gap = 0;
long long h = H;
for (int i = 0; i < n; i++) {
    cin >> a[i];
    sum -= a[i];
    h += a[i];
    if (h <= 0) {
        cout << i + 1 << endl;
        return 0;
    }
    gap = max(gap, sum);
}
if (sum <= 0) {
    cout << -1 << endl;
    return 0;
}

long long whole = (H - gap) / sum;
H -= whole * sum;
long long result = whole * n;

for (int i = 0;; i++) {
    H += a[i % n];
    result++;
    if (H <= 0) {
        cout << result << endl;
        break;
    }
}

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
    cin >> a[i];
map<int, vector<pair<int,int>>> segs;
for (int r = 0; r < n; r++) {
    int sum = 0;                              
    for (int l = r; l >= 0; l--) {
        sum += a[l];
        segs[sum].push_back({l, r});
    }
}
int result = 0;
vector<pair<int,int>> best;
for (const auto& p: segs) {
    const vector<pair<int,int>>& pp = p.second;
    int cur = 0;
    int r = -1;
    vector<pair<int,int>> now;
    for (auto seg: pp)
        if (seg.first > r) {
            cur++;
            now.push_back(seg);
            r = seg.second;
        }
    if (cur > result) {
        result = cur;
        best = now;
    }
}
cout << result << endl;
for (auto seg: best)
    cout << seg.first + 1 << " " << seg.second + 1 << endl;

int n, k, r;
vector<vector<pair<int,int>>> g;
int D;
vector<int> col;

void dfs(int u, int p, int f) {
    int color = 0;
    for (auto e: g[u])
        if (p != e.first) {
            if (color == f) {
                color = (color + 1) % D;
                f = -1;
            }
            col[e.second] = color;
            dfs(e.first, u, color);
            color = (color + 1) % D;
        }         
}

int main() {
    cin >> n >> k;
    g.resize(n);
    vector<int> d(n);
    for (int i = 0; i + 1 < n; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
        d[x]++, d[y]++;
    }
    map<int,int> cnt;
    for (int dd: d)
        cnt[dd]++;
    
    int kk = n;
    D = 0;
    for (auto p: cnt)
        if (kk > k)
            D = p.first,
            kk -= p.second;
        else
            break;
    col = vector<int>(n - 1);
    dfs(0, -1, -1);    
    cout << D << endl;
    for (int i = 0; i + 1 < n; i++)
        cout << col[i] + 1 << " ";
}

Hello, Codeforces!

I am pleased to invite you to Codeforces Round 547 (Div. 3), which will start on Mar/19/2019 17:35 (Moscow time). Everyone whose current rating is strictly less than 1600 is invited to participate officially. All others can take part out of the competition.

It so happened that the schedule of this month is not replete with rounds (coordinators, we hope for you!). Therefore I decided to partially correct the situation. All the problems of this round were invented and prepared by me on the last day of Hello Muscat Programming Bootcamp 2019 and on flights from Muscat to St. Petersburg. I even specially noted the time for preparation: for the current moment (the problems are ready for testing) I spent about 6 hours on their preparation, including inventing some of the problems. I really like working on problems, this is something at the intersection of creativity and programming. I really hope you enjoy the result of my work.

I am in Oman while writing the problems for the round.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over. You will be given 6-8 problems for 2 hours to solve them.

Note that the penalty for incorrect submissions in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

I hope a little later a list of thanks to testers will appear instead of this paragraph. So far I only plan to give the round to testing. Many thanks to the testers ivan100sic, KrK, Benq, I_love_Tanya_Romanova, nhho! UPD: And extra thanks to more testers Pavs, awoo, Narts, anon20016, Stresshoover, Ivan19981305.

Good luck on the round
— MikeMirzayanov

Hello!

We supported the rendering of LaTeX-formulas with MathJax in new posts and comments. Now the formulas will be as beautiful as in problem statements. Drawback: they are displayed not immediately, but redrawn after the page is displayed. Old posts and comments are displayed in the old way (already a lot of old content, backward compatibility is very important). Note that if you edit old post, it will still be displayed in the old style.

Here are some example: $$$1 \le n \le 10^{12}$$$,  $$$c = \sqrt{a^2+b^2}$$$,  $$$i\hbar\frac{\partial}{\partial t}\left|\Psi(t)\right \gt =H\left|\Psi(t)\right \gt $$$.