Greetings Codeforces Community!

Hope you are doing well, practicing social distancing and are continuing to learn during this time. 

The CodeChef April Long Challenge will begin soon! That means 10 days of intense non-stop coding where you can learn while competing in a contest. 

The contest will be live from 3rd April till 13th April. So code, learn and don't forget to become a part of this exceptional race to the top of the leaderboard.

The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese. 

Also if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them here.

Code against Programmers from all over the globe in this thrilling contest! Accompanying me on the problem setting panel are:

• Setters: Kritagya Agarwal, hackslash_123 (Raj Khandor), dvyn01 (Divyanshu Pandey), BohdanPastuschak (Bohdan Pastuschak), pieguy (David Stolp), 300iq (Ildar Gainullin), Dragonado (Chaithanya Shyam), Ashish Lal
• Tester: fmota (Felipe Mota)
• Editorialist: taran_1407 (Taranpreet Singh)
• Statement Verifier: Xellos (Jakub Safin)
• Admin: Alex_2oo8 (Alexey Zayakin)
• Russian Translator: Mediocrity (Fedor Korobeinikov)
• Vietnamese Translator: Team VNOI
• Bengali Translator: solaimanope (Mohammad Solaiman)
• Hindi Translator: Akash Shrivastava
• Mandarin Translator: Ioser (Hanlin Ren)

Contest Details:

• Time: 3rd April 2020 (1500 hrs) to 13th April 2020 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.  

• Contest link: https://bit.ly/APRIL20-Codeforces

• Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.

• Prizes: Top 20 performers in the Indian category and top 10 performers in the Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://goodies.codechef.com/

Good Luck! Hope to see you participating! Happy Programming!

Greetings Codeforces Community!

The CodeChef February Long Challenge is all set to be served. We invite coders from across the community to become a part of this ten-day long coding Contest. 

The Chef’s 11th Birthday is right around the corner and he has a special pre-birthday present for all participants of the February Long Challenge. Scholarships for the CodeChef DSA Certification will be awarded to some of the top-ranking coders. The present gives you the opportunity to win scholarships of as much as 100% too!

The contest will be live from 7th February till 17th February. So code, learn and don't forget to become a part of this exceptional race to the top of the leaderboard.

The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese.

Also if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them here.

Code against Programmers from all over the globe in this thrilling contest! Accompanying me on the problem setting panel are:

• Setters: sahi1422 (Sahil Chimnani), Alex_2oo8 (Alexey Zayakin), rishup132 (Ritesh Gupta), foyaz05 (Foyaz Akanda), Morphy (Alei Reyes), jtnydv25 (Jatin Yadav), Simon St James, Kushal Goel, nagpaljatin1411 (Jatin Nagpal)

• Tester: radoslav11 (Radoslav Dimitrov)

• Editorialist: tmwilliamlin168 (William Lin)

• Statement Verifier: Xellos (Jakub Safin)

• Admin: Alex_2oo8 (Alexey Zayakin)

• Russian Translator: Mediocrity (Fedor Korobeinikov)

• Vietnamese Translator: Team VNOI

• Bengali Translator: solaimanope (Mohammad Solaiman)

• Hindi Translator: Akash Shrivastava

• Mandarin Translator: Ioser (Hanlin Ren)

Contest Details:

• Start Date & Time: 7th February 2020 (1500 hrs) to 17th February 2020 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

• Contest link: http://bit.ly/FEB20-Codeforces

• Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.

• Prizes: Top 20 performers in the Indian category and top 10 performers in the Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://goodies.codechef.com/

Good Luck! Hope to see you participating! Happy Programming!

Greetings Codeforces Community!

To mark a delightful beginning to the month of December, CodeChef is all set to serve the December Long Challenge. A chance to secure an improved rating and heaps of mouthwatering CodeChef Laddus.

We’d encourage everyone to partake in this long contest which runs from 6th December till 16th December. It is an occasion to put to test your exceptional programming skills.

The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese. Also if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them here.

Come join your fellow programmers and actively participate in this thrilling contest! Accompanying me on the problem setting panel are:

• Setters: Vivek1998299 (Vivek Chauhan), Bhavya Rustgi, Akash_Tike (Akash Tike), rishup132 (Ritesh Gupta), Atreus (Abolfazl Soltani), foyaz05 (Foyaz Akanda), Alex_2oo8 (Alexey Zayakin), Rezwan.Arefin01 (Rezwan Arefin), vijju123 (Abhishek Pandey)

• Tester: 300iq (Ildar Gainullin)

• Editorialist: adamant (Alexander Kulkov)

• Statement Verifier: Xellos (Jakub Safin)

• Admin: Alex_2oo8 (Alexey Zayakin)

• Russian Translator: Mediocrity (Fedor Korobeinikov)

• Vietnamese Translator: Team VNOI

• Bengali Translator: solaimanope (Mohammad Solaiman)

• Hindi Translator: Akash Shrivastava

• Mandarin Translator: Ioser (Hanlin Ren)

Contest Details:

• Start Date & Time: 6th December 2019 (1500 hrs) to 16th December 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

• Contest link: http://bit.ly/DEC19-Codeforces

• Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.

• Prizes: Top 20 performers in the Indian category and top 10 performers in the Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://goodies.codechef.com/

Good Luck! Hope to see you participating! Happy Programming!

