Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
long long n;
cin >> n;
cout << max(6LL, n + 1) / 2 * 5 << '\n';
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
int W, H;
int x1, y1, x2, y2;
int w, h;
inline bool read() {
if(!(cin >> W >> H))
return false;
cin >> x1 >> y1 >> x2 >> y2;
cin >> w >> h;
return true;
}
inline void solve() {
int ans = INF;
if (x2 - x1 + w <= W) {
ans = min(ans, max(0, w - x1));
ans = min(ans, max(0, x2 - (W - w)));
}
if (y2 - y1 + h <= H) {
ans = min(ans, max(0, h - y1));
ans = min(ans, max(0, y2 - (H - h)));
}
if (ans == INF)
cout << -1 << endl;
else
cout << double(ans) << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
cout << fixed << setprecision(9);
int t; cin >> t;
while(t--) {
(read());
solve();
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int INF = 2e9 + 10;
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n;
scanf("%d", &n);
vector<vector<int>> a(2, vector<int>(n));
forn(i, 2) forn(j, n)
scanf("%d", &a[i][j]);
int ans = INF;
int sum1 = 0, sum2 = 0;
forn(i, n) sum1 += a[0][i];
forn(i, n){
sum1 -= a[0][i];
ans = min(ans, max(sum1, sum2));
sum2 += a[1][i];
}
printf("%d\n", ans);
}
}
1555D - Скажите палиндромам - нет!
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector<vector<int>> pr(6, vector<int>(n + 1));
string t = "abc";
int cur = 0;
do {
for (int i = 0; i < n; ++i)
pr[cur][i + 1] = pr[cur][i] + (s[i] != t[i % 3]);
++cur;
} while (next_permutation(t.begin(), t.end()));
while (m--) {
int l, r;
cin >> l >> r;
int ans = n;
for (int i = 0; i < 6; ++i)
ans = min(ans, pr[i][r] - pr[i][l - 1]);
cout << ans << "\n";
}
}
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int INF = 1e9;
vector<int> t, ps;
void push(int v){
if (v * 2 + 1 < int(ps.size())){
ps[v * 2] += ps[v];
ps[v * 2 + 1] += ps[v];
}
t[v] += ps[v];
ps[v] = 0;
}
void upd(int v, int l, int r, int L, int R, int val){
push(v);
if (L >= R)
return;
if (l == L && r == R){
ps[v] += val;
push(v);
return;
}
int m = (l + r) / 2;
upd(v * 2, l, m, L, min(m, R), val);
upd(v * 2 + 1, m, r, max(m, L), R, val);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
int get(){
return t[1] + ps[1];
}
struct seg{
int l, r, w;
};
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<seg> a(n);
forn(i, n){
scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);
--a[i].l, --a[i].r;
}
--m;
sort(a.begin(), a.end(), [](const seg &a, const seg &b){
return a.w < b.w;
});
t.resize(4 * m);
ps.resize(4 * m);
int ans = INF;
int j = 0;
forn(i, n){
while (j < n && get() == 0){
upd(1, 0, m, a[j].l, a[j].r, 1);
++j;
}
if (get() == 0){
break;
}
ans = min(ans, a[j - 1].w - a[i].w);
upd(1, 0, m, a[i].l, a[i].r, -1);
}
printf("%d\n", ans);
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
int n, q;
vector< array<int, 3> > es;
inline bool read() {
if(!(cin >> n >> q))
return false;
es.resize(q);
fore (i, 0, q) {
cin >> es[i][0] >> es[i][1] >> es[i][2];
es[i][0]--;
es[i][1]--;
}
return true;
}
vector< vector<pt> > g;
const int LOG = 19;
vector<int> up[LOG];
vector<int> tin, tout;
vector<int> xr;
int T = 0;
void dfs(int v, int p, int curXor) {
tin[v] = T++;
xr[v] = curXor;
up[0][v] = p;
fore (pw, 1, LOG)
up[pw][v] = up[pw - 1][up[pw - 1][v]];
for (auto [to, w] : g[v]) {
if (to == p)
continue;
dfs(to, v, curXor ^ w);
}
tout[v] = T;
}
void buildLCA() {
fore (pw, 0, LOG)
up[pw].resize(n);
tin.assign(n, -1);
tout.assign(n, -1);
xr.assign(n, 0);
T = 0;
fore (v, 0, n) {
if (tin[v] != -1)
continue;
dfs(v, v, 0);
}
}
int isPar(int p, int v) {
return tin[p] <= tin[v] && tout[v] <= tout[p];
}
int lca(int u, int v) {
if (isPar(u, v)) return u;
if (isPar(v, u)) return v;
for (int pw = LOG - 1; pw >= 0; pw--) {
if (!isPar(up[pw][v], u))
v = up[pw][v];
}
return up[0][v];
}
vector<int> par, rk;
void init(int n) {
par.assign(n, 0);
iota(par.begin(), par.end(), 0);
rk.assign(n, 1);
}
int top(int v) {
if (par[v] != v)
return par[v] = top(par[v]);
return v;
}
bool unite(int u, int v) {
u = top(u);
v = top(v);
if (u == v)
return false;
if (rk[u] < rk[v])
swap(u, v);
par[v] = u;
rk[u] += rk[v];
return true;
}
vector<int> F;
void inc(int pos, int val) {
for(; pos < sz(F); pos |= pos + 1)
F[pos] += val;
}
int sum(int pos) {
int ans = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
ans += F[pos];
return ans;
}
void addOnPath(int v, int l) {
while (v != l) {
inc(tin[v], 1);
inc(tout[v], -1);
v = up[0][v];
}
}
inline void solve() {
init(n);
g.resize(n);
vector<int> ans(q, -1);
fore (i, 0, q) {
int u = es[i][0];
int v = es[i][1];
int x = es[i][2];
if (unite(u, v)) {
ans[i] = 1;
g[u].emplace_back(v, x);
g[v].emplace_back(u, x);
}
}
buildLCA();
F.assign(2 * n + 5, 0);
fore (i, 0, q) {
if (ans[i] != -1)
continue;
ans[i] = 0;
int u = es[i][0];
int v = es[i][1];
int x = es[i][2];
int xorPath = xr[u] ^ xr[v];
if ((xorPath ^ x) != 1)
continue;
int l = lca(u, v);
int usedOnPath = sum(tin[u]) + sum(tin[v]) - 2 * sum(tin[l]);
if (usedOnPath > 0)
continue;
ans[i] = 1;
addOnPath(u, l);
addOnPath(v, l);
}
for (int res : ans)
cout << (res ? "YES" : "NO") << '\n';
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
good round
nice round
Problems A,B,C could have been presented in a different order.
thank you for your dedication for this round
problem E is so good, but I couldn't solve it during the contest :'(
How it is good?
These are some incredible problems!
Quality problems, quality constest. Also i think it perfectly encapsulates what a educational round should be: teaching cool techniques through problem-solving.
Can someone pls explain how to implement the segment tree in problem E
https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-10
First, sort the Segments by $$$w_i$$$
Then, use two-pointers + Segment tree. For each $$$i$$$, you can add $$$[l_i,r_i]$$$ by 1, and in the segment tree, record the minimal value.
for the second pointer, if the minimal value of $$$[l_i,r_i]$$$ is bigger than 2, then it means it is no longer useful, so you can add $$$[l_i,r_i]$$$ by $$$-1$$$, and the position of the second pointer ++
the answer is the minimal value of $$$w_i-w_j$$$ For each $$$i$$$.
Maybe my English is not good, if you want my code/still don't understand, you can ask me in codeforces.
You could also $$$update(L, R)$$$ by setting $$$wi$$$ at every index, do range minimum query, and get rid of the $$$(+1, -1)$$$ thing.
Can anybody explain how this range based segment tree works, editorial doesn't talks about it
https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-10
Thanks helpful very
For the problem C, if the map is N*M, how to solve it? Should I use twice DP?
Surprisingly this time Question A stumped me during the contest. It really took some time to understand and solve it, so if anyone would like a more detailed explanation with a slightly different approach feel free to visit my blog on it.
https://codeforces.me/blog/entry/93407
Can't the probelm A be solved using a DP-like approach? I tried but my code was failing on larger values like 99999 and greater.
problem A requires O(1) solution
"It induces at least one "all-tree-edge" cycle since u and v are already connected. It can't induce more than one "all-tree-edge" cycle, since it contradicts with tree edge definition, and if it induces a cycle with some other cycle edge, then we can replace that cycle edge with its own tree-edge path: our cycle will become "all-tree-edge" cycle, but it will use already used tree edges. In other words, it's enough to consider only one "all-tree-edge" cycle induced by any cycle edge."
Such Verbosity makes editorials rather convoluted.
Problem B is so interesting! It seems to need Pythagorean theorem, but we can prove that the best strategy only moves vertically or horizontally.
Could someone tell me how the BIT part of the last problem works in code? It is not something like ‘lowbit’ that I am familiar with. Just providing me a link should be ok :)
BIT stands for Binary Indexed Tree also known as Fenwick Tree. You can find more on cp-algorithms
In the solution of F, when add 1 to all the edge on the path, the function addOnPath just add the all the edges one by one. But isn't it O(n)? UPD: My bad, I didn't see that every edge will be at most delete once.
BledDest Please provide DP solution for Problem C Really Nice Problems