Codeforces Round #494 (Div. 3) Editorial

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	158
2	adamant	152
3	Um_nik	146
4	Dominater069	144
5	errorgorn	141
6	cry	139
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

Tutorial

Solution (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;
	cin >> n;
	
	vector<int> cnt(101);
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[x];
	}
	
	cout << *max_element(cnt.begin(), cnt.end()) << endl;
	
	return 0;
}

1003B - Binary String Constructing

Tutorial

Solution (Vovuh)

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int a, b, x;
	cin >> a >> b >> x;
	
	if (x % 2 == 0) {
		if (a > b) {
			for (int i = 0; i < x / 2; ++i)
				cout << "01";
			cout << string(b - x / 2, '1');
			cout << string(a - x / 2, '0');
		} else {
			for (int i = 0; i < x / 2; ++i)
				cout << "10";
			cout << string(a - x / 2, '0');
			cout << string(b - x / 2, '1');
		}
	} else if (a > b) {
		for (int i = 0; i < x / 2; ++i)
			cout << "01";
		cout << string(a - x / 2, '0');
		cout << string(b - x / 2, '1');
	} else {
		for (int i = 0; i < x / 2; ++i)
			cout << "10";
		cout << string(b - x / 2, '1');
		cout << string(a - x / 2, '0');
	}
	cout << endl;
	
	return 0;
}

1003C - Intense Heat

Tutorial

Solution (PikMike)

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++) 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(2e9);
const li INF64 = li(1e18);
const int MOD = INF + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 10000 + 7;

int n, k;
int a[N];

bool read () {
	if (scanf("%d%d", &n, &k) != 2)
		return false;
	forn(i, n) scanf("%d", &a[i]);
	return true;
}

int pr[N];

void solve() {
	pr[0] = 0;
	forn(i, n) pr[i + 1] = pr[i] + a[i];
	
	ld ans = 0;
	forn(r, n) forn(l, r + 1){
		if (r - l + 1 >= k){
			ans = max(ans, (pr[r + 1] - pr[l]) / ld(r - l + 1));
		}
	}
	
	printf("%.15f\n", double(ans));
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int tt = clock();
	
#endif
	
	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;

	while(read()) {	
		solve();
		
#ifdef _DEBUG
	cerr << "TIME = " << clock() - tt << endl;
	tt = clock();
#endif

	}
}

1003D - Coins and Queries

Tutorial

Solution (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, q;
	cin >> n >> q;
	
	vector<int> cnt(31);
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[__builtin_ctz(x)];
	}
	
	while (q--) {
		int x;
		cin >> x;
		
		int ans = 0;
		for (int i = 30; i >= 0 && x > 0; --i) {
			int need = min(x >> i, cnt[i]);
			ans += need;
			x -= (1 << i) * need;
		}
		
		if (x > 0)
			ans = -1;
		cout << ans << endl;
	}
	
	return 0;
}

1003E - Tree Constructing

Tutorial

Solution (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, d, k;
	cin >> n >> d >> k;
	
	if (d >= n) {
		cout << "NO" << endl;
		return 0;
	}
	
	vector<int> deg(n);
	vector<pair<int, int>> ans;
	set<pair<int, int>> q;
	
	for (int i = 0; i < d; ++i) {
		++deg[i];
		++deg[i + 1];
		if (deg[i] > k || deg[i + 1] > k) {
			cout << "NO" << endl;
			return 0;
		}
		ans.push_back(make_pair(i, i + 1));
	}
	for (int i = 1; i < d; ++i)
		q.insert(make_pair(max(i, d - i), i));
	
	for (int i = d + 1; i < n; ++i) {
		while (!q.empty() && deg[q.begin()->second] == k)
			q.erase(q.begin());
		if (q.empty() || q.begin()->first == d) {
			cout << "NO" << endl;
			return 0;
		}
		++deg[i];
		++deg[q.begin()->second];
		ans.push_back(make_pair(i, q.begin()->second));
		q.insert(make_pair(q.begin()->first + 1, i));
	}
	
	assert(int(ans.size()) == n - 1);
	cout << "YES" << endl;
	vector<int> p(n);
	for (int i = 0; i < n; i++)
	    p[i] = i;
	random_shuffle(p.begin(), p.end());
	for (int i = 0; i < n - 1; ++i)
	    if (rand() % 2)
		    cout << p[ans[i].first] + 1 << " " << p[ans[i].second] + 1 << endl;
		else
		    cout << p[ans[i].second] + 1 << " " << p[ans[i].first] + 1 << endl;
	
	return 0;
}

1003F - Abbreviation

Tutorial

Solution (Vovuh)

#include <bits/stdc++.h>

using namespace std;

const int N = 303;

