Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

doreshnikov's blog

Non-bipartite matchings, (in)correct algorithm

By doreshnikov, 19 months ago, translation, In English

Hello everyone!

I thought that maybe someone on Codeforces can help me find an error or build a counterexample. If you remember matchings in non-bipartite graphs, then the problem with Kuhn's algorithm is as follows: we need to find an augmenting path, but we can arrive at the desired vertex via an edge of the wrong type, mark it as visited, and leave.

First attempt to solve the problem: do a dfs on vertices of the form (v, flag), where flag is the type of edge we arrived by. Obviously, this doesn't work: we can go through both (v, false) and (v, true) because they are different vertices, but then our augmenting path in the original graph is not simple, and we haven't actually found an augmenting path.
Second attempt to solve the problem: do the same thing as before, but explicitly forbid dfs to go to vertices that have already been visited (are on the path from the start to the current vertex), even if they were visited with a different flag. Something like this:

vis[v, flag] <- false for each v, flag
path = []

dfs(v, flag):
    vis[v, flag] = true
    path.add(v)

    for u : g[v], such that (status[vu] != flag) && (u not in path) && (not vis[u, !flag]):
        dfs(u, !flag)

    path.pop()

Since people write Blossom algorithm, and I'm probably not smarter than Edmonds, who came up with it, there is either a counterexample to my “solution” or it just takes a long time, but I haven't yet realized why. I hope that there are smart people out there who will somehow see this post and explain to me where I'm wrong :)

Full text and comments »

doreshnikov
19 months ago
1

Codeforces Round #753 (Div. 3) Editorial

By doreshnikov, history, 3 years ago, In English

Short information

Sorry for another delayed editorial, I know I promised that it will come out sooner the previous time, but I wasn't feeling well today, so the work was slower than usual.

About problem F:

I am once again sorry for the inconveniences caused by tight ML in this problem. It was not the intended behavior since we relied too much on the main solution and didn't assume most of the solutions using DFS will fail. In this editorial I attach the code of the main solution that we expected from the beginning, it uses ~75MB of memory.

I guess, Div. 3 Rounds are not only for participants to learn but also can serve as educational for authors as well. I'll try not to repeat the same mistakes the next time :) Thanks to everyone for participating and hope to see you again!

The editorial

1607A - Linear Keyboard

Idea: doreshnikov, MikeMirzayanov

Tutorial

Solution

t = int(input())
for _ in range(t):
    k, s = input(), input()
    res = 0
    for i in range(1, len(s)):
        res += abs(k.index(s[i]) - k.index(s[i - 1]))
    print(res)

1607B - Odd Grasshopper

Idea: doreshnikov

Tutorial

Solution

t = int(input())
maps = [
    lambda x: 0,
    lambda x: x,
    lambda x: -1,
    lambda x: -x - 1
]

for _ in range(t):
    x0, n = map(int, input().split())
    d = maps[n % 4](n)
    print(x0 - d if x0 % 2 == 0 else x0 + d)

1607C - Minimum Extraction

Idea: doreshnikov

Tutorial

Solution

t = int(input())

for _ in range(t):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    res = a[0]
    for i in range(n - 1):
        res = max(res, a[i + 1] - a[i])
    print(res)

1607D - Blue-Red Permutation

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];

        string c;
        cin >> c;

        vector<int> l, r;
        forn(i, n)
            (c[i] == 'B' ? l : r).push_back(a[i]);
        sort(l.begin(), l.end());
        sort(r.begin(), r.end(), greater<int>());

        bool ok = true;
        forn(i, l.size())
            if (l[i] < i + 1)
                ok = false;
        forn(i, r.size())
            if (r[i] > n - i)
                ok = false;

        cout << (ok ? "YES" : "NO") << '\n';
    }
}

1607E - Robot on the Board 1

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

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

        int bx = 0, by = 0;
        int min_bx = 0, max_bx = 0, min_by = 0, max_by = 0;
        for (char c: s) {
            if      (c == 'L') min_by = min(min_by, --by);
            else if (c == 'R') max_by = max(max_by, ++by);
            else if (c == 'U') min_bx = min(min_bx, --bx);
            else               max_bx = max(max_bx, ++bx);

            if (max_bx - min_bx >= n) {
                if (bx == min_bx) min_bx++;
                break;
            }
            if (max_by - min_by >= m) {
                if (by == min_by) min_by++;
                break;
            }
        }

        cout << 1 - min_bx << ' ' << 1 - min_by << '\n';
    }
}

