Educational Codeforces Round 44 Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Tutorial

Solution (Vovuh)

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> pos(n / 2);
	for (int i = 0; i < n / 2; ++i)
		cin >> pos[i];
	sort(pos.begin(), pos.end());
	
	int ans1 = 0, ans2 = 0;
	for (int i = 0; i < n / 2; ++i) {
		ans1 += abs(pos[i] - (i * 2 + 1));
		ans2 += abs(pos[i] - (i * 2 + 2));
	}
	
	cout << min(ans1, ans2) << endl;
	
	return 0;
}

985B - Switches and Lamps

Tutorial

Solution (Vovuh)

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<string> s(n);
	vector<int> cnt(m);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
		for (int j = 0; j < m; ++j)
			if (s[i][j] == '1') ++cnt[j];
	}
	
	for (int i = 0; i < n; ++i) {
		bool ok = true;
		for (int j = 0; j < m; ++j) {
			if (s[i][j] == '1' && cnt[j] == 1)
				ok = false;
		}
		if (ok) {
			puts("YES");
			return 0;
		}
	}
	
	puts("NO");
	
	return 0;
}

985C - Liebig's Barrels

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;

int n, k, l, m;
vector<li> a;

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

inline void solve() {
	sort(a.begin(), a.end());
	int rg = int(upper_bound(a.begin(), a.end(), a[0] + l) - a.begin());
	
	if(rg < n) {
		puts("0");
		return;
	}
	li ans = 0;
	
	int u = 0;
	fore(i, 0, n) {
		ans += a[u++];
		
		fore(j, 0, k - 1) {
			if(rg - u > n - i - 1)
				u++;
			else
				break;
		}
	}
	cout << ans << endl;
}

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

985D - Sand Fortress

Tutorial

Solution (PikMike)

#include <bits/stdc++.h>

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

typedef long long li;

using namespace std;

const int INF = 2e9;
li n, h;

bool check(li maxh){
	li k = min(h, maxh);
	li cnt = maxh * maxh - k * (k - 1) / 2;
	return (cnt <= n);
}

li get(li maxh){
	li k = min(h, maxh);
	li cnt = maxh * maxh - k * (k - 1) / 2;
	li len = (2 * maxh - 1) - (k - 1);
	n -= cnt;
	return len + (n + maxh - 1) / maxh;
}

int main() {
	scanf("%lld%lld", &n, &h);
	li l = 1, r = INF;
	
	while (l < r - 1){
		li m = (l + r) / 2;
		
		if (check(m))
			l = m;
		else
			r = m;
	}
	
	printf("%lld\n", check(r) ? get(r) : get(l));
	return 0;
}

985E - Pencils and Boxes

Tutorial

Solution (PikMike)

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 500 * 1000 + 13;

int f[N];

void upd(int x){
    for (int i = x; i < N; i |= i + 1)
        ++f[i];
}

int sum(int x){
    int res = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        res += f[i];
    return res;
}

int get(int l, int r){
	if (l > r) return 0;
	return sum(r) - sum(l - 1);
}

int main(){
	int n, k, dif;
	scanf("%d%d%d", &n, &k, &dif);
	vector<int> a(n);
	forn(i, n)
		scanf("%d", &a[i]);
	sort(a.begin(), a.end());
	
	vector<int> dp(n + 1, 0);
	
	dp[0] = 1;
	upd(0);
	
	int l = 0;
	forn(i, n){
		while (l < i && a[i] - a[l] > dif)
			++l;
		dp[i + 1] = (get(l, i - k + 1) >= 1);
		if (dp[i + 1]) upd(i + 1);
	}
	
	puts(dp[n] ? "YES" : "NO");
}

985F - Isomorphic Strings

Tutorial

Solution (adedalic)

#include <bits/stdc++.h>

#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

using namespace std;

const int B = 2;

typedef array<int, B> ht;

ht MOD, BASE;

inline int norm(int a, const int &MOD) {
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}

inline int mul(int a, int b, const int &MOD) {
	return int(a * 1ll * b % MOD);
}

inline ht operator +(const ht &a, const ht &b) {
	ht ans;
	fore(i, 0, sz(ans))
		ans[i] = norm(a[i] + b[i], MOD[i]);
	return ans;
}

