Разбор Educational Codeforces Round 171

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3904
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3494
8	Um_nik	3396
9	gamegame	3386
10	maroonrk	3350

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

2026A - Перпендикулярные отрезки

Разбор

Решение (adedalic)

#include<bits/stdc++.h>
using namespace std;
 
int main() {
	int t; cin >> t;
	while (t--) {
		int X, Y, K;
		cin >> X >> Y >> K;
		int M = min(X, Y);
		cout << "0 0 " << M << " " << M << endl;
		cout << "0 " << M << " " << M << " 0" << endl;
	}
}

2026B - Черные клетки

Идея: BledDest

Разбор

Решение (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    
    long long ans = 1e18;
    
    auto upd = [&](vector<long long> a) {
      sort(a.begin(), a.end());
      for (int i = 1; i < (int)a.size(); ++i)
        if (a[i - 1] == a[i]) return;
      long long res = 0;
      for (int i = 0; i < (int)a.size(); i += 2)
        res = max(res, a[i + 1] - a[i]);
      ans = min(ans, res);
    };
    
    if (n % 2 == 0) {
      upd(a);
      cout << ans << '\n';
      continue;
    }
    
    for (int i = 0; i < n; ++i) {
      for (int x : {-1, 1}) {
        a.push_back(a[i] + x);
        upd(a);
        a.pop_back();
      }
    }
    
    cout << ans << '\n';
  }
}

2026C - Коллекционные фигурки

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 400043;
char buf[N];
 
bool can(const string& s, int k)
{
    int n = s.size();
    vector<int> used(n);
    for(int i = n - 1; i >= 0; i--)
        if(k > 0 && s[i] == '1')
        {
            used[i] = 1;
            k--;
        }
    int cur = 0;
    for(int i = 0; i < n; i++)
        if(used[i])
        {
            cur--;
            if(cur < 0) return false;
        }
        else cur++;
    return true;
}   
 
void solve()
{
    int n;
    scanf("%d", &n);
    scanf("%s", buf);                         
    if(n == 1)
    {
        puts("1");
        return;
    }
    string s = buf;
    int count_1 = 0;
    for(auto x : s) if (x == '1') count_1++;
    int l = 1;
    int r = count_1 + 1;
    while(r - l > 1)
    {
        int mid = (l + r) / 2;
        if(can(s, mid))
            l = mid;
        else
            r = mid;
    }
    long long ans = 0;
    for(int i = n - 1; i >= 0; i--)
        if(s[i] == '1' && l > 0)
            l--;
        else
            ans += (i + 1);
    printf("%lld\n", ans);
}
 
int main()
{
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++)
        solve();
}

2026D - Суммы на отрезках

Идея: shnirelman

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int n;
 
vector<long long> a;
vector<long long> pa;
vector<long long> ppa;
vector<long long> start;
vector<long long> block;
vector<long long> pblock;
 
vector<long long> prefix_sums(vector<long long> v)
{
 	int k = v.size();
 	vector<long long> res(k + 1);
 	for(int i = 0; i < k; i++) res[i + 1] = res[i] + v[i];
 	return res;
}
 
long long get_partial(int l, int r1, int r2)
{
	// s(l, r1) + s(l, r1 + 1) + ... + s(l, r2 - 1)
 	if(r2 <= r1) return 0ll;
 	int cnt = r2 - r1;
 	long long rem = pa[l] * cnt;
 	long long add = ppa[r2 + 1] - ppa[r1 + 1];
 	return add - rem;
}
 
pair<int, int> convert(long long i)
{
	int idx = upper_bound(start.begin(), start.end(), i) - start.begin() - 1;
	pair<int, int> res = {idx, i - start[idx] + idx};
	return res; 	
}
 
long long query(long long l, long long r)
{
	pair<int, int> lf = convert(l);
	pair<int, int> rg = convert(r);
	long long res = pblock[rg.first + 1] - pblock[lf.first];
	if(lf.second != lf.first) res -= get_partial(lf.first, lf.first, lf.second);
	if(rg.second != n - 1) res -= get_partial(rg.first, rg.second + 1, n);
	return res;	
}
 