1607F - Robot on the Board 2

Idea: doreshnikov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<string> dir(n);
        for (int i = 0; i < n; i++)
            cin >> dir[i];

        vector<vi> res(n, vi(m, 0));
        int opt = 0, optr = 0, optc = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (res[r][c] > 0)
                    continue;

                int nr = r, nc = c;
                int depth = 0;
                vector<pii> path;
                auto ok = [&n, &m](int row, int col) {
                    return row > -1 && row < n && col > -1 && col < m;
                };

                do {
                    res[nr][nc] = --depth;
                    path.emplace_back(nr, nc);
                    if (dir[nr][nc] == 'L')
                        nc--;
                    else if (dir[nr][nc] == 'R')
                        nc++;
                    else if (dir[nr][nc] == 'U')
                        nr--;
                    else
                        nr++;
                } while (ok(nr, nc) && res[nr][nc] == 0);

                int start = 1;
                if (ok(nr, nc)) {
                    if (res[nr][nc] < 0) {
                        int cycle = res[nr][nc] - depth + 1;
                        for (int i = 0; i < cycle; i++) {
                            auto p = path.back();
                            path.pop_back();
                            res[p.first][p.second] = cycle;
                        }
                    }
                    start = res[nr][nc] + 1;
                }
                while (!path.empty()) {
                    auto p = path.back();
                    path.pop_back();
                    res[p.first][p.second] = start++;
                }

                if (res[r][c] > opt) {
                    opt = res[r][c];
                    optr = r;
                    optc = c;
                }
            }
        }

        cout << optr + 1 << ' ' << optc + 1 << ' ' << opt << '\n';
    }
}

1607G - Banquet Preparations 1

Idea: doreshnikov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<pii> dishes(n);
        ll balance = 0;
        ll max_a = 0, max_b = 0;
        ll total_eat = static_cast<long long>(n) * m;

        for (int i = 0; i < n; i++) {
            cin >> dishes[i].first >> dishes[i].second;
            balance += dishes[i].first - dishes[i].second;
            max_a += min(m, dishes[i].first);
            max_b += min(m, dishes[i].second);
        }
        ll max_delta = 2 * max_a - total_eat, min_delta = total_eat - 2 * max_b;
        ll min_a = total_eat - max_b;

        ll eat_a;
        if (balance < 0) {
            eat_a = min_a;
            if (balance - min_delta >= 0)
                eat_a = min(max_a, (total_eat + balance + 1) / 2);
        } else {
            eat_a = max_a;
            if (balance - max_delta <= 0)
                eat_a = min(max_a, (total_eat + balance + 1) / 2);
        }
        ll ans = abs(balance - 2 * eat_a + total_eat);

        cout << ans << '\n';
        ll rest_a = eat_a - min_a;
        for (int i = 0; i < n; i++) {
            ll cur_a = 0;
            if (dishes[i].second < m)
                cur_a += m - dishes[i].second;
            ll add = min(rest_a, min(m - cur_a, dishes[i].first - cur_a));
            cur_a += add;
            rest_a -= add;
            cout << cur_a << ' ' << m - cur_a << '\n';
        }
    }
}

1607H - Banquet Preparations 2

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

struct seg {
    int a, b, m;
    int index;
};

int n, ans;
vector<seg> segments;
map<int, vector<seg>> diags;

void erase(multiset<pair<pair<int,int>, int>>& lr, int l, int r, int index) {
    pair<pair<int,int>,int> plr = make_pair(make_pair(l, r), index);
    auto i = lr.find(plr);
    assert(i != lr.end());
    lr.erase(i);
}

void erase(multiset<pair<pair<int,int>, int>>& lr, multiset<pair<pair<int,int>, int>>& rl, int l, int r, int index) {
    erase(lr, l, r, index);
    erase(rl, r, l, index);
}

map<int, pair<int,int>> dd;

void setup_dd(int index, int value) {
    assert(dd.count(index) == 0);
    int x = segments[index].a - value;
    int y = segments[index].m - x;
    assert(segments[index].a - x >= 0);
    assert(segments[index].b - y >= 0);
    assert(x + y == segments[index].m);
    dd[index] = make_pair(x, y);
}