Greetings Codeforces Community!

Did you enjoy our servings in the CodeChef’s September Lunchtime? Hopefully, you achieved an improved rating and a bunch of mouthwatering ACs.

Now, the CodeChef’s October Long Challenge is just around the corner. We urge everyone from our community to take part in this contest, starting 4th October till 14th October. It will be an occasion where you put to test your exceptional programming skills.

The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

Do join your fellow programmers and actively participate in this thrilling contest! Accompanying me on the problem setting panel are:

• Admin: Alex_2oo8 (Alexey Zayakin)

• Tester: Ioser (Hanlin Ren)

• Editorialist: Ioser (Hanlin Ren)

• Statement Verifier: Xellos (Jakub Safin)

• Setters: Alex_2oo8 (Alexey Zayakin), iamabjain (Abhinav Jain), jarvisnaharoy (Saranya Naha Roy), mayank1601 (Mayank Agrawal), shubhankarbhagwat.sb (Shubhankar Bhagwat), Alif01 (Fang Lixing), Mikaeel (Mikaeel Ghorbani)

• Russian Translator: Mediocrity (Fedor Korobeinikov)

• Vietnamese Translator: Team VNOI

• Bengali Translator: solaimanope (Mohammad Solaiman)

• Hindi Translator: Akash Shrivastava

• Mandarin Translator: Ioser (Hanlin Ren)

Contest Details:

• Start Date & Time: 4th October 2019 (1500 hrs) to 14th October 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.   

• Contest link: http://bit.ly/2o7Pdty

• Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.

• Prizes: Top 20 performers in Indian category and top 10 performers in Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://goodies.codechef.com/

