Codeforces Round 1043 (Div. 3) Разбор

Мы надеемся, что вам понравился контест! Спасибо вам за участие! Для нас это второй официальный раунд, поэтому мы были бы рады услышать ваши отзывы в комментариях и в мини опросе ниже.

Как вам контест?

Какие задачи вам понравились (можно выбрать несколько)?

Какие задачи вам не понравились (можно выбрать несколько)?

2132A - Домашнее задание

Идея: Wileyne; разработчик: Wileyne

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    string a, b, c;
    int n, m;
    cin >> n >> a;
    cin >> m >> b >> c;
    string add_left = "";
    for (int i = 0; i < m; ++i) {
        if (c[i] == 'V') {
            add_left += b[i];
        } else {
            a += b[i];
        }
    }
    reverse(add_left.begin(), add_left.end());
    cout << add_left + a << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

2132B - Загаданное число

Идея: fstilus; разработчик: fstilus

Подсказка

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long r;
        cin >> r;
        
        long long d = 11;
        vector <long long> ans;
        while (r >= d) {
            if (r % d == 0)
                ans.push_back(r / d);
            d = (d - 1) * 10 + 1;
        }
        
        cout << (int)ans.size() << '\n';
        for (int i = (int)ans.size() - 1; i >= 0; --i)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    
    return 0;
}

2132C1 - Хитрый продавец (простая версия)

Идея: fstilus; разработчик: KotlechkovEgor

Подсказка 1

Подсказка 2

Подсказка 3

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector <long long> cost;
    long long c = 3;
    long long cnt = 1;
    for (int i = 0; i < 21; ++i) {
        cost.push_back(c);
        c = 3 * c + cnt;
        cnt *= 3;
    }

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        long long min_k = 0;
        long long min_cost = 0;
        int sz = 0;
        while (n) {
            min_k += n % 3;
            min_cost += (n % 3) * cost[sz];
            n /= 3;
            sz++;
        }
        cout << min_cost << '\n';
    }
    
    return 0;
}

2132C2 - Хитрый продавец (сложная версия)

Идея: Boodoochai; разработчик: KotlechkovEgor

Подсказка 1

Подсказка 2

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector <long long> cost;
    long long c = 3;
    long long cnt = 1;
    for (int i = 0; i < 21; ++i) {
        cost.push_back(c);
        c = 3 * c + cnt;
        cnt *= 3;
    }

    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        vector <long long> tr;
        long long min_k = 0;
        while (n) {
            tr.push_back(n % 3);
            min_k += n % 3;
            n /= 3;
        }
        if (min_k > k) {
            cout << -1 << '\n';
            continue;
        }
        k -= min_k;
        k /= 2;
        for (int i = (int)tr.size() - 1; i >= 1; --i) {
            if (tr[i] <= k) {
                tr[i - 1] += 3 * tr[i];
                k -= tr[i];
                tr[i] = 0;
            } else {
                tr[i - 1] += k * 3;
                tr[i] -= k;
                break;
            }
        }
        ll an = 0;
        for (int i = (int)tr.size() - 1; i >= 0; --i)
            an += cost[i] * tr[i];
        cout << an << '\n';
    }
    
    return 0;
}

2132D - От 1 до бесконечности

Идея: fstilus; разработчик: fstilus

Подсказка 1

Подсказка 2

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long k;
        cin >> k;
        long long cur = 9, len = 1;
        while (k - cur * len > 0) {
            k -= cur * len;
            cur *= 10;
            len++;
        }
        string s = to_string(cur / 9 + (k - 1) / len);
        long long ans = 0;
        for (int i = 0; i < (k - 1) % len + 1; i++)
            ans += s[i] - '0';
        long long pr_s = 0;
        for (int i = 0; i < s.length(); i++) {
            int curd = s[i] - '0';
            if (curd)
                ans += curd * (len - 1) * cur / 2 + curd * (2 * pr_s + curd - 1) / 2 * cur / 9;
            cur /= 10, len--;
            pr_s += curd;
        }
        cout << ans << '\n';
    }
    
    return 0;
}