int solve(vector<seg> s) {
    int n = s.size();
    multiset<pair<pair<int,int>, int>> lr;
    multiset<pair<pair<int,int>, int>> rl;
    forn(i, n) {
        int min_d = max(s[i].m - s[i].b, 0);
        int max_d = min(s[i].a, s[i].m);
        lr.insert(make_pair(make_pair(s[i].a - max_d, s[i].a - min_d), s[i].index));
        rl.insert(make_pair(make_pair(s[i].a - min_d, s[i].a - max_d), s[i].index));
    }

    int result = 0;
    while (!rl.empty()) {
        result++;
        auto min_r_iterator = rl.begin();
        int r = min_r_iterator->first.first;
        int l = min_r_iterator->first.second;
        int index = min_r_iterator->second;
        erase(lr, rl, l, r, index);
        setup_dd(index, r);

        while (!lr.empty()) {
            auto min_l_iterator = lr.begin();
            int ll = min_l_iterator->first.first;
            int rr = min_l_iterator->first.second;
            int ii = min_l_iterator->second;
            if (ll <= r) {
                erase(lr, rl, ll, rr, ii);
                setup_dd(ii, r);
            } else
                break;
        }
    }

    return result;
}

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        cin >> n;
        diags.clear();
        dd.clear();
        segments = vector<seg>(n);
        forn(i, n) {
            seg s;
            s.index = i;
            cin >> s.a >> s.b >> s.m;
            diags[s.a + s.b - s.m].push_back(s);
            segments[i] = s;
        }
        int sum = 0;
        for (auto p: diags)
            sum += solve(p.second);
        cout << sum << '\n';
        forn(i, n)
            cout << dd[i].first << " " << dd[i].second << '\n';
    }
}

Full text and comments »

Tutorial of Codeforces Round 753 (Div. 3)

+122

doreshnikov
3 years ago
50

Codeforces Round #753 (Div. 3)

By doreshnikov, history, 3 years ago, In English

Hello Codeforces!

Once again, we are glad to invite you all to Codeforces Round 753 (Div. 3), the third division round held on Nov/02/2021 17:35 (Moscow time). This round was prepared (again) by me and MikeMirzayanov. The problems are different but our anticipation is the same :) Hope you will like the problems we've prepared!

Big thanks to MikeMirzayanov for great ideas as well as for helping me with writing good statements and better tests. I'm still a bit slow with some aspects of preparing problems so it's a really noticeable help for me. (UPD: as of this moment, it became much more noticeable, so, really, thanks a lot!)

Also special thanks for testing the round to RisingWizard, Capta1n_Shy, Mazaalai, GustavoMG, nizamoff, 2020akadaver, ashmelev, p0kemanbr, Kofta and, as usual, to Gassa for valuable comments! And last but not least, thanks to everyone who'll be participating! This round contains 8 problems and is expected to have a decent level of difficulty for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make tests strong enough but it doesn't at all guarantee that open hacks phase will be pointless.

You will be given 8 problems and 2 hours to solve them. We remind you that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes. Also please note that the number of problems has slightly increased since the last edit.

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

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

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

Good luck to everyone!

UPD: Editorial is out!

Full text and comments »

Announcement of Codeforces Round 753 (Div. 3)

+320

doreshnikov
3 years ago
275

Codeforces Round #744 (Div. 3) Editorial

By doreshnikov, history, 3 years ago, In English

1579A - Casimir's String Solitaire

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        cout << (count(s.begin(), s.end(), 'B') * 2 == s.size() ?
                 "YES\n" : "NO\n");
    }
}

1579B - Shifting Sort

Idea: doreshnikov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<pii> actions;
        for (int i = 0; i < n; i++)
            cin >> a[i];

        for (int i = 0; i < n - 1; i++) {
            int min_pos = i;
            for (int j = i + 1; j < n; j++)
                if (a[j] < a[min_pos])
                    min_pos = j;

            if (min_pos > i) {
                actions.push_back({i, min_pos});
                int opt = a[min_pos];
                for (int j = min_pos; j > i; j--)
                    a[j] = a[j - 1];
                a[i] = opt;
            }
        }

        cout << actions.size() << '\n';
        for (auto &lr: actions) {
            cout << lr.first + 1 << ' ' << lr.second + 1 << ' ' << lr.second - lr.first << '\n';
        }
    }

}

