Разбор Educational Codeforces Round 140

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Разбор

Решение (BledDest)

t = int(input())
for i in range(t):
    input()
    xs = []
    ys = []
    for j in range(3):
        x, y = map(int, input().split())
        xs.append(x)
        ys.append(y)
    print('YES' if len(set(xs)) == 3 or len(set(ys)) == 3 else 'NO')

1767B - Block Towers

Идея: BledDest

Разбор

Решение (awoo)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    x = a[0]
    a = sorted(a[1:])
    for y in a:
        if y > x:
            x += (y - x + 1) // 2
    print(x)

1767C - Count Binary Strings

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

const int N = 143;
int n;

int a[N][N];
int dp[N][N];

bool check(int cnt, int last)
{
    for(int i = 0; i < cnt; i++)
    {
        if(a[i][cnt - 1] == 0) continue;
        if(a[i][cnt - 1] == 1 && last > i) return false;
        if(a[i][cnt - 1] == 2 && last <= i) return false;
    }
    return true;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
            cin >> a[i][j];
    }
    if(a[0][0] != 2) dp[1][0] = 2;
    for(int i = 1; i < n; i++)
        for(int j = 0; j < i; j++)
            for(int k : vector<int>({j, i}))
                if(check(i + 1, k))
                    dp[i + 1][k] = add(dp[i + 1][k], dp[i][j]);
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans = add(ans, dp[n][i]);
    cout << ans << endl;
}

1767D - Playoff

Идея: Neon

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  string s;
  cin >> n >> s;
  int k = count(s.begin(), s.end(), '1');
  for (int x = 1 << k; x <= (1 << n) - (1 << (n - k)) + 1; ++x)
    cout << x << ' ';
}

1767E - Algebra Flash

Идея: BledDest

Разбор

Решение (awoo)

#include <bits/stdc++.h>

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

using namespace std;


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> c(n);
    forn(i, n){
        scanf("%d", &c[i]);
        --c[i];
    }
    vector<int> x(m);
    forn(i, m) scanf("%d", &x[i]);
    
    vector<long long> g(m);
    forn(i, n - 1){
        g[c[i]] |= 1ll << c[i + 1];
        g[c[i + 1]] |= 1ll << c[i];
    }
    g[c[0]] |= 1ll << c[0];
    g[c[n - 1]] |= 1ll << c[n - 1];
    
    int mid = m / 2;
    vector<int> dp(1 << mid, 1e9);
    forn(mask, 1 << (m - mid)){
        long long chk = 0;
        int tot = 0;
        forn(i, m - mid){
            if ((mask >> i) & 1)
                tot += x[i + mid];
            else
                chk |= g[i + mid];
        }
        if (((chk >> mid) | mask) != mask)
            continue;
        chk &= (1ll << mid) - 1;
        dp[chk] = min(dp[chk], tot);
    }
    forn(i, mid) forn(mask, 1 << mid) if (!((mask >> i) & 1)){
        dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask]);
    }
    int ans = 1e9;
    forn(mask, 1 << mid){
        long long chk = 0;
        int tot = 0;
        forn(i, mid){
            if ((mask >> i) & 1)
                tot += x[i];
            else
                chk |= g[i];
        }
        chk &= (1ll << mid) - 1;
        if ((chk | mask) != mask)
            continue;
        ans = min(ans, dp[mask] + tot);
    }
    printf("%d\n", ans);
    return 0;
}

1767F - Two Subtrees

Идея: shnirelman

Разбор

Решение (shnirelman)

#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;
using li = long long;
using ld = long double;
using pii = pair<int, int>;

const int INF = 2e9 + 13;
const li INF64 = 2e18 + 13;
const int M = 998244353;
const int A = 2e5 + 13;

const int N = 2e5 + 13;
const int B = 2000;
const int SQRTA = 500;
const int K = N / B + 113;

int val[N];
vector<int> g[N];
int sz[N];
int gr[N];
int leaf[N], group_root[N];
int par[N];
bool heavy[N];

int tin[N], tout[N], T = 0, mid[N];
int et[N];
int valet[N];


void dfs1(int v, int pr, int depth) {
    par[v] = pr;
    sz[v] = 1;

    int mx = -1;
    for(int i = 0; i < g[v].size(); i++) {
        int u = g[v][i];
        if(u != pr) {
            dfs1(u, v, depth + 1);
            sz[v] += sz[u];
            if(mx == -1 || sz[g[v][mx]] < sz[u])
                mx = i;
        }
    }

    if(mx != -1)
        swap(g[v][mx], g[v][0]);
}

void dfs2(int v) {
    et[T] = v;
    tin[v] = T++;

    for(int u : g[v]) {
        if(u != par[v])
            dfs2(u);
    }

    tout[v] = T;
}

struct Query {
    int ind;
    int v, u;
    int lv, rv, lu, ru;
    int b;

    Query() {};
};

bool cmp(const Query& a, const Query& b) {
    if(a.b != b.b)
        return a.b < b.b;
    else
        return a.lu < b.lu;
}

