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 - Сложный НОД

Идея задачи — GlebsHP

В этой задачи нужно было рассмотреть два случая:

1. a = b — отрезок состоит из одного числа, следовательно все числа из этого отрезка делятся на a и не делятся ни на какое число большее, чем a.
2. a < b — в этом случае НОД(a, a + 1, a + 2, ..., b) = НОД(НОД(a, a + 1), a + 2, ..., b) = НОД(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 - Ребус

Идея задачи — gen

Для начала давайте определим, существует ли решение ребуса. Для этого достаточно знать только количество положительных элементов (первый элемент всегда положительный и все знаки вопроса, перед которыми стоит  + ) и количество отрицательных элементов (все знаки вопроса, перед которыми стоит  - ). Обозначим эти количества как pos и neg, тогда минимальная сумма, которую мы можем получить — это min = (1 · pos - n · neg) (все положительные вопросики заменяем на минимальное значение 1, а все отрицательные — на максимальное n), аналогично, максимальная сумма равна max = (n · pos - 1 · neg). Тогда решение существует тогда и только тогда, когда min ≤ n ≤ max.

Пусть мы определили, что решение существует, теперь будем будем постепенно заменять вопросики числами. Пусть мы уже заменили некоторый префикс вопросиков на числа и получили там сумму S, текущий вопросик имеет знак sgn ( + 1 или  - 1) и справа (но не считая текущий) осталось pos_left положительных и neg_left отрицательных элементов. Текущий элемент мы заменим на число x. Как проверить, что мы можем заменить текущий вопросик на x? Точно так же, как мы вначале определяли, существует ли решение вообще. Мы можем найти минимальную и максимальную суммы, которые мы сможем получить — min_left = (S + sgn · x + pos_left - n · neg_left) и max_left = (S + sgn · x + n · pos_left - neg_left) соответственно, тогда мы можем заменить текущий вопросик на число x, если min_left ≤ n ≤ max_left. Как найти подходящее значение x? Можно честно решить систему неравенств, а можно просто перебрать все n значений.

BONUS Пусть k — количество знаков вопроса в ребусе. Докажите, что асимптотика решения с перебором (для примера, смотрите реализацию ниже) — O(k² + n), а не 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 - Международная олимпиада

Идея задачи — Alex_2oo8

Давайте посмотрим на сокращения, которые получают первые олимпиады. Первые 10 олимпиад (с 1989 до 1998 года соответственно) получают сокращение из одной цифры (IAO'9, IAO'0, ..., IAO'8) — на данный момент все одноцифренные сокращения заняты. Следующие 100 олимпиад (1999 - 2098) получат скоращение из двух цифр (так как последние две цифры у 100 подряд идущий чисел попарно различны). Аналогично, следующие 1000 олимпиад получат сокращения из трех цифр и так далее.

Теперь решим задачу в обратную сторну (по сокращению определим год). Пусть данное сокращение имеет длину k цифр, тогда мы знаем, что до нашей олимпиады прошли все олимпиады с сокращениями длины (k - 1), (k - 2), ..., 1, то есть 10^k - 1 + 10^k - 2 + ... + 10¹ = F олимпиад и наша олимпиада была одна из 10^k следующих. То есть наша олимпиада проходила в один из годов между (1989 + F) и (1989 + F + 10^k - 1), так как мы получили отрезок из 10^k подряд идущих чисел, то ровно одно число из этого отрезка будет иметь последние k цифр совпадающие с нашим сокращением, этот год и будет соответствовать нашему сокращению.

#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 - Покраска графа

Идея задачи — gen

Решим задачу отдельно для перекраски всего в красный и перекраски всего в синий, и выберем лучший из этих двух вариантов. Далее рассмотрим задачу для перекраски всех ребер в красный.

Понятно, что бессмысленно выбирать одну и ту же вершину дважды, так как во второй раз мы просто поменяем цвета назад, поэтому наша задача — разбить вершины на два множества S и T, где S — это вершины, которые мы выберем для перекраски, а T — вершины, которые мы не будем трогать (все оставшиеся). Пусть вершины u и v соеденены красным ребром, тогда, чтобы цвет ребра остался красным, обе вершины u и v должны принадлежать одному множеству (обе S или обе T). Если же вершины u' и v' соеденены синим ребром, то они должны принадлежать разным множествам (мы хотим поменять цвет этого ребра ровно один раз, значит одна из вершин принадлежит S, а вторая — T).

Теперь наша задача — это 0-1 покраска графа, которую можно решить, к примеру, DFS-ом или BFS-ом. Так как граф может быть несвязный, то необходимо обрабатывать компоненты по одной. Если для какой-то компоненты 0-1 покраски не существует, то получить все ребра красного цвета мы не сможем. Если же для каждой компоненты у нас нашлась 0-1 покраска, то в множество S нам следует добавить меньшую из 0-1 долей, так как мы хотим минимизировать размер множества S.

#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 - Азартный Ним

Идея задачи — GlebsHP

Первый игрок не может выиграть только если xor-сумма всех чисел равна 0. То есть задача состоит в том, чтобы посчитать количество способов разложить карточки так, чтобы xor-сумма верхних чисел равнялась нулю.

Пусть , a . Пусть карточки с номерами j₁, j₂, ..., j_k лежат числами b вверх, а все остальные — числами a, тогда xor-сумма такой концигурации равна , то есть . То есть мы хотим посчитать количество подмножеств c_i с xor-суммой S.

Заметим следующую особенность — если мы заменим в нашем множестве c₁ на , то ответ не изменится. Вместо {c₁, c₂} мы теперь можем взять , а вместо c₂ — . Поэтому мы можем выполнить следующие преобразования и ответ не изменится:

1. Выберем число c_f, в котором старший бит — еденица, если все элементы нули, то завершаемся
2. Заменим все остальные c_i, в которых старший бит тоже еденица на
3. Удалим число c_f из множество
4. Повторим действия 1-5 для оставшегося множества
5. Добавим c_f обратно в множество

После такого преобразования мы получим множество из k нулей и n - k чисел со свойством, что старший еденичный бит в этих счилах строго убывает. Как теперь проверить, можем ли получить xor-сумму S? Так как у нас осталось только одно число со старшим битом равным еденице, то старший бит зависит только от того, возьмем мы это число или нет. Так как мы знаем, каким этот бит должен получится в нашей xor-сумме, то мы можем однозначно определить, берем мы это число или нет. Аналогично продолжаем по всем следующим битам. Если в конце мы не получим подмножество с xor-суммой S, то эту xor-сумму получить невозможно (то есть второй игрок не может победить). Если же мы получили xor-сумму ровно S, то количество таких подмножеств будет 2^k, так как про n - k ненуллевых чисел мы уже однозначно определили, которые из них нам нужно взять, а из оставшихся k нулей мы можем выбрать произвольное подмножество и xor-сумму это не изменит. В данном случае вероятность победы второго игрока составляет , то есть ответ равен .

#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 - Двоичная табличка

Идея задачи — Alex_2oo8

Для начала рассмотрим медленное решение за O(2ⁿ · m). Давайте переберем все варианты по строчкам, каждую строчку мы либо будем инвертировать, либо не будем. Всю эту информацию можно сжать в битмаску — число от 0 до (2ⁿ - 1), где i-тый бит равен 1, если мы будем инвертировать i-тую строчку и 0, если не будем. Каждую из m колонок мы тоже можем сжать в битмаску над n битами (биты соответствуют значению в данной колонке на каждой из n строчек), обозначим битмаску для i-той колонки как col_i. Пусть маска строчек, которые мы будет инвертировать — это mask, тогда после того, как мы инвертируем все соответствующие строчки, в i-той колонке битмаска изменится на . Пусть содержит еденичек, тогда мы можем получить в этой колонке либо (n - k) еденичек (если инвертируем i-тую колонку), либо k (если не будем инвертировать). Тогда для зафиксированной маски строчек mask минимальное количество еденичек, которое может остаться в табличке, равно .

Теперь мы хотим научиться считать последнюю сумму быстрее, чем за O(m). Заметим, что нас не интересует само значение маски , а только количество еденичек в ней (от 0 до n). Поэтому мы можем сгруппировать все колнки по значению , пусть dp[k][mask] — это количество таких i, что , тогда мы можем посчитать сумму для фиксированной маски mask за O(n) — .

Осталось только научиться быстро считать значения dp[k][mask]. Эти значение можно считать при помощи динамического программирования. dp[0][mask] можно легко посчитать за O(m) для всех mask — просто пробегаемся по всем колонкам и увеличиваем соответствующее значение dp[0][col_i] на 1. Для k > 0, col_i и mask отличаются ровно в k битах, переберем один из этих битов (бит, в котором будет отличие) и обозначим его за p. Тогда col_i и отличаются ровно в (k - 1) битах. Казалось бы, количество таких колонок равно , но нет, так как мы лишними учли все колонки, в которых col_i и отличаются в бите p (то есть бит p совпадает у mask и col_i). Снова, последнее количество почти равно dp[k - 2][mask], за исключением тех колонок, которые отличаються в бите p от mask. Пусть , продолжая (что-то вроде принципа включений/исключений) мы получим, что количество, которое нас интересует равно dp[k - 1][next] - dp[k - 2][mask] + dp[k - 3][next] - dp[k - 4][mask] + dp[k - 5][next] - .... Что мы получим просуммировав такие значения по всем битам p? Мы получим dp[k][mask] · k, так как каждую колонку мы посчитаем ровно k раз (в каждом из битов, где есть отличие).

Таким образом, мы научились считать все значения dp[k][mask] за O(2ⁿ · n³) следующим образом:

Это все еще слишком медленно, но пересчет динамики можно ускорить до O(2ⁿ · n²), к примеру, следующим образом:

BONUS А вы можете решить эту задачу еще быстрее?

#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 - Взламывать или не взламывать

Идея задачи — Alex_2oo8

Первое наблюдение — так как взламывать можем только мы, то суммарный балл любого другого участника не может превышать 9000 (3 задачи по 3000 баллов), поэтому, если мы можем взломать как минимум 90 решений, то мы гарантированно можем занять первое место (только от взломов мы уже получаем 9000 баллов).

Теперь давайте решать задачу, зная, что количество потенциальных взломов не превосходит 90. Для начала — переберем конечную разбалловку (все 6³ вариантов). Теперь для каждой из задач мы можем однозначно определить, сколько взломов по ней мы сделаем (максимальное количество, после которого стоимость задачи будет такой, какую мы сейчас зафиксировали). Зная и конечную разбалловку, и количество наших взломов, мы можем посчитать свой суммарный балл. Теперь у нас есть участники, у которых мы ничего не можем взломать, на них мы уже никак повлиять не можем, поэтому можем уже посчитать, сколько из них нас обгоняют. Осталось не более 90 участников, у которых мы можем что-то взломать. Нас интересуют только те из них, кто на данный момент (пока мы у них ничего не взломали) нас обгоняют. Мы хотим как можно больше из них "скинуть" вниз. Эту задачу можно решать при помощи динамического программирования:

dp[p][i][j][k] — максимальное количество учасников среди первых p, которых мы можем "скинуть" вниз, взломав суммарно i раз по первой задаче, j по второй и k по третьей.

Переходы — перебираем множество задач, которые мы взломаем у следующего участника, и, если после этих взломов мы действительно "скинем" его вниз, то обновляем соответствующее значение ДП. К примеру, если достаточно взломать первую и третью задачи, то:

dp[p + 1][i + 1][j][k + 1] = max(dp[p + 1][i + 1][j][k + 1], dp[p][i][j][k] + 1)

BONUS А вы можете решить эту задачу, если за каждый успешный взлом дают 10 баллов, а не 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;
}

Привет, Codeforces!

Сегодня в 17:15 по московскому времени состоится финальный раунд чемпионата КРОК 2016, в котором 50 лучших участников отборочного раунда будут соревноваться за ценные призы, а также просто ради удовольствия. Призы лучшим в Финале:

• 1 место — 100000 рублей
• 2 местo — 70000 рублей
• 3 местo — 50000 рублей

А победителем игрового тура стал Belonogov, который был награжден призовым фондом 50000 рублей! Поздравляем!

Для всех остальных завтра в 19:35 по московскому времени будет проведен Codeforces Round #347 на почти идентичном наборе задач. Это будет обычный нерейтинговый раунд, отдельный для каждого дивизиона.

Задачи для вас подготовили Евгений Вихров (gen), координатор всея Codeforces Глеб Евстропов (GlebsHP) и я. Также хотелось бы поблагодорить Михаила Мирзаянова (MikeMirzayanov) и всю команду, работающую над Codeforces, за замечательную платформу, а также Александра Фетисова (AlexFetisov) за прорешивание задач.

Во время финального раунда для зрителей будет доступно текущее положение участников по специальной ссылке, которая появится здесь, а задачи вы сможете увидеть только завтра.

Надеемся, что вам понравятся наши задачи. Удачи финалистам сегодня и всем остальным завтра!

UPD 1: Ссылка на текущие результаты Финала: http://codeforces.net/spectator/contest/662/standings

UPD 2: Codeforces Round #347 будет нерейтинговым.

UPD 3: Разбалловка
Div 1: 500 — 1000 — 1500 — 2500 — 2500
Div 2: 500 — 1000 — 1500 — 2000 — 3000

UPD 4: Поздравляем победителей!

UPD 5: Разбор задач: http://codeforces.net/blog/entry/44408

Всем привет!

Уже скоро, 13 октября в 19:30 MSK состоится Codeforces Round #206. Автором задач являюсь я и это мой первый раунд!

За помощь в подготовке хочется поблагодарить координатора задач Геральда Агапова (Gerald), Евгения Вихрова (gen) за тестирование задач и Марию Белову (Delinur) за перевод условий на английский язык. Отдельное спасибо Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Разбалловка стандартная в обоих дивизионах: 500-1000-1500-2000-2500.

Желаю всем удачи и очень надеюсь, что Вам понравятся задачи!

Поздравляем победителей! Особые поздравления rng_58, единственному участнику, решившему все 5 задач!

Первый дивизион:

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

Второй дивизион:

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

UPD Опубликован разбор задач.

355A - Вася и цифровой корень

Если d = 0, то существует всего одно число, что , поэтому, если k = 1, то ответ — 0, иначе — No solution.

Если d > 0, то подоходящим числом, к примеру, являтся d × 10^k - 1.

Асимптотика решения: O(1) + O(k) на вывод решения.

355B - Вася и общественный транспорт

Если мы купим билет четвертого типа, то больше ничего покупать не надо, по-этому ответ — min(c₄, ответ из билетов первых трех типов).

Теперь, когда у нас нету билета четвертого типа, можно решать задачу независимо для автобусов и потом аналогично для троллейбусов.

Решая задачу только для автобусов, если мы купим билет третьего типа, то больше покупать ничего не надо, по-этому ответ равен min(c₃, ответ из билетов первых двух типов).

Без билетов третьего типа можно решать задачу независимо для каждого автобуса. Таким образом, если мы купим билет второго типа, то потратим c₂ бурлей, если же купим a_i билетов первого типа, то потратим (a_i × c₁) бурлей. Таким образом, ответ для автобуса i — min(c₂, a_i × c₁).

Собрав все вместе несложно получить следующее решение:

  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));

