Разбор Educational Codeforces Round 55

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

Разбор

Решение (Ajosteen)

#include <bits/stdc++.h>

using namespace std;

const int INF = int(2e9) + 99;

int n, x, y, d;

int dist(int x, int y){
	return (abs(x - y) + (d - 1)) / d;
}

int main() {
	
	int t;
	cin >> t;
	for(int i = 0; i < t; ++i){
    	cin >> n >> x >> y >> d;
    	
    	int len = abs(x - y);
    	int res = INF;
    	
    	if(len % d == 0) 
    		res = min(res, dist(x, y));
    	
    	len = y - 1;
    	if(len % d == 0)
    		res = min(res, dist(x, 1) + dist(1, y));
    	
    	len = n - y;
    	if(len % d == 0)
    		res = min(res, dist(x, n) + dist(n, y));
    		
    	if(res == INF)
    		res = -1;
    	
    	cout << res << endl;
	}
	
	return 0;
}

1082B - Вова и кубки

Разбор

Решение (Ajosteen)

#include <bits/stdc++.h>

using namespace std;

int n;
string s;

int main() {
	
	cin >> n >> s;
	
	vector <int> l(n), r(n);
	for(int i = 0; i < n; ++i){
		if(s[i] == 'G'){
			l[i] = 1;
			if(i > 0) l[i] += l[i - 1];
		}
	}
	for(int i = n - 1; i >= 0; --i){
		if(s[i] == 'G'){
			r[i] = 1;
			if(i + 1 < n) r[i] += r[i + 1];
		}
	}
	
	
	int res = 0;
	int cntG = 0;
	for(int i = 0; i < n; ++i)
			cntG += s[i] == 'G';
			
	for(int i = 0; i < n; ++i){
		if(s[i] == 'G') continue;
		int nres = 1;
		if(i > 0) nres += l[i - 1];
		if(i + 1 < n) nres += r[i + 1];
		res = max(res, nres);
	}
	
	res = min(res, cntG);
	if(cntG == n) res = cntG;
	cout << res << endl;
	return 0;
}

1082C - Мультипредметная олимпиада

Разбор

Решение (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())

int n, m;
vector<int> s, r;

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	s.assign(n, 0);
	r.assign(n, 0);
	
	fore(i, 0, n) {
		assert(cin >> s[i] >> r[i]);
		s[i]--;
	}
	return true;
}

vector< vector<int> > subs;

inline void solve() {
	subs.assign(m + 1, vector<int>());
	
	fore(i, 0, n)
		subs[s[i]].push_back(r[i]);
		
	fore(id, 0, sz(subs)) {
		sort(subs[id].begin(), subs[id].end());
		reverse(subs[id].begin(), subs[id].end());
	}
	
	vector<int> mx(n + 5, 0);
	fore(id, 0, sz(subs)) {
		int curSum = 0;
		fore(i, 0, sz(subs[id])) {
			curSum += subs[id][i];
			if(curSum < 0)
				break;
				
			mx[i + 1] += curSum;
		}
	}
	
	cout << *max_element(mx.begin(), mx.end()) << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

1082D - Граф максимального диаметра

Разбор

Решение (PikMike)

#include <bits/stdc++.h>

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

using namespace std;

const int N = 1000 + 7;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n)
		scanf("%d", &a[i]);
	
	int sum = 0;
	forn(i, n)
		sum += a[i];
	
	if (sum < 2 * n - 2){
		puts("NO");
		return 0;
	}
	
	vector<int> ones;
	forn(i, n) if (a[i] == 1){
		a[i] = 0;
		ones.push_back(i);
	}
	
	int t = ones.size();
	int dm = (n - t) - 1 + min(2, t);
	printf("YES %d\n%d\n", dm, n - 1);
	
	int lst = -1;
	if (!ones.empty()){
		lst = ones.back();
		ones.pop_back();
	}
	
	forn(i, n){
		if (a[i] > 1){
			if (lst != -1){
				--a[lst];
				--a[i];
				printf("%d %d\n", lst + 1, i + 1);
			}
			lst = i;
		}
	}
	
	for (int i = n - 1; i >= 0; --i){
		while (!ones.empty() && a[i] > 0){
			--a[i];
			printf("%d %d\n", i + 1, ones.back() + 1);
			ones.pop_back();
		}
	}
	return 0;
}