(For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating! Happy Programming!

Greetings Codeforces Community!

Brace yourself because Long Challenge contest of the month is HERE! Expect nothing short of a thoroughly thrilling 10-day code-cation; featuring exciting problems, amazing competition and lastly, a chance to level up your rating.

Moreover, the Long Challenge is particularly crafted to help you hone your coding skills, while competing amongst the best of the best. Top 20 participants from each college/university will win scholarships for CodeChef Certification exam. Visit the contest page to know more.

In addition, if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them with our admins here: https://www.codechef.com/problemsetting/new-ideas

Do join your fellow programmers and actively participate in this exciting contest. Joining me on the problem setting panel are:

• Setters: Newaj_69 (Md. Shafiq Newaj Shovo), Soul_Full_Of_Thunder (Yulian Yarema), sayantan_das24 (Sayantan Das), YouG22 (Utkarsh Garg), kartik_24 (Kartik Singhal), mraron (Noszály Áron), babin (Claudiu Babin), VladProg (Vlad Zavodnik), Danylo99 (Danylo Mocherniuk), Lewin (Lewin Gan), Morphy (Alei Reyes)
• Admin: Alex_2oo8 (Alexey Zayakin)
• Editorialist: vijju123 (Abhishek Pandey)
• Statement Verifier: Xellos (Jakub Safin)
• Russian Translator: Mediocrity (Fedor Korobeinikov)
• Vietnamese Translator: Team VNOI
• Bengali Translator: solaimanope (Mohammad Solaiman)
• Hindi Translator: Akash Shrivastava
• Mandarin Translator: gediiiiiii (Gedi Zheng)

Contest Details:

• Start Date & Time: 2nd August 2019 (1500 hrs) to 12th August 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
• Contest link: https://bit.ly/2LFPyxM
• Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.
• Prizes: Top 20 performers in Indian category and top 10 performers in Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://goodies.codechef.com/

(For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating! Happy Programming!

Greetings Codeforces community!

Come participate in CodeChef’s February Long challenge sponsored by ShareChat! This is a 10-day contest that invites participants to solve 7 problems and 1 tie-breaker style challenge problem. The contest is open to programmers of all skill levels. The contest problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

Participants of Long Challenge also have an opportunity to apply for job openings at ShareChat — India’s fastest growing social network! Visit the contest link to know more.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
- Testers: Alex_2oo8 (Alexey Zayakin), yashChandnani (Yash Chandnani)
- Editorialist: taran_1407 (Taranpreet Singh)
- Statement Verifier: Xellos (Jakub Safin)
- Setters: hmrockstar (Himanshu Mishra), Akil Vohra, Aditya Dimri, Daanish Mahajan, TooDumbToWin (Pranjal Jain), mraron (Áron Noszály), Slow_But_Determined (Abdullah Aslam), Stylianos Kasouridis, Alexander Zhou, Danylo Mocherniuk
- Russian Translator: Mediocrity (Fedor Korobeinikov)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: Team VNOI
- Bengali Translator: solaimanope (Mohammad Solaiman)
- Hindi Translator: Akash Shrivastava

Contest Details:

• Start Date & Time: 1st February 2019 (1500 hrs) to 11th February 2019 (1500 hrs). (Indian Standard Time, +5:30 GMT) — Check your timezone.
• Contest link: https://www.codechef.com/FEB19
• Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
• Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://www.codechef.com/laddu
  (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating! Happy Programming!

New Year Greetings to the CodeForces Community!

Start off 2018 with some stimulating coding challenges as part of the January Long Challenge from CodeChef. I hope they will give you a pleasant beginning to your coding campaign this year. Joining me on the problem setting panel, we have:

• Problem Setter: kingofbugs (Hruday Pabbisetty), Berezin (Dmytro Berezin), ed1d1a8d (Tiny Wong), chemthan (Trung Nguyen), killjee (Satyam Shubham), kingofnumbers (Hasan Jaddouh), include_sajal (Sajal Agrawal)
• Problem Tester: Alex_2oo8 (Alexey Zayakin)
• Editorialist: adamant (Alexander Kulkov)
• Admin: kingofnumbers (Hasan Jaddouh)
• Statement Verifier: Xellos (Jakub Safin)
• Russian Translator: CherryTree (Sergey Kulik)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: VNOI Team

I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below after the contest.

Contest Details:

Time: 5th January 2018 (1500 hrs) to 15th January 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/JAN18

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 global and top 20 Indian winners get 300 Laddus each, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. For those who have not yet got their previous winning, please send an email to [email protected].

Good Luck! Hope to see you participating!

Hello CodeForces Community!

It’s time to indulge in some appetizing problems which will be served in Lunchtime. So jot down the details, be there and leave your mark in this contest’s leader-board. Joining me on the problem setting panel, we have:

• Problem Setter: mgch (Misha Chorniy)
• Problem Tester: Alex_2oo8 (Alexey Zayakin)
• Problem Editorialist: adamant (Alexander Kulkov)
• Contest Admin: kingofnumbers (Hasan Jaddouh)
• Russian Translator: CherryTree (Sergey Kulik)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: Team VNOI

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below after the contest.

So, note down the details and be there when the contest starts:

Time: 25th November 2017 (1930 hrs) to (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/LTIME54

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: * Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating!!

Hello CodeForces Community!

Chef has served 10 exotic dishes in October Long Challenge. He would like you to take part in the competition and taste all the dishes. So note down the details and be there.

Joining me on the problem setting panel, we have:

• Problem Authors: Berezin (Dmytro Berezin), PraveenDhinwa (Praveen Dhinwa), altruist (Denis Anischenko), adkroxx (Adarsh Kumar), kingofbugs (Hruday Pabbisetty), kingofnumbers (Hasan Jaddouh)
• Problem Tester: Alex_2oo8 (Alexey Zayakin)
• Admin: kingofnumbers (Hasan Jaddouh)
• Language Verifier: Priyank Jaini
• Russian Translator: CherryTree (Sergey Kulik)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: Team VNOI

I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below after the contest.

Contest Details:

Time: 6th October 2017 (1500 hrs) to 16th October 2017 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/OCT17

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: * Top 10 global and top 20 Indian winners get 300 Laddus each, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating!

Hello CodeForces Community!

It’s that time of the month when the finest programmers around the globe battle it out in CodeChef’s Cook-Off. We are ready with the January Cook-Off 2017, so put on your coding hats and whet your appetite for five delectable problems and an action packed Sunday night. I invite you all to join in the contest and have a go at the problems. CodeChef January Cook-Off.

Joining me on the problem setting panel are:

• Problem Setter & Editorialist: Alex_2oo8 (Alexey Zayakin)
• Problem Tester: kingofnumbers (Hassan Jaddouh)
• Russian Translator: CherryTree (Sergey Kulik)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: VNOI Team
• Contest Admin: PraveenDhinwa (Praveen Dhinwa)

I hope you will enjoy solving them. Please give your feedbacks on the problem set in the comments below after the contest. You can find the rest of the details about the contest below.

Time: 22nd January 2017 (2130 hrs) to 23rd January 2017 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK78

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: * Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating!!

664A - Complicated GCD

Author of the idea — GlebsHP

We examine two cases:

1. a = b — the segment consists of a single number, hence the answer is a.
2. a < b — we have gcd(a, a + 1, a + 2, ..., b) = gcd(gcd(a, a + 1), a + 2, ..., b) = gcd(1, a + 2, ..., b) = 1.

#include <bits/stdc++.h>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;

    if (a == b) cout << a;
    else cout << 1;

    return 0;
}

663A - Rebus

Author of the idea — gen

First we check whether any solution exists at all. For that purpose, we calculate the number of positive (the first one and any other with the  +  sign) and negative elements (with the  -  sign) in the sum. Let them be pos and neg, respectively. Then the minimum value of the sum that can be possibly obtained is equal to min = (1 · pos - n · neg), as each positive number can be 1, but all negative can be  - n. Similarly, the maximum possible value is equal to max = (n · pos - 1 · neg). The solution therefore exists if and only if min ≤ n ≤ max.

Now suppose a solution exists. Let's insert the numbers into the sum one by one from left to right. Suppose that we have determined the numbers for some prefix of the expression with the sum of S. Let the sign of the current unknown be sgn ( + 1 or  - 1) and there are some unknown numbers left to the right, excluding the examined unknown, among them pos_left positive and neg_left negative elements. Suppose that the current unknown number takes value x. How do we find out whether this leads to a solution? The answer is: in the same way we checked it in the beginning of the solution. Examine the smallest and the largest values of the total sum that we can get. These are equal to min_left = (S + sgn · x + pos_left - n · neg_left) and max_left = (S + sgn · x + n · pos_left - neg_left), respectively. Then we may set the current number to x, if min_left ≤ n ≤ max_left holds. To find the value of x, we can solve a system of inequalities, but it is easier simply to check all possible values from 1 to n.

BONUS Let k be the number of unknowns in the rebus. Prove that the complexity of the described solution (implementation shown below) is O(k² + n), not O(k · n).

#include<bits/stdc++.h>

using namespace std;

char s[100];

int main() {
    int k = 0, n, pos = 1, neg = 0;
    while (true) {
        char c;
        scanf(" %c", &c);
        scanf(" %c", &c);

        if (c == '=') break;
        if (c == '+') pos++;
        if (c == '-') neg++;

        s[k++] = c;
    }

    scanf("%d", &n);

    if (pos - n * neg > n || n * pos - neg < n) {
        printf("Impossible\\n");

        return 0;
    }

    printf("Possible\\n");

    int S = 0;
    for (int i = 0; i < k; i++) {
        int sgn = 1;
        if (i > 0 && s[i - 1] == '-') sgn = -1;

        if (sgn == 1) pos--;
        if (sgn == -1) neg--;

        for (int x = 1; x <= n; x++)
            if (S + x * sgn + pos - n * neg <= n && S + x * sgn + n * pos - neg >= n) {
                printf("%d %c ", x, s[i]);

                S += x * sgn;

                break;
            }
	}

    printf("%d = %d\\n", abs(n - m), n);

    return 0;
}

662D - International Olympiad

Author of the idea — Alex_2oo8

Consider the abbreviations that are given to the first Olympiads. The first 10 Olympiads (from year 1989 to year 1998) receive one-digit abbreviations (IAO'9, IAO'0, ..., IAO'8). The next 100 Olympiads (1999 - 2098) obtain two-digit abbreviations, because all one-digit abbreviations are already taken, but the last two digits of 100 consecutive integers are pairwise different. Similarly, the next 1000 Olympiads get three-digit abbreviations and so on.

Now examine the inversed problem (extract the year from an abbreviation). Let the abbreviation have k digits, then we know that all Olympiads with abbreviations of lengths (k - 1), (k - 2), ..., 1 have passed before this one. The number of such Olympiads is 10^k - 1 + 10^k - 2 + ... + 10¹ = F and the current Olympiad was one of the 10^k of the following. Therefore this Olympiad was held in years between (1989 + F) and (1989 + F + 10^k - 1). As this segment consists of exactly 10^k consecutive natural numbers, it contains a single number with a k-digit suffix that matches the current abbreviation. It is also the corresponding year.

#include <bits/stdc++.h>

using namespace std;

char s[42];

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        scanf(" %s", s);
        
        int k = strlen(s + 4), year = atoi(s + 4), F = 0, tenPow = 10;
        for (int i = 1; i < k; i++) {
            F += tenPow;
            tenPow *= 10;
        }
        
        while (year < 1989 + F) year += tenPow;
        
        printf("%d\\n", year);
    }

    return 0;
}

662B - Graph Coloring

Author of the problem — gen

Examine the two choices for the final color separately, and pick the best option afterwards. Now suppose we want to color the edges red.

Each vertex should be recolored at most once, since choosing a vertex two times changes nothing (even if the moves are not consecutive). Thus we need to split the vertices into two sets S and T, the vertices that are recolored and the vertices that are not affected, respectively. Let u and v be two vertices connected by a red edge. Then for the color to remain red, both u and v should belong to the same set (either S or T). On the other hand, if u and v are connected by a blue edge, then exactly one of the vertices should be recolored. In that case u and v should belong to different sets (one to S and the other to T).

This problem reduces to 0-1 graph coloring, which can be solved by either DFS or BFS. As the graph may be disconnected, we need to process the components separately. If any component does not have a 0-1 coloring, there is no solution. Otherwise we need to add the smallest of the two partite sets of the 0-1 coloring of this component to S, as we require S to be of minimum size.

#include<bits/stdc++.h>

using namespace std;

const int MX = 100000;

int n, vis[MX];
vector<pair<int, char>> G[MX];
vector<int> part[3];

bool dfs(int v, int p, char c) {
    if (vis[v] != 0) {
        return vis[v] == p;
    }

    vis[v] = p;
    part[p].push_back(v);

    for (auto x : G[v]) {
        if (dfs(x.first, x.second == c ? p : p ^ 3, c) == false)
            return false;
    }

    return true;
}

vector<int> solve(char c) {
    memset(vis, 0, sizeof vis);

    vector<int> ans;
    for (int i = 0; i < n; i++)
        if (vis[i] == 0) {
            part[1].clear();
            part[2].clear();

            if (dfs(i, 1, c) == false) {
                for (int j = 0; j < n + 1; j++) ans.push_back(-1);

                return ans;
            }

            int f = 1;
            if (part[2].size() < part[1].size()) f = 2;

            ans.insert(ans.end(), part[f].begin(), part[f].end());
        }

    return ans;
}

int main() {
    int m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        char c;
        scanf("%d %d %c", &u, &v, &c);
        u--;
        v--;

        G[u].emplace_back(v, c);
        G[v].emplace_back(u, c);
    }

    auto f = solve('R');
    auto g = solve('B');

    if (g.size() < f.size()) f = g;

    if (f.size() > n) {
        printf("-1\\n");

        return 0;
    }

    printf("%d\\n", (int)f.size());
    for (int x : f) printf("%d ", x + 1);
    printf("\\n");

    return 0;
}

662A - Gambling Nim

Author of the idea — GlebsHP

It is known that the first player loses if and only if the xor-sum of all numbers is 0. Therefore the problem essentially asks to calculate the number of ways to arrange the cards in such a fashion that the xor-sum of the numbers on the upper sides of the cards is equal to zero.

Let and . Suppose that the cards with indices j₁, j₂, ..., j_k are faced with numbers of type b and all the others with numbers of type a. Then the xor-sum of this arrangement is equal to , that is, . Hence we want to find the number of subsets c_i with xor-sum of S.

Note that we can replace c₁ with , as applying c₁ is the same as applying . Thus we can freely replace {c₁, c₂} with and c₂ with . This means that we can apply the following procedure to simplify the set of c_i:

1. Pick c_f with the most significant bit set to one
2. Replace each c_i with the bit in that position set to one to
3. Remove c_f from the set
4. Repeat steps 1-5 with the remaining set
5. Add c_f back to the set

After this procedure we get a set that contains k zeros and n - k numbers with the property that the positions of the most significant bit set to one strictly decrease. How do we check now whether it is possible to obtain a subset with xor-sum S? As we have at most one number with a one in the most significant bit, then it tells us whether we should include that number in the subset or not. Similarly we apply the same argument for all other bits. If we don't obtain a subset with the xor-sum equal to S, then there is no such subset at all. If we do get a subset with xor-sum S, then the total number of such subsets is equal to 2^k, as for each of the n - k non-zero numbers we already know whether it must be include in such a subset or not, but any subset of k zeros doesn't change the xor-sum. In this case the probability of the second player winning the game is equal to , so the first player wins with probability .

#include <bits/stdc++.h>

using namespace std;

const int size = 1000 * 1000 + 1;
const int ssize = 100;

int n;
long long a[size], b[size];
long long ort[ssize];
long long p[ssize];

int main() {
    long long cur = 0ll;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld%lld", &a[i], &b[i]);
        cur ^= a[i];
        a[i] ^= b[i];
    }
    a[n] = cur;

    int len = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < len; j++) {
            if (a[i] & p[j])
                a[i] ^= ort[j];
        }
        if (a[i]) {
            ort[len++] = a[i];
            p[len - 1] = ((a[i] ^ (a[i] - 1)) + 1) >> 1;
        }        
    }
    if (a[n]) {
        printf("1/1\\n");
    } else {
        printf("%lld/%lld\\n", (1ll << len) - 1, (1ll << len));
    }

    return 0;
}