Асимптотика решения: O(n + m).

354A - Вася и робот

Переберем, сколько раз мы будем использовать операцию слева. Путь мы используем ее k раз, тогда понятно, что операциями слева мы заберем k первых предметов, а оставшиеся (n - k) предметов заберем справа. Тогда робот затратит sumLeft[k]·l + sumRight[n - k]·r энергии плюс некоторый штраф за одинаковые операции. Чтобы минимизировать этот штраф операции необходимо выполнять в порядке LRLRL ... RLRLLLLL ..., начиная с тех операций, которых больше. К примеру, если k = 7, n - k = 4, то выполнять операции надо в последовательности LRLRLRLRL LL. Таким образом нам надо будет заплатить штраф два раза (7 - 4 - 1).

sumLeft[i] — сумма первых i весов, sumRight[i] — сумма последних i весов.

Псевдокод решения:

  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);
  }

Асимптотика решения: O(n).

354B - Игра со строками

Будем говорить, что клетка (r, c) соответствует строке s, если существует корректный путь, заканчивающийся в клетке (r, c), которому соответствует строка s.

Найдем для строки s множество соответствующий ей клеток, назовем это множество состоянием. Одно состояние может соответствовать множеству разных строк. Перебрать все возможные строки мы не можем, так как их количество — слишком большое, однако перебрать все состояния мы можем. Несложно понять, что все клетки соответствующие одной строке находятся на одной диагонали, таким образом количество различных состояний равно 2¹ + 2² + ... + 2^n - 1 + 2ⁿ + 2^n - 1 + ... + 2² + 2¹ = O(2ⁿ). В реализации состояние можно охарактеризовать номером диагонали (от 1 до 2n - 1) и битовой маской клеток, которые в него входят (2ⁿ).