1082E - Увеличение частоты

Разбор

Решение (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())

const int INF = int(1e9);

int n, c;
vector<int> a;

inline bool read() {
	if(!(cin >> n >> c))
		return false;
	a.assign(n, 0);
	fore(i, 0, n)
		assert(scanf("%d", &a[i]) == 1);
	return true;
}

vector<int> cntC;

int getCnt(int l, int r) {
	return cntC[r] - cntC[l];
}

vector< vector<int> > segs;
vector<int> lst;

int maxSegment(const vector<int> &s) {
	int mx = -INF;
	
	int bal = 0;
	fore(i, 0, sz(s)) {
		bal = max(0, bal + s[i]);
		mx = max(mx, bal);
	}
	return mx;
}

inline void solve() {
	cntC.assign(n + 1, 0);
	fore(i, 0, n)
		cntC[i + 1] = cntC[i] + (a[i] == c);
	
	int cntDif = *max_element(a.begin(), a.end()) + 1;
	segs.assign(cntDif, vector<int>());
	lst.assign(cntDif, -1);
	
	fore(i, 0, n) {
		segs[a[i]].push_back(-getCnt(lst[a[i]] + 1, i));
		lst[a[i]] = i;
		segs[a[i]].push_back(1);
	}
	fore(v, 0, cntDif)
		segs[v].push_back(-getCnt(lst[v] + 1, n));
		
	int ans = 0;
	fore(v, 0, cntDif) {
		if(v == c) continue;
		ans = max(ans, maxSegment(segs[v]));
	}
	
	cout << getCnt(0, n) + ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

1082F - Быстрый набор

Разбор

Решение (PikMike)

#include <bits/stdc++.h>

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

using namespace std;

const int N = 500 + 7;
const int M = 11;
const int INF = 1e9;

struct node{
	int nxt[10];
	int cnt;
	node(){
		memset(nxt, -1, sizeof(nxt));
		cnt = 0;
	}
};

node trie[N];
int cnt;
int h[N];

void add(string s, int m){
	int cur = 0;
	forn(i, s.size()){
		int c = s[i] - '0';
		if (trie[cur].nxt[c] == -1){
			trie[cur].nxt[c] = cnt;
			h[cnt] = h[cur] + 1;
			++cnt;
		}
		cur = trie[cur].nxt[c];
	}
	trie[cur].cnt += m;
}

int n, k;

int dp[N][M][N];
int dp2[N][M][N][M];

int calc(int x, int rem, int k){
	if (dp[x][rem][k] != -1)
		return dp[x][rem][k];
	
	vector<int> ch;
	forn(i, 10) if (trie[x].nxt[i] != -1)
		ch.push_back(trie[x].nxt[i]);
	
	dp[x][rem][k] = INF;
	if (rem > 0)
		dp[x][rem][k] = min(dp[x][rem][k], calc(x, rem - 1, x));
	
	dp2[x][rem][k][ch.size()] = 0;
	for (int i = int(ch.size()) - 1; i >= 0; --i) forn(z, rem + 1)
		dp2[x][rem][k][i] = min(dp2[x][rem][k][i], calc(ch[i], z, k) + dp2[x][rem - z][k][i + 1]);
	
	dp[x][rem][k] = min(dp[x][rem][k], dp2[x][rem][k][0] + (h[x] - h[k]) * trie[x].cnt);
	
	return dp[x][rem][k];
}

int main() {
	trie[0] = node();
	cnt = 1;
	
	cin >> n >> k;
	forn(i, n){
		string s;
		int m;
		cin >> s >> m;
		add(s, m);
	}
	
	memset(dp, -1, sizeof(dp));
	
	forn(i, N) forn(j, M) forn(l, N) forn(t, M)
		dp2[i][j][l][t] = INF;
	
	int ans = calc(0, k, 0);
	
	cout << ans << endl;
	return 0;
}

1082G - Петя и граф

Разбор

Решение (Ajosteen)

#include <bits/stdc++.h>

using namespace std;

typedef long long li;

const int N = 2009;
const int INF = int(1e9) + 777;

struct edge{
	int to, f, c;
	edge () {}
	edge (int to, int f, int c) : to(to), f(f), c(c) {}
};

int n, m;
int s, t;
vector<edge> edges;
vector <int> g[N];
int u[N], cu;

void addEdge(int v, int to, int cap){

	g[v].push_back(edges.size());
	edges.push_back(edge(to, 0, cap));

	g[to].push_back(edges.size());
	edges.push_back(edge(v, 0, 0));
}

int dfs(int v, int need){
	if(v == t) return need;
	u[v] = cu;
	for(auto to : g[v]){
		edge &e = edges[to];
		if(u[e.to] != cu && e.c - e.f >= need){
			int add = dfs(e.to, need);
			if(add > 0){
				edges[to].f += add;
				edges[to ^ 1].f -= add;
				return add;
			}
		}
	}
	return 0;
}

li enlarge(int k){
	li res = 0;
	while(true){
		++cu;
		int add = dfs(s, k);
		res += add;
		if(add == 0) break;
	}
	return res;
}

li maxFlow(){
	li flow = 0;
	for(int k = (1 << 29); k > 0; k >>= 1){
		flow += enlarge(k);
	}
	return flow;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int nn, mm;
	cin >> nn >> mm;
	n = nn + mm + 5;
	m = nn + mm + mm + mm + 5;
	s = n - 1, t = n - 2;
	
	for(int i = 0; i < nn; ++i){
		int a;
		cin >> a;
		addEdge(i + mm, t, a);
	}

	li sum = 0;
	for(int i = 0; i < mm; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		sum += w;
		
		addEdge(s, i, w);
		addEdge(i, u + mm, INF);
		addEdge(i, v + mm, INF);
	}
	
	li fl = maxFlow();
	cout << sum - fl << endl;
	
	return 0;
}

_, string = raw_input(), raw_input() start, end, res = 0, 0, 0 for char in string: if char == "G": start += 1 else: end, start = start, 0 res = max(res, start + end + 1) print min(res, string.count("G"))

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

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

alessandrosolbiati

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

-17

python 6-lines AC solution to problem B

https://mirror.codeforces.com/blog/entry/60059 for more

→ Ответить

mangat

How to solve E

RobeZH

← Rev. 2 →

For problem E, I came up with an elegant (at least I thought during contest) O(nlogn) divide-and-conquer solution. I am just surprised to see the so easy linear solution after contest...

kumarpratyush4

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

could you explain your solution please?

denkora

In problem D, why do we have to loop from the end of the array at the end of algorithm?

I tried forward loop but gives WA on test 18... it seems that it doesn't construct tree well.

limabeans

+1. having the same issue

So I just thought about it. The reason why the for loop needs to be done in reverse is because there is a chance that the very last node in the bamboo tree needs a "one" node to satisfy the diameter requirement that was previously calculated.

Consider this test case

5
1 3 2 2 1

If you have both the bamboo construction for loop and the "ones add-on" for loop both go forwards, we'll add both one nodes to vertex 2 and never get the chance to append a one node to vertex 4 -- this would be required to make the diameter of the constructed graph 4, which would be the max.

Now I got it, for the construction of the bamboo we go forward and but then we must go backward to use all the remaining edges.

ghoshsai5000

Hello friends,

Here is my solution to problem E. The pedagogy is quite different from the one in the editorial and it might be helpful. :)