int main()
{
	scanf("%d", &n);
	a.resize(n);
	for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
	pa = prefix_sums(a);
	ppa = prefix_sums(pa);
	start = {0};
	for(int i = n; i >= 1; i--)
		start.push_back(start.back() + i);
	block.resize(n);
	for(int i = 0; i < n; i++)
		block[i] = get_partial(i, i, n);
	pblock = prefix_sums(block);
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
	 	long long l, r;
	 	scanf("%lld %lld", &l, &r);
	 	printf("%lld\n", query(l - 1, r - 1));
	}
 
}

2026E - Лучшая подпоследовательность

Идея: BledDest

Разбор

Решение (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
#define sz(a) int((a).size())
 
template<typename T = int>
struct Dinic {
  struct edge {
    int u, rev;
    T cap, flow;
  };
  
  int n, s, t;
  T flow;
  vector<int> lst;
  vector<int> d;
  vector<vector<edge>> g;
  
  Dinic() {}
  
  Dinic(int n, int s, int t) : n(n), s(s), t(t) {
    g.resize(n);
    d.resize(n);
    lst.resize(n);
    flow = 0;
  }
 
  void add_edge(int v, int u, T cap, bool directed = true) {
    g[v].push_back({u, sz(g[u]), cap, 0});
    g[u].push_back({v, sz(g[v]) - 1, directed ? 0 : cap, 0});
  }
 
  T dfs(int v, T flow) {
    if (v == t) return flow;
    if (flow == 0) return 0;
    T result = 0;
    for (; lst[v] < sz(g[v]); ++lst[v]) {
      edge& e = g[v][lst[v]];
      if (d[e.u] != d[v] + 1) continue;
      T add = dfs(e.u, min(flow, e.cap - e.flow));
      if (add > 0) {
        result += add;
        flow -= add;
        e.flow += add;
        g[e.u][e.rev].flow -= add;
      }
      if (flow == 0) break;
    }
    return result;
  }
 
  bool bfs() {
    fill(d.begin(), d.end(), -1);
    queue<int> q({s});
    d[s] = 0;
    while (!q.empty() && d[t] == -1) {
      int v = q.front(); q.pop();
      for (auto& e : g[v]) {
        if (d[e.u] == -1 && e.cap - e.flow > 0) {
          q.push(e.u);
          d[e.u] = d[v] + 1;
        }
      }
    }
    return d[t] != -1;
  }
 
  T calc() {
    T add;
    while (bfs()) {
      fill(lst.begin(), lst.end(), 0);
      while((add = dfs(s, numeric_limits<T>::max())) > 0)
        flow += add;
    }
    return flow;
  }
};
 
const int B = 60;
const int INF = 1e9;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int s = n + B, t = n + B + 1;
    Dinic mf(t + 1, s, t);
    for (int i = 0; i < n; ++i) {
      long long x;
      cin >> x;
      mf.add_edge(s, i, 1);
      for (int j = 0; j < B; ++j) {
        if ((x >> j) & 1) mf.add_edge(i, j + n, INF);
      }
    }
    for (int i = 0; i < B; ++i) mf.add_edge(i + n, t, 1);
    cout << n - mf.calc() << '\n';
  }
}

2026F - Мороженое в Бермарте

Идея: BledDest

Разбор

Решение (awoo)

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int P = 2000 + 5;
 
struct item{
	int p, t;
};
 
