Разбор Educational Codeforces Round 155

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

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

Идея: Roms

Разбор

Решение (Roms)


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

const int N = 109;

int t;
int n;
int s[N], e[N];
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> s[i] >> e[i];
        }
        
        bool ok = true;
        for (int i = 1; i < n; ++i) 
            if (s[i] >= s[0] && e[i] >= e[0])
                ok = false;
        
        if (!ok) {
            puts("-1");
            continue;
        }
        
        cout << s[0] << endl;
    }
    return 0;
}

1879B - Фишки на доске

Идея: BledDest

Разбор

Решение (Neon)


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

using li = long long;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<li> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    li mnA = *min_element(a.begin(), a.end());
    li sA = accumulate(a.begin(), a.end(), 0LL);
    li mnB = *min_element(b.begin(), b.end());
    li sB = accumulate(b.begin(), b.end(), 0LL);
    li ans = min(mnA * n + sB, mnB * n + sA);
    cout << ans << '\n';
  }
}

1879C - Чередуй!

Идея: Roms

Разбор

Решение (Roms)


#include <bits/stdc++.h>

using namespace std;

const int MOD = 998'244'353;

void upd(int &a, int b) {
    a = (a * 1LL * b) % MOD;
}


int t;
string s;

int main() {
	cin >> t;
	for (int tc = 0; tc < t; ++tc) {
	    cin >> s;
	    int res = 1;
	    int k = s.size();
	    int n = s.size();
	    for (int l = 0; l < n; ) {
	        int r = l + 1;
	        while(r < n && s[l] == s[r])
	            ++r;
            upd(res, r - l);
            --k;
            l = r;
	    }
	    
	    for (int i = 1; i <= k; ++i)
	        upd(res, i);
        cout << k << ' ' << res << endl;
	}
}

1879D - Сумма функций XOR

Идея: Roms

Разбор

Решение (Roms)


#include <bits/stdc++.h>

using namespace std;

const int N = 300005;
const int MOD = 998244353;
int n;
int a[N];

void add(int &a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
}

int sum(int a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
    if (a < 0)
        a += MOD;
    return a;
}

int mul(int a, int b) {
    return (a * 1LL * b) % MOD;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    
    int res = 0;    
    for (int b = 0; b < 30; ++b) {
        int cur = 0;
        vector <int> cnt(2);
        vector <int> sumOfL(2);
        cnt[0] = 1;
        int x = 0;
        for (int i = 0; i < n; ++i) {
            x ^= ((a[i] >> b) & 1);
            int sumOfR = mul(cnt[x ^ 1], i + 1);
            add(cur, sum(sumOfR, -sumOfL[x ^ 1]));
            
            ++cnt[x];
            add(sumOfL[x], i + 1);
        }
        
        add(res, mul(1 << b, cur));
    }
    
    cout << res << endl;
}

1879E - Интерактивная игра с раскраской

Идея: BledDest

Разбор

Решение (BledDest)


#include<bits/stdc++.h>

using namespace std;

const int N = 123;

int n;
int color[N];
int countColors[N][N];
int p[N];
vector<int> g[N];
int deg[N];

void add_edge(int x, int y)
{
	g[x].push_back(y);
	g[y].push_back(x);
}

bool tryTwoColors()
{
	int v1 = n + 1;
	int v2 = n + 2;
	for(int i = 2; i <= n; i++)
	{
		if(p[i] != 1)
		{
			add_edge(i, p[i]);
		}
	}
	for(int i = 2; i <= n; i++)
	{
		if(deg[i] == 1)
			add_edge(i, v1);
	}
	for(int i = 2; i <= n; i++)
	{
		if(p[i] != 1 && deg[p[i]] == 1)
			add_edge(i, v2);
	}
	add_edge(v1, v2);
	bool bad = false;
	for(int i = 2; i <= n + 2; i++)
		if(color[i] == 0)
		{
			color[i] = 1;
			queue<int> q;
			q.push(i);
			while(!q.empty())
			{
				int k = q.front();
				q.pop();
				for(auto y : g[k])
				{
					if(color[y] == 0)
					{
						color[y] = 3 - color[k];
						q.push(y);
					}
					else if(color[y] == color[k])
						bad = true;
				}
			}
		}
	if(bad)
		for(int i = 2; i <= n + 2; i++)
			color[i] = 0;
	return !bad;
}

void tryThreeColors()
{
	for(int i = 2; i <= n; i++)
		if(p[i] == 1)
			color[i] = 1;
		else
			color[i] = (color[p[i]] % 3) + 1;
}

int findVertex(const vector<int>& colors)
{
	int s = colors.size();
	for(int i = 2; i <= n; i++)
	{
		if(vector<int>(countColors[i], countColors[i] + s) == colors)
			return i;
	}
	return -1;
}