int cnt[A];
int block_index[A];
int block_mx[A];
int block_cnt_of_cnt[A / SQRTA + 13][A];

inline void insert(int i) {
    block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
    cnt[valet[i]]++;
    block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
    if(cnt[valet[i]] > block_mx[block_index[valet[i]]])
        block_mx[block_index[valet[i]]]++;
}

inline void erase(int i) {
    if(cnt[valet[i]] == block_mx[block_index[valet[i]]] && block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]] == 1)
        block_mx[block_index[valet[i]]]--;
    block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
    cnt[valet[i]]--;
    block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
}

int get_mode() {
    int mx = 0;
    for(int i = 0; i < A / SQRTA + 1; i++)
        mx = max(mx, block_mx[i]);
    for(int i = 0; ; i++) {
        if(block_mx[i] == mx) {
            for(int j = i * SQRTA; ; j++) {
                if(cnt[j] == mx)
                    return j;
            }
        }
    }
}

Query queries[N];
int ans[N];

void solve() {
    int n;
    cin >> n;

    for(int i = 0; i < n; i++)
        cin >> val[i];

    for(int i = 1; i < n; i++) {
        int v, u;
        cin >> v >> u;

        v--;
        u--;

        g[v].push_back(u);
        g[u].push_back(v);
    }

    dfs1(0, -1, 0);

    vector<pii> ord(n);
    for(int i = 0; i < n; i++) {
        ord[i] = {sz[i], i};
        gr[i] = -1;
    }

    sort(ord.begin(), ord.end());

    for(int i = 0; i < n; i++) {
        if(sz[i] >= B)
            heavy[i] = true;
    }

    int cur = 0;
    for(int i = 0; i < n; i++) {
        int v = ord[i].s;
        if(sz[v] < B || gr[v] != -1)
            continue;

        leaf[cur] = v;

        int u = v;
        while(gr[u] == -1 && sz[u] - sz[v] < B) {
            gr[u] = cur;
            group_root[cur] = u;
            u = par[u];
        }

        cur++;
    }

    dfs2(0);

    for(int i = 0; i < n; i++) {
        if(sz[i] < B) {
            gr[i] = cur + tin[i] / B;
        }
    }

    for(int i = 0; i < n; i++)
        valet[i] = val[et[i]];

    for(int i = 0; i < A; i++) {
        block_index[i] = i / SQRTA;
    }

    int q;
    cin >> q;

    for(int i = 0; i < q; i++) {
        queries[i].ind = i;
        cin >> queries[i].v >> queries[i].u;

        queries[i].v--;
        queries[i].u--;

        queries[i].lv = tin[queries[i].v];
        queries[i].rv = tout[queries[i].v];
        queries[i].lu = tin[queries[i].u];
        queries[i].ru = tout[queries[i].u];

        if(queries[i].lv > queries[i].lu) {
            swap(queries[i].v, queries[i].u);
            swap(queries[i].lv, queries[i].lu);
            swap(queries[i].rv, queries[i].ru);
        }

        queries[i].b = gr[queries[i].v];
    }

    sort(queries, queries + q, cmp);

    int lv = 0, rv = 0, lu = 0, ru = 0;
    li fir = 0, sec = 0;

    int hs = 0;
    for(int i = 0; i < q; i++) {
        int qlv = queries[i].lv;
        int qrv = queries[i].rv;
        int qlu = queries[i].lu;
        int qru = queries[i].ru;

        fir += abs(lv - qlv) + abs(rv - qrv);
        sec += abs(lu - qlu) + abs(ru - qru);

        if(queries[i].b < cur) {
            while(rv < qrv)
                insert(rv++);
            while(lv > qlv)
                insert(--lv);
            while(rv > qrv)
                erase(--rv);
            while(lv < qlv)
                erase(lv++);
        } else {
            while(rv > lv)
                erase(--rv);
            lv = qlv;
            rv = lv;
            while(rv < qrv)
                insert(rv++);
        }

        while(ru < qru)
                insert(ru++);
            while(lu > qlu)
                insert(--lu);
            while(ru > qru)
                erase(--ru);
            while(lu < qlu)
                erase(lu++);

        ans[queries[i].ind] = get_mode();
    }

    for(int i = 0; i < q; i++)
        cout << ans[i] << endl;
}

mt19937 rnd(1);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
//    freopen("input.txt", "r", stdin);

    solve();
}

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

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

Sheyer

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

+17

I have become an Expert thanks to this contest! Great D by the way.

→ Ответить

utility

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

-36

Don't worry , your new colour won't last long :D

AkibAzmain

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

+10

Despite getting a lot of downvotes, your prediction was indeed correct.

kallu_kakulu_dengey

← Rev. 2 →

In problem A, since the first line is empty. I read it as a string and never bothered to use it. It WA'd. This is my submission 185477892 . After the contest, I didn't even bother to read the first line and used the same code as above and it got AC. I am not sure why and could use some help.185647398

vgtcross