1579C - Ticks

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<vector<int>> status(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < m; j++)
                if (s[j] == '*')
                    status[i][j] = 1;
        }
        for (int i = n - 1; i > -1; i--) {
            for (int j = 0; j < m; j++) {
                if (status[i][j] == 0)
                    continue;
                int len = 0;
                while (j > len && j + len + 1 < m && i > len) {
                    if (status[i - len - 1][j - len - 1] == 0 || status[i - len - 1][j + len + 1] == 0)
                        break;
                    len++;
                }
                if (len >= k) {
                    for (int d = 0; d <= len; d++) {
                        status[i - d][j - d] = 2;
                        status[i - d][j + d] = 2;
                    }
                }
            }
        }
        bool ok = true;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (status[i][j] == 1)
                    ok = false;

        cout << (ok ? "YES" : "NO") << '\n';
    }
}

1579D - Productive Meeting

Idea: doreshnikov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        auto cmp = [](pii const &x, pii const &y) {
            return x > y;
        };
        set<pii, decltype(cmp)> a(cmp);
        vector<pii> answer;
        for (int i = 0; i < n; i++) {
            int ai;
            cin >> ai;
            if (ai > 0)
                a.emplace(ai, i + 1);
        }
        while (a.size() > 1) {
            auto p1 = *a.begin();
            a.erase(a.begin());
            auto p2 = *a.begin();
            a.erase(a.begin());
            answer.emplace_back(p1.second, p2.second);
            if (p1.first > 1) a.emplace(p1.first - 1, p1.second);
            if (p2.first > 1) a.emplace(p2.first - 1, p2.second);
        }
        cout << answer.size() << '\n';
        for (auto &p : answer) {
            cout << p.first << ' ' << p.second << '\n';
        }
    }
}

1579E1 - Permutation Minimization by Deque

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, a;
        cin >> n;
        deque<int> d;
        for (int i = 0; i < n; i++) {
            cin >> a;
            if (d.empty() || a < d[0])
                d.push_front(a);
            else
                d.push_back(a);
        }
        for (int x : d)
            cout << x << ' ';
        cout << '\n';
    }
}

1579E2 - Array Optimization by Deque

Idea: doreshnikov

Tutorial

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> node;
typedef tree<node, null_type, less<node>,
            rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        ordered_set s;
        long long cnt = 0;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            int less = s.order_of_key(node(a, 0)),
                    greater = i - s.order_of_key(node(a, n));
            cnt += min(less, greater);
            s.insert(node(a, i));
        }
        cout << cnt << '\n';
    }
}

1579F - Array Stabilization (AND version)

Idea: doreshnikov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, d;
        cin >> n >> d;
        vector<int> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        vector<bool> used(n, false);
        bool fail = false;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (used[i])
                continue;
            int cur = i, pref = 0, last = 0, iter = 0, ans = 0;
            do {
                used[cur] = true;
                if (a[cur] == 0) {
                    ans = max(ans, last);
                    last = 0;
                } else {
                    last++;
                    if (iter == pref) {
                        pref++;
                    }
                }
                cur = (cur + d) % n;
                iter++;
            } while (cur != i);
            if (iter != pref)
                ans = max(ans, pref + last);
            else {
                fail = true;
                break;
            }
            res = max(res, ans);
        }
        if (fail)
            cout << "-1\n";
        else
            cout << res << '\n';
    }
}

1579G - Minimal Coverage

Idea: doreshnikov, MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        int maxl = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            maxl = max(maxl, a[i]);
        }
        vector<vector<int>> dp(n + 1, vector<int>(2 * maxl + 1, INF));
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int left = 0; left <= 2 * maxl; left++) {
                if (dp[i][left] == INF)
                    continue;
                dp[i + 1][max(left - a[i], 0)] = min(dp[i + 1][max(left - a[i], 0)], dp[i][left] + a[i]);
                if (left + a[i] < dp[i + 1].size()) {
                    dp[i + 1][left + a[i]] = min(dp[i + 1][left + a[i]], max(dp[i][left] - a[i], 0));
                }
            }
        }

        int ans = 2 * maxl + 1;
        for (int left = 0; left <= 2 * maxl; left++)
            ans = min(ans, left + dp[n][left]);
        cout << ans << '\n';
    }
}