Из каждого состояния мы можем перейти в 26 различных состояний (на самом деле меньше), причем все возможные переходы зависят именно от состояния, а не от самой строки. На изображении — пример перехода: из состояния, которое выделено синем цветом по букве a мы перейдем в состояние, выделенное желтым цветом.

Теперь, подсчитаем для каждого состояния величину (кол-во букв A  -  кол-во букв B) в строке, начиная с этого состояния. Если в данный момент ходит первый игрок (на четной диагонали), то это значение надо максимизировать, если второй (на нечетной диагонали) — минимизировать. Реализовать это несложно в виде рекурсии с мемоизацией.

Победителя можно определить по значению состояния, соответствующему клетке (1, 1).

Асимптотика: O(2ⁿ × (n + alpha)), где alpha — размер алфавита.

354C - Вася и красивые массивы

В задаче было необходимо найти максимальное d, такое, что a_i ≥ d,  a_i mod d ≤ k.

Пусть m = min(a_i), из условия следует, что d ≤ m. Рассмотрим два случая:

. В данном случае переберем ответ от k + 1 до m, проверить, подходит ли число d в качестве ответа можно следующим образом:

Нам необходимо проверить, что a_i mod d ≤ k при фиксированном d, что равносильно , где . Так как все упомянутые интервалы [x·d..x·d + k] не пересекаются, то достаточно проверить, что , где cnt[l..r] — количество чисел a_i в интервале [l..r].

