Разбор Educational Codeforces Round 154

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		string s;
		cin >> s;
		if(s.find("1") < s.find("3"))
			cout << 13;
		else
			cout << 31;
		cout << endl;
	}
}

1861B - Две бинарных строки

Идея: Roms

Разбор

Решение (Roms)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        string a, b;
        cin >> a >> b;
        bool ok = false;
        for (int i = 0; i + 1 < a.size(); ++i) {
            if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') {
                ok = true;
            }
        }
        
        if (ok) 
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

1861C - Запросы к массиву

Идея: BledDest

Разбор

Решение 1 (Roms)

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200000;
 
int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        string s;
        cin >> s;
        int maxSortedPref = 0;
        int minNotSortedPref = 0;
        int bal = 0;
        bool good = true;
        
        for (auto c : s) {
            if (c == '+') {
                ++bal;
            } else if (c == '-') {
                --bal;
                maxSortedPref = min(maxSortedPref, bal);
                if (bal < minNotSortedPref)
                    minNotSortedPref = 0;
            } else if (c == '1') {
                maxSortedPref = max(maxSortedPref, bal);
            } else {
                if (bal <= 1) {
                    good = false;
                    break;
                }
                if (minNotSortedPref == 0 || minNotSortedPref > bal)
                    minNotSortedPref = bal;
            }
            if(minNotSortedPref <= maxSortedPref && minNotSortedPref != 0) {
                good = false;
                break;
            }
        }
        
        if (good)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

Решение 2 (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
vector<int> has0, has1;
vector<vector<int>> g;
 
bool ans;
 
bool dfs(int x, int d)
{
	if(has0[x] && (has1[x] || d <= 1))
		ans = false;
	bool res = false;
	for(auto y : g[x])
		res |= dfs(y, d + 1);
	if(has0[x] && res)
		ans = false;
	return res || has1[x];
}
 
void solve()
{
	ans = true;
	has0.push_back(0);
	has1.push_back(0);
	g.push_back(vector<int>());
	int ts = 1;
	
	string s;
	cin >> s;
	vector<int> st = {0};
	for(auto x : s)
	{
		int cur = st.back();
		if(x == '0')
			has0[cur] = 1;
		if(x == '1')
			has1[cur] = 1;
		if(x == '+')
		{
			g[cur].push_back(ts);
			st.push_back(ts);
			ts++;
			has0.push_back(0);
			has1.push_back(0);
			g.push_back(vector<int>());
		}
		if(x == '-')
			st.pop_back();
	}
	
	dfs(0, 0);
	cout << (ans ? "YES\n" : "NO\n");
	
	has0.clear();
	has1.clear();
	g.clear();
}
 
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
		solve();
}

1861D - Сортировка умножением

Идея: Roms

Разбор

Решение (Roms)

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200 * 1000 + 5;
 
int t;
int n;
int a[N];
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc){
    	cin >> n;
    	for (int i = 0; i < n; ++i)
    	    cin >> a[i];
    	
    	int cnt = 0;
    	for (int i = 1; i < n; ++i)
    	    cnt += (a[i - 1] >= a[i]);
    	    
    	int res = n, cnt2 = 0;
        for (int i = 0; i <= n; ++i) {
            bool isMultipliedByNegative = (i > 0);
            res = min(res, isMultipliedByNegative + cnt + cnt2);
            
            if (i + 1 < n)
                cnt -= (a[i] >= a[i + 1]);
            if (i > 0)
                cnt2 += (a[i - 1] <= a[i]);
        }
        
        cout << res << endl;
    }
}

1861E - Непересекающиеся подперестановки

Идея: BledDest

Разбор

Решение (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 sub(int x, int y)
{
	return add(x, -y);
}
 
int mul(int x, int y)
{
	return (x * 1ll * y) % MOD;
}
 
int binpow(int x, int y)
{
	int z = 1;
	while(y > 0)
	{
		if(y & 1) z = mul(z, x);
		x = mul(x, x);
		y /= 2;
	}
	return z;
}
 
int main()
{
	int n, k;
	cin >> n >> k;
	int ans = 0;
	vector<vector<int>> dp(n + 1, vector<int>(k, 0));
	dp[0][0] = 1;
	for(int i = 0; i < n; i++)
	{
		int cur = 0;
		for(int j = k - 1; j >= 1; j--)
		{
			cur = add(cur, dp[i][j]);
			dp[i + 1][j] = cur;
		}
		for(int j = k - 1; j >= 0; j--)
		{
			int nxt = (j + 1) % k;
			dp[i + 1][nxt] = add(dp[i + 1][nxt], mul(dp[i][j], k - j));
		}
		ans = add(ans, mul(dp[i + 1][0], binpow(k, n - (i + 1))));
	}
	cout << ans << endl;
}

1861F - Четыре масти

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
const int K = 4;
const int N = 2 * int(1e6) + 43;
 
pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
	return make_pair(a.first + b.first, a.second + b.second);
}
 
