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

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Разбор

Решение

#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 a, b, c, x, y;
        cin >> a >> b >> c >> x >> y;
        int ax = min(a, x);
        int by = min(b, y);
        a -= ax;
        x -= ax;
        b -= by;
        y -= by;
        if (c >= x + y)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

1675B - Сделай возрастающую

Идея: MikeMirzayanov

Разбор

Решение

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin >> n;
    vector<int>a(n);
    for(auto &i : a) cin >> i;
    int ans = 0;
    for(int i = n - 2; i >= 0; i--){
        while(a[i] >= a[i + 1] && a[i] > 0){
            a[i] /= 2;
            ans++;
        }
        if(a[i] == a[i+1]){
            cout << -1 << '\n';
            return;
        }
    }
    cout << ans << '\n';
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

1675C - Детективная задача

Идея: Gol_D

Разбор

Решение

#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;
        int n = s.length();
        vector<bool> a(n + 1);
        a[0] = true;
        forn(i, n)
            a[i + 1] = a[i] && (s[i] == '1' || s[i] == '?');
        vector<bool> b(n + 1);
        b[0] = true;
        for (int i = n - 1; i >= 0; i--)
            b[n - i] = b[n - i - 1] && (s[i] == '0' || s[i] == '?');
        int result = 0;
        forn(i, n)
            if (a[i] && b[n - i - 1])
                result++;
        cout << result << endl;
    }
}

1675D - Вертикальные пути

Идея: MikeMirzayanov

Разбор

Решение

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int>b(n + 1);
    vector<bool>leaf(n + 1, true);
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
        leaf[b[i]] = false;
    }

    if(n == 1){
        cout << "1\n1\n1\n\n";
        return;
    }

    vector<int>paths[n + 1];
    vector<bool>used(n + 1, false);
    int color = 0;

    for(int i = 1; i <= n; i++){
        if(!leaf[i]) continue;
        used[i] = true;
        paths[color].emplace_back(i);

        int v = i;
        while (b[v] != v && !used[b[v]]){
            v = b[v];
            used[v] = true;
            paths[color].emplace_back(v);
        }
        color++;
    }

    cout << color << '\n';
    for(auto &path : paths){
        if(path.empty()) continue;
        cout << (int)path.size() << '\n';
        reverse(path.begin(), path.end());
        for(auto &v: path) cout << v << ' ';
        cout << '\n';
    }
    cout << '\n';
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

1675E - Замени на предыдущий, минимизируй

Идея: myav

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back

template <class T> bool ckmax(T &a, T b) {return a<b ? a=b, true : false;}


void solve() {
    int n,k; cin >> n >> k;
    string s; cin >> s;

    char mn = 'a';
    for (int i = 0; i < n; i++) if(s[i] > mn) {
        if (s[i] - 'a' > k) {
            k -= mn - 'a';
            int to = s[i] - k;
            for (char c = s[i]; c > to; c--) {
                for (char &e:s) if (e == c) {
                    e = char(c-1);
                }
            }
            break;
        } else ckmax(mn, s[i]);
    }
    for (char &e:s) if (e <= mn) {
        e = 'a';
    }
    cout << s << endl;
}

int main() {
    int t;
    cin >> t;

    forn(tt, t) {
        solve();
    }
}

1675F - Влад и отложенные дела

Идея: Vladosiya

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define ll long long
//#define double long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

const int MOD = 1e9 + 7;
const int maxN = 5e3 + 1;
const int INF = 2e9;
const int MB = 20;

vector<vector<int>> g;
vector<bool> todo, good;

void dfs(int v, int p = -1) {
    for (int u : g[v]) {
        if (u != p) {
            dfs(u, v);
            if (todo[u]) {
                todo[v] = true;
            }
            if (good[u]) {
                good[v] = true;
            }
        }
    }
}

void solve() {
    int n, k;
    cin >> n >> k;
    g.clear();
    g.resize(n);
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    todo.resize(n);
    fill(all(todo), false);
    good.resize(n);
    fill(all(good), false);
    for (int i = 0; i < k; ++i) {
        int v;
        cin >> v;
        --v;
        todo[v] = true;
    }
    good[y] = true;
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v;
        --u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfs(x);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (i == x) {
            continue;
        }
        if (good[i]) {
            ++ans;
        } else if (todo[i]) {
            ans += 2;
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //    srand(time(0));
    int t = 1;
    cin >> t;
    while (t--) solve();
}

1675G - Сортировка блинчиков

Идея: Vladosiya

Разбор

Решение

#include <bits/stdc++.h>

//#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

typedef long double ld;
typedef long long ll;

using namespace std;

mt19937 rnd(143);

const ll inf = 1e9 + 7;
const ll M = 998'244'353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;

void solve(int test_case) {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), pancakes(1);
    for(int &e: a) cin >> e;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < a[i]; ++j){
            pancakes.emplace_back(i);
            int c = pancakes.size();
            pancakes[c - 1] += pancakes[c - 2];
        }
        if(i > 0) a[i] += a[i - 1];
    }
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(m + 1, vector<int>(m + 1, inf)));
    for(int j = 0; j <= m; j++){
        if(a[0] >= j) dp[0][j][j] = a[0] - j;//moved right
        else dp[0][j][j] = pancakes[j];//moved from right
    }
    for(int j = m - 1; j >= 0; --j){
        for(int k = j; k <= m; ++k){
            dp[0][j][k] = min(dp[0][j][k], dp[0][j + 1][k]);
        }
    }
    for(int i = 1; i < n; ++i){
        for(int j = 0; j <= m; ++j){
            for(int k = j; k <= m; ++k){
                int add = 0;
                if(a[i] >= k) add = a[i] - k;//moved to i + 1
                else {
                    int lend = min(j, k - a[i]);
                    add = pancakes[k] - pancakes[k - lend] - i * (lend);//moved from greater i
                }
                dp[i][j][k] = dp[i - 1][j][k - j] + add;
            }
        }

        for(int j = m - 1; j >= 0; --j){
            for(int k = (i + 1) * j; k <= m; ++k){
                dp[i][j][k] = min(dp[i][j][k], dp[i][j + 1][k]);
            }
        }
    }
    cout << dp[n-1][0][m];
}