Итоговая асимптотика решения: O(maxA log maxA), доказательство основывается на сумме гармонического ряда.

354D - Передача пирамиды

Данная задача решается динамическим программированием. Рассмотрим для начала решение за O(n³).

Пусть dp[i][j] — ответ для выделенной синим цветом на изображении части (минимальная стоимость передачи всех ячеек, которые находятся в синей области). Тогда в dp[n][0] будет содержатся ответ на задачу.

Как пересчитывать такую динамику? Понятно, что в самом левом столбце (внутри синей части) мы выберем в качестве вершины подпирамиды максимум одну ячейку. Если мы выберем две, то одна из данных подпирамид будет полностью содержать другую внутри (как синяя подпирамида содержит оранжевую). Теперь, переберем за O(n) ту клеточку, которая будет вершиной подпирамиды и получим следующий переход:

Для упрощения формул будем считать, что .

0 ≤ k ≤ i, где k — высота, на которой мы выберем вершину или 0, если в данном столбце не будет выбрана подпирамида, а sumUp[i][p] — количество помеченных клеточек в i-том столбце, на высоте начиная с p, их нам придется передавать по одной операциями первого типа.

Можно сократить одну степень, пересчитывая динамику так:

0 ≤ k ≤ i;

для всех j > 0.

Доказательство того, что это корректно довольно просто и оставляется читателю. :)

