Educational Codeforces Round 167 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

1989A - Catch the Coin

Tutorial

Solution (awoo)

for _ in range(int(input())):
	x, y = map(int, input().split())
	print("YES" if y >= -1 else "NO")

1989B - Substring and Subsequence

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    int ans = n + m;
    for (int i = 0; i < m; ++i) {
      int j = i;
      for (auto c : a) {
        if (j < m && c == b[j]) ++j;
      }
      ans = min(ans, n + m - (j - i));
    }
    cout << ans << '\n';
  }
}

1989C - Two Movies

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    int x = 0, y = 0, neg = 0, pos = 0;
    for (int i = 0; i < n; ++i) {
      if (a[i] > b[i]) {
        x += a[i];
      } else if (a[i] < b[i]) {
        y += b[i];
      } else {
        neg += (a[i] < 0);
        pos += (a[i] > 0);
      }
    }
    int ans = -1e9;
    for (int i = -neg; i <= pos; ++i)
      ans = max(ans, min(x + i, y + (pos - neg - i)));
    cout << ans << '\n';
  }
}

1989D - Smithing Skill

Idea: BledDest

Tutorial

Solution (adedalic)

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val a = readln().split(" ").map { it.toInt() }
    val b = readln().split(" ").map { it.toInt() }
    val c = readln().split(" ").map { it.toInt() }

    val mx = a.maxOrNull()!! + 1

    val best = IntArray(mx) { 1e9.toInt() }
    val calc = IntArray(mx) { 0 }

    for (i in a.indices)
        best[a[i]] = minOf(best[a[i]], a[i] - b[i])
    for (v in 1 until mx)
        best[v] = minOf(best[v], best[v - 1])

    for (v in 1 until mx)
        if (v >= best[v])
            calc[v] = 2 + calc[v - best[v]]

    var ans = 0L
    for (v in c) {
        var cur = v
        if (cur >= mx) {
            val k = (cur - mx + 1 + best[mx - 1]) / best[mx - 1]
            ans += 2L * k
            cur -= k * best[mx - 1]
        }
        ans += calc[cur]
    }
    println(ans)
}

1989E - Distance to Different

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int add(int x, int y)
{
 	x += y;
 	while(x >= MOD) x -= MOD;
 	while(x < 0) x += MOD;
 	return x;
}

int mul(int x, int y)
{
 	return (x * 1ll * y) % MOD;
}

int main()
{
	int n;
	cin >> n;
	int k;
	cin >> k;
	vector<vector<int>> dp(n + 1, vector<int>(k + 1));
	dp[0][0] = 1;
	vector<int> sum(k + 1);
	sum[0] = 1;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j <= k; j++)
		{
			int& d = dp[i + 1][min(j + 1, k)];
		 	d = add(d, sum[j]);
		 	if(i >= 2 && i != n - 1)
		 		d = add(d, -dp[i - 1][j]); 
		}
		for(int j = 0; j <= k; j++)
			sum[j] = add(sum[j], dp[i + 1][j]);
	}
	cout << dp[n][k] << endl;
}

1989F - Simultaneous Coloring

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 edge{
	int v, u;
};

vector<vector<int>> g, tg;
vector<int> ord;
vector<char> used;
vector<int> clr;

void ts(int v){
	used[v] = true;
	for (int u : g[v]) if (!used[u])
		ts(u);
	ord.push_back(v);
}

void dfs(int v, int k){
	clr[v] = k;
	for (int u : tg[v]) if (clr[u] == -1)
		dfs(u, k);
}

vector<long long> rk, p;
long long sum;
vector<long long*> where;
vector<long long> val;

long long cost(int x){
	return x == 1 ? 0ll : x * 1ll * x;
}

int getp(int a){
	return a == p[a] ? a : getp(p[a]);
}

void unite(int a, int b){
	a = getp(a), b = getp(b);
	if (a == b) return;
	if (clr[a] != clr[b]) return;
	if (rk[a] < rk[b]) swap(a, b);
	where.push_back(&sum);
	val.push_back(sum);
	sum -= cost(rk[a]);
	sum -= cost(rk[b]);
	sum += cost(rk[a] + rk[b]);
	where.push_back(&rk[a]);
	val.push_back(rk[a]);
	rk[a] += rk[b];
	where.push_back(&p[b]);
	val.push_back(p[b]);
	p[b] = a;
}

vector<edge> e;
vector<long long> ans;

