Разбор Educational Codeforces Round 43

№	Пользователь	Рейтинг
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

№	Пользователь	Вклад
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

Разбор

Решение (Vovuh)

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int n;
	string s;
	cin >> n >> s;
	if (n == 1) {
		cout << s << endl;
	} else {
		int cnt0 = 0;
		for (int i = 0; i < n; ++i)
			cnt0 += s[i] == '0';
		cout << 1;
		for (int i = 0; i < cnt0; ++i)
			cout << 0;
		cout << endl;
	}
	
	return 0;
}

976B - Лара Крофт и новая игра

Разбор

Решение (PikMike)

#include <bits/stdc++.h>

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

using namespace std;

int n, m;
long long k;

int main() {
	scanf("%d%d%lld", &n, &m, &k);
	if (k < n){
		printf("%lld 1\n", k + 1);
		return 0;
	}
	k -= n;
	long long row = k / (m - 1);
	printf("%lld ", n - row);
	if (row & 1)
		printf("%lld\n", m - k % (m - 1));
	else
		printf("%lld\n", k % (m - 1) + 2);
	return 0;
}

976C - Вложенные отрезки

Разбор

Решение (PikMike)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second

using namespace std;

typedef pair<int, int> pt;

const int N = 300 * 1000 + 13;

int n;
pair<pt, int> a[N];

int main() {
	scanf("%d", &n);
	forn(i, n){
		scanf("%d%d", &a[i].x.x, &a[i].x.y);
		a[i].y = i + 1;
	}
	
	sort(a, a + n, [&](pair<pt, int> a, pair<pt, int> b){if (a.x.x != b.x.x) return a.x.x < b.x.x; return a.x.y > b.x.y;});
	
	set<pt> cur;
	forn(i, n){
		while (!cur.empty() && cur.begin()->x < a[i].x.x)
			cur.erase(cur.begin());
		if (!cur.empty() && (--cur.end())->x >= a[i].x.y){
			printf("%d %d\n", a[i].y, (--cur.end())->y);
			return 0;
		}
		cur.insert({a[i].x.y, a[i].y});
	}
	
	puts("-1 -1");
	return 0;
}

976D - Множество степеней

Разбор

Решение (PikMike)

#include <bits/stdc++.h>

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

using namespace std;

typedef pair<int, int> pt;

const int N = 100 * 1000 + 13;

int n;
vector<int> d;
vector<int> g[N];

vector<pt> construct(int st, vector<int> d){
	if (d.empty())
		return vector<pt>();
	
	vector<pt> res;
	forn(i, d[0])
		for (int j = st + i + 1; j <= st + d.back(); ++j)
			res.push_back({st + i, j});
	
	int nxt = st + d[0];
	for (int i = 1; i < int(d.size()); ++i)
		d[i] -= d[0];
	d.erase(d.begin());
	if (!d.empty())
		d.pop_back();
	
	auto tmp = construct(nxt, d);
	for (auto it : tmp)
		res.push_back(it);
	
	return res;
}

int main() {
	scanf("%d", &n);
	d.resize(n);
	forn(i, n)
		scanf("%d", &d[i]);
	auto res = construct(0, d);
	printf("%d\n", int(res.size()));
	for (auto it : res)
		printf("%d %d\n", it.first + 1, it.second + 1);
	return 0;
}

976E - Неплохо сыграно!

Разбор

Решение (Ajosteen)

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 9;

int n, a, b;
int hp[N], dmg[N];

bool cmp(int i, int j){
	if(hp[i] - dmg[i] != hp[j] - dmg[j])
		return hp[i] - dmg[i] > hp[j] - dmg[j];
	return i < j;
}

int get(int id){
	return  hp[id] > dmg[id]? hp[id] : dmg[id];
}

int main(){
	scanf("%d %d %d", &n, &a, &b);
	for(int i = 0; i < n; ++i)
		scanf("%d %d", hp + i, dmg + i);
	
	b = min(b, n);
	vector <int> p(n);
	for(int i = 0; i < n; ++i) p[i] = i;
	sort(p.begin(), p.end(), cmp);
	long long res = 0, sum = 0;
	for(int i = 0; i < n; ++i){
		int id = p[i];
		if(i < b) sum += get(id);
		else sum += dmg[id];
	}
	res = sum; 

	if(b == 0){
		printf("%lld\n", res);
		return 0;
	}
	
	long long x = (1LL << a);
	for(int i = 0; i < n; ++i){
		int id = p[i];
		long long nres = sum;
		if(i < b){ 
			nres -= get(id);
			nres += hp[id] * x;
			res = max(res, nres);
		}
		else{
			nres -= dmg[id];
			nres += hp[id] * x;			
			int id2 = p[b - 1];
			nres -= get(id2);
			nres += dmg[id2];
			res = max(res, nres);
			
		}		
	}
	
	printf("%lld\n", res);
	return 0;
}