Также можно заметить, что нам не выгодно брать подпирамиду с высотой больше, чем , так как за нее мы заплатим  > 3k, однако, если передавать все клеточки по одной мы заплатим всего 3k. Таким образом второе измерение (j) в динамике можно сократить до .

Также, чтобы получить АС необходимо хранить только два последних слоя динамики, иначе не хватит памяти.

Асимптотика решения: .

354E - Счастливое представление числа

Авторское решение, намного сложнее предложенного участниками во время контеста:

Для начала напишем ДП за O(N * lucky_count(N)), где lucky_count(N) — количество счастливых чисел до N, lucky_count(10ⁿ) = 3ⁿ. Видно, что для всех достаточно больших N решение существует. На самом деле для всех N > 523.

Теперь, скажем для чисел  ≤ 10000 у нас есть решение, найденное ДПой. Решим задачу для больших чисел:

Следующая и ключевая идея — разделить задачу на две части. N = N1 + N2. Выберем N1 и N2 так, чтобы для них можно было легко найти ответ, а также, найдя 2 решения, было возможно их объеденить в одно. Пусть N1 = N mod 4000, N2 = N - N1. Однако, тут может появиться проблемма с тем, что для N1 нет решения, тогда сделаем N1 = N1 + 4000, N2 = N2 - 4000.