void calc(int l, int r, const vector<int> &cur){
	if (l == r - 1){
		ans.push_back(sum);
		return;
	}
	int m = (l + r) / 2;
	for (int i : cur) if (i < m){
		int v = getp(e[i].v), u = getp(e[i].u);
		for (int w : {v, u}) if (used[w]){
			g[w].clear();
			tg[w].clear();
			clr[w] = -1;
			used[w] = false;
		}
		g[v].push_back(u);
		tg[u].push_back(v);
	}
	ord.clear();
	for (int i : cur) if (i < m){
		for (int v : {getp(e[i].v), getp(e[i].u)}) if (!used[v]){
			ts(v);
		}
	}
	reverse(ord.begin(), ord.end());
	int k = 0;
	for (int v : ord) if (clr[v] == -1){
		dfs(v, k);
		++k;
	}
	int tim = val.size();
	for (int i : cur) if (i < m) unite(e[i].v, e[i].u);
	vector<int> tol, tor;
	for (int i : cur){
		if (i >= m)
			tor.push_back(i);
		else if (getp(e[i].v) == getp(e[i].u))
			tol.push_back(i);
		else
			tor.push_back(i);
	}
	calc(m, r, tor);
	while (int(val.size()) > tim){
		*where.back() = val.back();
		where.pop_back();
		val.pop_back();
	}
	calc(l, m, tol);
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m, q;
	cin >> n >> m >> q;
	e.resize(q);
	forn(i, q){
		int x, y;
		char c;
		cin >> x >> y >> c;
		--x, --y;
		if (c == 'R')
			e[i] = {y + n, x};
		else
			e[i] = {x, y + n};
	}
	rk.resize(n + m, 1);
	p.resize(n + m);
	iota(p.begin(), p.end(), 0);
	used.resize(n + m, 0);
	clr.resize(n + m, -1);
	g.resize(n + m);
	tg.resize(n + m);
	vector<int> cur(q);
	iota(cur.begin(), cur.end(), 0);
	calc(0, q + 1, cur);
	ans.pop_back();
	reverse(ans.begin(), ans.end());
	for (long long x : ans) cout << x << '\n';
	return 0;
}

for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i - 1] == b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1]; else dp[i][j] = dp[i - 1][j]; } } for (int i = 1; i <= m; i++) mx = max(mx, dp[n][i]);

#include <iostream> #include <vector> using namespace std; int main(){ int n, m; cin >> n >> m; vector<int> a(n+1, 0), b(n+1, 0); vector<long long> c(m+1, 0ll); for(int i=1; i<=n; i++) cin >> a[i]; for(int i=1; i<=n; i++) cin >> b[i]; for(int i=1; i<=m; i++) cin >> c[i]; long long mx = 0ll; for(int i=1; i<=m; i++) mx = max(mx, c[i]); int mxA = 1e9, best =1e9; for(int i=1; i<=n; i++) mxA = max(mxA, a[i]), best = min(best, a[i]-b[i]); // for all c[i], in 1 to m, if c[i] is greater than max(a_i), make it down to c[i] <= max(a_i) vector<long long> dp(mxA+1, 0ll); // dp[0] will be used to store the answer for(int i=1; i<=m; i++){ if(c[i] > mxA){ long long k = (c[i]-mxA)/best; dp[0] += 2ll*k; c[i] -= k*best; } } // once, all the c[i] have become down to c[i] <= max(a_i), apply dp to maximise exp. for(int i=1; i<=mxA; i++){ for(int j=1; j<=n; j++) if(i >= a[j]) dp[i] = max(dp[i], dp[i -(a[j]-b[j])]+2); } // sum all the experiences for(int i=1; i<=m; i++) dp[0] += dp[c[i]]; cout << dp[0] << endl; return 0; }

# number of test cases testCases = int(input()) i = 1 # loop for iterating the number of test cases while(testCases >= i): # coorditnates of the coin (xi, yi) x , y = map(int, input().split()) # check if yi is less than or equal to negative two print 'NO' else print 'YES' if y <= -2: print('NO') else: print('YES') i += 1

Comments (62)

Write comment?

Baraa-Ahmed

6 months ago, # |

Fast tutorial

→ Reply

niketh457

Interesting problemset

BILL_TIN

For problem D I kind of simulated the process by brute force, submission: 267758186

Notice that

if crafting and smelting cost $$$a_i - b_i$$$ of 2 kinds of weapons is equal, then it's never better to craft a weapon with a higher initial material cost $$$a_j$$$
if crafting and smelting cost $$$a_j - b_j$$$ of one kind of weapon is greater, it can only be useful to craft it if its material cost $$$a_j$$$ is lower

In my solution I simulate the process by going from lower operation cost $$$a_i - b_i$$$ and higher material cost $$$a_i$$$ to higher operation cost and lower material cost. On each step remaining metals with amount of ingots $$$c_k < a_i$$$ are useless for me, and any metals with $$$c_k \geq a_i$$$ will be reduced to metals with remaining quantity less than $$$a_i$$$, but at least $$$b_i$$$.