bool multi = false;

signed main() {
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

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

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

matteodellamico

2 года назад, # |

+19

With respect to the F problem, another (maybe simpler?) explanation:

hang the tree from x (or y, it's equivalent)
iteratively remove all leaves that are not in a or [x, y], we'll end up with only nodes that we'll visit
all edges from the resulting graph need to be traversed twice (back and forth), except the ones connecting x to y
if the graph after step 2 has n edges, the solution is 2 * (n — 1) — depth[y]

→ Ответить

Livu_sz

2 года назад, # ^ |

Can you please explain why answer can't be 2*(no of edges) — depth[y].

Link to My submission : Link

Sorry If I misunderstood your approach

It is exactly that, after removing from the graph all the leaves that aren't in a. You can have a look at my submission: https://codeforces.com/contest/1675/submission/156053555

InfinitePath

9 месяцев назад, # ^ |

The 3rd step seems intuitive enough with just a few examples, but I can't concretely come up with proof for the third step. Can you explain why this is always the case?

ShreyHehe

2 месяца назад, # ^ |

Brilliant! Thank You!

sharmaharisam

← Rev. 2 →

In case someone is interested, I made video Solutions for D-F

epsilon_573

Video Solution for G

happy_new_year_2022

sharmaharisam epsilon_573 you guys should do a collab, since one has uploaded d, e, f and the other has uploaded g. (YouTube collab, not contest collab xD).

Actually I was recording A-F last night, but E was so tricky to explain intuitively... I just skipped the video altogether :p

rest_api

.Edd

Maybe C is simpler if we do

3 Cases:

It is a '?' increment counter
it is a 0, return counter + 1
it is a 1, reset the counter and set it to 1.

ahmet23

Can anyone explain what does int lend = min(j, k - a[i]); mean, in problem G?

Vladosiya

It's the number of pancakes, we need to take from dishes with bigger index. k — a[i] is how many is missing to get sum = k but we can't need more than j, because all pancakes on previous dishes are placed, so it's min(j, k — a[i]).

v7fgg

Question D，why I always got tle if i look for the path from up to bottom?

and also tle with the tutorial's method

Penguin07

My $$$O(n * m^3)$$$ for G almost got TLE. Submission

Citypop

Any resources or similar problems to better understand G?

Any resources or similar problems to better understand G? Still confused by just reading editorial.

strglntoexist

Can anyone explain the solution of the problem G-Sorting Pancakes??

YMSeah

In G, intuitively we see that a dp solution will work. If we want to put some pancakes on the ith dish, we need to have the same or more pancakes on the previous dish. To determine what can be put down later, we need to know how many pancakes we have put down previously. Hence, we need to take note of 1) how many pancakes we put down on the ith dish, and 2) how many pancakes we have put down in total. These will form our state. Hence we can have dp[i][number of pancakes on ith dish][number of pancakes put down in total] to describe our solution. The number of states for dp[n][m][m] is n * m * m which is 250 * 250 * 250 which is small enough.

To transition to dp[i][j][k], we come from a previous state with fewer total pancakes. But the previous state's number of pancakes must be more. So we have dp[i-1][j2>=j][k-j] -> dp[i][j][k]. So, dp[i][j][k] = min(dp[i][j][k], dp[i-1][j2][k-j] + some transition value) for all j2>=j. The transition value (referred to as "add" in the editorial) is the number of moves required to go from a "pancake configuration" of having k-j pancakes in the first i-1 plates, to the same configuration but with exactly j pancakes on the ith plate. I don't know how people calculate these transition values elegantly. I had a greedy and incredibly messy way to calculate these.

Finally, the answer is the minimum value for dp[n — 1][j][m], for 0<=j<=m. I hope this helps.

You may refer to my solution 156195983 but it is in python, with the differences of me reversing a to solve for increasing pancakes, and I switched the definitions for j and k. So my definition is dp[i][prefix sum of pancakes up to i][number of pancakes on i].

NafisAlam

can u elaborate why the dp is : dp[i][number of pancakes on ith dish][number of pancakes put down in total] and why not dp[i][number of pancakes put down in total][number of pancakes on ith dish] ? Can we imagine this as a 3D matrix? If so, then what do the row, column and height of this matrix implicate?

Both ways work. I used the latter which is dp[i][number of pancakes put down in total][number of pancakes on ith dish] in my actual solution. But the solution used in the editorial uses the former which is dp[i][number of pancakes on ith dish][number of pancakes put down in total].

I will also discourage you from visualizing dp matrices spatially because it is very difficult and unnecessary. The important thing for doing dp is to have a firm understanding of the states, their transitions and their edge/boundary cases.

thank you for ur fast response sir :D

itish

Can someone explain the solution for problem E. Tutorial is somewhat complicated to understand.

ravenr

Can you please explain why in the task g dp transitions are d[i][last][k] = d[i-1][last][k-last] does it means that last = j, instead of last >= j?

Got it

tgp07

I solved problem F with dfs, dp, and LCA+binary lifting. A lot more stuff than needed lol

156882408 Warning: Code is quite messy and I haven't commented. Enter at your own peril.

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