Educational Codeforces Round 153 Editorial

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

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

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
	string s;
	cin >> s;
	int n = s.size();
	string a, b;
	for (int i = 0; i < 2 * n; ++i) {
	  a += "()"[i & 1];
	  b += ")("[i < n];
	}
	if (a.find(s) == string::npos) {
	  cout << "YES\n" << a << '\n';
	} else if (b.find(s) == string::npos) {
	  cout << "YES\n" << b << '\n';
	} else {
	  cout << "NO\n";
	}
  }
}

1860B - Fancy Coins

Idea: BledDest

Tutorial

Solution 1 (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		int m, k, a1, ak;
		cin >> m >> k >> a1 >> ak;
		int taken_k = m / k;
		int taken_1 = m % k;
		int taken_fancy_1 = max(0, taken_1 - a1);
		int left_regular_1 = max(0, a1 - taken_1);
		int taken_fancy_k = max(0, taken_k - ak);
		int to_replace = min(left_regular_1 / k, taken_fancy_k);
		int ans = taken_fancy_1 + taken_fancy_k - to_replace;
		cout << ans << endl;
	}
}

Solution 2 (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		int m, k, a1, ak;
		cin >> m >> k >> a1 >> ak;
		// function which calculates the number of fancy coins taken
		// if we take exactly x coins of value k
		auto f = [m, k, a1, ak](int x)
		{
			int taken_1 = m - k * x;
			return max(0, taken_1 - a1) + max(0, x - ak);
		};
		
		int lf = 0;
		int rg = m / k;
		while(rg - lf > 2)
		{
			int mid = (lf + rg) / 2;
			if(f(mid) < f(mid + 1))
				rg = mid + 1;
			else
				lf = mid;
		}
		int ans = 1e9;
		for(int i = lf; i <= rg; i++) ans = min(ans, f(i));
		cout << ans << endl;
	}
}

1860C - Game on Permutation

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int ans = 0;
    int mn = n + 1, mnWin = n + 1;
    while (n--) {
      int x;
      cin >> x;
      if (mn < x && x < mnWin) {
      	ans += 1;
      	mnWin = x;
      }
      mn = min(mn, x);
    }
    cout << ans << '\n';
  }
}

1860D - Balanced String

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
const int N = 111;
 
int n;
string s;
int dp[2][N][N * N];
 
int main() {
  cin >> s;
  n = s.size();
  dp[0][0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i + 1; ++j) {
      for (int cnt = 0; cnt <= j * (i + 1 - j); ++cnt) {
        dp[1][j][cnt] = n;   
      }
    }
    for (int j = 0; j <= i; ++j) {
      for (int cnt = 0; cnt <= j * (i - j); ++cnt) {
        dp[1][j + 1][cnt] = min(dp[1][j + 1][cnt], dp[0][j][cnt] + (s[i] != '0'));
        dp[1][j][cnt + j] = min(dp[1][j][cnt + j], dp[0][j][cnt] + (s[i] != '1'));
      }
    } 
    swap(dp[0], dp[1]);
  }
  int cnt0 = count(s.begin(), s.end(), '0');
  cout << dp[0][cnt0][cnt0 * (n - cnt0) / 2] / 2 << '\n';
}

1860E - Fast Travel Text Editor

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int INF = 1e9;
const int AL = 26;
 
struct query{
	int f, t, ans;
};
 
struct edge{
	int u, w;
};
 
int main() {
	cin.tie(0);
	iostream::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size();
	
	int m;
	cin >> m;
	vector<query> a(m);
	forn(i, m){
		cin >> a[i].f >> a[i].t;
		--a[i].f, --a[i].t;
		a[i].ans = abs(a[i].f - a[i].t);
	}
	
	int k = n - 1 + AL * AL;
	vector<vector<edge>> g(k);
	forn(i, n - 1){
		int j = n - 1 + (s[i] - 'a') * AL + (s[i + 1] - 'a');
		g[i].push_back({j, 0});
		g[j].push_back({i, 1});
		if (i > 0){
			g[i].push_back({i - 1, 1});
			g[i - 1].push_back({i, 1});
		}
	}
	
	for (int st = n - 1; st < k; ++st){
		vector<int> d(k, INF);
		d[st] = 0;
		deque<int> q;
		q.push_back(st);
		while (!q.empty()){
			int v = q.front();
			q.pop_front();
			for (auto it : g[v]){
				if (d[it.u] <= d[v] + it.w) continue;
				d[it.u] = d[v] + it.w;
				if (it.w == 0) q.push_front(it.u);
				else q.push_back(it.u);
			}
		}
		forn(i, m){
			a[i].ans = min(a[i].ans, d[a[i].f] + d[a[i].t] - 1);
		}
	}
	
	forn(i, m) cout << a[i].ans << '\n';
	return 0;
}