I was expecting this solution to get hacked or fail system tests, but somehow it's still standing (although I've seen some similar solutions getting hacked). After pondering on why did it not get TLE, I realized that each unique remaining value of $$$c_k$$$ will be considered at most once, and since there are at most $$$10^6$$$ unique values of $$$c_k$$$ the total time complexity will be amortized.

This solution is a result of me gaslighting myself that there are no more than $$$O(\sqrt{max(a_i)})$$$ unique differences $$$a_i - b_i$$$ (which is obviously not true).

rtckyw_

6 months ago, # ^ |

I did exactly the same, also waited to be hacked and then understood..

tabj84

can you please explain why you were able to use each value of ck atmost once? also, why does using lower_bound work here, shouldn't you use maximum amount of ingots for the best case (minimum difference)

Let's go over from a brute force solution to a more optimized one step by step:

Iterating over all kinds of weapons and then for each weapon iterating over all kinds of ingots is $$$O(N \cdot M)$$$
Now let's group different kinds of ingots with the same remaining quantity together, since if you can calculate the amount of xp for a single kind of metal with remaining $$$c_k$$$ ingots, you can do the same for $$$X$$$ kinds of metals with $$$c_k$$$ remaining ingots. You could store counts in an array or in a map. Since there could be $$$M$$$ unique values of $$$c_k$$$ you still would be iterating over all kinds of metals, leading to $$$O(N \cdot M)$$$ complexity
Now get rid of the values which we cannot smelt anything from, on each step it's useless to consider values $$$c_k$$$ lower than $$$a_i$$$, this is where lower_bound comes in. Also notice that after each smelting operation all values $$$c_k \geq a_i$$$ will get mapped to some values strictly less than $$$a_i$$$. Picture it like this: you pick the largest $$$a_0$$$ first, you erase all values $$$c_k \geq a_0$$$, then you pick second largest value $$$a_1$$$ and erase all values $$$a_1 \leq c_k < a_0$$$, so on and so forth. In total you will not iterate over more than $$$max(a_i) = 10^6$$$ unique values of $$$c_k$$$ (probably even less under given constraints).

hihitherethere

I did what you stated in 267754245, but it got hacked :( Could anyone tell me what I missed in my solution?

Grenier

yeah, i also do the same thing and waited to be hacked. As the blogger said, this complexity is hard to think through on the field. But as long as we find this similar to the monotone queue optimization DP property, coupled with memory search, it is easy to amorize the complexity. If you were a hack, you would have to make each a minus b different and find a number, and then take the remainder of each of these A minus b's different, which is obviously impossible to do.

Newtonian278

actually the first observation isn't it better to use the high initial material cost first ? like because that would let us have more ingots retained finally because of b ? better for future use. similarly for second one too we can argue the same its better to try using the higher cost aj if thats not possible to craft then go to aj having lower cost , for future benefit .

_brucewayne_

5 months ago, # ^ |

← Rev. 2 →

I was solving this today and my initial idea was the same but i was not sure that this would work since my mind was occupied by the n * m time complexity which would give tle. Nice solution btw.

formidablechief27

Detailed Video Editorial | English Language

B : https://youtu.be/izeasCQM6Mc

C : https://youtu.be/K9Lj5WFtwXc

Paras2856

Can anyone explain me why lcs was not working in problem B I was able to solve but still confused where it could have gone wrong

pkcf101

lcs does not work because as per the question we need to find the longest contiguous substring of b that occurs as a subsequence in a. for example if a="ab" and b="sasb" the lcs is "ab" with length 2 but as we can see it is not useful for us as in our final string there must be a 's' between 'a' and 'b'. the answer string would be "sabsb" with length 5.

Im_Gonna_Be_King_Of_Reds

Actually you needed to find the longest contiguous substring of b that occurs as a subsequence in a. It can be done using LCS algorithm only, it just need 1 little modification in the else part. Instead of finding max(dp[i — 1][j], dp[i][j — 1]), we can do this

nomanbinsafar

can you elaborate it aa bit more?i was trying the same thing but i don't know how this works.

pedrolino

I don't understand, why not use greedy for values of x <= A in D?

Spaseeker

actually we can get accepted by using greedy.

here's the link.

avixii

I calculated the string using a bruteforce. It seems to be missing a testcase. What is it that I am missing in this: https://mirror.codeforces.com/contest/1989/submission/267683386

you are ignoring the order when using the hashmap, for this test case for example:

1
cba
abc

the answer should be 5

Sorry the link was wrong, could you check this solution: https://mirror.codeforces.com/contest/1989/submission/267710157

in the first while you ignore only characters from b that do not appear in a, this is not necessarily optimal, for example in this case:

1
abc
acabc

your code gives 6, when it should be 5.

even if "ac" appears in the string a, it is better to ignore this prefix in the optimal solution.

Got it now. Thanks!

267914972 can anyone please explain why this might be giving a TLE? Is that the priority queue? I used it as a max-heap as I believe I should use maximum possible ingots each time, for the minimum difference in crafting and smelting

nightfury02

i did the same and got tle.

SuperMo

problem B test case sample can drive you insane they can work with any wrong algorithm you come up with

YOUNG_0503

So LCS is one of the wrong algorithms?

Fireborn25

yes, I used LCS earlier and got scammed

I got it.The ordinary LCS cannot tell which string is substring and which is subsequence.

can anyone please explain why i'm getting wrong answer on B 267919922

Isaac_Newton__

The order of the elements in the string are important by just counting the elements, you are ignoring the order .

rainb0ySimp

As usual, BledDest blesses us with high-quality problems!

Can someone please help me with D. I can't figure out why this is giving TLE on testcase 5

267937823

sandbag

Are D tests weak? My solution uses memoization with a vector of maps and passes in 2.8 seconds. My solution relies on the fact that if the net costs are very high or very low, then all of the metal is expended quickly. For this reason I think the worst case would be on the order of O(log n sqrt(max) n)? Submission: https://mirror.codeforces.com/contest/1989/submission/267939272

om172

← Rev. 4 →

my solution for question e was this : https://mirror.codeforces.com/contest/1989/submission/267952069

kmth.7z

tried solving B using dp, why doesn't it work?

https://mirror.codeforces.com/contest/1989/submission/267759332

Sidaksh

If you are using LCS logic,it will not work in this question.

aryanartist30

267826797 ques b) can anyone why its not giving right output or on which test case it fails