struct minstack {
	stack<item> st;
	stack<array<int, P>> dp;
	int get(int p) {return dp.empty() ? 0 : dp.top()[p];}
	bool empty() {return st.empty();}
	int size() {return st.size();}
	void push(item it) {
		if (empty()){
		    dp.push({});
		    for (int i = 0; i < P; ++i)
		        dp.top()[i] = 0;
		}
		else{
		    dp.push(dp.top());
		}
		st.push(it);
		for (int i = P - it.p - 1; i >= 0; --i)
			dp.top()[i + it.p] = max(dp.top()[i + it.p], dp.top()[i] + it.t);
	}
	void pop() {
		st.pop();
		dp.pop();
	}
	item top() {
		return st.top();
	}
	void swap(minstack &x) {
		st.swap(x.st);
		dp.swap(x.dp);
	}
};
 
struct mindeque {
	minstack l, r, t;
	void rebalance() {
		bool f = false;
		if (r.empty()) {f = true; l.swap(r);}
		int sz = r.size() / 2;
		while (sz--) {t.push(r.top()); r.pop();}
		while (!r.empty()) {l.push(r.top()); r.pop();}
		while (!t.empty()) {r.push(t.top()); t.pop();}
		if (f) l.swap(r);
	}
	int get(int p) {
		int ans = 0;
		for (int i = 0; i <= p; ++i)
			ans = max(ans, l.get(i) + r.get(p - i));
		return ans;
	}
	bool empty() {return l.empty() && r.empty();}
	int size() {return l.size() + r.size();}
	void push_front(item it) {l.push(it);}
	void push_back(item it) {r.push(it);}
	void pop_front() {if (l.empty()) rebalance(); l.pop();}
	void pop_back() {if (r.empty()) rebalance(); r.pop();}
	item front() {if (l.empty()) rebalance(); return l.top();}
	item back() {if (r.empty()) rebalance(); return r.top();}
	void swap(mindeque &x) {l.swap(x.l); r.swap(x.r);}
};
 
struct edge{
	int u, tp, p, t;
};
 
struct query{
	int i, p;
};
 
vector<vector<edge>> g;
vector<vector<query>> qs;
vector<int> ans;
mindeque ks;
 
void dfs(int v){
	for (auto& [i, p] : qs[v]){
		ans[i] = ks.get(p);
	}
	for (auto& [u, tp, p, t] : g[v]){
		if (tp == 0){
			dfs(u);
		}
		else if (tp == -1){
		    auto it = ks.front();
		    ks.pop_front();
			dfs(u);
			ks.push_front({it.p, it.t});
		}
		else{
			ks.push_back({p, t});
			dfs(u);
			ks.pop_back();
		}
	}
}
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int q;
	cin >> q;
	vector<int> st(1);
	vector<int> where(q, -1);
	int cnt = 1, cnt_real = 1;
	where[0] = 0;
	g.push_back({});
	qs.push_back({});
	
	auto copy_shop = [&](int x, bool real){
		g.push_back({});
		qs.push_back({});
		st.push_back(st[x]);
		if (real){
			where[cnt_real] = cnt;
			++cnt_real;
		}
		++cnt;
	};
	
	forn(i, q){
		int tp, x;
		cin >> tp >> x;
		--x;
		int v = where[x], u = -1;
		if (tp != 4){
			copy_shop(v, tp == 1);
			u = cnt - 1;
		}
		if (tp == 1){
			g[v].push_back({u, 0, -1, -1});
			continue;
		}
		if (tp == 3){
			g[v].push_back({u, -1, -1, -1});
			++st[u];
			where[x] = u;
			continue;
		}
		int p;
		cin >> p;
		if (tp == 4){
			qs[v].push_back({i, p});
			continue;
		}
		int t;
		cin >> t;
		g[v].push_back({u, 1, p, t});
		where[x] = u;
	}
	
	ans.assign(q, -1);
	dfs(0);
	forn(i, q) if (ans[i] != -1) cout << ans[i] << '\n';
	return 0;
}

#include <bits/stdc++.h> #define int long long using namespace std; const int inf = 1e18; void ac() { int n; cin >> n; string s; cin >> s; s.insert(s.begin(), '0'); int r = n * (n + 1) / 2, t = n; for (int i = n; i > 0; i--) if (s[i] == '1') { if (min(i, t) > 1) t = min(i, t) - 2, r -= i; } cout << r << endl; } signed main() { cin.tie(0)->sync_with_stdio(0); int t; cin >> t; while (t--) ac(); }

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