int n;
bool eq[N][N];
int dp[N][N];
string s[N];

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

	cin >> n;
	int allsum = n - 1;
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
		allsum += s[i].size();
	}
	
	for (int i = 0; i < n; ++i) {
		eq[i][i] = true;
		for (int j = 0; j < i; ++j) {
			eq[i][j] = eq[j][i] = s[i] == s[j];
		}
	}
	
	for (int i = n - 1; i >= 0; --i) {
		for (int j = n - 1; j >= 0; --j) {
			if (eq[i][j]) {
				if (i + 1 < n && j + 1 < n)
					dp[i][j] = dp[i + 1][j + 1] + 1;
				else
					dp[i][j] = 1;
			}
		}
	}
	
	int ans = allsum;
	for (int i = 0; i < n; ++i) {
		int sum = 0;
		for (int j = 0; i + j < n; ++j) {
			sum += s[i + j].size();
			int cnt = 1;
			for (int pos = i + j + 1; pos < n; ++pos) {
				if (dp[i][pos] > j) {
					++cnt;
					pos += j;
				}
			}
			int cur = allsum - sum * cnt + (j + 1) * cnt - j * cnt;
			if (cnt > 1 && ans > cur) {
				ans = cur;
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Comments (35)

Show archived | Write comment?

Varun

8 years ago, hide # |

In E, won't the distance change upon inserting new edges and if yes, how to update the "maximal distance set" efficiently?

→ Reply

vovuh

8 years ago, hide # ^ |

← Rev. 4 →

The previous explanation was wrong, i had understood it now.

If the distance for some vertex v will change after adding the new vertex, it means that we attach some leaf that increases the diameter of a tree. But it means that we attach a leaf to the vertex w with dist_w = d, but in this case we already doesn't have the answer.

DeliciousFlatChest

← Rev. 5 →

It is possible to prove that there exists such a tree iff n * (k - 2) <= -2 + k * (k - 1) ** (d // 2) for even n and n * (k - 2) <= -2 + k * (k - 1) ** (d // 2) + (k - 2) * (k - 1) ** (d // 2)for odd n. We simply check if conditions above are satisfied and proceed with making the tree or not.

Edit: also, obviously it must be that n > d as said in the article

Edit: k = 1 and k = 2 should be treated as special cases

aeternalis1

My solution to F was to assign an integer to each distinct string (since there's a maximum of 300) while keeping track of lengths for each of these integers and then run a KMP search to find the number of occurrences of each valid subsequence. This solution runs in approximately the same time complexity as the editorial's.

2014CAIS01

← Rev. 2 →

My solution is same with you.39944563

Or maybe it can solved by hashing, but it may be hacked if I use hashing with overflow.39945601 39946612

CelesteLight

← Rev. 3 →

There is an O(n) approach in problem C.

code

rough explanation

Scandium

your pish and pop operations aren't constant time operations.

But each node would be push and pop 1 time.

I don't know why so much downvotes.

No idea why you're getting downvotes (that shouldn't matter tho, if you think your comment is constructive), your solution is very efficient.

It is a classic method to optimize DP.

I think I am doing nothing wrong to point it out in the case that editorial doesn't mention.

It seems that people are likely to downvote algorithm they don't know.

I think that is a very simple way to analysis the complexity, but it might be far too difficult for those rating is under 1600?

ameyanator

Can you please explain your solution?

dahao

what wrong in problem F makes a lotta participants output 689 in test 6 instead of 581?

zoomswk

Those solutions most likely did not consider more than two segments (only exactly two). The sample tests did not cover this.

indubitable

can anyone explain me the method for Problem C becoz despite several efforts i m unable to figure it out

scoobydoo

my approach is quite simple what I have done is to check for all segments the average temperature and we will consider which gives best answer and has size >= k my code

Bro really thanks for ur help my approach is also quite the same but i got a TLE i m giving my code link plz help as I m beginner and really want to increase my skills http://mirror.codeforces.com/contest/1003/submission/39983625

Midoriya095

I think "accumulate" as a third for loop .So the complexity is 5e3*5e3*5e3 , it will give you TLE. In worst case if n is 5e3 and k is 1 .

thanx bro ,,,, rest i think my algorithm is correct am I right??

You're right,but in this problem you don't have to use "accumulate".Think in a different way.

i fixed by using sum=sum+v[i];

Try it : ) . If it gives you a wrong answer , think about "what is the wrong in your code and what is the test you will fail in ", if you don't know , tell me , I will help you : ) .

thanx bro ...i passed all the test cases... thanx for ur help

nine_tails9

In problem D my code passed all pretests but it timed out on 27th Case in system testing. No wonder how. Code complexity Q * 32 * 32. Can someone suggest something? Code

washinson

unordered_map operations works some more than O(1).

AlexArdelean

U can easily adjust to only Q * 32 operations with a greedy strategy. A complexity has no constants is it. your complexity is O(Q) if you say so. Map operations are O(log) so the number of operations is even worse in your solution. Just adapt to O(Q * log(MAX_VALUE) + N * log(MAX_VALUE)) which actually is O(N * log(VAX_VALUE)) because N and Q constrains are the same. Now to adapt you can just do this:

the solution

Evilandrew

Could someone explain why it didn't pass even the pretests? (problem D, WA test 4)

Code

MonsterInMe

for problem E,shortest code :http://mirror.codeforces.com/contest/1003/submission/39967116

aki167yuuki

why it times out on test 23?? (problem E) http://mirror.codeforces.com/contest/1003/submission/39989027 but if i assign the values of test 23 and upload the code here it will not time out!!: http://mirror.codeforces.com/contest/959/submission/39989086 why????????????? :(

nexus.chebykin

Is it possible to solve problem D using Python?

nem-E-sis

3 months ago, hide # ^ |

yes

sankalp_

Why is a random_shuffle performed at the end of the code for problem E?

Mr_Maverick

Any O(nlogn) or O(n) method for C?

m_scofield

6 years ago, hide # |

what is wrong in my code for C ,it's giving the wrong answer on test#4 https://mirror.codeforces.com/contest/1003/submission/85153194

AjaySabarish

For problem E

My proof that when you attach a new node , d(x) of other nodes won't change.

Let d(x) be the distance of the furthest node from x, now when you attach a new node to node u, and say d(w) changes, then u is the furthest node from w (i.e. d(w) = dist(w,u)), so it means u is the end point of the diameter (d(u) = D, because that's the algorithm we use to find the diameter of a tree, finding the furthest node from a random node), so at that point we simple exit the process.

vovuh's blog