2132E - Соревнование по арифметике

Идея: EzikBro; разработчик: EzikBro

Подсказка 1

Подсказка 2

Подсказка 3

Подсказка 4

Разбор

Решение 1

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector <int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());

    vector <long long> pa(n + 1), pb(m + 1);
    for (int i = 0; i < n; i++)
        pa[i + 1] = pa[i] + a[i];
    for (int i = 0; i < m; i++)
        pb[i + 1] = pb[i] + b[i];

    vector <pair <int, int>> ans(n + m + 1);
    int l = 0, r = 0;
    for (int i = 1; i < ans.size(); i++) {
        if (l < n && r < m) {
            if (a[l] < b[r])
                r++;
            else
                l++;
        }
        else if (l == n)
            r++;
        else if (r == m)
            l++;
        ans[i] = { l, r };
    }

    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        l = ans[z].first, r = ans[z].second;
        if (l > x)
            cout << pa[x] + pb[z - x] << '\n';
        else if (r > y)
            cout << pa[z - y] + pb[y] << '\n';
        else
            cout << pa[l] + pb[r] << '\n';
    }
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Решение 2

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector <int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
 
    vector <long long> pa(n + 1), pb(m + 1);
    for (int i = 0; i < n; i++)
        pa[i + 1] = pa[i] + a[i];
    for (int i = 0; i < m; i++)
        pb[i + 1] = pb[i] + b[i];
 
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
 
        int l = max(0, z - y);
        int r = min(z, x);
        while (l + 2 < r) {
            int m1 = (l + l + r) / 3;
            int m2 = (l + r + r) / 3;
            if (pa[m1] + pb[z - m1] > pa[m2] + pb[z - m2]) {
                r = m2;
            } else {
                l = m1;
            }
        }
 
        long long s = 0;
        for (int i = l; i <= r; i++)
            s = max(s, pa[i] + pb[z - i]);
 
        cout << s << '\n';
    }
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

2132F - Рада и Ромашковая долина

Идея: Friendiks, Wileyne; разработчики: Friendiks, Wileyne

Подсказка 1

Подсказка 2

Подсказка 3

Подсказка 4

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
vector <vector <int>> g;
vector <bool> used;
vector <int> d, h;
vector <pair <int, int>> edges;
vector <int> cut, path;
int mark = 1;

void dfs(int v, int p, int n) {
    used[v] = true;
    d[v] = h[v] = (p == -1 ? 0 : d[p] + 1);
    if (v == n) mark = 0;
    for (auto e : g[v]) {
        int to = edges[e].first + edges[e].second - v;
        if (to == p) continue;
        if (used[to])
            h[v] = min(h[v], d[to]);
        else {
            path[e] ^= mark;
            dfs(to, v, n);
            path[e] ^= mark;
            h[v] = min(h[v], h[to]);
            if (h[to] > d[v]) cut[e] = 1;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        g.assign(n + 1, {});
        used.assign(n + 1, false);
        d.assign(n + 1, 0);
        h.assign(n + 1, 0);
        edges = {};
        cut.assign(m, false);
        path.assign(m, false);
        mark = 1;
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            edges.push_back({a, b});
            g[a].push_back(i);
            g[b].push_back(i);
        }
        
        dfs(1, -1, n);
        
        vector <int> ans(n + 1, n + m);
        vector <int> dist(n + 1, n + m);
        queue <int> q;
        for (int i = 0; i < m; ++i) {
            if (cut[i] && path[i]) {
                ans[edges[i].first] = min(ans[edges[i].first], i + 1);
                ans[edges[i].second] = min(ans[edges[i].second], i + 1);
                if (dist[edges[i].first]) {
                    dist[edges[i].first] = 0;
                    q.push(edges[i].first);
                }
                if (dist[edges[i].second]) {
                    dist[edges[i].second] = 0;
                    q.push(edges[i].second);
                }
            }
        }
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto e : g[v]) {
                int to = edges[e].first + edges[e].second - v;
                if (dist[to] > dist[v] + 1) {
                    dist[to] = dist[v] + 1;
                    ans[to] = ans[v];
                    q.push(to);
                }
                else if (dist[to] == dist[v] + 1)
                    ans[to] = min(ans[to], ans[v]);
            }
        }
        
        int Q;
        cin >> Q;
        while (Q--) {
            int v;
            cin >> v;
            if (ans[v] == n + m) cout << -1;
            else cout << ans[v];
            if (t || Q) cout << '\n';
        }
    }
    
    return 0;
}

