Tutorial
Tutorial is loading...
Solution (rui_er)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
#define y1 y114514
int T, n, m, x1, y1, x2, y2;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int f(int x, int y) {
if((x == 1 || x == n) && (y == 1 || y == m)) return 2;
if(x == 1 || x == n || y == 1 || y == m) return 3;
return 4;
}
int main() {
for(scanf("%d", &T);T;T--) {
scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2);
printf("%d\n", min(f(x1, y1), f(x2, y2)));
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (rui_er)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e3+5;
int T, n, k, a[N][N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int main() {
for(scanf("%d", &T);T;T--) {
scanf("%d%d", &n, &k);
rep(i, 1, n) rep(j, 1, n) scanf("%d", &a[i][j]);
int diff = 0;
rep(i, 1, n) rep(j, 1, n) if(a[i][j] != a[n+1-i][n+1-j]) ++diff;
diff /= 2;
if(diff > k) puts("NO");
else {
k -= diff;
if(n & 1) puts("YES");
else if(k & 1) puts("NO");
else puts("YES");
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (rui_er)
#include <bits/stdc++.h>
using namespace std;
int T, n, m;
int ask(int x, int y) {
printf("? %d %d\n", x, y);
fflush(stdout);
scanf("%d", &x);
return x;
}
void give(int x, int y) {
printf("! %d %d\n", x, y);
fflush(stdout);
}
int main() {
for(scanf("%d", &T);T;T--) {
scanf("%d%d", &n, &m);
int T1 = ask(1, 1);
if(T1 >= n) {
int T2 = ask(1, T1+1);
give(T2+1, T1+1);
}
else if(T1 >= m) {
int T2 = ask(T1+1, 1);
give(T1+1, T2+1);
}
else {
int T2 = ask(T1+1, 1);
int T3 = ask(1, T1+1);
if(T2 == T1 && T3 == T1) give(T1+1, T1+1);
else if(T3 == T1) give(T1+1, T2+1);
else give(T3+1, T1+1);
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (rui_er)
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 1e5+5;
ll n, m, a[N], sz[N], son[N], fa[N], sum[N];
vector<ll> e[N];
set<tuple<ll, ll> > sons[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void dfs(ll u, ll f) {
sz[u] = 1;
sum[u] = a[u];
fa[u] = f;
for(auto v : e[u]) {
if(v == f) continue;
dfs(v, u);
sz[u] += sz[v];
sum[u] += sum[v];
sons[u].insert(make_tuple(-sz[v], v));
if(sz[v] > sz[son[u]] || sz[v] == sz[son[u]] && v < son[u]) son[u] = v;
}
}
int main() {
scanf("%lld%lld", &n, &m);
rep(i, 1, n) scanf("%lld", &a[i]);
rep(i, 1, n-1) {
ll u, v;
scanf("%lld%lld", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
while(m --> 0) {
ll op, u;
scanf("%lld%lld", &op, &u);
if(op == 1) printf("%lld\n", sum[u]);
else {
ll v = son[u];
if(!v) continue;
ll p = fa[u];
sz[u] -= sz[v];
sum[u] -= sum[v];
sons[u].erase(make_tuple(-sz[v], v));
son[u] = sons[u].empty() ? 0 : get<1>(*sons[u].begin());
fa[u] = v;
sz[v] += sz[u];
sum[v] += sum[u];
sons[v].insert(make_tuple(-sz[u], u));
son[v] = get<1>(*sons[v].begin());
fa[v] = p;
sons[p].erase(make_tuple(-sz[v], u));
sons[p].insert(make_tuple(-sz[v], v));
son[p] = get<1>(*sons[p].begin());
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (rui_er)
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, P = 4e5 + 5, K = 5e6 + 5, W = 5e6;
int n, m, a[N], tab[K], phi[K], p[P], pcnt, dis[K], fa[K][6];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void sieve(int lim) {
phi[1] = 1;
rep(i, 2, lim) {
if(!tab[i]) {
p[++pcnt] = i;
phi[i] = i - 1;
}
for(int j=1;j<=pcnt&&1LL*i*p[j]<=lim;j++) {
tab[i*p[j]] = 1;
if(i % p[j]) phi[i*p[j]] = phi[i] * phi[p[j]];
else {
phi[i*p[j]] = phi[i] * p[j];
break;
}
}
}
}
void initTree(int lim) {
dis[1] = 1;
rep(j, 0, 5) fa[1][j] = 1;
rep(i, 2, lim) {
dis[i] = dis[phi[i]] + 1;
fa[i][0] = phi[i];
rep(j, 1, 5) fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
int LCA(int u, int v) {
if(dis[u] < dis[v]) swap(u, v);
per(i, 5, 0) if(dis[fa[u][i]] >= dis[v]) u = fa[u][i];
if(u == v) return u;
per(i, 5, 0) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
struct Node {
int lca, ans, mndis, allrt;
};
struct SegTree {
Node t[N<<2];
#define lc(u) (u<<1)
#define rc(u) (u<<1|1)
void pushup(int u, int l, int r) {
int mid = (l + r) >> 1;
t[u].lca = LCA(t[lc(u)].lca, t[rc(u)].lca);
t[u].ans = t[lc(u)].ans + t[rc(u)].ans
+ (mid - l + 1) * (dis[t[lc(u)].lca] - dis[t[u].lca])
+ (r - mid) * (dis[t[rc(u)].lca] - dis[t[u].lca]);
t[u].mndis = min(t[lc(u)].mndis, t[rc(u)].mndis);
t[u].allrt = t[lc(u)].allrt && t[rc(u)].allrt;
}
void build(int u, int l, int r) {
if(l == r) {
t[u].lca = a[l];
t[u].ans = 0;
t[u].mndis = dis[a[l]];
t[u].allrt = a[l] == 1;
return;
}
int mid = (l + r) >> 1;
build(lc(u), l, mid);
build(rc(u), mid+1, r);
pushup(u, l, r);
}
void modify(int u, int l, int r, int ql, int qr) {
if(t[u].allrt) return;
if(l == r) {
t[u].lca = fa[t[u].lca][0];
--t[u].mndis;
t[u].allrt = t[u].lca == 1;
return;
}
int mid = (l + r) >> 1;
if(ql <= mid) modify(lc(u), l, mid, ql, qr);
if(qr > mid) modify(rc(u), mid+1, r, ql, qr);
pushup(u, l, r);
}
int queryLCA(int u, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) return t[u].lca;
int mid = (l + r) >> 1;
if(qr <= mid) return queryLCA(lc(u), l, mid, ql, qr);
if(ql > mid) return queryLCA(rc(u), mid+1, r, ql, qr);
int ans = queryLCA(lc(u), l, mid, ql, qr);
if(ans == 1) return 1;
return LCA(ans, queryLCA(rc(u), mid+1, r, ql, qr));
}
int queryAns(int u, int l, int r, int ql, int qr, int lca) {
if(ql <= l && r <= qr) {
return t[u].ans + (r - l + 1) * (dis[t[u].lca] - dis[lca]);
}
int mid = (l + r) >> 1, ans = 0;
if(ql <= mid) ans += queryAns(lc(u), l, mid, ql, qr, lca);
if(qr > mid) ans += queryAns(rc(u), mid+1, r, ql, qr, lca);
return ans;
}
#undef lc
#undef rc
}sgt;
int main() {
sieve(W);
initTree(W);
scanf("%d%d", &n, &m);
rep(i, 1, n) scanf("%d", &a[i]);
sgt.build(1, 1, n);
while(m --> 0) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if(op == 1) sgt.modify(1, 1, n, l, r);
else {
int lca = sgt.queryLCA(1, 1, n, l, r);
printf("%d\n", sgt.queryAns(1, 1, n, l, r, lca));
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (Celtic, centroid decomposition)
// Celtic
#include<bits/stdc++.h>
#define N 501001
#define MAX 2005
using namespace std;
typedef long long ll;
typedef long double db;
const ll inf=1e18,mod=998244353,inv3=(mod+1)/3;
inline void read(ll &ret)
{
ret=0;char c=getchar();bool pd=false;
while(!isdigit(c)){pd|=c=='-';c=getchar();}
while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
ret=pd?-ret:ret;
return;
}
ll n,m,x,y,siz[N],son[N],minn=inf,num=0,f[N],sum,root;
vector<ll>v[N];
bool vis[N];
inline void find(ll ver,ll fa)
{
siz[ver]=1;
ll maxn=0;
for(int i=0;i<v[ver].size();i++)
{
ll to=v[ver][i];
if(to==fa||vis[to])
continue;
find(to,ver);
siz[ver]+=siz[to];
maxn=max(maxn,siz[to]);
}
maxn=max(maxn,num-siz[ver]);
if(maxn<minn)
{
minn=maxn;
root=ver;
}
return;
}
ll valmx[N],valmn[N],sz[N],now,fat[N];
struct node
{
ll x,y,ver;
}a[N];
inline bool cmp1(node a,node b)
{
return a.x<b.x;
}
inline bool cmp2(node a,node b)
{
return a.y<b.y;
}
ll cnt;
vector<ll>g[N];
inline void dfs(ll ver,ll fa,ll d)
{
valmx[ver]=max(valmx[fa],ver);
valmn[ver]=min(valmn[fa],ver);
if(ver!=now)
{
if(valmx[ver]==ver||valmx[ver]==now)
sum++;
if(valmn[ver]==ver||valmn[ver]==now)
sum++;
if(valmx[ver]==ver&&valmn[ver]==now)
sum-=2;
if(valmx[ver]==now&&valmn[ver]==ver)
sum-=2;
if(valmn[ver]==ver)
f[now]++;
if(valmn[ver]==now)
f[ver]++;
g[d].push_back(ver);
a[++cnt]=node{valmx[ver],valmn[ver],ver};
}
sz[ver]=1;
fat[ver]=d;
// cout<<"dfs"<<ver<<" "<<fa<<" "<<d<<endl;
for(int i=0;i<v[ver].size();i++)
{
ll to=v[ver][i];
if(to==fa||vis[to])
continue;
if(ver==now)
dfs(to,ver,to);
else
dfs(to,ver,d);
sz[ver]+=sz[to];
}
return;
}
ll tree[N];
inline void update(ll pos,ll num)
{
pos++;
while(pos<N)
{
tree[pos]+=num;
pos+=pos&-pos;
}
return;
}
inline ll query(ll pos)
{
pos++;
ll ret=0;
while(pos)
{
ret+=tree[pos];
pos-=pos&-pos;
}
return ret;
}
inline void calc()
{
sort(a+1,a+cnt+1,cmp1);
for(int i=1;i<=cnt;i++)
{
ll j=i;
for(;j<=cnt&&a[j].x==a[i].x;j++);
j--;
for(int k=i;k<=j;k++)
{
if(a[k].x==a[k].ver)
sum+=i-1,sum-=2*query(a[k].y)/*,cout<<"del "<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/;
}
for(int k=i;k<=j;k++)
{
if(a[k].y==a[k].ver)
update(a[k].y,1);
}
i=j;
}
for(int i=1;i<=cnt;i++)
{
ll j=i;
for(;j<=cnt&&a[j].x==a[i].x;j++);
j--;
for(int k=i;k<=j;k++)
{
if(a[k].y==a[k].ver)
update(a[k].y,-1);
}
i=j;
}
sort(a+1,a+cnt+1,cmp2);
for(int i=cnt;i;i--)
{
ll j=i;
for(;j&&a[j].y==a[i].y;j--);
j++;
for(int k=j;k<=i;k++)
{
if(a[k].y==a[k].ver)
sum+=cnt-i;
}
i=j;
}
ll tmp=0;
for(int i=1;i<=cnt;i++)
{
ll j=i;
for(;j<=cnt&&a[j].y==a[i].y;j++);
j--;
for(int k=i;k<=j;k++)
f[a[k].ver]+=tmp;
for(int k=i;k<=j;k++)
if(a[k].ver==a[k].y)
tmp++;
i=j;
}
return;
}
inline void decalc()
{
sort(a+1,a+cnt+1,cmp1);
for(int i=1;i<=cnt;i++)
{
ll j=i;
for(;j<=cnt&&a[j].x==a[i].x;j++);
j--;
for(int k=i;k<=j;k++)
{
if(a[k].x==a[k].ver)
sum-=i-1,sum+=2*query(a[k].y)/*,cout<<"back"<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/;
}
for(int k=i;k<=j;k++)
{
if(a[k].y==a[k].ver)
update(a[k].y,1);
}
i=j;
}
for(int i=1;i<=cnt;i++)
{
ll j=i;
for(;j<=cnt&&a[j].x==a[i].x;j++);
j--;
for(int k=i;k<=j;k++)
{
if(a[k].y==a[k].ver)
update(a[k].y,-1);
}
i=j;
}
sort(a+1,a+cnt+1,cmp2);
for(int i=cnt;i;i--)
{
ll j=i;
for(;j&&a[j].y==a[i].y;j--);
j++;
for(int k=j;k<=i;k++)
{
if(a[k].y==a[k].ver)
sum-=cnt-i;
}
i=j;
}
ll tmp=0;
for(int i=1;i<=cnt;i++)
{
ll j=i;
for(;j<=cnt&&a[j].y==a[i].y;j++);
j--;
for(int k=i;k<=j;k++)
f[a[k].ver]-=tmp;
for(int k=i;k<=j;k++)
if(a[k].ver==a[k].y)
tmp++;
i=j;
}
return;
}
inline void divide(ll ver)
{
vis[ver]=true;
now=ver;
cnt=0;
valmn[0]=inf;
dfs(ver,0,0);
// cout<<"??"<<ver<<" "<<sum<<endl;
/* cout<<ver<<endl;
for(int i=1;i<=cnt;i++)
cout<<a[i].x<<" "<<a[i].y<<endl;*/
calc();
// cout<<ver<<" "<<cnt<<endl;
for(int i=0;i<v[ver].size();i++)
{
ll to=v[ver][i];
if(vis[to])
continue;
cnt=0;
for(auto x:g[to])
a[++cnt]=node{valmx[x],valmn[x],x}/*,cout<<ver<<" "<<to<<" "<<x<<endl*/;
g[to].clear();
// cout<<ver<<" "<<to<<" "<<cnt<<endl;
decalc();
}
// cout<<"result::"<<ver<<" "<<sum<<endl;
for(int i=0;i<v[ver].size();i++)
{
ll to=v[ver][i];
if(vis[to])
continue;
num=siz[to];
minn=inf;
find(to,ver);
// cout<<ver<<" "<<to<<" "<<root<<endl;
divide(root);
}
return;
}
signed main()
{
read(n);
for(int i=1;i<n;i++)
{
read(x);
read(y);
v[x].push_back(y);
v[y].push_back(x);
}
num=n;
find(1,0);
divide(root);
printf("%lld\n",sum);
/* for(int i=1;i<=n;i++)
cout<<f[i]<<" ";
cout<<endl;*/
read(m);
for(int i=1;i<=m;i++)
{
ll x;
read(x);
n++;
f[n]=f[x]+1;
sum+=(n-1)-f[n];
printf("%lld\n",sum);
}
exit(0);
}
Solution (rui_er, reconstruction trees)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 4e5+5;
ll n, m, k, faMx[N], faMn[N], disMx[N], disMn[N], dfn[N], sz[N], tms;
ll A, B, C, ans;
vector<ll> eMx[N], eMn[N], reMx[N], reMn[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Dsu {
ll fa[N];
void init(ll x) {rep(i, 1, x) fa[i] = i;}
ll find(ll x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool merge(ll x, ll y) {
ll u = find(x), v = find(y);
if(u == v) return 0;
fa[u] = v;
return 1;
}
}dsu;
struct BIT {
ll c[N], sz;
void init(ll x) {sz = x; rep(i, 1, x) c[i] = 0;}
ll lowbit(ll x) {return x & (-x);}
void add(ll x, ll k) {for(; x <= sz; x += lowbit(x)) c[x] += k;}
ll ask(ll x) {ll k = 0; for(; x; x -= lowbit(x)) k += c[x]; return k;}
ll Ask(ll x, ll y) {return ask(y) - ask(x - 1);}
}bit;
void dfs1(ll u) {
dfn[u] = ++tms;
sz[u] = 1;
disMx[u] = disMx[faMx[u]] + 1;
B += disMx[u] - 1;
for(ll v : reMx[u]) {
dfs1(v);
sz[u] += sz[v];
}
}
void dfs2(ll u) {
disMn[u] = disMn[faMn[u]] + 1;
A += disMn[u] - 1;
C += bit.Ask(dfn[u], dfn[u] + sz[u] - 1);
bit.add(dfn[u], 1);
for(ll v : reMn[u]) dfs2(v);
bit.add(dfn[u], -1);
}
int main() {
scanf("%lld", &n);
rep(i, 1, n-1) {
ll u, v;
scanf("%lld%lld", &u, &v);
if(u < v) swap(u, v);
eMx[u].push_back(v);
eMn[v].push_back(u);
}
dsu.init(n);
rep(i, 1, n) {
for(ll j : eMx[i]) {
j = dsu.find(j);
dsu.merge(j, i);
faMx[j] = i;
reMx[i].push_back(j);
}
}
dsu.init(n);
per(i, n, 1) {
for(ll j : eMn[i]) {
j = dsu.find(j);
dsu.merge(j, i);
faMn[j] = i;
reMn[i].push_back(j);
}
}
bit.init(n);
dfs1(n);
dfs2(1);
ans = A + B - 2 * C;
// printf("%lld + %lld - 2 * %lld = %lld\n", A, B, C, ans);
printf("%lld\n", ans);
for(scanf("%lld", &m); m; m--) {
scanf("%lld", &k);
disMn[++n] = disMn[k] + 1;
ans += n - disMn[n];
printf("%lld\n", ans);
}
return 0;
}
Super Fast Editorial
problem descriptions were very bad. learn english.
https://mirror.codeforces.com/blog/entry/62730
I am not a native speaker either but to me the statements were clear and I understood them without a problem.
So do I
https://www.scotthyoung.com/blog/2018/12/03/learn-english/
this contest is better than the previous one div2
Fast Tutorial.
Thanks for very fast editorial!
I believe the diagrams in the editorial solution for A could have been much simpler, just block the TOP, BOTTOM, LEFT or RIGHT block depending on the position of either (x1, y1) or (x2, y2).
That would give away the solution...
I meant the pictures given in the editorial solution. :)
oh, lol
Very good contest!
$$$n log^3$$$ with unordered_map constant got TL in E(((
unordered_map can be "hacked" to be linear per operation
I know, but in fact, the number of different elements added was very small, O(logw), so it should still work fast enough, in O(1)
orz contest. Problems are gold
seriously, were you guys paid to write these comments? what's good about this round? just mention one good problem
E and F were Epic.
Overall, the contest was well balanced and the statements were clear so yes it is a good contest
E and F were very standard problems, idk what you found epic about them, moreover you didn't solve them.
The statements weren't clear at all(the coloring in B wasn't specific at the beginning, I found D hard to understand too), and very confusing.
and A, B, C, D are pretty much on the same level, so I don't know what your definition of balanced is.
Please, don't cry over each contest you don't do well in and start blaming authors, contest you find bad others find great, just try to learn from mistakes you make and you'll eventually improve.
who is crying? my rank was even better than yours. I am just saying that there was nothing spectacular about the round, as people claim.
Ofc you are saying this from a fake account…
I think E is interesting but F are too classical, but it's a good and educational round though.
Yes we are. Maybe you should contact the authors and start making money?
The idea in E is segment-tree-beats, isn't it? I guess it is a hard E for div 2.
Don't need segment-tree-beats, just 2 trees, 1 for lca and other to count number of changes to reach 1.
My submission
Thanks for good problems and lightning-fast Editorial!
UPD: as well as fast rating-changing within less than 1 hour after the contest.
Great contest!
Even tho I only solved A -> D but I had lots of observations on E, F and I think they're absolutely worth upsolving.
Waiting for more more rounds from you in the future!
ya E has a beautiful observation. i also try to upsolve
Can you explain use of DSU according to tutorial in the solution?
Great contest and fast editorial!
going to expert possibly:))))
the link for the solution of F using RT is broken it is showing "you are not allowed to view the requested page"
Oops, it seems that you can't view the submission. How can I share the submissions correctly?
I'll fix them soon.
UPD: fixed.
Could you elaborate on how to calculate C in problem F in the RT solution ? Thanks in advance.
Oh sorry, I forgot about this message.
You first calculate the dfs number ($$$\operatorname{dfn}$$$) and subtree size ($$$\operatorname{sz}$$$) of every vertex on the max-RT. Then $$$u$$$ is in subtree of $$$v$$$ on the max-RT if and only if $$$\operatorname{dfn}(v)\le\operatorname{dfn}(u)\le\operatorname{dfn}(v)+\operatorname{sz}(v)-1$$$.
Then, you dfs on the min-RT. Entering a vertex $$$u$$$, you have all ancestors of $$$u$$$ marked in the fenwick tree. You can use the dfs number and size on max-RT to calculate how many ancestors of $$$u$$$ on min-RT is in the subtree of $$$u$$$ on max-RT.
https://mirror.codeforces.com/contest/1797/submission/201352138 WHat is wrong in this for B
editorial faster than my code's time complexity
Beautiful Contest, I like all the questions. Especially the C and D questions although easy to get solution tricky to implement!!
i am newbie can anyone tell why solution of problem a fail my approach to a was first i check for x1 and x2 at corners if they are at corners means that they only move two steps so we block only two steps if they not at corners but at first row or first column or nyh row or mth col they move only three steps then we need to block only three steps if they not at corners and also not at 1 or nthrow or mthcol then they must in between something in between so we move 4 steps so i check both this conditions for (x1,x2) and (y1,y2) and tale min of both of them so my pretest was pass during contest but fail on system test can anyone pls tell where my codes fails here is my code 201316107
1 100 1000 100 100 50 50
//ans should be 3,but output is 4
First of all, I am also a newbie, but you seem to forget the case where n,m equals 1,2,3. If either n and m equals 1, the answer must be 1
Today I wrote the forbidden complexity in E, O(N log(W) sqrt(N)) !!
I didn't thought such atrocity could pass System test but it did.
Now I know that with seg tree I can do in O(N log^2 N)
Such a great contest, well done, authors
Nice problems，fast Editorial and fast ranting update.
I think there is another solution in C which is maybe easier. Consider (x, y) as the answer we need to find. If we query (a, b), we will get max(abs(x — a), abs(y — b)) as answer. We can ask (1, 1) (get k1) and (2, 1) (get k2) and we have 2 cases. If k1 = k2 then y — 1 must equal to k1 cause if it not then k1 = abs(x — 1), k2 = abs(x — 2) => k1 != k2. If k1 != k2 then abs(x — 1) = k1, abs(x — 2) = k2 and we can calculate x. The final query will be (1, y) if you can find y or (x, 1) if you can find x.
three-point localization www
the problem can be harder if the 3 points are given and u need to calc the position
I think C can be done in 2 queries, by querying (1, 1) and (n, 1) and then solving a system of equations.
Consider this:
Where is the king?
(5, 1) ? maybe im missing something
It could also be $$$(5, 2)$$$, $$$(5, 3)$$$, $$$(5, 4)$$$ or $$$(5, 5)$$$
I think im misunderstanding something about the problem. If distance from (1, 1) is 4 , how can you reach (5, 5) from (1, 1) in 4 steps?
King also moves diagonally
10 10
? 1 1
1
? 10 1
8
! 2 1 or ! 2 2 ?
How can it be ! 2 2, if distance from (1, 1) is 1?
King can move diagonally so 2,2 to 1,1 is 1
Probably the stupidest mistake ever in C.
I printed the string "! n m" instead of "!" and the values of n and m...
This is the first time I solved A and B so fast that I'm rated as top 300, but C got me stuck till the end because of this stupid mistake.....
Я снял видео-разбор задач A, B, C, D. Кому интересно, разбор можно посмотреть по ссылке: https://youtu.be/DjynOzLa818
Thank you rui_er for excellent problems and fast editorial. I enjoyed the problems very much.
https://mirror.codeforces.com/contest/1797/submission/201344789 Can someone please tell me my mistake for Problem C.
flush the output ( cout.flush(); ) after printing anything
endl flushes automatically
ohh, i dont know about that
in the first test case for n=3, m=4, r=2, c=2
you will get a=1, b=2, c=1 in your code and y=1 and x=-1
while printing x and y you are printing -1(x) so you are getting wrong output format
just dry run your code you will get it.
Can someone explain the idea behind the Centroid-Decomposition solution in task F?
Consider the operation of adding vertices. If we know the initial answer and array $$$f_n$$$ meaning the number of paths in which one end is $$$i$$$ and the other is the minimum, we can easily calculate the increase of the answer because the adding vertex must be the maximum. And we have $$$f_{n+j}=f_{k_j}+1$$$ in the $$$j$$$-th operation.
Then we consider how to calculate the initial answer and array $$$f_i$$$.
We can use Centroid-Decomposition. Denote $$$u$$$ as the current centroid. We can calculate the paths passing the vertex $$$u$$$. If we calculate the maximum and minimum from each vertex to the root, each vertex can be represented as a triple $$$(i,max_i,min_i)$$$. Then the answer passing $$$u$$$ is a two-dimension counting points problem. It can be solved in $$$O(n\log n)$$$. We need to do it again for each subtree because two vertices in the same subtree can't contribute to the answer.
Total time complexity $$$O(n\log^2 n)$$$.
Thank you very much!
What is the "two-dimension counting points problem" that we got here?
My approach to Problem C:
Find the distance from $$$(1,1)$$$ (let it be $$$k$$$), now the king must be on the following two segments:
Now take the intersection point of the two segments, i.e., $$$(k+1,k+1)$$$. Find the distance from $$$(k+1,k+1)$$$ (let it be $$$d$$$).
You will have two possible options only: $$$(k+1-d,k+1)$$$ (let it be point $$$p1$$$) or $$$(k+1,k+1-d)$$$ (let it be point $$$p2$$$).
In the third query find the distance from $$$p1$$$, if it's $$$0$$$ then print $$$p1$$$ else the king was on $$$p2$$$.
Note : When $$$k+1$$$ exceeds either $$$n$$$ or $$$m$$$, then make the $$$x$$$ or $$$y$$$ coordinate to $$$n$$$ or $$$m$$$ (in the $$$2nd$$$ step). The approach/idea will remain the same.
Nice problems
Could someone tell why I'm getting "wrong output format illegal query (test case 1)" in this code?
https://mirror.codeforces.com/contest/1797/submission/201367288
because the board has size n*m (n rows and m columns). You ask the question "? m 1". But there may be no line m, for example if n = 3,n = 5. (You are asking the question "? 5 1" and there are only 3 lines.)
Thanks,I interchanged n and m I'm so dumb
Submission Can somebody check why this is giving idleness limit exceeded on test 2. I have used endl and cout.fflush to flush the output. Thanks!
201382009
By the way, if you use endl, you can not prescribe flush since it is already included in endl
Test 3 of the D is the worst ivention of humanity. But the xontest was really fun and i enjoyed solving it. I especially liked D. Also E feels a bit unbalanced for a div2.
I tried submitting my solution for C but it's continuously prompting ""wrong output format illegal query (test case 2)" on the first test case
Link to my submission -> 201341675
Got it! was just exceeding the upper limit for query. Will take care next time.
what does it means? I am having the same issue please help.
When the field is, for example, 8 by 5, and the first response to the request is "? 1 1" this is 7. The next query according to your algorithm will be "? 8 8" although this cell is located outside the field, therefore the error
Thanks mate got it and sorted it out!
I dealt with it by making a case for
"if $$$query + 1$$$ exceeds n or m we know $$$query + 1$$$ is definitely the other co-ordinate."
and I will just make another query to find the other element.
in the example of 8 5 we ask
"? 1 1" --> 7
then since 8>5 we know 1st co-ordinate is 8 then the next query
"? 8 1" --> something
and
"! 8 (something + 1)"
for problem E, rather than using a segment tree to solve everything, you can just use a sparse table to get the LCA of the range, and then get the minimum depth (depth = how far away is the number from 1) and the sum of depth using a seg tree. This leads to an O(w log w + n log n log w + m log w) sol (w log w for the sieve, n log n log w for sparse table build + seg tree updates, and m log w sparse table query). This could technically be sped up to O(w log log w + n log n log w + m log log w) but doesn't really matter.
Here's the code (its a bit messy but still most understandable then the tutorial's solution in my opinion): 201387841
Hope this helps!
You are not recalculating the lca after type 1 queries, the lca can change for certain
(l,r)after a type 1 query involving some part of(l,r), you have only calculated for the initial values. Can you explain, pleaseInstead of calculating the lca, we can find the depth of the lca. If the depth of one of the nodes in a range is less than the initial lca depth of the range, we know that that is the new lca. This is because if the depth is higher then the initial lca of the range, the lca will not change because the lca is still one of the node's ancestors, but if the depth is lower than the initial lca, the lca is no longer on of the node's ancestors, but now the node is one of the lca's ancestors, meaning this node is the new lca. This basically means that the depth of the current lca will be the min of the depth of the original lca and the depth of the current numbers in the range of (l, r).
Can anyone finds the runtime error in this code? Thank you!
1797D
****
Can someone help me about prblm e.. here is my solution.. https://paste.ubuntu.com/p/w9TBJNmBp5/
First interactive that i could solve. The problem statements were very clear looking forward for more such rounds
Implementation based round that only exists to confuse with tricks and shortcuts. A round befitting of Chinese authors. The problems were god awful that only wants people to think how to implement, not how to solve.
oh，I think my mind is we
I have a different solution to problem E, does not require any dsu, just some logic + vectors + segtree.
Problem E can also be solved using just a segment tree(struct tournament in a code) with sum on an interval. For each query operation we know that the answer must be one of the numbers which the leftmost element in an interval can turn into using some number of operations. For each element we will store that set of numbers and maintain the number of operations for each number in a segment tree. Also for each number we will store the set of indexes that can become that number using some number of operations. We can answer each query by binary searching on the set of numbers which the leftmost element can turn into. If we are currently answering a query and need to know if each element in an interval can become a given number, we need to check if all numbers in a given interval can turn into it(can be done using lower_bound() on a set and a segment tree) and calculate the sum of operations with the before mentioned segment tree. When updating an interval, we can update the elements one by one as mentioned in the editorial, and decrease the number of operations for all numbers that the current element can turn into by one. The tricky part of understanding this idea is how this segment tree works(ordering of the leaves is somewhat similar to how we order nodes in HLD) and how to maintain it.
Code: 201457307
Can Problem E be optimized to $$$\mathcal{O}(q \log n)$$$ by maintaining the max and min dfn?
I think the problem descriptions were clear!
rui_er is there really a solution for problem E without $$$\Omega(n\log w)$$$ ?
We thought some of the testers (like LXH-cat) wrote the solution with a single $$$\log$$$.
I guess so.
Hi. Can someone please help me out by letting me know why my submission 202689621 for $$$E$$$ fails?
My basic idea is to maintain a single segment tree where every node is a pair of integers. First entry is their LCA and second is the minimum number of operations. While merging segments in $$$build$$$ and $$$query$$$, I have just climbed up starting from LCAs of both the segments. This process wasn't required in $$$update$$$ because we are doing point updates in which the node takes value of its ancestor which is just one level above it (its parent). So LCA of every segment containing it either changes just by one level or doesn't change at all.
Thank you.
Take a look at Ticket 16840 from CF Stress for a counter example.
Thanks a lot mate! I forgot to take care of the set iterator after deleting element from it.
Can anyone tell me Why this gives the wrong output? 205025905 But when I change the insert process of set -ve it works? 205025843 . What stl problem is creating?
Problem D- Li Hua and Tree Can someone what's wrong in this implementation?
why My solution on problem B fails on test case 5 Here is my solution please explain me why?? my solution link is : https://mirror.codeforces.com/contest/1797/submission/250240610
For problem B, the image in the description about the rotation to 180 degrees, regarding the test case 2, doesn't seem right.
For those who didn't quite understand well the D's idea, read about the rerooting technique. It feels more natural if you knows it.