976F - Минимальное k-покрытие

Разбор

Решение (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define sz(a) int((a).size())
#define x first
#define y second

const int INF = int(1e9);
const int N = 4221;

struct edge {
    int to, c, f, id;

    edge(int to = 0, int c = 0, int f = 0, int id = -1) : to(to), c(c), f(f), id(id) {}
};

vector<edge> es;
vector<int> g[N];

void add_edge(int fr, int to, int cap, int id) {
    g[fr].push_back(sz(es));
    es.emplace_back(to, cap, 0, id);
    g[to].push_back(sz(es));
    es.emplace_back(fr, 0, 0, id);
}

int pw[N];
int n1, n2, m;

inline bool read() {
    if(!(cin >> n1 >> n2 >> m))
        return false;

    fore(id, 0, m) {
        int u, v;
        assert(cin >> u >> v);
        u--, v--;

        pw[u]++;
        pw[n1 + v]++;

        add_edge(u, n1 + v, 1, id);
    }
    return true;
}

int d[N], q[N], hd, tl;
inline bool bfs(int s, int t, int n) {
    fore(i, 0, n)
        d[i] = INF;
    hd = tl = 0;

    d[s] = 0;
    q[tl++] = s;
    while(hd != tl) {
        int v = q[hd++];
        if(v == t)
            break;

        for(int id : g[v]) {
            if(es[id].c - es[id].f == 0)
                continue;

            int to = es[id].to;
            if(d[to] > d[v] + 1) {
                d[to] = d[v] + 1;
                q[tl++] = to;
            }
        }
    }
    return d[t] < INF;
}

int nxt[N];

int dfs(int v, int t, int mx) {
    if(v == t) return mx;
    if(mx == 0) return 0;

    int sum = 0;
    for(; nxt[v] < sz(g[v]); nxt[v]++) {
        int id = g[v][nxt[v]];
        int rem = es[id].c - es[id].f;
        int to = es[id].to;

        if(rem == 0 || d[to] != d[v] + 1)
            continue;

        int cur = 0;
        if((cur = dfs(to, t, min(mx - sum, rem))) > 0) {
            es[id].f += cur;
            es[id ^ 1].f -= cur;
            sum += cur;
        }

        if(sum == mx)
            break;
    }
    return sum;
}

inline int dinic(int s, int t, int n) {
    int mf = 0;
    while(bfs(s, t, n)) {
        fore(i, 0, n)
            nxt[i] = 0;

        int cf = 0;
        while((cf = dfs(s, t, INF)) > 0)
            mf += cf;
    }
    return mf;
}

vector<int> res[N];

inline void getCert(int k) {
    fore(v, 0, n1) {
        for(int id : g[v]) {
            if(es[id].to < n1 || es[id].to >= n1 + n2)
                continue;
            assert(es[id].c > 0);
            if(es[id].f > 0)
                continue;

            res[k].push_back(es[id].id);
        }
    }
}

void solve() {
    int cnt = *min_element(pw, pw + n1 + n2);

    int s = n1 + n2; int t = s + 1;
    fore(i, 0, n1)
        add_edge(s, i, pw[i] - cnt, -1);
    fore(i, n1, n1 + n2)
        add_edge(i, t, pw[i] - cnt, -1);

    int mf = 0, mn = cnt;
    while(mn >= 0) {
        mf += dinic(s, t, n1 + n2 + 2);
        getCert(mn);

        if(mn > 0) {
            for (int id : g[s]) {
                assert(es[id].id < 0);
                assert((id & 1) == 0);
                es[id].c++;
            }
            for (int id : g[t]) {
                assert(es[id].id < 0);
                assert(es[id].c == 0);
                es[id ^ 1].c++;
            }
        }
        mn--;
    }

    fore(i, 0, cnt + 1) {
        printf("%d ", sz(res[i]));
        for(int id : res[i])
            printf("%d ", id + 1);
        puts("");
    }
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
#endif

    if(read()) {
        solve();
    }
    return 0;
}

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

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

Exctues

7 лет назад, # |

Исправьте пожалуйста описание разбора к B

→ Ответить

priyatam_sai

An nlogn solution itself gave tle for me in C.nested segments question using c++ default sort function, is there any one like this.

http://codeforces.net/contest/976/submission/37770261

YogayogayoG

7 лет назад, # ^ |

It is your cmpr function.

but exactly why it created problem??

clearlove20

it can't make rgt in increasing order

DebSourav33

I am confused too.. what's the problem here? :/ I have submitted very much the same solution as yours and I have got Correct Answer!

http://codeforces.net/contest/976/submission/37790630

See this

Vasiljko

Never use equal sign in compare function

spectaclehong

← Rev. 2 →

+13

you must use <,> operator with compare function,not <=,>=. because it can occur cycle in stl sorting.

mouse_wireless

When in doubt, read language specifications.

Here is the documentation for sort. You can see that the 3rd argument needs to define a strict weak ordering. You can read about the mathematical concept, or you can go directly to the cpprefence of Compare.

JayZhan

976D — Degree Set ,Graph for some (d1, d2, ..., dk) need to be sorted?

awoo

+17

What do you mean by "sorted"? My checker takes the list of edges you output and calculates the degree set to compare it with the given one.

prudent

problem B

can You please explain why we don't consider the case, when we do -1 to k, by decreasing height of our final answer?

We transition from the number of steps Lara made to the number of cells she visited. You can see that she visits (m - 1) cells of the bottom row, then (m - 1) cells of the row above it and so on. And the formula tells you which one of these cells was the (k - n)-th.

Jakube

Alternative solution for F: For a fixed degree d connect a new source vertex s with each vertex of U with capacity ∞ and demand d, and connect every vertex of V with capacity ∞ and demand d to a new sink vertex t. And then find the minimal flow as described in the e-maxx-eng article Flow with demands (add two more vertices to get rid of the demands, and do a binary search on the minimal flow value).

This has a worse complexity than the editorial solution (due to the binary search and a slightly bigger network), but my implementation 37840246 still runs in under 1 second using Edmond-Karp.

bluejay

Is anyone getting WA on test case 10 of E well played :| http://codeforces.net/contest/976/submission/37842203 here is my submission

nader

Same here: http://codeforces.net/contest/976/submission/37768647

Bch

I getted too, you are wrong because you are trying to maximize hp[i] * 2^a — dmg[i], but its not correct. For example you have got hp[i] * 2^a — dmg[i] > hp[j] * 2^a — dmg[j], but dmg[i] + hp[j] * 2^a — dmg[j] can be larger then dmg[j] + hp[i] * 2^a — dmg[i] and you should use your a spells on j but not i.

OptxPrime

How is solution for E nlogn? If we precalc powers of two it is O(n) isnt it?

You need to sort your array complexity of sorting — nlogn.

Wow...wrote same solution after contest but now I forgot you need to sort hahaha

Changed >= to > om sort, and from Runtime error in test 84 got accepted.. Can someone explain why?

neverwin

see this http://codeforces.net/blog/entry/59163?#comment-427659

ekolodin

6 лет назад, # |

Можно поподробнее разбор задачи D -- а то что-то вообще не понятно, откуда это все получается: "Граф для некоторого (d1, d2, ..., dk) можно получить из графа (d2 - d1, d3 - d1, ..., dk - 1 - d1) добавлением (dk - dk - 1) вершины, изначально не соединенной ни с чем, и d1 вершины, соединенной со всеми вершинами, объявленными ранее." Как "вершина, соединенная со всеми вершинами, объявленными ранее." может иметь степень d1, она будет иметь степень k — 1. И как "Вершины, не соединенные ни с чем, получат степень d1", если вершины не соединенные ни с чем имеют степень 0???

bekzhan29

6 лет назад, # ^ |

"Вершины, не соединенные ни с чем, получат степень d1", так как у нас есть d1 вершин которые соединены со всеми, значит вершины которые якобы ни с кем не соединены получат степень d1 ведь они соединены с теми вершинами.

arvindr9

Can you please add a link to this editorial that is accessible from the contest? I cannot access the editorial from here.

Done

straw__hat

← Rev. 8 →

Why is this wrong for question no. D?

Input
3
2 3 4
Participant's output
6
1 2
1 3
1 4
1 5
2 3
2 4

memezAreDreamz

Degree of vertex 5 in your graph is 1 whereas the given degree set is {2, 3, 4}

ghostkkk

In problem F, why is the complexity O((n + m)2) ?

LanaDelRey

5 лет назад, # |

how to calculate dinic's complexity in problem F?why not n*n*m?

abhishekjoshi2612

ME:making 100 of test cases for B problem codeforces: a single formula for all the cases ME: pikachu face INNER ME: crying

beginner1010

I do not understand the correctness of proof of problem D. How do we know that there is a solution for the sub-problem $$$(d_2 - d_1, d_3 - d_1, \cdots, d_{k - 1} - d_1)$$$. awoo Could you please help me with it?

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