bc bxbc

addict_0x0F

I tried to solve Problem C, I am calculating x, y pos & neg in similar way as shown in the editorial. after that i tried greedy approach, i got rid of the for loop and made both x and y equal by doing this.

int temp; // assume x >= y
temp=min(x-y,pos);
y+=temp , pos-=temp;

temp=min(x-y,neg);
x-=temp , neg-=temp;

now we have a simple case where x==y which can be solved easily by doing this

x+=(pos>>1)  , y+=(pos>>1);
x-=(neg>>1)   ,y-=(neg>>1);

if((pos^neg)%2 && (neg%2))
{
   x--;
}
cout<<x<<endl;

EDIT: ACCEPTED

For people why LCS is not working for problem b actually you needed to find the longest contiguous substring of b that occurs as a subsequence in a. It can be done using LCS algorithm only, it just need 1 little modification in the else part. Instead of finding max(dp[i — 1][j], dp[i][j — 1]), we can do this

Valters07

F can be solved by using the well-known Radecki algorithm

Aspirebugs

For problem D i have written same solution as given in tutorial but it is giving TLE on test case 9

267975922 can anyone justify?

madhavG

no fastIO

got accepted thanks!

7710753532

[resolved]

thatdns

For D, I think I'm doing the same thing that's mentioned in the tutorial but I'm getting TLE. Can someone please help me here? I don't know what's causing the TLE. https://mirror.codeforces.com/contest/1989/submission/268040829

I got it. IO was slow :( Adding ios::sync_with_stdio(false); resolved it

saadamin2006

Bro you are a lifesaver. Thank you.

redraven

Can anyone tell me how to do B by graphs?

lakkshyag

Appreciate the Todd Howard reference in Q4

any one knows why the DP on problem C is wrong
is it not always optimal to take the maximum min at each state ? I tried making a simple dp[n][2] dp[i][0] means to take the first option and extend from the maximum min from dp[i-1] and dp[i][0] means to take the second option and also extend max min from dp[i-1]

can some help why this is wrong ? here is my submission https://mirror.codeforces.com/contest/1989/submission/268130928

alifwide

hey you got the answer? i was using the same approach but so far no luck with dp

no it's not solvable with dp it's not always optimal to only extend the maximum min, sometimes you need to extend a non optimal sub answer to reach the optimal final answer so it's not dp at all I guess. try to think greedy .

stone_head

Can anyone please explain why this Code is not working? I can't find where I have made a mistake. Is my approach wrong?

nikhil09.dixit

Amazing editorial of D!!!

aadityavir11

can someone tell why this submission is wrong 268881012 for problem C

the_last_smilodon

5 months ago, # |

Was it intentional that O(nlogn) solutions of D Fail or is my implementation just garbage? python code

SonuGupta001

Someone please explain why this solution is taking so long for larger values of c = 1e9, even after optimisation. It is supposed to run in O(max(a_i)*n) time but it's not.

yuunp

4 months ago, # |

In my case i did the solution that is from awoo(specifically the first 1), is this considered a bad practice??

Here is the code:

hrszo

9 days ago, # |

Can anyone tell why my code for B was wrong? https://mirror.codeforces.com/contest/1989/submission/296237273

awoo's blog