Educational Codeforces Round 124 Editorial

#	User	Rating
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	pajenegod	145
9	SecondThread	145

Tutorial

Solution (BledDest)

t = int(input())
for i in range(t):
    n = int(input())
    print(2 ** n - 1)

1651B - Prove Him Wrong

Idea: adedalic

Tutorial

Solution (awoo)

for _ in range(int(input())):
	n = int(input())
	if 3**(n-1) > 10**9:
		print("NO")
	else:
		print("YES")
		print(*[3**x for x in range(n)])

1651C - Fault-tolerant Network

Idea: adedalic

Tutorial

Solution (adedalic)

#include<bits/stdc++.h>

using namespace std;

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

typedef long long li;

const int INF = int(1e9);

int n;
vector<int> a, b;

inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	b.resize(n);
	fore (i, 0, n)
		cin >> b[i];
	return true;
}

int bestCandidate(const vector<int> &vals, int cur) {
	int bst = INF + 10, pos = -1;
	fore (i, 0, n) {
		if (bst > abs(cur - vals[i])) {
			bst = abs(cur - vals[i]);
			pos = i;
		}
	}
	return pos;
}

inline void solve() {
	li bst = 10ll * INF;
	
	vector<int> cds1 = {0, bestCandidate(b, a[0]), n - 1};
	vector<int> cds2 = {0, bestCandidate(b, a[n - 1]), n - 1};
	
	for (int var1 : cds1) {
		for (int var2 : cds2) {
			li ans = (li)abs(a[0] - b[var1]) + abs(a[n - 1] - b[var2]);
			
			if (var1 > 0 && var2 > 0)
				ans += abs(b[0] - a[bestCandidate(a, b[0])]);
			if (var1 < n - 1 && var2 < n - 1)
				ans += abs(b[n - 1] - a[bestCandidate(a, b[n - 1])]);
			
			bst = min(bst, ans);
		}
	}
	cout << bst << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while (t--) {
		read();
		solve();
	}
	return 0;
}

1651D - Nearest Excluded Points

Idea: BledDest

Tutorial

Solution (vovuh)

#include <bits/stdc++.h>

using namespace std;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> a(n);
    for (auto &[x, y] : a) scanf("%d %d", &x, &y);
    
    set<pair<int, int>> st(a.begin(), a.end());
    map<pair<int, int>, pair<int, int>> ans;
    queue<pair<int, int>> q;
    for (auto [x, y] : a) {
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (st.count({nx, ny})) {
                continue;
            }
            ans[{x, y}] = {nx, ny};
            q.push({x, y});
            break;
        }
    }
    
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!st.count({nx, ny}) || ans.count({nx, ny})) {
                continue;
            }
            ans[{nx, ny}] = ans[{x, y}];
            q.push({nx, ny});
        }
    }
    
    for (auto [x, y] : a) {
        auto it = ans[{x, y}];
        printf("%d %d\n", it.first, it.second);
    }
    
    return 0;
}

1651E - Sum of Matchings

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 3043;

vector<int> g[2 * N];
int n;
int used[2 * N];

int choose2(int n)
{
    return n * (n + 1) / 2;
}

int count_ways(int L, int R, const vector<int>& forbidden)
{
    if(L > R)
    {
        int ml = *min_element(forbidden.begin(), forbidden.end());
        int mr = *max_element(forbidden.begin(), forbidden.end());
        return choose2(ml) + choose2(mr - ml - 1) + choose2(n - 1 - mr);
    }
    int minl = 0;
    int maxl = L;
    int minr = R;
    int maxr = n - 1;
    for(auto x : forbidden)
    {
        if(L <= x && x <= R)
            return 0;
        else if(x < L) minl = max(minl, x + 1);
        else maxr = min(maxr, x - 1);
    }                            
    return (maxl - minl + 1) * (maxr - minr + 1);
}

vector<int> cur;

void dfs(int x)
{
    if(used[x] == 1) return;
    used[x] = 1;
    cur.push_back(x);
    for(auto y : g[x]) dfs(y);
}