rdd6584

My problem E solution is super simple.

It might me helpful for you.

https://mirror.codeforces.com/contest/1082/submission/46421135

vatsal

Can you explain it?

In one word, It is like a parallel two pointer for every number.

For every 'i', you need to change left of some numbers that count(left, i, X) < count(left, i, C), to 'i'. But you don't need to immediately calculate it for every number. Because count(i, i, vec[i]) is always 1.

Sorry for my bad English.

Sturdy

No issues with your english but I couldn't get you

DeepWorm

Neighter do I. And it's really simple.

afrizal

-9

Especially this part. Can elaborate more?

Because count(i, i, vec[i]) is always 1.

← Rev. 5 →

If count(left, i, x) < count(left, i, c), we should change left to i. Then, its count is maybe 0. But We know answer always exist on some events increasing count about x. So, we don't have to change lefts immediatly. Therefore, If count(left, i, vec[i]) > count(left, i, c), we use it as it is. But else, we use it be changed about left. We can easily know we have to change left to i, and count(left, i, vec[i]) will be 1.

Don't forget all x have different left.

HelloWorld

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

I will explain how I understood his code.
Let's define an array $$$num$$$, where $$$num$$$_{$$$a_i$$$} is maximum length of a subsequence like this:
$$$c, c, \dots, c, a_i, \dots, a_i, a_i.$$$ This is the subsequence of first i elements of array $$$a$$$.
So, how to calculate this array $$$num$$$?
$$$if$$$ $$$a_i=c$$$ we do nothing
$$$else$$$ $$$num$$$_{$$$a_i$$$} $$$ = $$$ $$$max($$$ $$$pref$$$_$$$i$$$ $$$,$$$ $$$num$$$ _{$$$a_i$$$} $$$)+1$$$ This way we are either $$$1)$$$ starting a new sequence by appending $$$a_i$$$ to the sequence of $$$c$$$. or $$$2)$$$ extending $$$c, c, \dots, c, a_i, \dots, a_i, a_i.$$$ by appendind $$$a_i$$$ to the end.
How does it help?
Let $$$pref$$$_$$$i$$$ be number of $$$c$$$ in the prefix of array $$$a$$$. Say, we are at an index $$$i$$$. When we subtract $$$pref$$$_$$$i$$$ from $$$num$$$_{$$$a_i$$$}, we get $$$cnt(l,i,a_i) - cnt(l,i,c)$$$ where $$$l$$$ is the index of first $$$a_i$$$ in the above sequence. Now, we iterate through all $$$i$$$ and find the maximum of $$$cnt(l,i,a_i) - cnt(l,i,c)$$$.
Finally we add this value to $$$pref$$$_$$$n$$$ which is our answer.
Note: $$$cnt$$$ is the same as defined in the editorial.