inline ht operator -(const ht &a, const ht &b) {
	ht ans;
	fore(i, 0, sz(ans))
		ans[i] = norm(a[i] - b[i], MOD[i]);
	return ans;
}

inline ht operator *(const ht &a, const ht &b) {
	ht ans;
	fore(i, 0, sz(ans))
		ans[i] = mul(a[i], b[i], MOD[i]);
	return ans;
}

int CMODS[] = {int(1e9) + 7, int(1e9) + 9, int(1e9) + 21, int(1e9) + 33, int(1e9) + 87, int(1e9) + 93, int(1e9) + 97, int(1e9) + 103};
int CBASE[] = {1009, 1013, 1019, 1021};

const int N = 200 * 1000 + 555;

int n, m;
char s[N];
int x[N], y[N], len[N];

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	assert(scanf("%s", s) == 1);
	
	fore(i, 0, m) {
		assert(scanf("%d%d%d", &x[i], &y[i], &len[i]) == 3);
		x[i]--, y[i]--;
	}
	return true;
}
void setMods() {
	mt19937 rnd;
	unsigned int seed = n;
	fore(i, 0, n)
		seed = (seed * 3) + s[i];
	fore(i, 0, m) {
		seed = (seed * 3) + x[i];
		seed = (seed * 3) + y[i];
		seed = (seed * 3) + len[i];
	}
	rnd.seed(seed);
	
	set<int> mids;
	while(sz(mids) < sz(MOD))
		mids.insert(rnd() % 8);
	vector<int> vmids(mids.begin(), mids.end());
	fore(i, 0, sz(MOD)) {
		MOD[i] = CMODS[vmids[i]];
		BASE[i] = CBASE[i];
	}
}

ht pBase[N];
ht ph[27][N];
vector<int> ord[N];

ht getHash(int id, int l, int r) {
	return ph[id][r] - ph[id][l] * pBase[r - l];
}

inline void solve() {
	setMods();
	
	pBase[0] = {1, 1};
	fore(i, 1, N)
		pBase[i] = pBase[i - 1] * BASE;
		
	fore(c, 0, 26) {
		ph[c][0] = {0, 0};
		fore(i, 0, n) {
			int val = (s[i] == c + 'a');
			ph[c][i + 1] = ph[c][i] * BASE + ht{val, val};
		}
	}
	
	vector<int> curOrd(26, 0);
	iota(curOrd.begin(), curOrd.end(), 0);
	for(int i = n - 1; i >= 0; i--) {
		ord[i] = curOrd;
		auto it = find(ord[i].begin(), ord[i].end(), int(s[i] - 'a'));
		ord[i].erase(it);
		ord[i].insert(ord[i].begin(), int(s[i] - 'a'));
		curOrd = ord[i];
	}
	
	fore(q, 0, m) {
		int s1 = x[q], s2 = y[q];
		bool ok = true;
		
		fore(i, 0, 26) {
			if(getHash(ord[s1][i], s1, s1 + len[q]) != 
				getHash(ord[s2][i], s2, s2 + len[q])) {
				ok = false;
				break;
			}
		}
		puts(ok ? "YES" : "NO");
	}
}

int main(){
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	if(read()) {
		solve();
	}
	return 0;
}

985G - Team Players

Tutorial

Solution (adedalic)

#include <bits/stdc++.h>

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int(a.size())

using namespace std;

typedef unsigned long long uli;

const int N = 200 * 1000 + 555;

int n, m;
uli a, b, c;
vector<int> g[N];

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	assert(cin >> a >> b >> c);
	fore(i, 0, m) {
		int u, v;
		assert(scanf("%d%d", &u, &v) == 2);
		
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return true;
}

vector<uli> ps[N];

inline uli getSum(int v, int l, int r) {
	return ps[v][r] - ps[v][l];
}

const int MX = 700;
int id[N];

const int B = 1111;
bitset<N> has[B];
int szh = 0;