2132G - Известный балетмейстер

Идея: fstilus; разработчики: fstilus, pskobx

Подсказка 1

Подсказка 2

Подсказка 3

Подсказка 4

Подсказка 5

Подсказка 6

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int P[2] = { 107, 61 };
int BP[2];

long long bin_pow(long long a, int n) {
    long long ret = 1;
    while (n) {
        if (n & 1) ret = (ret * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return ret;
}

inline int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) return res - MOD;
    return res;
}

inline int sub(int a, int b) {
    int res = a - b;
    if (res < 0) return res + MOD;
    return res;
}

inline int mult(int a, int b) {
    long long res = (long long)a * b;
    if (res >= MOD) return res % MOD;
    return res;
}

int main() {
    int t;
    cin >> t;
    
    BP[0] = bin_pow(P[0], MOD - 2);
    BP[1] = bin_pow(P[1], MOD - 2);
    vector <int> pows[2];
    vector <int> bpows[2];
    for (int j = 0; j < 2; j++) {
        pows[j].resize(1e6, 1);
        bpows[j].resize(1e6, 1);
        for (int i = 1; i < 1e6; i++) {
            pows[j][i] = mult(pows[j][i - 1], P[j]);
            bpows[j][i] = mult(bpows[j][i - 1], BP[j]);
        }
    }
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        vector <string> f(n);
        for (int i = 0; i < n; i++)
            cin >> f[i];
        
        vector <vector <int>> hash(n + 2, vector <int> (m + 2, 0));
        vector <vector <int>> bhash(n + 2, vector <int> (m + 2, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][i - 1], pows[1][j - 1]));
                hash[i][j] = add(sub(add(hash[i - 1][j], hash[i][j - 1]), hash[i - 1][j - 1]), cur);
            }
        }
        for (int i = n; i >= 1; i--) {
            for (int j = m; j >= 1; j--) {
                int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][n - i], pows[1][m - j]));
                bhash[i][j] = add(sub(add(bhash[i + 1][j], bhash[i][j + 1]), bhash[i + 1][j + 1]), cur);
            }
        }
        
        auto isp = [&](int x1, int y1, int x2, int y2) {
            int hsh = add(sub(sub(hash[x2][y2], hash[x1-1][y2]), hash[x2][y1-1]), hash[x1-1][y1-1]);
            int bhsh = add(sub(sub(bhash[x1][y1], bhash[x2+1][y1]), bhash[x1][y2+1]), bhash[x2+1][y2+1]);
            hsh = mult(hsh, mult(bpows[0][x1 - 1], bpows[1][y1 - 1]));
            bhsh = mult(bhsh, mult(bpows[0][n - x2], bpows[1][m - y2]));
            return hsh == bhsh;
        };
        
        int mn = n * m * 4;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (isp(1, 1, i, j)) mn = min(mn, (2 * n - i) * (2 * m - j));
                if (isp(1, j, i, m)) mn = min(mn, (2 * n - i) * (m + j - 1));
                if (isp(i, 1, n, j)) mn = min(mn, (n + i - 1) * (2 * m - j));
                if (isp(i, j, n, m)) mn = min(mn, (n + i - 1) * (m + j - 1));
            }
        }
        
        cout << mn - m * n << '\n';
    }
    
    return 0;
}