662C - Binary Table

Author of the idea — Alex_2oo8

First let's examine a slow solution that works in O(2ⁿ · m). Since each row can be either inverted or not, the set of options of how we can invert the rows may be encoded in a bitmask of length n, an integer from 0 to (2ⁿ - 1), where the i-th bit is equal to 1 if and only if we invert the i-th row. Each column also represents a bitmask of length n (the bits correspond to the values of that row in each of the n rows). Let the bitmask of the i-th column be col_i, and the bitmask of the inverted rows be mask. After inverting the rows the i-th column will become . Suppose that contains ones. Then we can obtain either k or (n - k) ones in this column, depending on whether we invert the i-th column itself. It follows that for a fixed bitmask mask the minimum possible number of ones that can be obtained is equal to .

Now we want to calculate this sum faster than O(m). Note that we are not interested in the value of the mask itself, but only in the number of ones it contains (from 0 to n). Therefore we may group the columns by the value of . Let dp[k][mask] be the number of such i that , then for a fixed bitmask mask we can calculate the sum in O(n) — .

What remains is to calculate the value of dp[k][mask] in a quick way. As the name suggests, we can use dynamic programming for this purpose. The value of dp[0][mask] can be found in O(m) for all bitmasks mask: each column col_i increases dp[0][col_i] by 1. For k > 0, col_i and mask differ in exactly k bits. Suppose mask and col_i differ in position p. Then col_i and differ in exactly (k - 1) bits. The number of such columns is equal to , except we counted in also the number of columns col_i that differ with in bit p (thus, mask and col_i have the same value in bit p). Thus we need to subtract dp[k - 2][mask], but again, except the columns among these that differ with mask in bit p. Let ; by expanding this inclusion-exclusion type argument, we get that the number of masks we are interested in can be expressed as dp[k - 1][next] - dp[k - 2][mask] + dp[k - 3][next] - dp[k - 4][mask] + dp[k - 5][next] - .... By summing all these expressions for each bit p from 0 to n, we get dp[k][mask] · k, since each column is counted in k times (for each of the bits p where the column differs from mask).