Теперь решение гарантированно существует и для N1 и для N2, причем в решении для числа N1 мы будем использовать только числа из не более, чем 3 цифр ( < 1000). Доказательство довольно просто: если N1 < 4000 — то очевидно; иначе — если в решении используется число вида (4000 + some_lucky_number), то заменим его на просто some_lucky_number и получим решение для (N1 - 4000), однако его не существует!

Решение для N1 мы нашли при помощи ДП, теперь нам нужно найти решение для N2. Если оно будет использовать только числа вида (some_lucky_number × 1000), то мы сможем легко объеденить его с решением для N1, по-этому будем искать именно такое решение. Тут мы будем использовать тот факт, что N2 делится на 4. Для простоты поделим N2 на 1000, а в конце просто умножим все Ans2(i) на ту же 1000. Пусть P = N2 / 4. Теперь будем конструктивно строить решение. Рассмотрим, к пример, P = 95: идем по цифрам этого числа, последняя цифра — 5, означает, что мы хотим в пяти числах ответа на последнюю позицию (в десятичной записи) поставить цифру 4, хорошо — ставим и в последнем, шестом, числе оставляем на последней позиции 0. Идем дальше, цифра 9 — у нас нету девяти чисел, но мы можем семь четверок заменить на четыре семерки, тогда нам на вторые позиции надо поставить (9 - 7) четверок и 4 семерки, в сумме в 6 чисел, как раз то, что надо.

Таким образом, если очередная цифра d ≤ 6, то просто в первые d чисел ответа ставим цифру 4 на очередную позицию, если же d > 6, то в 4 числа ставим цифру 7 и в d - 7 чисел ставим цифру 4. Во всех остальных числах оставляем на данной позиции 0.

Если Ans1(i) — ответ для числа N1, Ans2(i) — для числа N2, то ответом для числа N будет просто Ans(i) = Ans1(i) + Ans2(i).

Асимптотика решения на одно число: O(logN).

Во время контеста многие участники сдали следующее решение:

dp[i][j] — можем ли мы расставив цифры на последние i позиций чисел ответа так, чтобы получить верные последние i цифр в сумме и перенос на следующий разряд был равен j. Тогда решение существует, если dp[19][0] = true, чтобы восстановить ответ просто для каждого состояния запоминаем, из какого состояния мы в него пришли. База — dp[0][0] = true. Переход — перебераем, сколько мы поставим четверок и сколько семерок в i-тый разряд.