pair<long long, long long> operator-(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
	return make_pair(a.first - b.first, a.second - b.second);
}
 
// prefix sums for an array of pairs
vector<pair<long long, long long>> pref_sums(const vector<pair<long long, long long>>& a)
{
	int n = a.size();
	vector<pair<long long, long long>> ans(n);
	ans[0] = a[0];
	for(int i = 1; i < n; i++)
		ans[i] = ans[i - 1] + a[i];
	return ans;
}
 
// for an array of pairs denoting linear functions, evaluate
// them in the corresponding points
vector<long long> eval(const vector<pair<long long, long long>>& a)
{
	int n = a.size();
	vector<long long> ans(n);
	for(int i = 0; i < n; i++)
		ans[i] = a[i].first * i + a[i].second;
	return ans;
}
 
void solve()
{
	int n;
	scanf("%d", &n);
	vector<vector<int>> a(n, vector<int>(K));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < K; j++)
			scanf("%d", &a[i][j]);
	vector<int> b(K);
	for(int i = 0; i < K; i++)
		scanf("%d", &b[i]);
	
	int deck_size = 0;
	for(int i = 0; i < K; i++)
		deck_size += b[i];
	
	// calculate the remaining number of cards for each player
	long long full = deck_size;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < K; j++)
			full += a[i][j];
	vector<int> remain(n, full / n);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < K; j++)
			remain[i] -= a[i][j];
	
	// for every player, calculate the maximum number of cards
	// they already have among all suits
	// and store it in a multiset
	vector<int> min_val(n);
	for(int i = 0; i < n; i++)
		min_val[i] = *max_element(a[i].begin(), a[i].end());
	multiset<int> min_vals;
	for(int i = 0; i < n; i++)
		min_vals.insert(min_val[i]);
	
	// for every mask of suits and every player, calculate
	// the number of cards in those suits they already have
	vector<vector<int>> already_has(1 << K, vector<int>(n));
	for(int mask = 0; mask < (1 << K); mask++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < K; j++)
				if(mask & (1 << j))
					already_has[mask][i] += a[i][j];
	// for every mask of suits and every player, calculate the
	// maximum value of x such that if that player can receive 
	// no more than x cards in each suit, the vertex of that
	// player should belong to T in the cut
	vector<vector<int>> max_x(1 << K, vector<int>(n));
	for(int mask = 0; mask < (1 << K); mask++)
		for(int i = 0; i < n; i++)
		{
			int suits = __builtin_popcount(mask);
			if (suits == 0) max_x[mask][i] = N - 2;
			else
			{
				// incoming edges have capacity of
				// x - a[i][j]
				int incoming = -already_has[mask][i];
				// outgoing edge has capacity of remain[i]
				// find the maximum x such that
				// suits * x + incoming < remains[i]
				int x = (remain[i] - incoming) / suits;
				x = min(x, N - 2);
				max_x[mask][i] = x;
			}
		}
	
	// for every mask and for all players, calculate the sum of 
	// values they add to the cut if they can have no more than
	// x cards of each suit in the mask
	vector<vector<long long>> add_to_cut(1 << K, vector<long long>(N));
	for(int mask = 0; mask < (1 << K); mask++)
	{
		int suits = __builtin_popcount(mask);
		vector<pair<long long, long long>> aux(N);
		for(int i = 0; i < n; i++)
		{
			// for the i-th player, they add remains[i] to
			// the minimum cut if x > max_x[mask][i]
			// otherwise, they add
			// suits * x - already_has[mask][i]
			int incoming = -already_has[mask][i];
			// add [suits * x - incoming] on segment [0, max_x]
			int x = max_x[mask][i];
			pair<long long, long long> f1 = {suits, incoming};
			aux[0] = aux[0] + f1;
			aux[x + 1] = aux[x + 1] - f1;
			// add remain[i] on [max_x + 1, N)
			pair<long long, long long> f2 = {0, remain[i]};
			aux[x + 1] = aux[x + 1] + f2;
			aux[N - 1] = aux[N - 1] - f2;
		}
		// sum up those functions and evaluate them
		add_to_cut[mask] = eval(pref_sums(aux));
	}
	
	// now we're ready to solve the problem!
	vector<int> ans(n);
	// iterate on the player we want to maximize
	for(int i = 0; i < n; i++)
	{
		// iterate on the suits they will maximize
		for(int j = 0; j < K; j++)
		{
			int d = min(remain[i], b[j]);
			int max_cards = a[i][j] + d;
			b[j] -= d;
			// find the maximum current score over all others
			min_vals.erase(min_vals.find(min_val[i]));
			int max_rival = *min_vals.rbegin();
			min_vals.insert(min_val[i]);
			if(max_rival >= max_cards)
				ans[i] = max(ans[i], 0);
			else
			{
				// binary search on the maximum cards over all
				// opponents
				int L = max_rival - 1;
				int R = max_cards;
				while(R - L > 1)
				{
					int mid = (L + R) / 2;
					long long min_cut = 1e18;
					long long req_flow = deck_size - remain[i];
					// iterate on the mask of suit vertices
					// which belong to S
					for(int mask = 0; mask < (1 << K); mask++)
					{
						int suits = __builtin_popcount(mask);
						long long cur_cut = 0;
						for(int z = 0; z < K; z++)
							if(!(mask & (1 << z)))
								cur_cut += b[z];
						cur_cut += add_to_cut[mask][mid];
						// don't forget to discard our player
						// from the flow network!
						if(mid > max_x[mask][i])
							cur_cut -= remain[i];
						else
						{
							long long add = mid * suits - already_has[mask][i];
							cur_cut -= add;
						}
						min_cut = min(min_cut, cur_cut);
					}
					if(min_cut < req_flow)
						L = mid;
					else
						R = mid;
				}
				ans[i] = max(ans[i], max_cards - R);
			}
			b[j] += d;
		}
	}
	
	for(int i = 0; i < n; i++)
		printf("%d ", ans[i]);
	puts("");
}
 