Therefore, we are now able to count the values of dp[k][mask] in time O(2ⁿ · n³) using the following recurrence:

This is still a tad slow, but we can speed it up to O(2ⁿ · n²), for example, in a following fashion:

BONUS Are you able to come up with an even faster solution?

#include<bits/stdc++.h>

using namespace std;

char s[100000];
int col[100000], dp[21][1 << 20];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf(" %s", s);

        for (int j = 0; j < m; j++) col[j] |= (s[j] - '0') << i;
    }

    for (int i = 0; i < m; i++) dp[0][col[i]]++;

    for (int k = 1; k <= n; k++)
        for (int mask = 0; mask < (1 << n); mask++) {
            int sum = k > 1 ? (k - 2 - n) * dp[k - 2][mask] : 0;
            for (int p = 0; p < n; p++) sum += dp[k - 1][mask ^ (1 << p)];

            dp[k][mask] = sum / k;
        }

    int ans = n * m;
    for (int mask = 0; mask < (1 << n); mask++) {
        int cnt = 0;
        for (int k = 0; k <= n; k++) cnt += min(k, n - k) * dp[k][mask];

        ans = min(ans, cnt);
    }

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

    return 0;
}

662E - To Hack or not to Hack

Author of the idea — Alex_2oo8

Observation number one — as you are the only participant who is able to hack, the total score of any other participant cannot exceed 9000 (3 problems for 3000 points). Hence hacking at least 90 solutions automatically guarantees the first place (the hacks alone increase the score by 9000 points).