cin >> [whatever] doesn't work as you think. The input data is split into tokens: a token is a sequence of characters. Tokens are separated by whitespaces (incl. normal spaces and newline characters). Doing cin >> [whatever] reads the next token* and tries to convert it into the type of the variable. Doing cin >> [whatever] always skips over any spaces and newline characters. Thus, your cin >> s reads the first integer into your string, messing up the values. In order to read a full line into a single string (including all spsces, but not the newline character) you need to do the following:

string s;
getline(cin, s);

*doing cin >> [char] only reads the next character, but it still skips whitespaces.

Tima3

I will have time to grow old before the moment when I completely read, understand and solve the problem F... The longest editorial I've ever seen

And that's why we're not there yet. You're blue, I'm green haahha

tspbcontest

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

lol he went on to become orange and u a grey

Hahahah, indeed. Well done Tima3! You did incredible

so u still doing CP or left it

Left it. Haven't practiced much, which you can see on my graph ahaha.

satyam343

I think the overall complexity of attached solution of E is $$$O(2^{m/2} \cdot m)$$$

OMG_wc

+33

problem A-E video Editorial for Chinese:

BiliBili

aditya_01

-20

hi just a request.Please add english captions or if possible please speak in english.

Thanks for such a great video.

Zzybb

but you , my friend , you are the truly hero.

CodeWithSunny

Full Detailed Solution with Explanation of Problem C

Mustafiz

Firstly, let's prove that the order of characters in s is interchangeable Can anyone discribe it more widely. why it is happend.i can't visualize this.

WaisKamal

Problem A:

...and one of the resulting parts becomes a rectangle.

It never becomes a rectangle, rather it becomes a quadrilateral.

HarshaNP

Please make the editorial more understandable.

YocyCraft

Most of solutions and tutorials with "mask" are pretty hard to understand.

arda

This editorial was hard to understand, please make it easier to understand next time

Yaria

Alas, you are right, and there are too many hard-to-understand editorials on Codeforces. Sometimes I would rather directly learn top contestants' code.

suyasho786

can anyone explain the problem D

GTR.3910

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

There is an alternative solution for 1767E - Algebra Flash not using meet-in-the-middle, but employing an additional observation. I suspect that it works in $$$O(2^{m/2}*m)$$$ and system tests validate this, but I could use someone's help for a complete analysis.

A general idea is to activate every color in the beginning and deactivate colors one by one — well, actually two for one (at least). Firstly, we look at the lowest unselected color — call it $$$v$$$. Two options — either make it true (Deactivated) or false (Leave as activated).

First case: we make $$$v$$$ true. Then let's look at its neighbors. If neighboring color $$$u$$$ comes before $$$v$$$ $$$(u < v)$$$, this means we already assigned it some color. Otherwise we still didn't decide on color of $$$u$$$ and have to make it false (Because $$$v$$$ and $$$u$$$ cannot be deactivated simultaneously due to the same reasons as described in the editorial).

Second case: we make $$$v$$$ false. There is an important observation to use: If $$$v$$$ is false and all of its neighbors are false too, such color selection cannot be optimal.

Proof

Now, when we set $$$v$$$ to false, at least one of the neighbors must be set to true. So let's select that neighbor and then apply a known procedure for true vertexes (mark its neighbors as false)

Partial proof of complexity.

Since we remove at least 2 vertexes at each state, the maximum depth of recursion is at most $$$m/2$$$. Also, at each state, we have two choices: either to make the lowest color $$$x$$$ true or false. In case of making $$$x$$$ true, we create at most one new state.

In case of making $$$x$$$ false, we select $$$x$$$'s neighbor $$$y$$$, which we mark as true. The number of such neighbors can be up to $$$m$$$, but let's look at each generated state individually. The state with $$$x$$$ false and $$$y$$$ true is a repeated state, which we will also cover when $$$y$$$ will be the lowest unselected color. How many times such states are visited — is something that I need a help with.

If we apply some clever memoization — then the complexity is for sure $$$O(2^{m/2}*m)$$$, but even without memoization the solution passes the System Tests quite confidently.

Note: There is an edge case to look at when marking non-deactivatable colors as false.

Submission: 189735982

phatdapchai

In problem F, in the first solution, why do we need to separate queries into light and heavy? Help, please.

the_Incharge

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

can someone share the n^2 approach for problem C.

eklavya_k

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

n^2 solution: Code

dsu[i] = set no in which ith element belongs, the elements in a set must exist in same state (0 or 1) as they're connected with a[i][j] = 1.
c[i] = position of the nearest index j such that s[i] to s[j] must have at least 2 diff elements
same[i][j] = number of ways elements from i to j would be same
dp[i] = number of binary strings considering only rules till 0 to i
Hopefully, you understand

rutuparn

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

can someone write the time complexity of problem [problem:1767D]D?

arkash707

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

o(n) + log(n), n is max 18 steps. Its only linear since we need to parse the input string, the actual algorithm part is logarithmic.

akshatchaudhary

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

It will be exponential, something of the order $$$O(2^n)$$$, that is the reason, in the constraints we have $$$n \le 18$$$ as $$$2^{18} \approx 2 \times 10^5$$$.

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