inline void solve() {
	memset(id, -1, sizeof id);
	szh = 0;
	fore(v, 0, n) {
		sort(g[v].begin(), g[v].end());
		
		ps[v].assign(sz(g[v]) + 1, 0);
		fore(i, 0, sz(g[v]))
			ps[v][i + 1] = ps[v][i] + g[v][i];
		
		if(sz(g[v]) >= MX) {
			assert(szh < B);
			id[v] = szh++;
			
			for(int to : g[v])
				has[id[v]][to] = 1;
		}
	}
	
	uli all = 0;
	fore(v, 0, n) {
		uli lw = v, gr = n - v - 1;
		all += a * v * (gr * (gr - 1) / 2);
		all += b * v * (lw * gr);
		all += c * v * (lw * (lw - 1) / 2);
	}
	
	uli sub1 = 0;
	fore(v, 0, n) {
		for(int to : g[v]) {
			if(to > v)
				break;
			
			uli cnt = to;
			uli sum = cnt * (cnt - 1) / 2;
			sub1 += a * sum + cnt * (b * to + c * v);
			
			cnt = v - to - 1;
			sum = (2 * to + cnt + 1) * cnt / 2;
			sub1 += b * sum + cnt * (a * to + c * v);
		}
		
		uli sum = 0;
		fore(i, 0, sz(g[v])) {
			if(g[v][i] > v)
				break;
			
			uli cnt = i;
			sub1 -= a * sum + cnt * (b * g[v][i] + c * v);
			sum += g[v][i];
		}
	}
	all -= sub1;
	
	uli sub2 = 0;
	uli cntE = 0, sumE = 0;
	fore(v, 0, n) {
		sub2 += sumE + cntE * c * v;
		for(int to : g[v]) {
			if(to > v)
				break;
			
			cntE++;
			sumE += a * to + b * v;
		}
	}
	
	fore(v, 0, n) {
		for(int to : g[v]) {
			if(to > v)
				break;
			
			int pos = int(lower_bound(g[to].begin(), g[to].end(), to) - g[to].begin());
			sub2 -= a * getSum(to, 0, pos) + pos * (b * to + c * v);
			
			int pos2 = int(lower_bound(g[to].begin(), g[to].end(), v) - g[to].begin());
			sub2 -= b * getSum(to, pos, pos2) + (pos2 - pos) * (a * to + c * v);
		}
	}
	
	vector<char> curh(n + 5, 0);
	fore(v, 0, n) {
		if(id[v] == -1) {
			fore(i2, 0, sz(g[v])) {
				int u2 = g[v][i2];
				if(u2 > v)
					break;
				
				if(id[u2] != -1) {
					fore(i1, 0, i2) {
						int u1 = g[v][i1];
						if(has[id[u2]][u1])
							sub2 += a * u1 + b * u2 + c * v;
					}
				} else {
					for(int to : g[u2]) {
						if(to > u2)
							break;
						curh[to] = 1;
					}
					fore(i1, 0, i2) {
						int u1 = g[v][i1];
						if(curh[u1])
							sub2 += a * u1 + b * u2 + c * v;
					}
					for(int to : g[u2]) {
						if(to > u2)
							break;
						curh[to] = 0;
					}
				}
			}
		} else {
			fore(u2, 0, v) {
				if(!has[id[v]][u2])
					continue;
				for(int u1 : g[u2]) {
					if(u1 > u2)
						break;
					if(has[id[v]][u1])
						sub2 += a * u1 + b * u2 + c * v;
				}
			}
		}
	}
	all -= sub2;
	cout << all << endl;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(10);

	if(read()) {
		solve();
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
#endif
	}
	return 0;
}

Comments (58)

Show archived | Write comment?

awoo

7 years ago, # |

← Rev. 2 →

+21

Okay, formulas got better.

→ Reply

Phanix

In problem D, for n=5,H=2, why is [2,3] wrong? I seem to be missing something here

HIT_Zero

7 years ago, # ^ |

+29

The pillars are infinite. So your example is [2, 3, 0, 0, ...]. The difference between 3 and 0 is beyond 1.

Ahh damn I knew I was missing something simple. Thanks!

JayZhan

Problem D binary search on h the height becomes h,h-1,h-2...2,1,0 and if h>H make it becomes H and change the height on the right too. if H=5 There are two case: 1. [9,8,7,6,5,4,3,2,1,0][ 5,6,7,6,5,4,3,2,1,0] Sum=(9+1)*9/2-(4+2+0...) 2. [8,7,6,5,4,3,2,1,0][5,6,6,5,4,3,2,1,0] Sum=(8+1)*8/2-(3+1+0..) find the smallest h that sum>=n Note: 1+3+..n=[(n+1)/2]^2=tmp 2+4+..n=tmp+n east to calculate