Комментарии (54)

Показать архивные | Написать комментарий?

Mitpro

12 месяцев назад, скрыть # |

← Rev. 3 →

I found the solution for C2 1 minute after the contest ended! I am so sad :(

→ Ответить

ketan_k_j

12 месяцев назад, скрыть # ^ |

-8

++ :(

xy7777

Can you tell me your method(s) to solve the C2? I don't understand their solution.Thanks

yiwangwuqian

Greedly to buy smaller groups,greedly to make biggest smaller.

georkings

Thanks for the fast editorial and the contest... very mathematical

prayag2

+17

Thank you for the contest! The problems felt very new and refreshing.

Folka

This contest is below the average not good and not bad.

osasboiii

Amazing contest! C2 was really fun.

MisterGir

My G is just Ctrl C + Ctrl V . ( I mean copying hashes) — My solution. Try to hack!

Sorry for my English)

wasif2397

-11

F is a piece of cake if you've solved this

_raayyyaaaannnnn_

F was easy but i just missed the output format:( i thought if there are no valid lanes then just output -1 and go for another testcase :sed:

MathModel

+15

Thank you for the contest ! , although I did unrated , but definitely one of my most favorite Div3's .

Kudos to authors.

wish_i_was_orphan

← Rev. 2 →

HELP

I did exact same thing as mentioned in editorial for problem F but it gives WA,any help is appreciated Kogut_Ivan .

Submission — 334939521

F was easy but i missed the output format i thought if there are no valid lanes then just output single line -1 and move for another testcase:(

MiracleMagician

D is already online available: Geek for geeks cses

chromate00

I am here after hearing that 2132E - Arithmetics Competition is practically equivalent to 2063D - Game With Triangles. As the coauthor of that problem, I must confirm that this is true. So you cannot fail to disappoint, huh...

toberu

+23

I demand justice for ternary search solution for problem E! This problem is actually so fun to do ternary search with, as the moment you realize the function is linear brings so much satisfaction (from my 10-second long experience, it is indeed satisfactory)!

hossain.rasel.1042

D is similar like digit queries of CSES problemset. I already solved digit queries still not able to solve the d problem sad :(

robicodex18

+14

F was really amazing!

omaralimm

The problems were too mathematical and time consuming. Personally, I did not like the contest.

Nisikto

Who is supposed to know or think this: If Vadim appends k zeros to the number x, what will be the ratio between n and x? I'm not doing math olympiad.

Actually it's very easy to find the solution once one think like a mathematician.

Octa_pe_info

Math forces. I did e and f but not c2 and d, hope to see another div 3 soon ☺️

Vidush.rk11

Can someone explain why ternary search works in E but not binary search?

Senku

I used binary search 334924908

Idea : Sort both arrays in descending order and try to find i and j such that a[i] and b[j] are as close as possible

harlenka

С2 is so nice

Dynamic_Elaina

+10

E and C2 are interesting！But I don't like D.

cuigod

Hello! If my rating is 1400 right now, what number of tasks in a contest should i ac so that it won't drop the rating? Thx

_SSH_

5 (Div 3) 3 (Div 2)

ankeet

Simpler solution to D:

Binary search for the largest $$$L$$$ such that the total number of digits in $$$1, ..., L$$$ is at most $$$k$$$. Then, compute the sum of digits of all numbers in $$$1, ..., L$$$ as well as the partial piece of $$$L + 1$$$.

The number/sum of digits in $$${1, ..., N}$$$ are standard problems. The latter can be calculated via a digit-dp like approach.

Code: 334983266

_Untrackable_

thnx dude:)

Forever-2022

A good contest! I love it.

Larin_Lev

Why should we do k /= 2 in C2 solution?

If you move a 3^x deal, you need three 3^(x — 1) deals. -1+3=2, so we should do k /= 2 in C2 solution

yangyang1000

Good C2 but bad F and G.

itsrohit

Wileyne Note that this function is convex Isn't the function concave ?

shorya2448

Yes I also think so.

Trumpsunderwear

In problem-C1, I found attached statement ambiguous

Statement

Which parameter should be minimized first? no of deals or cost

Because as per formula, cost(3^(x+1)) > cost(3*3^x)

Proof

This means if we increase no of deals cost will reduce but if we reduce no of deals cost will increase

Mr_Bald

The statement, "considering that he will make the least possible number of deals", defines the number of deals explicitly. That is, you need to consider the minimum number of deals in general. From there, minimize the amount that will be paid.

Note: The minimum number of deals is sum of digits in the base-3 representation of the given number.

Hoang_Thien_De

Why do I get Wrong Answer on test 97 when I submit the author's code (problem G)?

yoshi_likes_e5

Considering that the base set and modulo in the editorial's solution is fixed, I would guess that test 97 is a hack case.

Random fact

ER3N_Yager

Feels like I’m doing a math olympiad, not a Codeforces contest

stoppppittttadiiii

great editorial!

Very simmilar problem to G

n00bmaster__

F is such a great problem!! Loved it,although I have not read the tutorial yet but saw some solutions,I think everyone's doing the same thing as I did.

Shadow_T

I think this one is not bad, but why are so many people against it? I think C2 and D are both pretty good.

：)

momoforce

If a unimodal function has a flat top, can the ternary search algorithm be applied on the integer domain only if the flat top occurs at the extremum point? I used to think that if there was a flat top, the ternary search could not be used.

JJCUBER

It can be applied to that along with a few other forms of unimodal integer functions. You can search a unimodal integer function so long as it has strict inequality on one end and loose inequality on the other. In other words, it must be in one of these forms:

$$$f(1) \lt f(2) \lt \dots \lt f(k) \geq f(k+1) \geq f(k+2) \geq \dots$$$ $$$f(1) \leq f(2) \leq \dots \leq f(k) \gt f(k+1) \gt f(k+2) \gt \dots$$$ $$$f(1) \gt f(2) \gt \dots \gt f(k) \leq f(k+1) \leq f(k+2) \leq \dots$$$ $$$f(1) \geq f(2) \geq \dots \geq f(k) \lt f(k+1) \lt f(k+2) \lt \dots$$$

If we were to allow loose inequality on both ends, then getting the same value twice wouldn't tell us where we are relative to the maximum/minimum (whereas allowing it on strictly one end tells us that we are currently still on the same side of the maximum/minimum so long as we are comparing two consecutive spots during the ternary search). An example of an implementation which supports the aforementioned ternary search property can be found on kactl.

Your point is very enlightening, thank you!

mack_lykyn_

I just found out that there is something wrong with the problem B, why is it so? after I spent a lot of time solving problem B then I just read the solution from the editorial I just wrote the same way only and the answer is accepted, but here is my custom testcase why I found wrong, consider n = 123123, then the answer according to the editorial is 2 123 11193

so, is this solution right or wrong?, I feel sorry for those who wasted time on solution B

problem is mistaken

khanhdungtrinh

In problem E, the writer says "This will be the optimal answer because all the cards taken from array a will be at least as large as all the cards that have not yet been taken from array b , meaning there is no point in making additional swaps of cards from one array to another." Can any explain this? I don't understand.

Licnex

11 месяцев назад, скрыть # |

Alright how the hell is this a div 3 competition?

afangbc

5 недель назад, скрыть # |

why so many downvotes?

№	Пользователь	Рейтинг
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

№	Пользователь	Вклад
1	Qingyu	158
2	maspy	150
3	Um_nik	146
4	Errichto	139
5	adamant	136
6	maroonrk	134
7	DNR	133
8	Dominater069	131
9	Proof_by_QED	130
9	AmShZ	130

Блог пользователя Kogut_Ivan