1860F - Evaluate RBS

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int INF = 1e9;
 
struct bracket{
	int a, b, c;
};
 
struct point{
	int x, y;
};
 
long long cross(const point &a, const point &b){
	return a.x * 1ll * b.y - a.y * 1ll * b.x;
}
 
long long dot(const point &a, const bracket &b){
	return a.x * 1ll * b.a + a.y * 1ll * b.b;
}
 
bool operator <(const point &a, const point &b){
	return cross(a, b) > 0;
}
 
int main() {
	int t;
	cin >> t;
	while (t--){
		int n;
		cin >> n;
		vector<bracket> val;
		forn(i, 2 * n){
			int a, b;
			string c;
			cin >> a >> b >> c;
			val.push_back({a, b, c[0] == '(' ? 1 : -1});
		}
		map<point, vector<int>> opts;
		forn(i, 2 * n) forn(j, 2 * n){
			int dx = val[i].b - val[j].b;
			int dy = val[j].a - val[i].a;
			if (dx <= 0 || dy <= 0) continue;
			opts[{dx, dy}].push_back(i);
			opts[{dx, dy}].push_back(j);
		}
		opts[{1, INF}];
		vector<int> ord(2 * n), rord(2 * n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&](int i, int j){
			long long di = dot({INF, 1}, val[i]);
			long long dj = dot({INF, 1}, val[j]);
			if (di != dj) return di < dj;
			return val[i].c > val[j].c;
		});
		forn(i, 2 * n) rord[ord[i]] = i;
		int neg = 0, cur = 0;
		vector<int> bal(1, 0);
		for (int i : ord){
			cur += val[i].c;
			bal.push_back(cur);
			neg += cur < 0;
		}
		bool ans = neg == 0;
		vector<int> prv;
		for (auto it : opts){
			vector<int> tot = prv;
			for (int x : it.second) tot.push_back(x);
			sort(tot.begin(), tot.end(), [&](int i, int j){
				return rord[i] < rord[j];
			});
			tot.resize(unique(tot.begin(), tot.end()) - tot.begin());
			for (int x : tot) neg -= bal[rord[x] + 1] < 0;
			vector<int> tmp = tot;
			sort(tot.begin(), tot.end(), [&](int i, int j){
				long long di = dot(it.first, val[i]);
				long long dj = dot(it.first, val[j]);
				if (di != dj) return di < dj;
				return val[i].c > val[j].c;
			});
			vector<int> nrord(tot.size());
			forn(i, tot.size()) nrord[i] = rord[tmp[i]];
			forn(i, tot.size()) rord[tot[i]] = nrord[i];
			for (int x : tot){
				bal[rord[x] + 1] = bal[rord[x]] + val[x].c;
				neg += bal[rord[x] + 1] < 0;
			}
			if (neg == 0){
				ans = true;
				break;
			}
			prv = it.second;
		}
		puts(ans ? "YES" : "NO");
	}
	return 0;
}

Comments (53)

Write comment?

Why_so_ez

8 months ago, # |

← Rev. 2 →

+10

Pardon me if this is a stupid question, In problem D, after dp is used, the editorial says the answer is in the dp[n][cnt0][need], why can't "need" also be equal to just cnt0*cnt1 instead of (cnt0*cnt1/2) because in 00011 its balanced and the number of 01 subsequences is cnt0*cnt1 so should'nt we also check dp[n][cnt0][cnt0*cnt1].Thanks

→ Reply

Ryehl

8 months ago, # ^ |

00011 is not balanced there are 6 subsequences of 01 but 0 subsequence of 10

ah fudge thanks a lot for answering

rumman_sust

00011 is not balanced unless you mean one of the resulting string after swap(s) is balanced. For example: 01010. In that case, the count of 01 & 10 is 3 which is equal to 3*2/2.

cpnoob1