int main()
{
	int t = 1;
	for(int i = 0; i < t; i++) solve();
}

#include <iostream> #include <vector> #include <string> #include <set> #include <map> #include <queue> #include <deque> #include <algorithm> #include <cmath> #include <iomanip> #include <string.h> using namespace std; typedef long long ll; typedef vector<ll> vi; typedef pair<int,int> pi; #define F first #define S second #define PB push_back #define MP make_pair #define REP(i,a,b) for (int i = a; i <= b; i++) int KadaneAlgorithm(const vector<int>& array) { int best = 0, sum = 0; for (int k = 0; k < array.size(); k++) { sum = max(array[k], sum + array[k]); best = max(best, sum); } return best; } int main() { ios::sync_with_stdio(0); cin.tie(0); ll t; cin >> t; while(t--) { ll n; cin >> n; vi a(n); for(int i = 0 ;i < n ;i++) { cin >> a[i]; } vi pref(n,0); pref[0] = 1; ll res = 0; //cout << 1 << " "; for(int i = 1 ;i < n ;i++) { pref[i] = pref[i-1] + (a[i] >= a[i-1]); // cout << pref[i]<<" "; } //cout << endl; ll sum = 0; for(int i = 1 ; i < n ;i++) { if(a[i] <= a[i-1]) res++; } for(int i = n - 2 ; i >= 0;i--) { if(a[i] >= a[i+1]) { sum++; // cout << sum << endl; } pref[i] += sum; } for(int i = 0 ;i < n ;i++) { // cout << pref[i] << " "; } //cout << endl; for(int i = 0 ;i < n ;i++) { res = min(res,pref[i]); //cout <<pref[i] + ((n- (i+1)) - (pref[n-1] - pref[i]) )<<endl; } cout << res << endl; } return 0; }

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

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

SunnyYuan2009

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

← Rev. 3 →

+27

These solutions explain very clearly.

I'm sad I didn't AC problem D, but it is interesting!