Написать комментарий?

fight_for_NoConstructive

8 дней назад, # |

← Rev. 2 →

Maybe problems with single algorithms and tricks are not fit for edu round? :(

→ Ответить

123gjweq2

8 дней назад, # ^ |

-11

Trump is gonna win in a landslide damn

can_anyone_be_ORZ

are constructive problems that bad?

chenhongrui

Now I think there is no difference between Div.2 Round and Edu Round.

-15

But the last problem in this contest is actually more difficult than most div.1 problems

peacebringer167

7 дней назад, # ^ |

I like your profile picture

YouKnowCipher

← Rev. 8 →

-74

Any ideas or approaches on how to solve the 4th (D) problem? I’m not finding any hints to proceed.

djm03178

It says the round was last updated 9 hours ago, so it was during system testing. You can see that https://clist.by/standings/educational-codeforces-round-171-rated-for-div-2-54382517/ has only ACs made before ~15 min yet. There's no way these problems were that hard.

I appreciate your clarification. It really helps me understand the reasoning behind it.

KIMJONGOOF

-8

Alternate solution for C in O(n) time.

-> https://codeforces.me/contest/2026/submission/288737415

-16

Alternate Solution for C in O(n) time -> https://codeforces.me/contest/2026/submission/288737415

Elfen_Lied_Opening

If anyone did C using 2 pointers and iterate the input string right to left can you explain your approach? I can't understand why we move the left pointer to the left when we hit a 0.

Krrishchanchal

Well you just use the number present at 0 for a previous item instead of the left pointer's item so you decrement that

SkibidiPilav

Check my submission for left to right approach with 2 queues. I guess you could replace the queues with 2 pointers and it could be like a 2 pointer approach

K_vinay_123

Do C really need Binary Search. I wasn't able to solve c during contest because of wasting time on B due to miss reading the problem. My solution link.As a pupil for me I no where thought of Binary Search and I have seen most of the submissions were O(n)

FatihCihan

For problem F ,

struct mindeque {
        //...
	int get(int p) {
		int ans = 0;
		for (int i = 0; i <= p; ++i)
			ans = max(ans, l.get(i) + r.get(p - i));
		return ans;
	}
        //...
};

When we call get(p) , it returns a subset value with a price exactly p. Because each time it is checking for i from l , and p-i from r. What happens when we want a price not equal to p but below p ? To resolve this issue we should probably make something like

if(dp[i] == 0){
    dp[i] = dp[i-1];
}

But I dont see anything like that in the code. I dont think the code is actually wrong but please correct my mistake.

awoo

The $$$\mathit{dp}$$$ array is initialized with all zeros. You can think of it as "pay $$$i$$$ coins to get an icecream with tastiness $$$0$$$". Since you can do this for all $$$i$$$, you can turn buying a subset with total price below $$$p$$$ into exactly $$$p$$$ by buying this empty item with the remainder of the coins. I guess I will add this to the editorial.

I see , thats a clever trick. Thanks for the help.

brxteforceman

problem $$$A$$$ can also reasoned with the fact that for perpendicular lines $$$slope_{AB}*slope_{CD}=|1|$$$.

try, fixing first segment $$$AB$$$ to $$$(0,0)$$$ and $$$(x,y)$$$ for ease. now $$$slope_{AB} = y/x$$$.

to make them perpendicular to each other, we want to do $$${y/x}*{x/y} =1$$$ therefore $$$slope_{CD}=x/y$$$ $$$(0,x)$$$ and $$$(y,0)$$$. but it may be possible that the $$$x$$$ or $$$y$$$ values that we are selecting (by swapping in $$$CD$$$) are greater than those allowed in the constraints.

as a result, we can only do $$$min(x,y)$$$ as maximum value to satisfy this construction .therefore, we set $$$x=y=min(x,y)$$$

harshitsoora

← Rev. 3 →

Please correct me if wrong.

Consider this example (x, y) = (9, 3). Now consider lines -

AB (0, 0) -> (9, 3) :- size = sqrt(90), slope = 1/3

CD (0, 3) -> (1, 0) :- size = sqrt(10), slope = -3

These are perpendicular but one line is greater than min(x, y) * sqrt(2) !!

I believe the test cases are wrong to evaluate the problem, and solution exist outside of square box (0, 0) -> (min(x, y), min(x, y))

zrnstnsr

both segments need to be longer than K

shsh

A very simple solution exists for C:

Essentially, we want to get the most expensive toys for free so we iterate the days in reverse order. On day i, if we can visit the shop and there are at least two unbought toys, we buy toy i and the cheapest toy not bought yet. Otherwise, toy i must have been bought on a subsequent day.

Nathan4

Elegant

valavshonok

Problem C The greedy O(n) solution

Of all the figures, we will take some of them for free.

For each figure from this set, we must have a figure to the left, for which we will pay.
Of all the figures that we can take for free, it is advantageous for us to take the most expensive ones.

Let's go from right to left and maintain the number of figures taken for free that have not yet found a pair.

Let cnt be the number of figures that need to be paired.

If s[i] == 1, then we can try not to pay for the ith figure, this is possible if there are enough figures on the left to cover the needs of all the free figures taken before, for which there has not yet been a pair and another + 1 (a pair for the ith figure) If cnt < i, then we will take the ith figure for free, and increase cnt by 1.

Otherwise, we are obliged to pay for this figure, then we can pair it with one of the ones taken for free, or just buy it.

Code

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	long long ans = 0, cnt = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == '1' && cnt < i) {
			cnt++;
			continue;
		}
		cnt = max(cnt - 1, 0ll);
		ans += i + 1;
	}
	cout << ans << '\n';
}