int main()
{
	cin >> n;
	for(int i = 2; i <= n; i++)
	{
		cin >> p[i];
		deg[p[i]]++;
	}
	
	if(*max_element(p + 2, p + n + 1) == 1)
	{
		for(int i = 2; i <= n; i++)
			color[i] = 1;
	}
	else if (!tryTwoColors())
		tryThreeColors();
	
	int colorsUsed = *max_element(color + 2, color + n + 1);
	
	cout << colorsUsed << endl;
	for(int i = 2; i <= n; i++)
	{
		cout << color[i];
		if(i == n) cout << endl;
		else cout << " ";
	}
	cout.flush();
	
	for(int i = 2; i <= n; i++)
	{
		countColors[i][color[i]]++;
		countColors[p[i]][color[i]]++;
	}
	
	while(true)
	{
		int resp;
		cin >> resp;
		if(resp == -1 || resp == 1)
			exit(0);
		vector<int> counts(colorsUsed + 1);
		for(int i = 1; i <= colorsUsed; i++)
			cin >> counts[i];
		int v = findVertex(counts);
		assert(v != -1);
		cout << color[v] << endl;
		cout.flush();
	}
}

1879F - Остаться в живых

Идея: BledDest

Разбор

Решение (awoo)


#include <bits/stdc++.h>

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

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n;
		scanf("%d", &n);
		vector<int> h(n), a(n);
		forn(i, n) scanf("%d", &h[i]);
		forn(i, n) scanf("%d", &a[i]);
		int mxa = *max_element(a.begin(), a.end()) + 1;
		
		int l = mxa == 1 ? 0 : (__lg(mxa - 1) + 1);
		vector<vector<pair<int, int>>> st(l, vector<pair<int, int>>(mxa, make_pair(0, -1)));
		vector<vector<int>> st2(l, vector<int>(mxa));
		forn(i, n){
			if (h[i] > st[0][a[i]].first){
				st2[0][a[i]] = st[0][a[i]].first;
				st[0][a[i]] = {h[i], i};
			}
			else if (h[i] > st2[0][a[i]]){
				st2[0][a[i]] = h[i];
			}
		}
		
		auto combine = [&st, &st2](int i, int x, int y){
			int mx = max(st[i][x].first, st[i][y].first);
			if (mx == st[i][x].first)
				return max(st2[i][x], st[i][y].first);
			return max(st[i][x].first, st2[i][y]);
		};
		
		for (int j = 1; j < l; ++j) forn(i, mxa){
			if (i + (1 << (j - 1)) < mxa){
				st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
				st2[j][i] = combine(j - 1, i, i + (1 << (j - 1)));
			}
			else{
				st[j][i] = st[j - 1][i];
				st2[j][i] = st2[j - 1][i];
			}
		}
		vector<int> pw(mxa + 1);
		for (int i = 2; i <= mxa; ++i) pw[i] = pw[i / 2] + 1;
		
		auto getmx = [&st, &pw](int l, int r){
			int len = pw[r - l];
			return max(st[len][l], st[len][r - (1 << len)]);
		};
		auto getmx2 = [&st, &st2, &pw, &combine](int l, int r){
			int len = pw[r - l];
			if (st[len][l].second != st[len][r - (1 << len)].second)
				return combine(len, l, r - (1 << len));
			return max(st2[len][l], st2[len][r - (1 << len)]);
		};
		
		vector<long long> svmx(mxa), svmx2(mxa);
		vector<int> svwho(mxa, -1);
		for (int x = 1; x < mxa; ++x){
			for (int l = 1; l < mxa; l += x){
				int r = min(mxa, l + x);
				int ac = (l - 1) / x + 1;
				auto tmp = getmx(l, r);
				long long mx = tmp.first * 1ll * ac;
				int who = tmp.second;
				long long mx2 = getmx2(l, r) * 1ll * ac;
				if (who == -1) continue;
				if (mx > svmx[x]){
					svmx2[x] = svmx[x];
					svmx[x] = mx;
					svwho[x] = who;
				}
				else if (mx > svmx2[x]){
					svmx2[x] = mx;
				}
				svmx2[x] = max(svmx2[x], mx2);
			}
		}
		
		vector<long long> ans(n);
		forn(i, mxa) if (svwho[i] != -1)
			ans[svwho[i]] = max(ans[svwho[i]], svmx[i] - svmx2[i]);
		
		forn(i, n) printf("%lld ", ans[i]);
		puts("");
	}
	return 0;
}

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

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

masonpop

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

Clear editorial!

→ Ответить

lightmon

Clear Editorial, but it should have appeared in a more clear place lmao

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

It's now in the right place now

vmpyr

D was pretty fun

kauperwood

There is a question on task D, why we don't take into account carry-over units from previous digits when counting the i-th bit? Thanks in advance.

moyegege

There are no such carry-over units because it is the sum of XOR not plus(maybe)

Yes, I agree, but after XOR we also add them to each other and we have to take into account that the previous bits affect the current one

lizhanran

F was really fun

notaapoorv