xsc

for D exists O(1) solution.

http://codeforces.net/contest/985/submission/38514950

orange4glace

Does sqrt work in O(1)?

Magolor

Nope, but STL sqrt works faster than O(loglogn).

SQRT works very fast.

see http://acm.timus.ru/rating.aspx?space=1&num=1001 solution rating !!

ameyanator

Can you please explain this- "Otherwise, for each i from 1 to n let's take no more than k smallest staves from this segment in the i-th barrel, but in such way, that there are at least n - i staves left for next barrels."

Every barrel will have atleast one stave from the range [1,rg) otherwise there will be two barrels whose volume difference will be greater than l.

So for each barrel i from 1 to n, start picking up the staves (smallest first) from [1,rg) until you reach the required number of staves (k) or if there there are fewer than n-i staves left in the range [1,rg) because you still need to build n-i barrels and each of these needs atleast one stave from this range

eugalt

← Rev. 4 →

Correct me if I am wrong.

In the first example for problem C:

4 2 1

2 2 1 2 3 2 2 3

Isn't [1, 2], [2, 2], [2, 2], [3, 3] a valid solution with answer 8?

vladalos

l = 1, and the volume of your first barrel is equal to 1, and the volume of your fifth is 3,so abs(3-1) is definitely bigger than 1.

Ah, I get it. Thanks.

ankur.trapasiya

How the solution for 985A works? what principal/logic is this? I'm struggling to understand.

saumyadip

You have to first sort the positions of the pieces because in one move you can either move left or right. We need to sort the positions to get optimal answer. Now the there are N positions and N/2 pieces. These N/2 pieces can be on black position or on white position since we need to place them in same color. Black positions are odd numbers till N and white pieces are even numbers till N (BWBWBW....BW) . Now the number of steps required by each piece is the absolute difference of required position where it should be and initial position of the piece given in the array. Thats what they have done for N/2 pieces. They are taking the minimum steps when placing in white position and black position.

My Code : http://codeforces.net/contest/985/submission/38496335

anishakd4

6 years ago, # ^ |

Thanks saumyadip

xuanquang1999

In author solution of problem F, is the mt19337 random generator unpredictable enough?

adedalic

If a seed of generator is fixed, any random generator will generate same sequence every time. So it is necessary to set a seed with diffenent values.

On the other hand, as author, I would like to have a deterministic solution which will not depend on time it was started.

I guess it is OK to use hash without unpredictable random in author solution (if the hash is strong enough, like the 8-modulo hash in author solution for F). No one beside author can see the solution and generate the anti-hash testcase until the end of the hacking phase.

15ucs145

i dont understanf why i am getting TLE in problem C my code

amnesiac_dusk

← Rev. 3 →

Java's inbuilt Arrays.sort() uses a double pivot quick-sort whose worst case is O(n^2), So, it can be hacked by a testcase specially designed to break it. Some O(nlogn) sort like Merge sort or heap sort could be used or radix sort. You can also add a random shuffle before Arrays.sort or use Integer instead of int so that java's inbuilt Arrays.sort() over Objects(timsort) will be used.
TLE with Arrays.sort()-38492535
AC with Arrays.sort() over Integer- 38524250