Now we are left with the problem where the number of hacks we make is at most 90. We can try each of the 6³ possible score assignments for the problems in the end of the round. As we know the final score for each problem, we can calculate the maximum number of hacks we are allowed to make so the problem gets the assigned score. This is also the exact amount of hacks we will make in that problem. As we know the number of hacks we will make, we can calculate our final total score. Now there are at most 90 participants who we can possibly hack. We are interested only in those who are on top of us. By hacking we want to make their final score less than that of us. This problem can by solved by means of dynamic programming:

dp[p][i][j][k] — the maximum number of participants among the top p, whom we can push below us by hacking first problem i times, second problem j times and third problem k times.

The recurrence: we pick a subset of solutions of the current participant that we will hack, and if after these hacks we will push him below us, we update the corresponding dp state. For example, if it is enough to hack the first and the third problems, then dp[p + 1][i + 1][j][k + 1] = max(dp[p + 1][i + 1][j][k + 1], dp[p][i][j][k] + 1)

BONUS Can you solve this problem if each hack gives only 10 points, not 100?

#include<bits/stdc++.h>

#define time ololo

using namespace std;

int time[5000][3], n, solved[3], canHack[3], score[3], willHack[3], bestPlace, dp[2][90][90][90], ci, li;

int submissionScore(int sc, int tm) {
    if (tm == 0) return 0;

    return sc * (250 - abs(tm)) / 250;
}

int calcScore(int p) {
    int sum = 0;
    for (int i = 0; i < 3; i++) sum += submissionScore(score[i], time[p][i]);

    return sum;
}

int countHacks(int p) {
    int cnt = 0;
    for (int i = 0; i < 3; i++) cnt += time[p][i] < 0;

    return cnt;
}

int solve() {
    memset(dp, 0, sizeof dp);

    int myScore = 0;
    for (int i = 0; i < 3; i++) myScore += 100 * willHack[i] + submissionScore(score[i], time[0][i]);

    ci = 0;
    li = 1;
    for (int p = 1; p < n; p++)
        if (countHacks(p) > 0 && calcScore(p) > myScore) {
            ci ^= 1;
            li ^= 1;

            for (int i = 0; i <= willHack[0]; i++)
                for (int j = 0; j <= willHack[1]; j++)
                    for (int k = 0; k <= willHack[2]; k++)
                        dp[ci][i][j][k] = dp[li][i][j][k];

            for (int ii = 0; ii < 2; ii++)
                for (int jj = 0; jj < 2; jj++)
                    for (int kk = 0; kk < 2; kk++) {
                        if (ii == 1 && time[p][0] >= 0) continue;
                        if (jj == 1 && time[p][1] >= 0) continue;
                        if (kk == 1 && time[p][2] >= 0) continue;

                        int s = submissionScore(score[0], time[p][0]) * (ii ^ 1)
                              + submissionScore(score[1], time[p][1]) * (jj ^ 1)
                              + submissionScore(score[2], time[p][2]) * (kk ^ 1);

                        if (s > myScore) continue;

                        for (int i = ii; i <= willHack[0]; i++)
                            for (int j = jj; j <= willHack[1]; j++)
                                for (int k = kk; k <= willHack[2]; k++)
                                    dp[ci][i][j][k] = max(dp[ci][i][j][k], dp[li][i - ii][j - jj][k - kk] + 1);
                    }
        }

    int res = 1 - dp[ci][willHack[0]][willHack[1]][willHack[2]];
    for (int p = 1; p < n; p++) if (calcScore(p) > myScore) res++;

    return res;
}

void brute(int p) {
    if (p == 3) {
        int res = solve();

        bestPlace = min(bestPlace, res);

        return;
    }

    for (int i = 0; i < 6; i++) {
        int mn = i == 5 ? 0 : (n >> (i + 1)) + 1;
        int mx = (n >> i);

        if (solved[p] >= mn && solved[p] - canHack[p] <= mx) {
            score[p] = 500 * (i + 1);
            willHack[p] = min(canHack[p], solved[p] - mn);

            brute(p + 1);
        }
    }
}

int main() {
    memset(solved, 0, sizeof solved);
    memset(canHack, 0, sizeof canHack);
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++) {
            scanf("%d", &time[i][j]);

            solved[j] += time[i][j] != 0;
            canHack[j] += time[i][j] < 0;
        }

    if (canHack[0] + canHack[1] + canHack[2] > 89) {
        printf("1\\n");

        return 0;
    }

    bestPlace = n;
    brute(0);

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

    return 0;
}