This makes sense thank you

Enderbrine16

Why the line cnt = max(cnt - 1, 0ll);? Why decrement count as you move from right to left?

this is the number of characters that we took for free, but have not yet found a pair of them that we will pay for. when we pay for the symbol i, we can pair it with the free symbol, which means making cnt = max(cnt — 1 and 0)

ay012

do you have a proof why greedy gives the min answer , i know its intuitive but how to show that the case of not doing greedy will not make a better answer as such ? how to show its always best to free from rigthmost ? the binary search is easy to prove because we are fixing length of free items , but here we dont have any such constraint in our hand in greedy sol

_regular_show

This is really elegant, thank you!

BiggestOtaku

I feel like editorial's code for D is too much complicated, it could have been much simpler 288580929.

chaihard

I felt the explanation given for D was quite intuitive and what I thought suring the contest. Do you mind explaining your approach for D in short?

Firstly this problem can be seen as difference of two types of sums, till(r) - till(l-1).

The blocks of type (1, x), (2, x) ... each can be calculated by first calculating the value for (1, x) then removing contribution of a[1], a[2]...

Also I used additional array (psps) in which psps[i] = s(1, 1) + s(1, 2) +.... s(1, i), can be calulated as prefix_array of prefix_array of a

For calculating till(f) for say some f first terms, we can locate the number of blocks used in O(log(n)) as (2 * n + 1 - i) * (i) / 2 <= f for i blocks used.

Now some remaining terms are left, let them be f2 = f - (2 * n + 1 - i) * (i) / 2 (i is the number of blocks used).

Now the terms left are s(i + 1, i + 1), s(i + 1, i + 2), ... s(i + 1, i + f2) [First f2 terms of i + 1th block]

using prefix array of a if we add prefix sum of first i terms of a to all these terms, these is sum becomes s(1, i + 1), s(1, i + 2) ... s(1, i + f2), this can be calculated using the psps array I introduced earlier.