In problem C, I used the approach of maximum increasing subsequence. If Alice puts the chip on ith number, BOB, in the next turn, will put it to the second smallest number in maximum increasing subsequence, and then Alice has to move to the smallest number in the next turn which makes BOB the winner.

so Alice can only win if the size of the maximum increasing subsequence is 1 till the ith number. so that bob has to move the chip to the smallest number and Alice wins.

I got the wrong answer on test case 2. Please help me to know why this approach did not work. Thanks in advance.

lakshya7878

Alice will not win if the length is 1, She'll only put the coin in first move on the i th element. Now Bob won't have anywhere to move that coin to, So Bob wins. Alice only wins if the length of the maximum increasing subsequence ending at ith element has the length 2 : she puts the coin on ith element, then Bob has to move it to the remaining 1 element, then Alice won't have any moves to make further.

ImStrong

Lets take an example:

arr = [1, 2, 3, 4]
Expected Answer: 1
Your Answer: 2

According to your solution position with value 2 and 4 will be lucky.

But if you see for the value 4, Bob will make a move to 2, Then Alice is forced to make a move to 1, and Bob can't make a move now. So Bob wins.

SlayerS

nvm

PCxOM

6 months ago, # ^ |

Thanks for the example, i had a similar issue

smalyarovsky

-15

It is now obviuos that this round had a problem with tests for task D. They were weak, tons of wrong greedy solutions got accepted and then hacked. Only an idiot would consider tests of such a quality normal. This is not okay, and I think the least authors owe to contestants is an apology for their sloppy work. Things like this should not be allowed by the community.

P.S.: Dear BledDest, I'm asking, I'm begging on my knees: please, don't make other posts about how wrong being toxic is. Because, as we've seen yesterday, sometimes if the author spends too much time fighting with toxicity in the community, he may not have enough time left to develop good tests for his problems.

P.P.S.: Don't mean to offend anybody. Make love, not crappy tests.

blitztage

-32

“Greedy makes man blind and foolish, and makes him an easy prey for death.”
-Rumi

transfermarket

Literally no one asked

-38

If the test were strong, you can just spamming greedy solution without proving it.

P/S: FST==Skill issue

P/s: BledDest don't listen to the idiot who can't prove his solution because of his skill issue and then blamming you for FST. Your contest is awesome.

-12

Maybe then we should remove all the tests? To assure nobody will send a solution without proving? Moron, submitting without a strong prove is a common thing in competitive programming, exactly because there are tests to tell if solution is right or wrong! And btw remind me, what harm is in someone spamming wrong greedy solution, getting a WA verdict and receiving extra penalty?

← Rev. 3 →

FST==skill issue

hahahahahahahaha

Anyway don't blame BledDest for your FST. Blame your skill issue.

If you blame him for FST then maybe there should be no hacking phrase and every solution passes pretest should pass all the test????????????

Actually, I think it is hard to make the test that break the solution without knowing them first.

-10

meme

chu65536

+32

This man speaks facts.

What is the point of tests if they accpet ideologically wrong solutions? More than 20% of solutions were hacked right after the contest. Need to pretend that everything is okay and not pay attention to it?

i_love_turtles

OMG Lucy in cyberpunk O.o

szdytom

+28

There is also a $$$O(n^4/\omega)$$$ approach for D:

Let's say the imbalance score of a string is the difference between the number of 01 and 10 sequences. Then the desired string should have a imbalance score of 0. There are two observations:

You will never operate on a position twice, and you will never operate on two zeros or ones.
By swapping a pair of 0 and 1 at position $$$(p, q)$$$, the imbalance score increases/decrease by $$$2 \times(p-q)$$$, no matter what substring is between the pair.

So you can calculate the imbalance score of the initial string and then do a backpack with bitset. In detail, let $$$S_0$$$ denote the set of position where there are 0s initially, and $$$S_1$$$ the set of position where there are 1s initially, and $$$d$$$ to be imbalance score of the initial string.

By observation 2, the task is now transformed into this: find the minimal $$$k$$$ such that you can select exactly $$$k$$$ numbers from each of $$$S_0$$$ and $$$S_1$$$, so that the sum of the $$$k$$$ numbers selected from $$$S_0$$$ is exactly $$$d/2$$$ greater than the sum of the $$$k$$$ numbers selected from $$$S_1$$$.

https://codeforces.com/contest/1860/submission/219317671

kookeudas