Hello Codeforces!

The Final Round of CROC 2016 will be held today at 17:15 Moscow time, where the best 50 participants from the Elimination Round will be competing for the valueable prices, as well as for their personal entertainment.

Everyone else will be able to participate in Codeforces Round #347 tomorrow at 19:35 Moscow time that will feature an almost identical problem set. It is going to be a usual unrated round, separate for each division.

The problem set was prepared by Evgeny Vihrov (gen), the one and only coordinator of Codeforces Gleb Evstropov (GlebsHP) and me. I would also like to thank Mike Mirzayanov (MikeMirzayanov) and all of the Codeforces team for the incredible contest development system and Alexander Fetisov (AlexFetisov) for test-solving the problems.

During the Final Round the contest scoreboard will be linked here, but the problems themselves will be available only tomorrow.

We hope that you like our problems. Good luck to the finalists and to everyone else tomorrow!

UPD 1: The link to the current standings: http://codeforces.me/spectator/contest/662/standings

UPD 2: Codeforces Round #347 will be unrated.

UPD 3: Scoring:
Div 1: 500 — 1000 — 1500 — 2500 — 2500
Div 2: 500 — 1000 — 1500 — 2000 — 3000

UPD 4: Congratulations to the winners!

UPD 5: Editorial: http://codeforces.me/blog/entry/44408

Hello everyone!

Very soon on 13 october at 19:30 MSK will take place Codeforces Round #206. I am author of the problems and it's my first round!

I would like to thank problem coordinator Gerald Agapov (Gerald), Evgeny Vihrov (gen) for problem testing and Mary Belova (Delinur) for translation of statements to English. Special thanks to Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Score distribution will be standard in both divisions: 500-1000-1500-2000-2500.

I wish good luck for everyone and hope that you will enjoy the problems!

Congratulations to the winners! Special congratulations to rng_58, the only participant, who have solved all 5 problems!

First division:

1. rng_58
2. sankear
3. VArtem
4. sillycross
5. Endagorion

Second division:

1. sola_93
2. Bega
3. squirtle
4. Dixtosa
5. anupam.kanyal

UPD The editorial has been published.

355A - Vasya and Digital Root

If d = 0, the there is the only number with , so, if k = 1, the answer is 0, otherwise — No solution.

If d > 0, then one of correct numbers is d × 10^k - 1.

Time complexity: O(1) + O(k) for the output.

355B - Vasya and Public Transport

If we buy a ticket of the fourth type, we don't have to buy anything else, so, the answer is min(c₄, answer using tickets of first three types).

Now, when we don't have ticket of the fourth type, we can solve the task separately for buses and trolleys.

Solving the problem only for buses: if we buy a ticket of the third type, we don't have to buy anything else, so, the answer is min(c₃, answer using tickets of first two types).

Without tickets of type three, we can solve the problem separately for each bus. If we buy a ticket of the second type, we will spend c₂ burles and if we buy a_i tickets of the first type, we will spend (a_i × c₁) burles. So, the answer for bus i is min(c₂, a_i × c₁).

Now it is not difficult to obtain the following solution:

  function f(x, k) {
    res = 0;
    for i = 1 .. k
      res = res + min(c2, x[i] * c1);

    return min(c3, res);
  }

  ans = min(c4, f(a, n) + f(b, m));

Time complexity: O(n + m).

354A - Vasya and Robot

Brute force how many times we will use operation from the left. So, if we use it k times, then it's clear, that we will take first k items by the left operations and last (n - k) items by the right operations. So, robot will spend sumLeft[k]·l + sumRight[n - k]·r energy plus some penalty for the same operations. To minimize this penalty we should perform the operations in the following order LRLRL ... RLRLLLLL ..., starting from the bigger set. For example, if k = 7, n - k = 4, we should perform operations in this order: LRLRLRLRL LL. So, we will have to pay the penalty two times (7 - 4 - 1).

sumLeft[i] — sum of first i weights, sumRight[i] — sum of last i weights.

Solution in pseudocode:

  ans = inf;
  for i = 0 .. n {
    curr = firstSum[i] * l + lastSum[n-i] * r;
    if ( i > n - i ) curr = curr + (2i - n - 1) * Ql;
    if ( i < n - i ) curr = curr + (n - 2i - 1) * Qr;

    ans = min(ans, curr);
  }

Time complexity: O(n).

354B - Game with Strings

We will say that cell (r, c) corresponds to a string s, if there exist correct path, which ends in the cell (r, c) and this path corresponds to a string s.

Let call a set of cells which corresponds to some string s a state. One state can correspond to different strings. We can't brute force all possible strings, because their count — is too big, but we can brute force all possible states. It's not hard to observe that all cells that corresponds to some string s lies on same diagonal, so the total count of states is 2¹ + 2² + ... + 2^n - 1 + 2ⁿ + 2^n - 1 + ... + 2² + 2¹ = O(2ⁿ). In implementation we can denote state with diagonal number (from 1 to 2n - 1) and bitmask of cells corresponding to this state (2ⁿ).

From each state we can move to 26 different states (actually less) and all possible moves depends on the state, not on the string. On the image you can see an example of move: from state, which is highlighted in blue by letter a we will move to the state, which is highlighted in yellow.