→ Ответить

Dr.Mahareeq

+15

thanks for the tutorial

Kirilliym

+12

Good problems, thanks for the round!

BledDest

+13

Переводы разборов на русский скоро появятся (в течение 40 минут). Прошу прощения за задержку.

imprayas12

← Rev. 2 →

"BledDest is a graph theory lunatic" had me cracked up.

1ightwhite

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

The point is that the sentence's coming from himself.

JohanXLiebert

Test 3,682nd test case->great work in testing!

ash88

D was looking hard but it is easy

areke

Another easy way to implement E is to just combine the last two states into one. So $$$dp_{i,j}$$$ counts how many of arrays of length $$$i$$$ exist such that the number of elements on the suffix we use is $$$x \equiv j \pmod k$$$ and the current cost of the array is $$$c = j\ /\ k$$$. Then the transitions are the same, but you just reset the partial sum whenever $$$j \equiv 0 \pmod k$$$ since you can never transition to a lower cost.

Submission: 221342327

Aftershock007

Thanks this is really helpful

attky

In problem C, if you have : ++++1-0 when we verify the number elements in the array we have 3 elements but the array has to be sorted.

Edit : I misunderstood the second condition

otiko_lagadze

during contest i had some trouble implementing C (i had same idea as described in approach 1) and using segment trees seemed easier to me. Idea is identical as described in approach 1 but it was easier for me to implement this way, so i thought of sharing it: code.

butterflies

Hi all, it would really help if you can post some insights/hints for the problems of this contest on https://starlightps.org ! Here's a link to the problems: https://starlightps.org/problems/collection/cf-edu-154/. This will help us get more data so users can have a platform to:

share/discover hints/insights on various problems
find similar problems given insights they struggled with.

Check it out if you're interested. Thanks!

ddamel

awoo,BledDest I think in tutorial of problem E, in the paragraph before the last, you should have written: "difference is: $$$dp_{i,j,c}$$$", instead of $$$dp_{i,j+1,c}$$$

because we have according to the second type of transitions

$$$dp_{i+1,j} <== d_{i,j} + d_{i,j+1} + ... + dp_{i,k-1}$$$

$$$dp_{i+1,j+1} <== d_{i,j+1} + d_{i,j+2} + ... + dp_{i,k-1}$$$

difference: $$$dp_{i+1,j}-dp_{i+1,j+1} = dp_{i,j}$$$ and not $$$dp_{i,j+1}$$$

I hope I'm not mistaking, but correct me if I'm wrong...

thx

Thank you, this is an error. Will be fixed in a couple of minutes

Siyah

woww clear editorial , tnx awoo , BledDest

I_FloPPed21

at problem B wouldnt the example a = 00010000 b = 00011111 give a no?

ignore the question I didnt read that it ends with 1 and starts with 0

MohamedSameh

thank you for the editorial It was really helpful, I have a question How on earth did you come up with that idea of the last x elements on problem E, You assumed some number and built the dp table on the assumed number, it is my first time to see such a thing I Don't think this sort of things come from practice, and the amazing thing is that most of accepted solutions are the same idea, Is that I'm too dump or you are too smart? Thank You :D

Sparsely

The title for D in the tutuorial text is Russian, not English. awoo fix it pls, thx

stalkkk_19

Hey Author,

I am in trouble to get the Problem B

according to me for the test case

1
1000101
1000100

I am not able to find the way to make this same : (

but according to the Author code

it is printed YES

Can anyone know how to make this equal ??

anonymous_yuvi

According to the question .. both the strings should start with 0 and end with 1's.

So your test case is wrong.

k200154

What's wrong with this solution for C?

1xx55

In your code dealing with '-' :

if (!unsorted.empty() && elements < unsorted.back())
            unsorted.pop_back();

IF shoule be replaced by WHLIE , for the cases like this : ++++000-1 , you need to pop back more than once.

Then your code will get accepted. :)

Ahmed_Ashraf_f

Any one could help me I don't know what is the wrong in this solution

https://codeforces.me/contest/1861/submission/221355113

++++1-0

thanks

Noobish_Monk

Can someone please explain, what is the partial sum technique mentioned in E and why is it true?

detective...dots

← Rev. 6 →

For problem D can someone explain how can this be sorted in 4 operations? n = 9, a = [10 5 10 9 6 9 8 9 5]