Full text and comments »

Tutorial of Codeforces Round 744 (Div. 3)

+141

doreshnikov
3 years ago
98

Codeforces Round #744 (Div. 3)

By doreshnikov, history, 3 years ago, translation, In English

Hello Codeforces!

Sorry for a bit delayed English announcement, we are glad to invite you all to Codeforces Round 744 (Div. 3), third division round held on Sep/28/2021 17:35 (Moscow time). This round was prepared by me and MikeMirzayanov and we hope that you'll find the problems interesting and enjoy solving them.

I would like to thank MikeMirzayanov for helping me with both writing and preparing the problems for this round. Since it's the second Div. 3 round held I'm involved in but only the first one I'm preparing problems for from zero all the way to the end, without his guidance it would've taken much more of my time.

Also special thanks to nizamoff, andreumat, QAZZY, Vladosiya, CtrlAlt, vladmart, Igorjan94, okwedook, ashmelev and Aris for testing the round and giving their feedback on the problems as well as to Gassa and geranazavr555 for proofreading and correcting the statements. This round is very noticeably better than it could've been without your contribution. And last but not least, thanks to everyone who'll be participating! This round contains 7 to 8 problems and is expected to be of decent level of difficulty for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

You will be given 7-8 problems and 2 hours 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

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

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

Good luck and have fun!

UPD: Editorial is out!

Full text and comments »

+308

doreshnikov
3 years ago
264

Codeforces Round #731 (Div. 3) Editorial

By doreshnikov, 3 years ago, translation, In English

1547A - Shortest Path with Obstacle

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        vector<int> a(2), b(2), f(2);
        cin >> a[0] >> a[1];
        cin >> b[0] >> b[1];
        cin >> f[0] >> f[1];
        int ans = abs(a[0] - b[0]) + abs(a[1] - b[1]);
        if ((a[0] == b[0] && a[0] == f[0] && min(a[1], b[1]) < f[1] && f[1] < max(a[1], b[1]))
                || (a[1] == b[1] && a[1] == f[1] && min(a[0], b[0]) < f[0] && f[0] < max(a[0], b[0])))
            ans += 2;
        cout << ans << endl;
    }
}

1547B - Alphabetical Strings

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        string s;
        cin >> s;
        size_t L = s.find('a');
        if (L == string::npos) {
            cout << "NO" << endl;
            continue;
        }
        size_t n = s.length(), R = L;
        bool yes = true;
        for (size_t i = 1; i < n; i++) {
            size_t pos = s.find(char('a' + i));
            if (pos == string::npos || (pos != L - 1 && pos != R + 1)) {
                yes = false;
                break;
            } else {
                L = min(L, pos);
                R = max(R, pos);
            }
        }
        cout << (yes ? "YES" : "NO") << endl;
    }
}

1547C - Pair Programming

Idea: geranazavr555, MikeMirzayanov

Tutorial

Solution

#include <iostream>
#include <vector>

typedef std::vector<int> vi;

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int k, n, m;
        std::cin >> k >> n >> m;

        vi a(n), b(m);
        for (int i = 0; i < n; i++)
            std::cin >> a[i];
        for (int i = 0; i < m; i++)
            std::cin >> b[i];

        int pos1 = 0, pos2 = 0;
        vi res;
        bool ok = true;
        while (pos1 != n || pos2 != m) {
            if (pos1 != n && a[pos1] == 0) {
                res.push_back(0);
                k++;
                pos1++;
            } else if (pos2 != m && b[pos2] == 0) {
                res.push_back(0);
                k++;
                pos2++;
            } else if (pos1 != n && a[pos1] <= k) {
                res.push_back(a[pos1++]);
            } else if (pos2 != m && b[pos2] <= k) {
                res.push_back(b[pos2++]);
            } else {
                std::cout << -1 << '\n';
                ok = false;
                break;
            }
        }

        if (ok) {
            for (int cur : res)
                std::cout << cur << ' ';
            std::cout << std::endl;
        }
    }

    return 0;
}

1547D - Co-growing Sequence

Idea: doreshnikov

Tutorial

Solution

def f(x, y):
    return x & ~y