Now, for each state we can calculate a value of (count of letters A  -  count of letters B) in the string, starting from this state. If at the moment is first players turn (an even diagonal), we have to maximize this value, otherwise — minimize. It can be implemented as recursion with memoization.

The winner can be determined by the value of state, which corresponds to the single cell (1, 1).

Complexity: O(2ⁿ × (n + alpha)), where alpha is the size of alphabet.

354C - Vasya and Beautiful Arrays

The problem was to find greatest d, such that a_i ≥ d,  a_i mod d ≤ k holds for each i.

Let m = min(a_i), then d ≤ m. Let consider two cases:

. In this case we will brute force answer from k + 1 to m. We can check, if number d is a correct answer in the following way:

We have to check that a_i mod d ≤ k for some fixed d, which is equals to , where . Since all these intervals [x·d..x·d + k] doesn't intersects each with other, we can just check that , where cnt[l..r] — count of numbers a_i in the interval [l..r].

Time complexity: O(maxA log maxA), proof is based on the sum of harmonic series.

354D - Transferring Pyramid

This tasks is solvable with dynamic programming. First of all let consider solution with complexity O(n³).

Let dp[i][j] be the answer for the highlighted in blue part (minimal cost of transferring all special cells that lies inside this area). Then dp[n][0] will be the answer for our original problem.

How to recalculate such DP? It's clear that in the leftmost column (inside the blue area) we will choose at most one cell as the top of some subpyramid. If we choose two, then the smallest one will lie fully inside the biggest one (as the orange subpyramid lies inside the blue one). Now, let brute force the cell, which will be the top of subpyramid in this column in time O(n) and we will obtain the following transition:

To simplify the formulas, let assume that .

0 ≤ k ≤ i, where k is the height on which we will choose our top cell, or 0, if we don't choose any subpyramid in this column. sumUp[i][p] — count of special cells in the i-th column at height starting from p, this cells we will have to transfer one by one, using the first type operations.

We can reduce the complexity by one n, if we will recalculate out DP in the following way:

0 ≤ k ≤ i;

for all j > 0.

The proof that this is correct is quite simple and is left to the reader. :)

Also, we can observe that it is not profitably to take some subpyramid with height greater than , because for such subpyramid we will pay  > 3k, but if we transfer all cells using the first type operations we will pay only 3k. So, the second dimension (j) in out DP can be reduced to .

Also, to receive AC, you should store only last 2 layers of the DP, otherwise there will be not enough memory.

Time complexity: .

354E - Lucky Number Representation

Author's solution, much more complicated than suggested by many participants during the competition, easy solution will be described below.

First of all, let write a DP with complexity O(N * lucky_count(N)), where lucky_count(N) is the count of lucky numbers  ≤ N, lucky_count(10ⁿ) = 3ⁿ. As we can see, for all sufficiently large N solution exists. Really — for every N > 523.

Now, we can say that for N ≤ 10000 we have a solution, which is found using DP. Let's solve the task for larger values of N.

Next and key idea is to separate the task into two parts: N = N1 + N2. Let's choose N1 and N2 in such way that for them it was easy to find a solution and then merge these two solutions into one. Let N1 = N mod 4000, N2 = N - N1. Here we can have a problem that there is no solution for number N1, in this case we can do N1 = N1 + 4000, N2 = N2 - 4000.

Now it is guaranteed that solutions exists for both N1 and N2, moreover, the solution for number N1 will contain only numbers of not more than 3 digits ( < 1000). The proof is quite easy: if N1 < 4000 — it is obvious; else — if the solution uses some number of the form (4000 + some_lucky_number), we can replace it with just some_lucky_number and receive a correct solution for number (N1 - 4000), but is doesn't exist!

So, the solution for number N1 we have found using DP, now let's find the solution for N2. If it will contains only of numbers of the form (some_lucky_number × 1000), then we will be able to easily merge this solution with solution for N1, so, let's find such a solution. Here we will use the fact that N2 is divisible by 4. For simplicity, let's divide N2 by 1000 and in the end multiply all Ans2(i) by the same 1000. Let P = N2 / 4. Now, let's construct the solution. Consider, for example, P = 95: we will walk through digits of this number, last digit — 5, means that we want to put digit 4 at the last decimal position of five answer numbers — ok, put it and in the last, sixth, number leave there digit 0. Go forward, digit 9 — we don't have nine numbers, but we can replace seven fours with four sevens, then to the second position we have to put (9 - 7) fours and 4 sevens, in total — 6 numbers, exactly as much as we have.

Thus, if next digit d ≤ 6, we just put to the first d answer numbers digit 4 to the next position; if d > 6, then we put 4 sevens and (d - 7) fours. In all other numbers we just leave digit 0 at this position.

If Ans1(i) — answer for N1, Ans2(i) — for N2, the the answer for N will be just Ans(i) = Ans1(i) + Ans2(i).

Time complexity for one number: O(logN).

During the competition many participants have wrote the following solution:

dp[i][j] — can we put the digit to the last i decimal positions of the answer number in such way that we will get correct last i digits in the sum and with carry to the next position equals to j. Then the solution exist iff dp[19][0] = true. To restore the answer we just have to remember for each state the previous state. Base — dp[0][0] = true. Transition — brute force how many fours and sevens we will put to the i-th position.