Fatoom

Could someone explain why we need this line in problem B, res = min(res, cntG); Thanks.

WingsWings

int nres = 1;

we considered 'S' as 'G' to combine 'G' in the two sides, trying to get the longest subsegment.

For examble:

input

4 SGGG

Before res = min(res, cntG);, res = 4. It's an wrong answer.

vivek_shah

Update :- Got it :)

zsnapdragonz

In problem D, I was wrong in test 18. The vecdict is "Given diameter is incorrect 388 389", but in my output the diameter is 389? Anyone tell me why? Thanks so muck

Kelly

The checker checks the diameter of your graph using your adjacency list, not just the diameter your output after "YES".

tantam75

Here is my idea of E:

We have a naive solution: consider each segment [l, r], get the maximum appearance of a number in the segment, assume it is x, then update result with cnt(1, l - 1, c) + x + cnt(r + 1, n, c), where cnt(l, r, j) is number of apperance of j in segment [l, r].

In the solution above, for each segment [l, r], we choose the number with highest appearance and then change to c. But in fact, we can greedy change all the elements equal a_r in segment [l, r]. Proof: If we choose the number with highest appearance, assume it is y, and y ≠ a_r, then we can get better result if we choose segment [l, r'], where r' < r, cnt(r' + 1, r, y) = 0, y = a_r', because cnt(r' + 1, n, c) ≥ cnt(r + 1, n, c) and cnt(l, r', y) = cnt(l, r, y), so cnt(1, l - 1, c) + cnt(l, r, y) + cnt(r + 1, n, c) ≤ cnt(1, l - 1, c) + cnt(l, r', y) + cnt(r + 1, n, c).

So at the position i, let f_{a_i} be the most number of c in segment [1, i] if you change all the elements equal a_i to c in some segment [l, i]. Then: f_{a_i} = max(f_{a_i} + 1, cnt(1, i - 1, c) + 1). We update result with f_{a_i} + cnt(i + 1, n, c).

My submission: 46365450

I like this one. GJ

bjn

You saved my day

resonbility

I understand that all a[i] in (l,r) can change to a[r] but : why calculate cnt( 1,i ,d ) only not cnt(1,l-1,c) and cnt(l,r,d)

sorry for my poor English....

At position i, f_{a_i} is the maximum c we can get if we change all number equal a_i in some segment [l, i] to c. That means there is a segment [l, i] which the sum cnt(1, l - 1, c) + cnt(l, i, a_i) is maximum and we suppose this sum equal f_{a_i}. So we update result with cnt(1, l - 1, c) + cnt(l, i, a_i) + cnt(i + 1, n, c) = f_{a_i} + cnt(i + 1, n, c).

What a wonderful solution!!!!

Why you can prove that it's optimal to change the elements equal a_r in [l, r]? The proof seems to have only proved that changing a_r' is better than changing a_r. Could you please explain it in more detail?

I mean that changing all numbers equal a_r' = y to c in segment [l, r'] is better than changing all number equals y (which have the most apperance) in segment [l, r].

Got it! Thanks very much! : )

stupidaftowin

i used binary search to solve B

i used binary search for problem B

Ealham

Would you explain a bit how you used Binary Search?

46471253

here it is.

utkarshahuja1

Can anybody tell me why my code for problem C is giving WA?

The link to my code : https://mirror.codeforces.com/contest/1082/submission/46672149

adedalic

Your solution gives wrong answer on test like:

2 2
1 1
2 -1

Thanks man.

What should be the output of this?

It should be 1

mblazev

This editorial isn't linked from problems but only from the announcement so it's a bit harder to find.

awoo

Oops, sorry, now it's linked.

am1tbh47

In explanation to Problem G:

"if a project-vertex belongs to S, then we take this project; if an instrument-vertex belongs to S, then we take this instrument; all other projects and instruments are discarded..If an edge between some project and some instrument is cut, then it means that the answer is incorrect (we try to take a project requiring some instrument we don't take), and the cut value is infinite. Otherwise, the value of the cut is equal to the total cost of taken instruments and discarded projects, and we need to minimize it."

I didn't get what this means. Once we determine Minimum cut from the graph, it says discard all projects and instruments that are not part of the cut. But then it also states value of the cut is equal to total cost of instruments and discarded projects.
Also, how can the cut value be infinite if all edges from source to projects have finite capacity and all edges from instruments to sink have finite capacity?

Can someone please explained with an example or in a simpler way. Thanks.

DrSamosa

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

I am currently failing test 11 for prob D. This is my solution https://mirror.codeforces.com/contest/1082/submission/80575032. Can anyone please tell me what is wrong with it?

Khaled_Mardini

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

tgp07

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

I know this post is really really old, but I wanted to share my solve for E. Altho it's far less elegant, it AC's and I don't think anyone else has mentioned it.

Basically, we'll let dp[i] be max # of c's we can make if we let the chosen segment end at position i. Naturally, dp[i] will also consider the prefix of the array before the segment as well. Once we've computed dp[i], we can simply brute force the suffix and combine it with the appropriate dp value to pick the answer which gives us the most occurrences of c. Let's also precompute ps[i] = (#of occurrences of c before and including position i).

Now I'll go over how to compute dp[i]. Here is an observation. Let's say we're at the ith character and trying to compute dp[i]. Note that the character we should choose to convert in our segment ending at position i is a[i]. This is because if we didn't choose a[i], then we wouldn't even need to extend our segment to position i in the first place. So it makes sense for the segment to convert all the instances of the value of a[i] inside it to c. Also note that it's always better for the segment to start at an instance of a[i]. If it didn't start at an instance of a[i], then we could keep moving it to the right until we hit an instance of a[i] while possibly improving our answer even further. So note that we only need to consider the past instances of a[i] when considering the transitions for dp[i]. Let's create a map M such that M[k] will store the maximal value of the following expression: (ps[j-1] + #of instances of k at and after position j), where j is some instance of a[i] to the left. Note that as we iterate i from 1 to n, if we don't see any previous instances of a[i], then dp[i] = 1 + ps[i-1], where the 1 is from a segment starting and ending at position i that converts a[i] to c. We can then update M[a[i]] = 1 + ps[i-1]. Otherwise if a past instance of a[i] has occurred, then we can first increment M[a[i]] by 1. This is b/c we have reached a new instance of a[i] at our current position, so by starting a segment at the optimal position j up to position i, our best answer will be M[a[i]] plus the 1 from converting the value of a[i] at position i to a c. Finally, we can update M[a[i]] by picking the max of its existing value and 1 + ps[i-1]. Set dp[i] equal to this new quantity. Keep doing this process to successfully compute the dp array.

238795645

ashibh

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

Thanks! Was looking for an explanation

smit_384

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

Thank you for explaining.

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