but, why is it always mimimum cnt of exchanges that 0 and 1 in order if (cnt of 01) > (cnt of 10)?

IceNagisa

I think it's $$$O(n^4/\omega)$$$ though much faster than std

You are correct, I've just updated the comment.

kunalsrv20

Hey, can you elaborate more about "backpack with bitset"? Is it some technique ? Any useful link will be appreciated !!

1854B - Earn or Unlock uses this trick.

B.i.b.e.r

it is stored in dp(n,cnt0,need) , where cnt0 is equal to the number of characters 0 in the string s , and need=cnt0⋅cnt12 (because the number of subsequences 01 should be equal to the number of subsequences 10). But our dynamic programming stores the number of changes in the string, and the problems asks for the minimum number of swaps. However, we can easily get it from the dp value. Since the amounts of zeroes and ones are fixed in the string, then the number of changes from 0 to 1 equals to the number of changes from 1 to 0 and we can pair them up. So, the answer to the problem is the half of the dp value.

Can anyone explaine me how need is equal to c0*c1 also how storing string changes helps in calculating answer?Please

Khaled47

Take for example, n = 5 c0 = 3 and c1 = 2. To maximize the number of 01s, we can take the string 00011. Here the maximum number of 01s is 3*2 = 6, and the minimum number of 10s is 0. Our objective is to reach the middle where the number of 01s = number of 10s = 0+c0*c1/2 = c0*c1/2.

THanks for reply ,i got half but still confused like why we need to create string of form 00001111 like how does it gaurnatees minimlaity for swaps.This is the only correlation I am finding hard to understand.

We dont need to create a string of the form 00001111. The maximum value that the number of 01s and 10s can take is when it is of this form. The thing that guarantees the minimality of swaps is the dynamic programming algorithm he wrote where we have a subproblem of the form (i,cnt0,cnt01). The minimum value is at (n,number of zeros in string , c0*c1/2) which is when the number of 01s in the string is of value c1*c0/2 and so is the number of 10s.

Got it bro thanks

trgt26

In problem C, How is it solved using Binary Indexed Tree or Segment tree? What is the logic?

i_m_swachha

Segment tree or BIT was used to calculate the "Longest Increasing Subsequence" size from 1 to index i for all i from 1 to n.

https://codeforces.com/contest/1860/submission/219290618

Is this code calculating "Longest Increasing Subsequence"?

The code is checking if the size of the "LIS" is 2 from index 1 to index i if we must take the i'th element. But it is not calculating the actual size.

MountainKing

-35

Very late Editorial.

konahamaru

What can be the best complexity in problem C, if we would allow repetitions in the array?

people_plus_plus

But the solution will be the same

mega_bot

Can anyone explain the problem D solution?

Rafi

In problem D, Is there any way to solve it with recursive dp?

+11

Yes: 219363424

mihleonid

There is alternative solution with recursive dp. In my opinion, it is harder (but possible) to proof that it is not TL (Time Limit) exceeding solution. 219620926

The complexity of recursive DP is O(n^4). But there won't be more than 100*100*5000(c0*c1*d) states. Actually it is even smaller than that, because c0+c1<=100. Plus the time limit was 2 seconds and there was no multiple test cases.

Harshit_Raj_14

-7

I solved two problems during the contest and upsolved the third one. Here I would like to share my approach in them.

Problem A — Not a Substring Just one simple fact is enough that in the two cases of a valid bracket sequence (((...))) and ()()()... there is only one common substring "()". Otherwise having s in one of them surely makes the other situation our answer t.

Problem B — Fancy Coins This was a very interesting problem and I would like to call my approach a greedy+compromise method. First we act by spending all ak coins, then a1 coins. Then we find the number of fancy coins used as the first case. Another case we deal with is where we compromise by spending lesser a1 coins and more fancyk coins. The minimum of the two situations will be the answer.

Problem C — Game on Permutation The perfect strategy for Alice to win will be a condition a[j]>a[i] for every j<i. And it should occur only once in any subarray. That's the perfect winning strategy for Alice. For that to happen, we take two variables: firstmin(fm) and secondmin(sm). If our current element becomes something like: sm<curr && curr<fm If we find the above condition, then curr is a winning position for Alice, and we will update curr=sm and move forward.

If you want to read a much detailed solution, here's my in-depth written editorial on it — https://medium.com/@Harshit_Raj_14/educational-codeforces-round-153-rated-for-div-2-editorial-a286eda94f5c

