2026A - Perpendicular Segments
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (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;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (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';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (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();
}
Idea: shnirelman
Tutorial
Tutorial is loading...
Solution (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));
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (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';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (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;
}
Maybe problems with single algorithms and tricks are not fit for edu round? :(
Trump is gonna win in a landslide damn
are constructive problems that bad?
Now I think there is no difference between Div.2 Round and Edu Round.
But the last problem in this contest is actually more difficult than most div.1 problems
I like your profile picture
I believe yesterday's contest was excessively difficult for educational rounds. In my opinion, it was the hardest educational round of all time. You can view the statistics from Clist: smash me.
UPD: Sorry for misunderstanding. I didn't saw that it wasn't updated.
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.
Alternate Solution for C in O(n) time -> https://mirror.codeforces.com/contest/2026/submission/288737415
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.
Well you just use the number present at 0 for a previous item instead of the left pointer's item so you decrement that
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
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)
For problem F ,
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
But I dont see anything like that in the code. I dont think the code is actually wrong but please correct my mistake.
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.
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)$$$
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))
both segments need to be longer than K
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.
Elegant
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.
This makes sense thank you
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)
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
This is really elegant, thank you!
I feel like editorial's code for D is too much complicated, it could have been much simpler 288580929.
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 <= ffor 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
What was the O(n) solution for B?
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
If you are struggling to write good A problems, I can put some time in order to help.
What is the O(n) Solution of B. ?
First, notice that we only paint a cell that isn't listed if and only if
Nis odd. Otherwise, just join adjacent cells & output the maximum distance out of all the pairs. For oddN, 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 evenNwith the remainingN-1cells. This can be done efficiently inO(N)by maintaining a prefix & suffix max of connecting pairs of cells leading to a particular cell.Code: 288522179
B also has a O(nlogn) solution : https://pastebin.com/AWNxu6MN
Can you give some hints about doing B in O(n)?
You can maintain prefix and suffix max and check for each element being removed. Obviously, you do this when $$$n$$$ is odd.
Did anyone get AC for E using a randomised approach? This was my closest, WA on test 34.
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.
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
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 ?