long long calc(const vector<int>& cycle)
{
    int m = cycle.size();
    int k = m / 2;
    long long ans = 0;
    for(int i = 0; i < m; i++)
    {
        int z = cycle[i];
        if(z >= n) z -= n;
        ans += choose2(n) * 1ll * (choose2(z) + 0ll + choose2(n - z - 1));
        int l = n - 1, r = 0, L = n - 1, R = 0;
        int pl = i, pr = i;
        for(int j = 0; j < k; j++)
        {
            for(auto x : vector<int>({cycle[pl], cycle[pr]}))
            {
                if(x < n)
                {
                    l = min(l, x);
                    r = max(r, x);
                }
                else
                {
                    L = min(L, x - n);
                    R = max(R, x - n);
                }
            }
            vector<int> f, F;
            pl--;
            if(pl < 0) pl += m;
            pr++;
            if(pr >= m) pr -= m;
            for(auto x : vector<int>({cycle[pl], cycle[pr]}))
            {                     
                if(x < n) f.push_back(x);
                else F.push_back(x - n);
            }
            long long add = count_ways(l, r, f) * 1ll * count_ways(L, R, F);
            ans += add;
        }
    }
    return ans;       
}

int main()
{
    cin >> n;
    for(int i = 0; i < 2 * n; i++)
    {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    long long ans = n * 1ll * choose2(n) * 1ll * choose2(n) * 2ll;
    for(int i = 0; i < n; i++)
    {
        if(used[i]) continue;
        dfs(i);
        vector<int> cycle = cur;
        ans -= calc(cycle);
        cur = vector<int>();
    }
    cout << ans / 2 << endl;
}

1651F - Tower Defense

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>

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

using namespace std;

struct node{
	node *l, *r;
	long long sumc, sumr;
	node() : l(NULL), r(NULL), sumc(0), sumr(0) {}
	node(node* l, node* r, long long sumc, long long sumr) : l(l), r(r), sumc(sumc), sumr(sumr) {}
};

node* build(int l, int r, vector<int> &c){
	if (l == r - 1)
		return new node(NULL, NULL, c[l], 0);
	int m = (l + r) / 2;
	node* nw = new node();
	nw->l = build(l, m, c);
	nw->r = build(m, r, c);
	nw->sumc = nw->l->sumc + nw->r->sumc;
	return nw;
}

node* upd(node* v, int l, int r, int pos, int val){
	if (l == r - 1)
		return new node(NULL, NULL, 0, val);
	int m = (l + r) / 2;
	node* nw = new node(v->l, v->r, 0, 0);
	if (pos < m)
		nw->l = upd(v->l, l, m, pos, val);
	else
		nw->r = upd(v->r, m, r, pos, val);
	nw->sumc = nw->l->sumc + nw->r->sumc;
	nw->sumr = nw->l->sumr + nw->r->sumr;
	return nw;
}

long long getsum(node *v, int mult){
	return v->sumc + v->sumr * mult;
}

int trav(node *v, int l, int r, int L, int R, long long &lft, int mult){
	if (L >= R){
		return 0;
	}
	if (l == L && r == R && lft - getsum(v, mult) >= 0){
		lft -= getsum(v, mult);
		return r - l;
	}
	if (l == r - 1){
		return 0;
	}
	int m = (l + r) / 2;
	int cnt = trav(v->l, l, m, L, min(m, R), lft, mult);
	if (cnt == max(0, min(m, R) - L))
		cnt += trav(v->r, m, r, max(m, L), R, lft, mult);
	return cnt;
}

struct seg{
	int l, r, lst, cur;
};

int main() {
	int n;
	scanf("%d", &n);
	vector<int> c(n), r(n);
	forn(i, n) scanf("%d%d", &c[i], &r[i]);
	
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int x, int y){
		return c[x] / r[x] > c[y] / r[y];
	});
	vector<int> vals;
	for (int i : ord) vals.push_back(c[i] / r[i]);
	
	vector<node*> root(1, build(0, n, c));
	for (int i : ord)
		root.push_back(upd(root.back(), 0, n, i, r[i]));
	
	vector<seg> st;
	for (int i = n - 1; i >= 0; --i)
		st.push_back({i, i + 1, 0, c[i]});
	
	long long ans = 0;
	int q;
	scanf("%d", &q);
	forn(_, q){
		int t;
		long long h;
		scanf("%d%lld", &t, &h);
		while (!st.empty()){
			auto it = st.back();
			st.pop_back();
			if (it.r - it.l == 1){
				it.cur = min((long long)c[it.l], it.cur + (t - it.lst) * 1ll * r[it.l]);
				if (it.cur <= h){
					h -= it.cur;
				}
				else{
					st.push_back({it.l, it.r, t, int(it.cur - h)});
					h = 0;
				}
			}
			else{
				int mx = vals.rend() - lower_bound(vals.rbegin(), vals.rend(), t - it.lst);
				int res = it.l + trav(root[mx], 0, n, it.l, it.r, h, t - it.lst);
				assert(res <= it.r);
				if (res != it.r){
					if (it.r - res > 1)
						st.push_back({res + 1, it.r, it.lst, 0});
					int nw = min((long long)c[res], r[res] * 1ll * (t - it.lst));
					assert(nw - h > 0);
					st.push_back({res, res + 1, t, int(nw - h)});
					h = 0;
				}
			}
			if (h == 0){
				break;
			}
		}
		if (st.empty()){
			st.push_back({0, n, t, 0});
		}
		else if (st.back().l != 0){
			st.push_back({0, st.back().l, t, 0});
		}
		ans += h;
	}
	
	printf("%lld\n", ans);
	return 0;
}