Also the codes are available on my github repo — https://github.com/Harshit-Raj-14/My-Codeforces-Solution/tree/main/Educational%20Codeforces%20Round%20153%20(Rated%20for%20Div.%202)

Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing articles.

LeoPro

The rotating sweep line intuition in F is cumbersome and not so easy to think about. I find the following way to be more easy and intuitive (Well, they are equivalent, but I don't like rotating sweeplines).

Sorting pairs $$$(a, b)$$$ by $$$ax + by$$$ is the same as sorting pairs by $$$a + b\cdot \frac{y}{x}$$$. Now you can replace $$$\frac{y}{x}$$$ with any positive real $$$t > 0$$$, and you sort pairs by $$$a + b\cdot t$$$. From now it's obvious, that initially you arrange the pairs lexicographically ($$$t = +\varepsilon$$$), and then gradually increase $$$t$$$, the pairs that are swapped are of kind $$$(a_1, b_1)$$$ and $$$(a_2, b_2)$$$, where $$$a_1 < a_2, b_1 > b_2$$$ (and the swap is performed for $$$t = \frac{a_2 - a_1}{b_1 - b_2}$$$).

manitianajay45

Finally new Color(CM).

Video Editorial for Problem D,E:-

https://youtu.be/khVG1JPdR1o

Video Editorial for Problem A,B,C:-

https://youtu.be/wZF5qfvBhuM

aditya_108

Explanation for those who are confused in Problem E why the author has not constructed a transposed graph to find out the distance from f -> s :

Let say we are connecting an edge of weight 1 when we are going from dummy node to an index node and an edge of weight 0 from index node to dummy node. When we are finding shortest distance from dummy node to index node then bfs on the normal graph will work. It is obvious.

But when we are finding shortest distance from index node to dummy node then we should apply bfs from the index node. But we can't do that as it will result in O(n^2) complexity. Alternative is that we can apply bfs from dummy node in the transposed graph and find the shortest path for each index node. So the complexity is now reduced.

But it is not necessary to construct the transposed graph. Edges between index nodes are already bidirectional. In transposed graph, from dummy to index we will have an edge weight of 0 now . In the original graph, we are getting an extra edge weight as from dummy to index we are traversing via edge weight 1 and rest all edges in path have the same effect.

So we can use the original distance and reduce it by 1.

Hope it helps !!

Track-Days

Problem D. Let dp[i][z][b] = min number of swaps to make first i characters balanced given that we have seen z zeros so far and the number of 01s — 10s so far is b. Now let's assume that s[0...i] is balanced after performing some number of operations. Let's also assume that s[i + 1] = 1. Then the introduction of the character s[i + 1] increases the "balance" by z (the number of previously seen zeros). Presumably, this balance may be fixed in only 1 swap. However this isn't obvious to me at all. Someone help please!

-1e11

7 months ago, # |

BledDest Sorry for necroposting. For Problem F, I would like make a clarification to the problem statement by asking what the expected output is given the following test case:

According to the second paragraph of your problem statement, we may choose $$$(x, y) = (1, 1)$$$ so all the $$$a_i \cdot x + b_i \cdot y$$$ are $$$5$$$ and place them in ()() since it's a tie. However, the sample solution written by awoo above outputs NO instead.

Thanks a lot!

BledDest

7 months ago, # ^ |

+20

This test case is given in incorrect format. There are $$$2n$$$ points in the problem, not $$$n$$$, so the number in the second line should be $$$2$$$.

If you change it to $$$2$$$, then the model solution says YES.

Thanks for your replying and sorry for making such a stupid mistake...

fancybear527

6 months ago, # |

In Problem B. It is nowhere written what is used for fancy coins.

Graffolyon

4 months ago, # |

Hint1

Hint2

If a[i] < a[j] given j < i will a[i] be unlucky. Maintain two variables lucky and unlucky. lucky store min lucky number till index i. unlucky store min unlucky number till index i Now for i check
If lucky < a[i] then a[i] is unlucky. Update unlucky=min(unlucky,a[i]) .
Otherwise if unlucky < a[i] then a[i] is lucky. Update lucky=min(lucky,a[i])

Submission : 237228234

Mavis

4 months ago, # ^ |

Double ke jalwe har jagah dikh rahe h OoO

awoo's blog