t = int(input())
for tt in range(t):
    n = int(input())
    a = list(map(int, input().split()))

    ans = [0] * n
    for i in range(1, n):
        ans[i] = f(ans[i - 1] ^ a[i - 1], a[i])
    print(" ".join(map(str, ans)))

1547E - Air Conditioners

Idea: geranazavr555, MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, k;
        cin >> n >> k;
        vector<int> a(k);
        forn(i, k)
            cin >> a[i];
        vector<int> t(k);
        forn(i, k)
            cin >> t[i];
        vector<long long> c(n, INT_MAX);
        forn(i, k)
            c[a[i] - 1] = t[i];

        long long p;

        vector<long long> L(n, INT_MAX);
        p = INT_MAX;
        forn(i, n) {
            p = min(p + 1, c[i]);
            L[i] = p;
        }

        vector<long long> R(n, INT_MAX);
        p = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            p = min(p + 1, c[i]);
            R[i] = p;
        }

        forn(i, n)  
            cout << min(L[i], R[i]) << " ";
        cout << endl;
    }
}

1547F - Array Stabilization (GCD version)

Idea: doreshnikov

Tutorial

Solution

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const unsigned int MAX_A = 1'000'000;
vector<unsigned int> sieve(MAX_A + 1);
vector<unsigned int> prime;

unsigned int gcd(unsigned int a, unsigned int b) {
    return b == 0 ? a : gcd(b, a % b);
}

unsigned int solve() {

    unsigned int n;
    cin >> n;
    vector<unsigned int> a(n);
    for (unsigned int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unsigned int common = a[0];
    vector<set<unsigned int>> facts(n);
    for (unsigned int i = 1; i < n; i++) {
        common = gcd(common, a[i]);
    }
    for (unsigned int i = 0; i < n; i++) {
        unsigned int t = a[i] / common;
        while (t != 1) {
            facts[i].insert(sieve[t]);
            t /= sieve[t];
        }
    }

    unsigned int answer = 0;
    for (unsigned int i = 0; i < n; i++) {
        for (unsigned int p : facts[i]) {
            int l = (i + n - 1) % n, r = i;
            unsigned int cnt = 0;
            while (facts[l].count(p) > 0) {
                facts[l].erase(p);
                l--; cnt++;
                if (l < 0) {
                    l = n - 1;
                }
            }
            while (facts[r].count(p) > 0) {
                if (r != i) {
                    facts[r].erase(p);
                }
                ++r %= n; cnt++;
            }
            answer = max(answer, cnt);
        }
        facts[i].clear();
    }

    return answer;

}

int main() {

    sieve[1] = 1;
    for (unsigned int i = 2; i <= MAX_A; i++) {
        if (sieve[i] == 0) {
            sieve[i] = i;
            prime.push_back(i);
        }
        for (unsigned int j = 0; j < prime.size() && prime[j] <= sieve[i] && i * prime[j] <= MAX_A; j++) {
            sieve[i * prime[j]] = prime[j];
        }
    }

    unsigned int t;
    cin >> t;
    for (unsigned int i = 0; i < t; i++) {
        cout << solve() << '\n';
    }

}

1547G - How Many Paths?

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int n;
vector<vector<int>> g;
set<int> s[2];

void dfs(int u, vector<int>& color, bool use_s) {
    color[u] = 1;
    for (int v: g[u])
        if (color[v] == 0)
            dfs(v, color, use_s);
        else if (use_s)
            s[color[v] - 1].insert(v);
    color[u] = 2;
}

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int m;
        cin >> n >> m;
        g = vector<vector<int>>(n);
        forn(i, 2)
            s[i] = set<int>();
        forn(i, m) {
            int x, y;
            cin >> x >> y;
            x--, y--;
            g[x].push_back(y);
        }
        vector<int> color = vector<int>(n);
        dfs(0, color, true);
        vector<vector<int>> c(2, vector<int>(n));
        forn(i, 2)
            for (auto u: s[i])
                dfs(u, c[i], false);
        forn(i, n) {
            int ans = 0;
            if (color[i] != 0) {
                ans = 1;
                if (c[0][i])
                    ans = -1;
                else if (c[1][i])
                    ans = 2;
            }
            cout << ans << " ";
        }
        cout << endl;
    }
}

Full text and comments »

Tutorial of Codeforces Round 731 (Div. 3)

editorial, tutorial, 731

+228

doreshnikov
3 years ago
145