Comments (28)

Show archived | Write comment?

hunter_of_alts

2 years ago, # |

I am wondering Why I didn't think about BFS on D during contest

→ Reply

Gemini17

2 years ago, # ^ |

+22

I have a strange solution using binary search instead of BFS. Maybe it can help you when you can't think about BFS.

Let us consider the answer is $$$k$$$. The set of points whose distance between $$$(x_i,y_i)$$$ equal $$$k$$$ form a diamond. It's our job to find whether it is "full" with points given in the problem. Diamonds are annoying. We can turn it with $$$45$$$ degree to make it a square. Now we can sort the points in the order $$$x_i+y_i$$$ so every points in the same oblique line, from top left to bottom right, stay together. Then we can calculate the number of consecutive points in the way from bottom left to top right. Using rmq to calculate the smallest one and check whether it is legal, or "full" anyway. Obviously, the answer has monotonicity, so we can use binary search.

The time complexity of this algorithm is also $$$O(n\log{n})$$$.

My solution 149159334

SanweiTreap

Ah, I have a similar solution. However, I didn't think of sorting and used parallel binary search. It's so stupid of me that it's $$$O(n\log ^2 n)$$$ and got FST(MLE) at last because of my shit like code. Thank you for offering me such clear binary search solution! Hope there would be no FST forever:(

redmption

Felt like a complete idiot the moment my eyes fell on "BFS" in the editorial

peek4b00

I am wondering if there is some solution for D of nroot(n) complexity ? I got tle on test 30 because of extra log factor. If anyone did it in O(nroot(n)) ,suggest me your approach?

You can see my solution above. Enumerating the answer instead of binary search, you will get a solution of $$$O(n\sqrt{n})$$$ complexity.

handlecurrentinuse

My $$$O(n \sqrt{n} \log n)$$$ solution https://codeforces.com/contest/1651/submission/149151251 passed the test cases. I use binary search on vectors instead of sets to reduce the constant factor.

code0rdie

Problem C was easy to understand but very punishing implementation.

variety-jones

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

Note that for problem D: Nearest Excluded Points, you need to select the constraints a bit creatively. We basically want to pack as many points as possible in a single box, so you should select co_ord_high as a small value and choose n_high = co_ord_high^2 (or a smaller number). (Remember that we should have at least $$$n$$$ distinct points in the box chosen).

For example, co_ord_high = 6 and n = 36 works.

If you just select the parameters randomly, there's a high chance that you won't find a failing testcase.

BRAINIAC77

Bug in my solution of D?

Iterate over all points, if the answer for this point is yet to found then call function rec(Pi) from this point.

Description of rec(Pi) function:

