Educational Codeforces Round 155 — 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

Idea: Roms

Tutorial

Solution (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 - Chips on the Board

Idea: BledDest

Tutorial

Solution (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 - Make it Alternating

Idea: Roms

Tutorial

Solution (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 - Sum of XOR Functions

Idea: Roms

Tutorial

Solution (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 - Interactive Game with Coloring

Idea: BledDest

Tutorial

Solution (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 - Last Man Standing

Idea: BledDest

Tutorial

Solution (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;
}

Your code here... #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> arr(n); for(int i=0; i<n; i++){ cin>>arr[i]; } int ans = 0; int mul = 1; for(int i=0; i<32; i++){ int c_odd = 0; bool odd = false; for(int j=0; j<n; j++){ if((arr[j] & (1<<i))>0){ odd = (!odd); } if(odd){ c_odd++; } } for(int j=0; j<n; j++){ ans += (c_odd*mul); if((arr[j]&(1<<i))){ c_odd = (n-j-c_odd); } } mul*=2; } cout<<ans<<endl; return 0; }

Comments (35)

Write comment?

masonpop

7 months ago, # |

Clear editorial!

→ Reply

lightmon

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

7 months ago, # ^ |

It's now in the right place now

AbdulRahmanLuai

the editorial link in the contest problems is wrong, (problem c).

vmpyr

D was pretty fun

Agreed

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

Has_Aim

if the i-th bit is on then it contribute to the sum as (1 << i).

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!

kkd_6969

can someone explain D, such that we are taking L as fixed and varying R, then incorporating the length of the subarray factor? please tell me the distance update in this code (code for XOR sum of all subarray)

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

not_wiz

In problem D, can someone please explain how are they handling 1 in (r — l + 1) while computing the answer ?

moghit_ad

I'm having the same problem over the past two days.

i can get the Xor sum of all subarrays but intervalls is pretty hard for me .

did you get it ?

I inferred it this way.

As we know (r — l + 1) is the length of the subarray and we are computing the prefix sums on the bits-array comprising of 0s and 1s. If you look at the editorial code, the sumOfL[x] denotes the sum of lengths of subarray where parity of count of 1s is x. Now, if for the given r, let say there are 3 subarrays with odd count of 1s. Then our ans is (1 << b) * 3 * r — (1 << b) * (sum of l values for those 3 subarrays). We compute length from the difference of lengths of subarray ending at r — subarray ending at l.

Hope that helps or atleast give you some direction.

drakefake785

can someone explain why have we considered every number as 0 or 1 in PROBLEM D.i could'nt understand the editorial.it would be really helpful.

madghostek

We do this to find out how much each bit contributes to the final answer. We are xoring a bunch of different segments of the original array, but we know the numbers, and we know which of those numbers have n-th bit set. This means we can very quickly find out which segments $$$[l;r]$$$ will have the bit set after xoring, prefix sum can answer that. We also know the length of those segments, the $$$(r-l+1)$$$ factor, so we have everything, after calculating it on single bits you need to construct the answer back by shifting to left, and summing up all those answers for different bits.

I think the hardest thing in this problem is noticing that the prefix sum allows to find all the "working" segments for given bit, but there's no way to do that without taking the numbers apart into single bits.

If this still doesn't help, solve an example where the numbers are actually all 0 and 1, because it's easy to follow.

Oh now I understood. Thanks for clarification.

M-Manas-s

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

Bnahmad15

6 months ago, # ^ |

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

ashueep

6 months ago, # |

← 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!

5 months ago, # ^ |

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

3 months ago, # |

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

11 days ago, # |

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

BledDest's blog