Codeforces Educational Round 181 – Solutions A to D

This post contains clean explanations and solutions for problems A to D from Educational Codeforces Round 181 (Rated for Div. 2). All problems are solved using C++ and include step-by-step approaches.

Codeforces Educational Round 181

Problem A – Difficult Contest

Idea: A contest string is said to be "difficult" if it contains the substring "FFT" or "NTT" anywhere. Our task is to rearrange the letters of the input string so that neither of those substrings appears. If the string is already non-difficult, we can print it as-is. Otherwise, we rearrange the letters in any way to avoid forming the "FFT" or "NTT" substrings.

Approach:

Scan from the left while values ≤ k
Scan from the right while values ≤ k
If both ends meet or cross, all problems are solved
Otherwise, total = left count + right count

Solution A


  // solution for Codeforces Educational Round 181 – Solution A
  #include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

bool isDifficult(const string& s) {
    for (size_t i = 0; i + 2 < s.size(); ++i) {
        if ((s[i] == 'F' && s[i+1] == 'F' && s[i+2] == 'T') ||
            (s[i] == 'N' && s[i+1] == 'T' && s[i+2] == 'T')) {
            return true;
        }
    }
    return false;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;

        if (!isDifficult(s)) {
            cout << s << '\n';
            continue;
        }

        // Count characters
        vector<int> count(26, 0);
        for (char c : s) count[c - 'A']++;

        string res = "";

        // Build result: output T's first, then F's, then N's, then rest
        // This avoids "FFT" and "NTT"
        for (int i = 0; i < count['T' - 'A']; ++i) res += 'T';
        for (int i = 0; i < count['F' - 'A']; ++i) res += 'F';
        for (int i = 0; i < count['N' - 'A']; ++i) res += 'N';
        for (int i = 0; i < 26; ++i) {
            if (i + 'A' == 'F' || i + 'A' == 'N' || i + 'A' == 'T') continue;
            res += string(count[i], i + 'A');
        }

        cout << res << '\n';
    }

    return 0;
}

Problem B – Left and Down

Idea: For several queries describing rectangles by two corners, verify if the second corner is not to the right or above the first one.
We must confirm all rectangles move left or down (or stay) but never right or up.

Approach:

For each query, check if x₂ ≤ x₁ and y₂ ≥ y₁.
If all satisfy, print "YES"; otherwise, print "NO".

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    bool valid = true;
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x2 > x1 || y2 < y1) {
            valid = false;
        }
    }

    cout << (valid ? "YES\n" : "NO\n");
    return 0;
}

Problem C – Count Good Numbers

Idea: Good numbers are those where digits at even positions are divisible by 5 and digits at odd positions are divisible by 4.
We want to count how many such numbers of length n exist modulo 10⁹+7.

Approach:

Count how many even and odd positions the number has.
Even positions have 5 possible digits; odd positions have 4.
Calculate (5^even) * (4^odd) modulo 10⁹+7.
Use fast modular exponentiation.

#include <iostream>
using namespace std;

const int MOD = 1000000007;

long long modPow(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int even = (n + 1) / 2;
    int odd = n / 2;

    long long ans = (modPow(5, even) * modPow(4, odd)) % MOD;
    cout << ans << '\n';

    return 0;
}

Problem D – Segments Covering

Idea: Given n segments [l, r], find the minimum number of points that cover all segments.
A point covers a segment if it lies within [l, r].

Approach:

Sort segments by their right endpoint.
Iterate over segments; greedily pick the right endpoint of the first uncovered segment as a covering point.
Skip all segments covered by the chosen point.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<pair<int,int>> segments(n);
    for (int i = 0; i < n; ++i) {
        cin >> segments[i].first >> segments[i].second;
    }

    sort(segments.begin(), segments.end(), [](auto &a, auto &b) {
        return a.second < b.second;
    });

    vector<int> points;
    int last_point = -1;
    for (auto &seg : segments) {
        if (seg.first > last_point) {
            last_point = seg.second;
            points.push_back(last_point);
        }
    }

    cout << points.size() << '\n';
    for (int p : points) cout << p << ' ';
    cout << '\n';

    return 0;
}

📘 Final Notes

These problems cover important concepts like string manipulation, condition checking, modular exponentiation, and greedy algorithms — all fundamental for competitive programming Div. 2 contests.

Check back for more solution walkthroughs and practice material!

Go to Link

CodeforcesSolved

Codeforces Educational Round 181 – Solutions A to D