Srbmaury

l=1,r=2,x=3   30  15  10  9  6  9  8  9  5 
l=1,r=4,x=-1 -30 -15 -10 -9  6  9  8  9  5
l=7,r=8,x=2  -30 -15 -10 -9  6  9 16 18  5
l=9,r=9,x=4  -30 -15 -10 -9  6  9 16 18 20

Thanks

grand__warden

Problem C Approach 1(Roms) Can anyone explain why we need to check it after each query? After each query, we can just check that the longest sorted prefix is shorter than the shortest non-sorted prefix

zym

If the current query is '1', then make longest sorted prefix equal current length, which is consistent with the current query. And the shortest non-sorted prefix is consistent with the previous queries. If longest sorted prefix is shorter than the shortest non-sorted prefix, it means the current query is valid based on the previous queries.

If the current query is '0', then make shortest non-sorted prefix=min(shortest non-sorted prefix, cur_length), which is consistent with the current query. Then check the inequality.

armennarkoman

Seems like this editorial doesn't explain why there is no better solution in problem D, which makes prefix with length x negative by several multiplications on negative number

hydra_cody

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

← Rev. 4 →

HELP, Can anyone prove the solution to Problem D. Why does this approach give an optimal solution? Thanks.

Shaadsajjad

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

Why Was My Submission Skipped Despite Submitting First https://codeforces.me/blog/entry/120756

jaineshmachhi

Can anyone help me in which test case is this solution going wrong it shows WA on 303 (test case 3)

lyh3.14

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

I have an easier solution for E.

We can use dp in one dimension. Dp[i] means how many arrays with length i has the subarray from i-k+1 to i, which contains integers 1~k. Fac[i] means the factorial from 1 to i. Pw[i] means the i-th power of k.Every time, dpi has initial value fac[k] * pw[i-k]， because we chose number from 1~k optionally to fill the position 1 ~ i-k+1, and from 1-k+1 to i, the ways is equal to an arrangement of 1~k.

But this may cause duplication, for example. n = 4, k = 3 and for the array 1 2 3 1, we will calculate the contribution in both dp[3] and dp[4], but the cost of this array is 1. To solve this, when we calculate dp[i], we need to minus dp[j] which j is from i — k + 1 to i — 1. Actually we need to minus dp[j] * fac[i-j] because dp[j] only caluculate array of length j. From the position j+1 to i, the ways we fill it is equal to an arrangement of 1~i-j.

Submission: Code

DuongForeverAlone

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

Your solution is brilliant, although I don't know why the answer is sum of all dp[i] * Pow(k, n — i). It looks like taking any possible from the rest n — i elements, but it will be confused, as I don't know whether there is any duplication or not. Could you explain this part?

Alex_Sense1

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

In the BledDest approach for problem C, specifically in this line:
"In terms of our tree, it means that a vertex marked with 0 has an ancestor (possibly itself) marked with 1."
Shouldn't it be the other way? find a vertex marked with 1 that has an ancestor marked with 0?

Fugally787

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

For C, what about the condition where something that is unsorted, is a prefix of something that's unsorted? Isn't that an automatic 'NO' as well?

For example, we have a 1, then we delete some characters without adding any, then we have a 0. That couldn't happen.

DangKhoizzzz

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

someone know why this submission keep wrong on test 3 problem C pls

my submission

jrsak_vrmr

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

Can anyone tell me where am i doing wrong this is d question.

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

can anyone please help awoo

TheLostCookie

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

For problem E, after some experimentation, the following relationship seems to be true for $$$m > k$$$:

$$$dp_{m,j} = k!\text{ }dp_{m-k,j} + \sum_{i=1}^{k-1}{(k-i)(i-1)!dp_{m-i,j}}, j=0,1,2,\dots,k-1$$$

where $$$dp_{i,j}$$$ is defined as in the editorial.

This can be proven with induction, but can someone offer a mathematical interpretation for the formula?

(Using this equation alongside $$$ans_n = k\text{ }ans_{n-1} + dp_{n,0} $$$ gives an $$$\mathcal{O}(k\text{ }log\text{ }k\text{ }log\text{ }n)$$$ solution to E via the standard problem of finding the $$$n$$$ th term of a linear recurrence relation.)

RANJAN888

Nice explanation

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