In D's editorial, if pref(x) is equal to the number of ones on the prefix of length x modulo 2, then for even number of ones, shouldn't pref(x) be 0?

BledDest

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

keter

-21

E is so cringe

pranarudCF2023

For anyone else struggling to formalize why their intuition for B leads to an optimal arrangement of chips:

The key insight is what the tutorial notes -- a valid chip arrangement must satisfy either (1) each row has at least 1 chip or (2) each column has at least 1 chip.

Now, we have two cases.

Say we have a valid chip arrangement that satisfies (1). Then, we can make an arrangement that is as cheap or cheaper by removing any extra chips so that each row has exactly one chip (vs. at least one). From here, observe that the cheapest 1-chip-per-row arrangement is the one you get by picking the cheapest column and filling each cell in it with a chip. Any other 1-chip-per-row arrangement is more expensive because there will be a chip in the same row, but a more expensive column.

Similarly, say we have a valid chip arrangement that satisfies (2). Then, we can make an arrangement that is as cheap or cheaper by removing any extra chips so that each column has exactly one chip (vs. at least one). From here, observe that the cheapest 1-chip-per-column arrangement is the one you get by picking the cheapest row and filling each cell in it with a chip. Any other 1-chip-per-column arrangement will be more expensive because there will be a chip in the same column, but a more expensive row.

OmarAboutaleb77

+10

Proof of the insight: Suppose that there is at least one row missing and at least one column missing. You can then pick a cell such that the cells location is (missing row,missing col) which isn’t covered.

hazzlek

← Rev. 2 →

In problem F, it's not necessary to use a sparse table. It is enough to store 2 maximums for every suffix and for a segment [l, r] we can take suff max on [l, a]. This works because if exist some hj >= hi, where l <= i <= r and j > r, we will get j's real value in a different segment and this value will be definitely greater than i's

awoo

Oh, that's neat. Cool idea!

bestial-42-centroids

Thanks to the authors for their work on this round :)

Here is my advice about the problems

IanISam

Nsqrtn pass on F:225085205

M-Manas-s

How are we colouring a bamboo (All nodes having one child except the last one) in E ?

Bnahmad15

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

By the explanation, it will use three colors. 1 2 3 1 2 3 ...

ashueep

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

← Rev. 4 →

My approach on C: If we consider a maximal block of same character sequence of size say $$$l$$$ then the number of ways we can pick an element to survive in that block is $$$l$$$ ways, after which there exists $$$(l-1)!$$$ arrangements to delete the remaining elements in the block. Hence there exists a total of $$$(l - 1)! \times l = l!$$$ ways within the block to perform the valid operation. And if there are $$$k$$$ such blocks then there exists a total of $$$\prod_{i}^{k}l_{i}!$$$ valid operations.

This approach fails however, not sure why. Any help/corrections appreciated!

Did you figure it out?

I just thought of a counter example: 0011 expected answer: 8 because n-k = 2 -> 2!*2*2 = 8 The solution you provided is 4. Still not sure why it doesn’t work

So after thinking for a bit your solution only computes the number of ways to permute each group, in other words, the number of ways you can pick a number from each of the groups. It doesn’t take into account that you can select numbers from different groups before fully finishing one group (I don't know if that makes sense).

arundwivedi

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

Can someone please explain why the time complexity in D comes out to be nlogA? Shouldn't it be n^2logA?

We are going from l=1 to r for every r; that means (n^2)/2 linear time operations employing n^2 time complexity. Am I wrong some where?

kinitic013

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

Hey can any one help me out here, getting WA on testcase 6 for Problem D submission

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

Heh Solved it with new dp approach smirking check out this 263789195

_Untrackable_

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

can u explain ur dp approach?

7 недель назад, # ^ |

hey,for every bit i I created a binary array, where arr[x] is set if xth elements ith bit is set,then did some dp over that array (now i don't really remember exactly what i did back then but ) here first my aim was to calculate just f(l,r) on for every l,r possible on that binary array so lets say there are count number of pairs with xor set.answer contribution would be (2^i)*count , where i is ith bit of array , after that slight modification would add r-l+1 factor as well (initially my dp state was something like counting pairs with set and unset pretty easy transition. form there i moved toward solution)

harshith_04

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

I used a similar approach, check this once 276079653

much cleaner

Surge226

5 недель назад, # |

Sorry for necroposting, but in problem C can anyone explain that why changing of indices of other characters (after deleting some character) does not effect the answer?

Thanks

akashghadge

5 недель назад, # ^ |

This part of the editorial makes it clear. So even if we delete the char and index, the number of ways remains the same.

For example, let's consider that the string s=001100 and the chosen indices to erase are 1, 4 and 5. Then there are 3!=6 ways to choose the order of them:

1, 4, 5; 1, 5, 4; 4, 1, 5; 4, 5, 1; 5, 1, 4; 5, 4, 1.

4 недели назад, # ^ |

Ok got it now. Thanks.

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