Case 1: if Pi has any adjacent cell which is not in the input, set it as the answer for Pi and return.

Case 2: if all adjacent cells of Pi is present in the input, call rec function for the adjacent cells if there answers are yet to found. And then choose answer for Pi among the 4 adjacent cells answers(choose the one with shortest Manhattan distance).

code: here

Consider all points in $$$[1,7] \times [1, 7]$$$

Input

A Valid Output

Your Output

If you want to analyze this testcase, compute the Manhattan distance of all points using the valid output, and see which points' Manhattan distance did you not minimize.

meyi

+16

F is too similar with CF453E.

awoo

+20

Oh, so that's how that problem is solved! I remember seeing it ages ago and not being able to come up with the solution.

UZMath

Hi everyone

Luminolic_Black

← Rev. 2 →

In problem F, I understand until the "Then it creates a segment that covers the prefix and possibly a segment of length 1" part. Because monsters take time to go from $$$i$$$ to $$$i+1$$$, surely the visited towers in the prefix won't have equal drain times? Rather the prefix drain time sequence for monster $$$j$$$ would be something like $$$t_j,t_j+1,t_j+2,..., t_j+r_j-1$$$, where $$$r_j$$$ is the farthest tower drained? If it is so, then $$$O(n)$$$ new segments would be created instead, which breaks the complexity? Can someone please explain to me how we would maintain such a thing, or if I misunderstood? Thanks in advance

toniskrijelj

Same question, can someone please explain a little bit more in detail or give some example?

+23

Ok, yeah, I missed one transition in the editorial.

Basically, you can imagine that each monster doesn't visit towers with intervals of one second, but just arrives at each of them at the same time $$$t$$$ following the order of towers. What does that change? For tower $$$2$$$, the time is just shifted down by $$$1$$$. For tower $$$3$$$, it's by $$$2$$$. And so on. Absolute time changed, but relative time differences between monsters remained the same. And that's what matters for the solution.

l.o_o.l

Can anyone help me calculate the time complexity of problem D? I am unable to figure out how the time complexity of the BFS solution in O(n log n).

johnLate

The provided solution uses a map and a set inside the BFS iteration, this is where the $$$\log n$$$ comes from.

It seems the size of the coordinate space requires either using data structures with $$$\log n$$$ access times, or you have to use sorting and/or binary search.

Ohh... missed their complexity.. thanks!!

tizo

In problem D I tried to sort of do this dp/bfs type solution, which didn't work. What I thought is let's say I want to find the answer for some point. This point has 2 types of surrounding points. Either it has a point which is not from the set, then any neighbor point not from the set one will be the answer. Or it only has neighboring points which are from the set. In that case recursively solve the problem and collect the closest points to each of the neighbors and find which one is closest to current one. It passes only the first 8 test cases :( Help is appreciated. Not sure why my logic/implementation is flawed.

https://codeforces.com/contest/1651/submission/149762286

Failing testcase : Ticket 2185

The testcase contains all but one point in $$$[1,4] \times [1,4]$$$

Oh wow this is so cool. Thanks. Edit: Unfortunately, my answer is different but still should be correct as the difference is the same as the expected. Might try to find another test case that fails.

No, it's not correct. Don't go by the highlighted difference, the backend does have a valid checker to handle multiple correct answers.

For example, the highlighted difference tells you that 6th, 8th, 12th and 14th numbers differ.

Now, if you look at the 8th point, which is $$$(3,3)$$$, the jury's answer prints $$$(3,5)$$$ which has a Manhattan distance of 2. However, your answer prints $$$(0,3)$$$ which has a Manhattan distance of 3.

Oh, my bad. I tried comparing the distance and I guess I miscalculated. Thanks a lot for your help. This tool is really cool.

sgweo8ys

Problem F can be solved simply by chunking in $$$O(n\sqrt n)$$$

My solution

Yaria

D is interesting! I want to add one more thing: the time complexity of a normal BFS implementation for a graph with N vertices and M edges is O(M), but here in the graph each vertex is connected to 4 neighbors so M <= 4*N. So the time complexity is indeed O(N*log(N)).

awoo's blog