My Java solution also TLEd due to same reason :(

thanxx man, got it!!! and does it only happen in educational rounds or in normal rounds we should take care of Arrays.sort()

Usually normal rounds are of small length, so this kind of hacks rarely happen. But creating a custom sort function which first randomly shuffles the array and then sorts or some other sort should be on the safer side.

Dexter420

Can Somebody explain DP part of Solution E

Necrozma

Same question xD

Also, Necrozma

Maybe the code of O(n²) solution will help a bit more?

Code

for (int i = 0; i <= n; ++i)
    dp[i] = 0;
dp[0] = 1
for (int i = 0; i < n; ++i){
    for (int j = 0; j <= i; ++j)
        if (dp[j] == 1 && i - j + 1 >= k && a[i] - a[j] <= d)
            dp[i + 1] = 1;
puts(dp[n] == 1 ? "YES" : "NO")

bluejay

Hey, by checking i+1-j>=k, you basically check if i and j can be taken in a segment, what if the jth is already taken in some previous segment and taking i,j together "disturbs" it?

You update from dp_j and that is the state for the first j elements being distributed. j-th element is the first one not taken.

Jain_Yash

Please can you explain the use of array f[N] . I am not able to understand.

That is BIT

Vesper_Lynd

can anybody help in understanding div 2 C,i havent got the idea n-i stacks to be left for each i??

First, sort array in non-decreasing order.

We must have a barrel which contains a₁ stave. So each maximal total sum of volumes of barrel cannot be larger than a₁ + l

let C = (number of stave which has length ≤ a₁ + l) - N.

If C < 0, then answer is 0.

Otherwise, While picking staves, if C > 0, pick the smallest stave you have, and decrease C by 1. else, pick the largest stave you have.

thanks i got it!!

How to solve F with LCP?

vivek_shah

awoo, Can u give me any practice problem link similar to DP involved in Problem E?
P.S : I am new to DP.

Huh, you know, this is such a basic dp usage. No particular problem comes to my head. I can recommend to search some dp trains on e-olymp, they have lots of great contests on certain topics.

erina

Well it is annoying that the third problem WA on test 13

killer_god

in problem F. More over, if we sort all positions pos_i^s for all distict characters in s and sort all positions pos_j^t for t, then pos_i^s must be equal pos_i^t for any i.

can someone expalain this?

rachitiitr

If both strings are isomorphic, then the first occurrence of character X in S MUST be the first occurrence of some character Y in T.

So if you sort the positions of first occurrences of distinct letters for S and T, they will be exactly same (only if they are isomorphic, also the reverse might not be true).

Thanks. got it.

push-0_coder

About problem 985E — Pencils and Boxes. I was thinking about proof. For "YES" condition its fairly simple. But what about "NO". Can'nt we get other segments. other than what is describe by DP solution.

Usually, there is next idea behind this type of task: (solution exists) → (author solution finds answer) $\text{[math]}$ !(author solution finds answer) → !(solution exists).

kesh4281

6 years ago, # |

Another approach in problem E is to first sort the whole array. My approach- https://codeforces.net/contest/985/submission/54277798 Now start from back, I am using 0 based indexing, now mem[j] stores if from index j, I can have a soln. or not. Base case is mem[n]=1 and mem[j] can be known as we need to know nearest location after k indexes from where mem[i]==1. or just look at my soln.- In my soln. mem[j] stores if from index j ican construct a soln. or not. nr[j] stores nearest index >=j where mem[i]==1.

chaudhary_19

can anyone please help me in A problem...how you come up with the idea of this formula

KG_1910

5 years ago, # |

In second question if you enter 2x3 matrix 1 1 0 0 1 1 so answer will be yes or no ???

Tutorial's code give yes but answer will be no!!

rotavirus

5 years ago, # ^ |

answer is "no" obviusly, and the tutorial code also gives "no"

Tutorial c9de gives yes

You can check it

i've checked. it gives no

ohhh really it gives yes i checked it again

i checked it 4 times and it gives no

input is 2 3 1 1 0 0 1 1 ????

input is

2 3
110
011

there is 2 switch if you you on only one switch how it posible all lamps on.

Priyansh31dec

Can someone explain to me how the O(n^2) solution is working in case of ProbE Pencils and Boxes? I am facing a lot of difficulty in understanding how the given solution is taking care of the constraint that every box contains at least k elements.

towrist

4 years ago, # |

I have an alternate (simpler?) solution to $$$Problem D$$$: we binary search over the answer:

Can $$$x$$$ be the answer? First, notice monotonicity of this boolean upto $$$x \leq n$$$. Now, lets fill up the range with maximum possible stones (can be found by easy math). It will be obviously of the form $$$h_1 ≤ h_2 ≤ ... ≤ h_k ≥ ...\geq1=h_x$$$. If the sum of $$$h_i$$$ is less than $$$n$$$, obviously NO $$$x$$$ can't be the answer. Otherwise, we prove by construction, that it is.

For while $$$n$$$ is less than sum, decrease the sum by $$$1$$$ by removing one from the height of the greatest pile. It obviously maintains the invariant $$$|h_i-h_{i+1}|\leq1$$$.

Olympia

3 years ago, # |

My $$$\mathcal{O} (N \log N A)$$$ TLEs. Interesting that authors made such tight constraints (easily fixable).

awoo's blog