So sum of first f terms if first i blocks are used and f2 extra terms is

till(f) = prefix_sum_of_blocks[i] + (psps[i + f2] - psps[i]) - f2 * (ps[i])

Editorial's explanation is fine, its just I feel uneasy seeing long codes

Ylandolsi

add hints please

19Doors

What was the O(n) solution for B?

knightFighterr

for every query most of the work can be easily done in O(1). The only thing that takes is finding the index pair (i,j) (S[i,j]) from the index given in queries. Which can be done in both O(1) i.e by using quadratic equation root and O(logn), i.e by using binary search

If you solve it using quad equations. the conde complexity goes upto O(q).

for n%2=0 its trivial, and for n%2=1, you can calculate prefix maxima for difference of pairs and also calculate suffix maxima for the same thing, and then take the minimum of the maximum of the 2 values for all odd elements, and thats the answer

rmz

+14

If you are struggling to write good A problems, I can put some time in order to help.

roronoa_2z

What is the O(n) Solution of B. ?

biximo

First, notice that we only paint a cell that isn't listed if and only if N is odd. Otherwise, just join adjacent cells & output the maximum distance out of all the pairs. For odd N, since we are coloring at most 1 cell that isn't on the list black, this is equivalent to taking out 1 cell, connecting that with an adjacent cell (which is equivalent to a distance of 1), and solving the problem for even N with the remaining N-1 cells. This can be done efficiently in O(N) by maintaining a prefix & suffix max of connecting pairs of cells leading to a particular cell.

Code: 288522179

AaravSin

3 дня назад, # ^ |

i committed the amateur mistake of thinkinG we can pair a cell more than once. Maybe they could have explicitly mentioned one cell can be painted black only once/

compounding

B also has a O(nlogn) solution : https://pastebin.com/AWNxu6MN

mohit_here

Can you give some hints about doing B in O(n)?

synthborne

You can maintain prefix and suffix max and check for each element being removed. Obviously, you do this when $$$n$$$ is odd.

Po00iu6

SamuelTull

Did anyone get AC for E using a randomised approach? This was my closest, WA on test 34.

Thirvin

+12

However, we can rewrite popcount(x) as 60−zeroes(x), where zeroes(x) is equal to the number of bits equal to 0 among the first 60 bits in x. So, we have to maximize the value of k+zeroes(x).

I am curious about 'maximize the value of k+zeroes(x)'.
Shouldn't be 'maximize the value of k+zeroes(x)-60'?
Why there's no mention about minus 60 and in code?

UPD:
I saw it.
when calculating the answer it uses 'n-max_flow' which already remove the effect of 60 bits.

Axial-Tilted

n — max_flow is a simplified equation of (n + 60 — max_flow) — 60 this is more intuitive to think about the (n + 60 — max_flow) is your value and u are subtracting 60 because for each bit in the 60 its either zero and added 1 which it should add or 1 and added 0 which it should subtract 1

7 дней назад, # |

why is n too small in problem E ? even the worst bipartite graph matching algorithms work in n^3 also for this problem specifically we have small V and small E so whats the reasoning behind not using 500 or 800 ?

yashkhsgvt

6 дней назад, # |

Just a dumb question, but because of it I struggle with question "B". If n is even, I don't thing solution of it is so simple.

Let assume case like this [ 2, 100,101,102]. In this case if we paint wall [1,2,100,101,102] then it is possible to to keep k=1.

Only issue is we have to paint wall 101 twice for which I didn't saw any limitation in question.

Feel free to let me know if I miss something or I made a error with the analysis.

AMBUJ_2003

5 дней назад, # ^ |

In question, it was stated, "choose two white cells i and j"

so u cant pick an already coloured cell

hamossa

does anyone know why this solution 289069335 for b is wrong?

neatshit

5 дней назад, # |

can someone explain the working of binary search approach for D , like the jiangly's code , almost seems like binary search on answer , but i am not able to get it .

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