Thank you for participating! Sorry for being much harder than usual Div. 2 :( But we still hope you find some of our problems interesting.
Rating predictions (Inspired by sum's editorial)
It seems like a joke now...
| Person | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| zltzlt | 800 | 1400 | 1600 | 2000 | 2300 | 2800 |
| small_peter | 800 | 1400 | 1700 | 1600 | ||
| WRuperD | 800 | 1300 | 1600 | 2000 | 2800 | |
| yinhee | 800 | 1000 | 1500 | 2100 | 2200 | 2700 |
| sinsop90 | 1000 | 1300 | 1500 | 2000 | 2200 | |
| YuJiahe | 800 | 1100 | 1600 | 1900 | 2700 | |
| CharlieV | 2400 | 2500 | 3000 | |||
| JWRuixi | 1800 | |||||
| Edwin__VanCleef | 1600 | 1800 | ||||
| QwQwf | 1000 | 1600 | 2000 | 2100 | ||
| wsc2008qwq | 900 | 1000 | 1800 | 2500 | 2600 | |
| starrykiller | 900 | 1400 | 1700 | 1900 | ||
| rui_er | 800 | 1000 | 1600 | 2100 | 2500 | |
| Jryno1 | 800 | 1200 | 1600 | 2100 | 2700 | |
| StarSilk | 800 | 1200 | 1600 | 2000 | 2500 | 3000 |
| lovely-ckj | 1000 | 1300 | 1800 | 2000 | ||
| FengLing | 800 | 1100 | 1400 | 2200 |
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Average | 857 | 1236 | 1640 | 2029 | 2438 | 2833 |
| Actual | 800 | 1300 | 1800 | 2400 | 2600 | 3000 |
1981A - Turtle and Piggy Are Playing a Game
Idea: zltzlt
Hint 1
What is Piggy's optimal strategy?
Hint 2
What does $$$2l \le r$$$ mean?
Solution
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
scanf("%d", &T);
while (T--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", __lg(r));
}
return 0;
}
1981B - Turtle and an Infinite Sequence
Idea: zltzlt
Hint 1
Consider each bit separately.
Hint 2
Calculate the time when the $$$d$$$-th bit of $$$a_n$$$ becomes $$$1$$$.
Solution 1
Tutorial is loading...
Solution 2
The answer is the bitwise OR of the range $$$[\max(0, n - m), n + m]$$$. Let's figure out how to calculate the bitwise OR of the range $$$[l, r]$$$.
We can consider each bit separately. If the $$$d$$$-th bit of $$$l$$$ is $$$1$$$ or the $$$d$$$-th bit of $$$r$$$ is $$$1$$$, then the $$$d$$$-th bit of the answer is $$$1$$$.
Otherwise, if $$$\left\lfloor\frac{l}{2^{d + 1}}\right\rfloor \ne \left\lfloor\frac{r}{2^{d + 1}}\right\rfloor$$$, then the $$$d$$$-th bit has been flipped at least twice from $$$l$$$ to $$$r$$$, so in this case the $$$d$$$-th bit of the answer is also $$$1$$$.
Time complexity: $$$O(\log (n + m))$$$ per test case.
Code for Solution 1
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
void solve() {
ll n, m;
scanf("%lld%lld", &n, &m);
ll ans = 0;
for (int i = 0; i <= 30; ++i) {
ll x = n & ((1LL << (i + 1)) - 1);
ll t = (1LL << i) - x;
if (n >= (1LL << i)) {
t = min(t, x + 1);
}
if (x >= (1LL << i) || t <= m) {
ans |= (1LL << i);
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Code for Solution 2
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
void solve() {
ll n, m;
scanf("%lld%lld", &n, &m);
ll l = max(0LL, n - m), r = n + m, ans = 0;
for (int i = 31; ~i; --i) {
if ((l & (1LL << i)) || (r & (1LL << i)) || (l >> (i + 1)) != (r >> (i + 1))) {
ans |= (1LL << i);
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
1981C - Turtle and an Incomplete Sequence
Idea: zltzlt
Hint 1
Figure out the case where $$$a'_1 \ne -1, a'_n \ne -1$$$ and $$$a'_2 = a'_3 = \cdots = a'_{n - 1} = -1$$$ first.
Hint 2
Imagine a full binary tree. Consider the sequence as a walk on the full binary tree.
Solution
Tutorial is loading...
Code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, a[maxn];
inline vector<int> path(int x, int y) {
vector<int> L, R;
while (__lg(x) > __lg(y)) {
L.pb(x);
x >>= 1;
}
while (__lg(y) > __lg(x)) {
R.pb(y);
y >>= 1;
}
while (x != y) {
L.pb(x);
R.pb(y);
x >>= 1;
y >>= 1;
}
L.pb(x);
reverse(R.begin(), R.end());
for (int x : R) {
L.pb(x);
}
return L;
}
void solve() {
scanf("%d", &n);
int l = -1, r = -1;
vector<int> vc;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
if (a[i] != -1) {
if (l == -1) {
l = i;
}
r = i;
vc.pb(i);
}
}
if (l == -1) {
for (int i = 1; i <= n; ++i) {
printf("%d%c", (i & 1) + 1, " \n"[i == n]);
}
return;
}
for (int i = l - 1; i; --i) {
a[i] = (((l - i) & 1) ? a[l] * 2 : a[l]);
}
for (int i = r + 1; i <= n; ++i) {
a[i] = (((i - r) & 1) ? a[r] * 2 : a[r]);
}
for (int _ = 1; _ < (int)vc.size(); ++_) {
int l = vc[_ - 1], r = vc[_];
vector<int> p = path(a[l], a[r]);
if (((int)p.size() & 1) != ((r - l + 1) & 1) || r - l + 1 < (int)p.size()) {
puts("-1");
return;
}
for (int i = 0; i < (int)p.size(); ++i) {
a[l + i] = p[i];
}
for (int i = l + (int)p.size(), o = 1; i <= r; ++i, o ^= 1) {
a[i] = (o ? a[i - 1] * 2 : a[i - 1] / 2);
}
}
for (int i = 1; i <= n; ++i) {
printf("%d%c", a[i], " \n"[i == n]);
}
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
1981D - Turtle and Multiplication
Idea: sinsop90
Hint 1
$$$a_i$$$ should take different primes.
Hint 2
Transform it into a graph problem.
Solution
Tutorial is loading...
Code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 4000100;
const int N = 1000000;
int n, a[maxn], pr[maxn], tot, stk[maxn], top;
bool vis[maxn];
inline void init() {
for (int i = 2; i <= N; ++i) {
if (!vis[i]) {
pr[++tot] = i;
}
for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {
vis[i * pr[j]] = 1;
if (i % pr[j] == 0) {
break;
}
}
}
mems(vis, 0);
}
inline bool check(int x) {
if (x & 1) {
return x + 1 + x * (x - 1) / 2 >= n;
} else {
return x * (x - 1) / 2 - x / 2 + 2 + x >= n;
}
}
vector<pii> G[10000];
void dfs(int u) {
while (G[u].size()) {
pii p = G[u].back();
G[u].pop_back();
if (vis[p.scd]) {
continue;
}
vis[p.scd] = 1;
dfs(p.fst);
}
stk[++top] = pr[u];
}
void solve() {
scanf("%d", &n);
int l = 1, r = 10000, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
for (int i = 1; i <= ans; ++i) {
vector<pii>().swap(G[i]);
}
int tot = 0;
for (int i = 1; i <= ans; ++i) {
for (int j = i; j <= ans; ++j) {
if (ans % 2 == 0 && i % 2 == 0 && i + 1 == j) {
continue;
}
G[i].pb(j, ++tot);
G[j].pb(i, tot);
}
}
for (int i = 1; i <= tot; ++i) {
vis[i] = 0;
}
top = 0;
dfs(1);
reverse(stk + 1, stk + top + 1);
for (int i = 1; i <= n; ++i) {
printf("%d%c", stk[i], " \n"[i == n]);
}
}
int main() {
init();
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
1981E - Turtle and Intersected Segments
Idea: zltzlt
Developed by 244mhq.
Hint 1
Stop thinking about Boruvka.
Hint 2
Most of the edges in the graph are useless.
Solution
Tutorial is loading...
Code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 1000100;
int n, lsh[maxn], tot, fa[maxn];
pii b[maxn];
struct node {
int l, r, x;
} a[maxn];
struct edg {
int u, v, d;
edg(int a = 0, int b = 0, int c = 0) : u(a), v(b), d(c) {}
} E[maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
return 1;
} else {
return 0;
}
}
void solve() {
tot = 0;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].l >> a[i].r >> a[i].x;
lsh[++tot] = a[i].l;
lsh[++tot] = (++a[i].r);
}
int m = 0;
sort(lsh + 1, lsh + tot + 1);
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
for (int i = 1; i <= n; ++i) {
a[i].l = lower_bound(lsh + 1, lsh + tot + 1, a[i].l) - lsh;
a[i].r = lower_bound(lsh + 1, lsh + tot + 1, a[i].r) - lsh;
b[++m] = mkp(a[i].l, i);
b[++m] = mkp(a[i].r, -i);
}
set<pii> S;
sort(b + 1, b + m + 1);
int tt = 0;
for (int i = 1; i <= m; ++i) {
int j = b[i].scd;
if (j > 0) {
auto it = S.insert(mkp(a[j].x, j)).fst;
if (it != S.begin()) {
int k = prev(it)->scd;
E[++tt] = edg(j, k, abs(a[j].x - a[k].x));
}
if (next(it) != S.end()) {
int k = next(it)->scd;
E[++tt] = edg(j, k, abs(a[j].x - a[k].x));
}
} else {
j = -j;
S.erase(mkp(a[j].x, j));
}
}
for (int i = 1; i <= n; ++i) {
fa[i] = i;
}
sort(E + 1, E + tt + 1, [&](const edg &a, const edg &b) {
return a.d < b.d;
});
ll ans = 0, cnt = 0;
for (int i = 1; i <= tt; ++i) {
if (merge(E[i].u, E[i].v)) {
++cnt;
ans += E[i].d;
}
}
cout << (cnt == n - 1 ? ans : -1) << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
1981F - Turtle and Paths on a Tree
Idea: yinhee
Developed by 244mhq and zltzlt.
Thanks AFewSuns and crazy_sea for discovering Solution 2, which runs faster than Solution 1!
Hint 1
Try some dp that takes $$$O(n^2)$$$ time.
Hint 2
What's the maximum MEX in the optimal good set of paths?
Solution 1
Tutorial is loading...
Solution 2
Read the $$$O(n^2)$$$ part of Solution 1 first.
Consider using a segment tree to maintain the dp values. The transitions for $$$u$$$ with at most one child are easy to maintain, so we only need to consider the case with two children.
First, use a segment tree to maintain the minimum value of $$$f_{u,i} + i$$$, so $$$\text{minx}$$$ and $$$\text{miny}$$$ can be computed. The value of $$$f_{u,a_u}$$$ can be set to $$$+\infty$$$ by a point update.
Ignoring how to compute $$$k$$$ for now, in the end, all $$$f_{x,i}$$$ are incremented by $$$\text{miny}$$$, all $$$f_{y,i}$$$ are incremented by $$$\text{minx}$$$, and the segment trees are merged. Finally, all $$$f_{u,i}$$$ are taken as the minimum with $$$k$$$.
To compute $$$k$$$, which is $$$\min\limits_{i \neq a_u} (f_{x,i} + f_{y,i} + i)$$$, we can use a similar segment tree merging method, quickly computing this as we recursively descend to the leaf nodes of the segment tree. Additionally, we need to maintain the minimum value of $$$f_{u,i}$$$.
Time complexity: $$$\mathcal{O}(n \log n)$$$ per test case.
Code for Solution 1
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 25050;
const int inf = 0x3f3f3f3f;
int n, m, a[maxn], f[maxn][4000];
vector<int> G[maxn];
void dfs(int u) {
if (G[u].empty()) {
for (int i = 1; i <= m; ++i) {
f[u][i] = (i == a[u] ? inf : 0);
}
return;
}
if ((int)G[u].size() == 1) {
int x = G[u][0];
dfs(x);
int mn = inf;
for (int i = 1; i <= m; ++i) {
if (i != a[u]) {
mn = min(mn, f[x][i] + i);
}
}
if (u == 1) {
printf("%d\n", mn);
return;
}
for (int i = 1; i <= m; ++i) {
f[u][i] = (i == a[u] ? inf : min(f[x][i], mn));
}
return;
}
int x = G[u][0], y = G[u][1], mnx = inf, mny = inf, k = inf;
dfs(x);
dfs(y);
for (int i = 1; i <= m; ++i) {
if (i != a[u]) {
mnx = min(mnx, f[x][i] + i);
mny = min(mny, f[y][i] + i);
k = min(k, f[x][i] + f[y][i] + i);
}
}
k = min(k, mnx + mny);
if (u == 1) {
printf("%d\n", k);
return;
}
for (int i = 1; i <= m; ++i) {
f[u][i] = (i == a[u] ? inf : min({f[x][i] + mny, f[y][i] + mnx, k}));
}
}
void solve() {
scanf("%d", &n);
m = min(n + 1, 3863);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
vector<int>().swap(G[i]);
}
for (int i = 2, p; i <= n; ++i) {
scanf("%d", &p);
G[p].pb(i);
}
dfs(1);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Code for Solution 2
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 1e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
#define LC tree[x].lc
#define RC tree[x].rc
ll t,n,a[25025],ch[25025][2],ans=inf;
ll rt[25025],tot=0;
struct node{
ll minn1,minn2,lz,lzmin,lc,rc;
il void addtag(ll v,ll vmin,ll l){
minn1=min(minn1+v,vmin);
minn2=min(minn2+v,vmin+l);
lz+=v;
lzmin=min(lzmin+v,vmin);
}
}tree[1000010];
il void pushup(ll x){
tree[x].minn1=min(tree[LC].minn1,tree[RC].minn1);
tree[x].minn2=min(tree[LC].minn2,tree[RC].minn2);
}
il ll newnode(){
tree[++tot]=(node){(ll)inf,(ll)inf,0,(ll)inf,0,0};
return tot;
}
il void pushdown(ll x,ll l,ll r){
if(!LC) LC=newnode();
if(!RC) RC=newnode();
ll mid=(l+r)>>1;
tree[LC].addtag(tree[x].lz,tree[x].lzmin,l);
tree[RC].addtag(tree[x].lz,tree[x].lzmin,mid+1);
tree[x].lz=0;
tree[x].lzmin=inf;
}
void upd(ll &x,ll l,ll r,ll pos){
if(!x) x=newnode();
if(l==r){
tree[x].minn1=tree[x].minn2=inf;
return;
}
ll mid=(l+r)>>1;
pushdown(x,l,r);
if(pos<=mid) upd(LC,l,mid,pos);
else upd(RC,mid+1,r,pos);
pushup(x);
}
void add(ll &x,ll l,ll r,ll ql,ll qr,ll v){
if(!x) x=newnode();
if(ql<=l&&r<=qr){
tree[x].addtag(v,(ll)inf,l);
return;
}
ll mid=(l+r)>>1;
pushdown(x,l,r);
if(ql<=mid) add(LC,l,mid,ql,qr,v);
if(mid<qr) add(RC,mid+1,r,ql,qr,v);
pushup(x);
}
void mdf(ll &x,ll l,ll r,ll ql,ll qr,ll v){
if(!x) x=newnode();
if(ql<=l&&r<=qr){
tree[x].addtag(0,v,l);
return;
}
ll mid=(l+r)>>1;
pushdown(x,l,r);
if(ql<=mid) mdf(LC,l,mid,ql,qr,v);
if(mid<qr) mdf(RC,mid+1,r,ql,qr,v);
pushup(x);
}
ll merge(ll x,ll y,ll l,ll r){
if(!LC&&!RC){
tree[y].addtag(0,tree[x].minn1,l);
return y;
}
if(!tree[y].lc&&!tree[y].rc){
tree[x].addtag(0,tree[y].minn1,l);
return x;
}
ll mid=(l+r)>>1;
pushdown(x,l,r);
pushdown(y,l,r);
LC=merge(LC,tree[y].lc,l,mid);
RC=merge(RC,tree[y].rc,mid+1,r);
pushup(x);
return x;
}
ll query(ll x,ll y,ll l,ll r){
if(!LC&&!RC) return tree[x].minn1+tree[y].minn2;
if(!tree[y].lc&&!tree[y].rc) return tree[y].minn1+tree[x].minn2;
ll mid=(l+r)>>1,res=inf;
pushdown(x,l,r);
pushdown(y,l,r);
res=min(res,query(LC,tree[y].lc,l,mid));
res=min(res,query(RC,tree[y].rc,mid+1,r));
return res;
}
void dfs(ll u){
if(!ch[u][0]){
mdf(rt[u],1,n+1,1,n+1,0);
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);
if(u==1) ans=0;
}
else if(!ch[u][1]){
dfs(ch[u][0]);
rt[u]=rt[ch[u][0]];
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);
ll minn=tree[rt[u]].minn2;
mdf(rt[u],1,n+1,1,n+1,minn);
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);
if(u==1) ans=minn;
}
else{
ll x=ch[u][0],y=ch[u][1];
dfs(x);
dfs(y);
if(a[u]<=(n+1)){
upd(rt[x],1,n+1,a[u]);
upd(rt[y],1,n+1,a[u]);
}
ll minx=tree[rt[x]].minn2,miny=tree[rt[y]].minn2,k=min(query(rt[x],rt[y],1,n+1),minx+miny);
add(rt[x],1,n+1,1,n+1,miny);
add(rt[y],1,n+1,1,n+1,minx);
rt[u]=merge(rt[x],rt[y],1,n+1);
mdf(rt[u],1,n+1,1,n+1,k);
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);
if(u==1) ans=k;
}
}
il void clr(){
fr(i,1,n) ch[i][0]=ch[i][1]=rt[i]=0;
tot=0;
ans=inf;
}
int main(){
t=read();
while(t--){
n=read();
fr(i,1,n) a[i]=read();
fr(i,2,n){
ll x=read();
if(!ch[x][0]) ch[x][0]=i;
else ch[x][1]=i;
}
dfs(1);
writeln(ans);
clr();
}
}
/*
1
5
3 2 2 1 1
1 1 2 2
ans:
4
*/
Auto comment: topic has been updated by zltzlt (previous revision, new revision, compare).
Look at the standings. It seems your F is too hard for a div2 so it works like a 5-problem round. Is that good?
I will elaborate on that.
You're right, it wasn't expected and that's mostly my fault -- I was able to come up with $$$O(n^2)$$$ solution pretty easily and thought that a lot of people will think about solution $$$O(n \cdot bound)$$$ after some time. In general, I don't want for last problem to be that hard and I will try to listen to feedback of other people more carefully. I still hope that people had fun thinking about this problem (and others problem of the round).
And one more point -- we intentionally didn't put in pretests tests where you need to use very big value of bound (maximum one that zltzlt was able to construct was around 3k and you can pass pretests with around 1k). I also want to elaborate on that. In general, I would vote for pretests to be as strong as possible, but here it was kinda special -- we didn't want people to try to squeeze solutions just with pure guessing (and since I've underestimated the problem, I thought that a lot of people will try to do so), that's why I agreed to not use such tests into pretests. In retrospect, I would insist on putting them (because problem already turned out to be too hard), and I fell sorry for maspy, congratulations on the win though!
I proved that the required upper bound is $$$O(N / \log N)$$$, but because creating a test case that achieves that upper bound also seemed non-trivial, I didn't seriously consider the constant factor. I ended up submitting with a slightly conservative estimate, taking into account the possibility of tight TL or ML. (Also, since the pretest succeeded with a limit of 1K, I submitted with a limit of 2K.)
While it might have been better to have some cases in the pretests closer to optimality, I think it's great that there were test cases in the system tests that required quite large upper bounds. Thanks for preparing a good contest!
look at the tester predictions, it is hard to be very accurate in predicting difficulties. F isnt very relevant for div2'ers anyways (only about 10 solve an average F?) that numbeer only decreased by 10.
So, why are they in div2 contests?
to give div2 people a harder problem to upsolve
A problem having no solve is different from not having a problem.
Do you think everyone who didn't solve that problem just quit after solving 5 problems?
Sorry for wrongly predicted the difficulty of problem F. As the writer, I wrongly predicted the difficulty to solve O(n^2) sol as well as calculating the maximum of MEX. So as is said above, guys can just consider it as a joke now:(
Very surprised this didn't pass D:
https://mirror.codeforces.com/contest/1981/submission/263490566
Time complexity should be $$$O(Nlog\sqrt{N})$$$
Edit: nvm I forgot to consider that it was multi-tested
problem C has quite a bit heavy implementation.
Not really, it took me about 20 minutes to implement.
In thought it is hard to implement but in code not really. Using bitmask simplify it.
C has a significantly simpler $$$\mathcal O\left(n \log\left(n\right)\right)$$$ solution. Notice that instead of stopping at the LCA, if the path has missing entries, it is valid to continue farther up the tree. The path only has to stop when it runs out of missing entries or it reaches the root. Therefore, assuming at least one entry is not missing, a simple solution is to repeatedly choose the largest entry $$$x$$$ with missing neighbors and replace those missing neighbors with $$$\left\lfloor\frac x2\right\rfloor$$$ (or $$$2$$$ if $$$x = 1$$$). This can be implemented in about 20 lines with a priority queue:
Wow great idea
I did this but got some stupid rte on testcase 4.
I could not understand your solution very well. It sounds like a great idea. Can you please explain in more detail (possibly with your thinking approach). Thank you
For example, consider the sequence [9, -1, -1, -1, -1, -1, -1, 5]. The solution presented in the editorial is to find the unique simple path from 9 to 5 in the binary tree ([9, 4, 2, 5]) and then alternate between 5 and 10, resulting in the sequence [9, 4, 2, 5, 10, 5, 10, 5]. Most of the complicated logic in the solution is for finding this path, and in particular, for finding 2, the LCA of 9 and 5.
My solution is to repeatedly find the largest entry with a missing neighbor and set its missing neighbor(s) to its value divided by two. In this example, 9 is initially the largest such entry, so set its missing neighbor to floor(9/2) = 4. Then, 5 is the largest such entry, so set its missing neighbor to floor(5/2) = 2. If the largest such entry is ever 1, we cannot set its neighbor to floor(1/2) = 0, so set it to 2 instead. Ties are broken arbitrarily. The full sequence of operations in this example is:
For the last sample input, in the first step, 7 is the largest number, so set its missing neighbors to floor(7/2) = 3. Then, there are four 3's, each of which has at least one missing neighbor, so choose one arbitrarily (here I chose the first one). Then, there are two 1's and three 3's with missing neighbors, so chose one of the 3's arbitrarily (here I chose the last one). This case proceeds as follows:
In the binary tree, this corresponds to choosing a path that gets as close to the root as possible and using the cycle 1 2 1 2 ... to fill any remaining space. This can be implemented easily using a priority queue.
I got what you were trying to do , and i myself got the intuition maybe we can find the largest and insert half on each of its side , but i wasnt particularly able to get a conclusive proof to why this should work , I cannot think of a testcase at particular , but it just seemed to me that , there may exist a case where this solution wont work , do you have any proof as such why was this working , it will help me a lot in maybe understanding your thinking better or anything in such .
Thank you in advance.
Assume that at least one space is not missing and that a solution exists. The other cases are easy: if all entries are missing, we can just set the first entry to $$$1$$$ and use the same algorithm, and to check whether there is no solution, we can just use the same algorithm and do a linear-time check at the end that the constraints are satisfied. Removing these steps and I/O, the remaining implementation is:
Also note that the output is bounded by $$$\max\left(2, \max_i a_i\right)$$$, so it cannot exceed $$$10^9$$$.
Now, consider each nonempty consecutive run of missing spaces. There are two cases here: either the run is a prefix/suffix of the array or it is a subarray with non-missing entries on either side.
In the suffix/prefix case, the algorithm will start from the non-missing element adjacent to the run and iteratively add values that meet the constraints.
The second case is slightly trickier. Let $$$a_i$$$ and $$$a_j$$$, $$$i < j$$$, be the entries on either side of the run. Consider the binary tree described in the editorial where $$$1$$$ is the root, $$$n$$$'s children are $$$2n$$$ and $$$2n+1$$$, and $$$n$$$'s parent is $$$\left\lfloor\frac n2\right\rfloor$$$. The solution, which we assume exists, will be a walk from $$$a_i$$$ to $$$a_j$$$ in this tree.
Such a walk must consist of a simple path from $$$a_i$$$ to $$$a_j$$$ (which is unique in a tree) and some circuits. Trees are bipartite, so these circuits must have even length. Since we are assuming a solution exists, then, letting $$$d\left(a, b\right)$$$ be the distance from $$$a$$$ to $$$b$$$ in the tree, $$$j - i = d\left(a_i, a_j\right) + 2k$$$ for some integer $$$k \ge 0$$$ ($$$2k$$$ is the total length of the circuits and $$$d\left(a_i, a_j\right)$$$ is the length of the simple path).
Suppose we start with the run
9 - - - - - - - - - - - - 5. $$$d\left(9, 5\right) = 3$$$ due to the simple path9 4 2 5and $$$j - i = 13 = d\left(9, 5\right) + 2\cdot 5$$$. One possible solution is9 19 9 4 2 1 3 6 3 7 3 1 2 5, which is the simple path9 4 2 5plus the even-length circuits9 19 9and2 1 3 6 3 7 3 1 2.When this is true, this algorithm constructs such a walk. It does this by repeatedly choosing the deepest endpoint (this will be the endpoint with the greater value, ignoring ties) and connecting it to its parent. This will reach the LCA after $$$d\left(a_i, a_j\right)-1$$$ steps and have $$$2k$$$ steps left.
Then, it constructs an even-length circuit to fill the remaining length. First, it alternately connects the left/right endpoint to its parent, so after any even number of steps, a circuit is formed. Then, if there are still any missing entries, it completes the circuit with alternating 1's and 2's.
Suppose we start with
19 - - - - - - 8. After two steps, we have19 9 4 - - - - 8, which is just the simple path19 9 4 8plus an even number of missing entries. After two more steps, we have either19 9 4 2 - - 4 8or19 9 4 - - 2 4 8(depending on tie-breaking), which is the simple path plus the circuit4 2 4. After two more steps, we have19 9 4 2 1 2 4 8, which extends this circuit to4 2 1 2 4.Suppose we start with
19 - - - - - - - - - - - - 8. After two steps, the algorithm produces19 9 4 - - - - - - - - - - 8, which is the simple path19 9 4 8plus an even number of missing entries. Then, after four more steps, we have19 9 4 2 1 - - - - - - 2 4 8or19 9 4 2 - - - - - - 1 2 4 8, which is the simple path plus the circuit4 2 1 2 4. Since we have reached the root and there are still empty entries remaining, they are filled in with alternating 1's and 2's:19 9 4 2 1 2 1 2 1 2 1 2 4 8, resulting in the simple path19 9 4 8plus the even circuit4 2 1 2 1 2 1 2 1 2 4.Thanks bro got the idea.
Say you have two numbers a and b with b>a and with x negative ones between them. The main claim is that if there exists a way to replace these x negative ones with some positive integers to satisfy the problem's condition, then there exist a way in which the number just before b is floor(b/2). This is because say you had 2*b or 2*b+1 just before b, then at some point between a and 2*b+1 you must have reached b. Keep doing this recursively till you reach a point when the number just before b is b/2. Fill the numbers between this point and our originial b with b/2 and b alternatively.
Question B Detailed Video Editorial
https://youtu.be/Gb5nnpg0TDk
Thank you so much for this. Literally a life saver
Can someone explain what might be wrong with this solution for problem C? https://mirror.codeforces.com/contest/1981/submission/263494280
Thanks !
Can anyone explain what is wrong with this solution 263791858 for C
C's editorial is not friendly as a regular C. LCA is not something that most people thinking about in this position. There's still a solution without using such advanced topic, but why the author didn't do that?
I solved C in the contest and I don't understand what the editorial is talking about.
Why downvote editorial?
Why downvote comment?
Problem C, I use brute-force searching with "merge intervals" to get an AC. Hacks welcome.
263496224
can you please explain your solution , what you did using merge intervals and how that concept is being used here ?
Explanation replied.
Can you please explain your solution
Explanation replied.
Can anyone explain what is wrong with this solution 263791858 for C
Explanation:
For each step, value
xcan be transformed into either ofx/2,2*x, or2*x+1.If we deal with a interval of integers
[left, right], it will become a union of 2 intervals:[left/2, right/2][2*left, 2*right+1][1, 1e9].Therefore, for each step, we operate on the set of continous intervals (type
Intervalsin my code), and use the good-old leetcode's "merge interval" solution (ivls_shrinkin my code) after each step.Finally, after the specified number of steps, we see if the target value is an element of the the final intervals, and fill back the numbers by looking up the stored history.
Here are my 2 submissions for problem B 263489923 and 263504667 .The first submission gives AC while the second submission gives a WA. The difference between the two submissions is that in the 1st submission ,in the end I have written
and therefore it gives AC. I can't really figure out if we don't write these two lines ,why my code gives WA ,or are the tests weak ?
Can someone explain, how in problem C
is generating the path between the two nodes ?
I'll try explaining whatever I've understood.
The code tries to find L, the path from the left node x to the LCA(x,y), and likewise R for the right node y. Every right shift (by 1) operation at a given node corresponds to moving one level up to it's parent node. Since the root node is always 1, we can see that the depth of a node corresponds to the position of it's MSB as every step down is accompanied by a left shift. So, deeper nodes have higher MSB positions, which can be easily evaluated by __lg(x). This serves as a quick tool to compare depths.
As for the algorithm :
First, we try to make the depths of the left and right nodes equal by moving the lower node (the one with higher position of MSB) up. If the LCA is either of x or y, our search ends here.
If not, say the LCA is at some depth d and our current depth is d_curr. Then we must move both of our nodes up by d_curr-d times to reach the LCA. The takeaway being that, we must move them up simultaneously until they are equal.
Then, we can follow L to reach the LCA from x, then the reverse of R to reach y ultimately. This will give us the shortest path.
Thanks
Love the first hint of the problem E
For problem $$$C$$$, i found this logic. In order to go from one positive value to next positive value, we find the minimum no. of operations required, then if the required operations is less than given steps and has same parity as required, it is possible to go from one value to next, otherwise just return -1. This we do for all such positive values. Then, for first and last element, we just fill remaining -1s by doing *2, /2 and so on.
HOW TO FIND OPERATIONS EFFECTIVELY?
Let's say for example, we want to make 3 to 9, this can be done in 4 operations but how?
$$$(3)_1$$$$$$_0$$$ $$$=$$$ $$$(11)_2$$$ and $$$(9)_1$$$$$$_0$$$ $$$=$$$ $$$(1001)_2$$$, we just find the common bits from MSB in both, don't change them and first delete the uncommon ones from val1(here 3) and insert uncommon ones from val2(here 9). Here, common bits are only MSB, so operations required will be 1(for deletion from 3) and 3(from addition from 9), so total 4.
During removing, do /2 operation, doing addition and bit is 0, do *2 operation, bit is 1, do *2+1 operation. We do this for all pairs of positive values of a.
Submission Link :- 263497185
what even is that solution to C lmao how can people even think about it as traversing a binary tree at all that's needlessly complicated and sounds like something that should be used within a moderately difficult Div2D. Instead, uhhh, my solution is much simplier, only kinda implementation heavy.
(before the yapping, here's the submission: https://mirror.codeforces.com/contest/1981/submission/263477772)
The condition that either val[i] has to be the rounded down value of val[i+1]/2 or the other way around can be interpeted as "when moving from an element to the next one, add or remove a bit from the back". This means that, as long as there exists a valid chain of suffix add/remove operation to "transition" between all non-empty values, there exists a valid sequence (for the prefix and suffix empty numbers, just fill them with random shit that still satisfies the condition).
My algo goes as follows:
1) Chug every non-empty number into a vector, alongside with their position.
2) When considering 2 consecutive non-empty number, consider their bit sequence. Shove all of them into 2 corresponding deque, dq1 for the first number and dq2 for the second one
3) When transforming from the first number to the 2nd one by suffix addition/deletion operations, we will want to keep the common prefix. Pop all of these out of the front of the 2 dqs. Then, delete the suffix of number 1 until it's empty (by constantly /2-ing the current value), then add the bits accordingly (by doubling the previous number, then either add 0 or 1 depending on the number on the front of dq2). Call the total amount of bit removal/addition operations num
4) When transforming from a number at position i to position j, a total of (j-i) operations are needed. After we're done with transforming val[i] into val[j], just keep adding in a bit and then remove it in the next step. If (j-i-num) (the amount of "filler" operations) is non-negative and divisible by 2, the transition is possible. Otherwise, return -1.
(would say that it's only a bit less complicated than the binary tree solution, this is kinda complicated for a div2C lmao)
wait nvm it's actually the same thing lmao.
at least the requirement is only 2 dqs instead of actually having to implement LCA. Though the LCA of 2 numbers in a complete binary tree is their prefix bit sequence or something anyways, so, uhhhhh
You don't even need two deques; see my submission: 263480468.
...for all that matters, I highly doubt that this dumb fuck who failed to get Expert 8 times in a row could compare with the efficiency and beauty of the legendary Tourist, but you do you
I highly doubt that this dumb fuck who writes
author: touriston the top of his code while not being even 1/1000th of tourist's skill could compare with the efficiency and beauty of tourist either.C has a much harder solution in tutorial , I did something which i feel is much simpler we just need to fill numbers between two non -1 numbers ,other than that its easy .Firstly store all the index where v[i]!=-1 then between two such indices we need to fill such that conditions are fullfilled , so say we want to fill numbers between l and r indices ,if v[l-1]>v[r+1] fill v[l] with v[l]/2 else v[r] with v[r]/2, we will try and get the two numbers as close as possible and minimum as possible(if we fill from both sides we can maintain the conditions more easily as from at least one side the number will be either half of the previous or next) , so basically they will both reach 1 at end after dividing by two as much as possible , after that we can just continue filling 2 and 1 alternatively ,after all this we should check if conditions are satisfied as there are cases where the numbers cannot come as close to each other https://mirror.codeforces.com/contest/1981/submission/263488558
As simple an idea as jiangly 263500214. Nice explanation!
C really has so much implementation.Hope it can be easier nxt time.qaq
check this one:265693364
Wow it looks really simple,thank you!(^_^)
Can i get a counter test case for my solution of second problem
link: https://mirror.codeforces.com/contest/1981/submission/263471361
Here is the test case :
1
9 1
Expected : 11 , found : 15
ya got it by dry running thank you.
zltzlt Can you please explain why the following is true in Task B?
When $$$\left\lfloor\frac{l}{2^{d + 1}}\right\rfloor \ne \left\lfloor\frac{r}{2^{d + 1}}\right\rfloor$$$, $$$dth$$$ digit will be flipped at least twice between $$$[l,r]$$$
Because the $$$d$$$-th bit of $$$l$$$ and the $$$d$$$-th bit of $$$r$$$ are both $$$0$$$, and since $$$\left\lfloor\frac{l}{2^{d + 1}}\right\rfloor \ne \left\lfloor\frac{r}{2^{d + 1}}\right\rfloor$$$ there exists an $$$x$$$ in range $$$[l, r]$$$ such that the $$$d$$$-th bit of $$$x$$$ is $$$1$$$.
In problem D
we can choose $$$x$$$ primes such that we can make $$$\ x \ * (x \ + \ 1) \ / \ 2 \ >= \ n \ - \ 1$$$ pairs,
but don't know how to make such an arrangement.
please tell me i'm in correct direction or not. Thanks!
If more GMs were to participate on time, the estimated rating of F could be lower? 4k blew my mind.
Can anyone please explain why my following approach for the problem B fails:
I observed each bit individually and checked for two possibilities:
I tried to find the greatest number smaller than 'n' whose ith bit is set. If it exists, check if the difference between this number and 'n' is less than or equal to 'm'. If this difference is less than or equal to 'm', the ith bit in the answer would be set.
In the second case, I tried to find the smallest number greater than 'n' whose ith bit is set, and then check if the difference between this number and 'n' is less than or equal to 'm'. If this difference is less than or equal to 'm', the ith bit in the answer would be set.
Here is my submission: https://mirror.codeforces.com/contest/1981/submission/263527422
Implementation issue I think. Double check
I believe all it does is convert fst to 0.
https://mirror.codeforces.com/contest/1981/submission/263527099
--> wrong submission
https://mirror.codeforces.com/contest/1981/submission/263500175
--> correct submission
why (temp.size()-1)>len --> is performing differently when I substitute siz = temp.size()
temp.size() is by default a size_t
can you plz explain it further?
Because it's an unsigned, it overflows.
Can anyone please tell the mistake in this code, getting WA.
https://mirror.codeforces.com/contest/1981/submission/263510295
Thank you!
https://mirror.codeforces.com/contest/1981/submission/263498446
--> try to get the test case as I did..see the flag and no variable and if statement.. you will get it
Someone will never think such complex solution in problem C!
I solved C with Two Pointers method, just filling the
-1gaps in the array!My solution: 263542553
Time Complexity:
O(n)Uphacks are welcome!
i have done 2 pointer filling with LCA at common number we get by dividing two . soln.
just missed to submit in contest by 2 minutes
hey very good solution, but could you explain that greedy nature you used. if (arr[L] >= arr[R]) { if (arr[L] > 1) { arr[L + 1] = arr[L] >> 1; L++; } else { // 1 cannot be divided by 2, cz all a[i] >= 1 arr[R — 1] = arr[R] << 1; R--; } } else if (arr[L] < arr[R]) { if (arr[R] > 1) { arr[R — 1] = arr[R] >> 1; R--; } else { arr[L + 1] = arr[L] << 1; L++; } }
Okkayy... Suppose you have a gap like:
[4, -1, -1, -1, 3]4and3, as4 >= 3, the gap:[4, 2, -1, -1, 3][4 >>= 1 means dividing by 2, so 4/2 is 2]2and3,3 >= 2, then:[4, 2, -1, 1, 3]2 >= 1, then[4, 2, 1, 1, 3]-1Consider the same gap with an extra
-1! Then finally we will get[4, 2, 1, -1, 1, 3]1 >= 1, but here we cannot divide 1 by 2, because by rule, alla[i] >= 1, so multiply by2, then we are getting[4, 2, 1, 2, 1, 3].Now, imagine different gaps and try yourself to fill it up!
thanks, got it very nice approach
what was the intution behind such approach ? How can a newbie comeup with some intution like this ?
Consider a gap:
[4, _, 16], here you can use8in the gap. Means multiplying by two the smaller side (4 <= 16).[4, 8, 16]is valid.[4, 8, 4]is valid for[4, _, 4]. In my previous comment I showed division approach. But,Q. Why division? Why not multiplication?
In the problem statement, you see a floor function is used. So I got the idea not to multiply numbers as much as I can, because multiplying a numbers minimizes the usage of the floor function, as a result two non-equal number will be mismatched!
[4, _, 5], but[4, 8, 5]is invalid. Where[4, 2, 5]is valid option!xcannot have multiplefloor(x/2)!xandycan have samefloor(x/2) = floor(y/2)So, there is an observation that using division can minimize the difference between two numbers (e.g. 4 and 5 etc.), but using multiplication never minimizes the difference! And integer dividing already doing floor!
Q. Why are we using multiplication in 1?
This answer was already given in my previous comment. As we always divide the bigger one, we will get 1 when both side have
1s, so these are already equal sides. Multiplication can be used when there is no value differences between two sides! As multiplication doesn't remove value differences between the sides.The case
[1, _, 1]is similar to[4, _, 4]which is mentioned above.got it !
Very similar idea with better implementation, i guess,: 265693364.
Basic idea of D was almost exactly same as https://mirror.codeforces.com/problemset/problem/367/C
Super short solution for B.
int a = max(0ll, n-m), b=n+m;int ans = (b | ((1<<__lg(a^b))-1));if(!m){cout << n << endl;continue;}cout << ans << endlI just used the xor to account for the spread and chose the largest element that I can reach (m+n) as the base. The idea being that the largest bit in xor is the largest bit that spreads and all bits less than that would also spread.
simple bruteforce for problem solution
now i am realizing i am finding LCA but didn't realise at time
i like problem c though i use brute force to find the path during the contest...
Check this one: 265693364. I'm just using two pointers here.
Why do these writers write code that is not understandable.I agree you guys are pro but that doesnot mean every one can understand it.What does this means ,I am unable to understand for B: void solve() { ll n, m; scanf("%lld%lld", &n, &m); ll l = max(0LL, n — m), r = n + m, ans = 0; for (int i = 31; ; --i) { if ((l & (1LL << i)) || (r & (1LL << i)) || (l >> (i + 1)) != (r >> (i + 1))) { ans |= (1LL << i); } } printf("%lld\n", ans); }
please, why my code wrong (problem B)
include <bits/stdc++.h>
using namespace std;
long long cases, m, n;
int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
thanks, it has been fixed. I forgot to OR minn, i just think it is not important
(#include <bits/stdc++.h>) using namespace std;
long long cases, m, n;
string binary(int n) { string ans = ""; while (n > 0) { ans = char(n%2 + '0') + ans; n = n / 2; } return ans; }
int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
Hello In question D. Let the number of vertices in the complete graph be m. If m is odd, then the degree of each node is even, so this graph contains an Eulerian path, and the path length is equal to the number of edges, which is m(m+1)2.
But how the edges should be mc2 which is (m*(m-1)) / 2.
self-loop edges exist
Yaa I got thanks..
Can someone explain why are we looking at only the endpoints of the required sub array to look at in problem B?
In problem D if I tried to keep extra edges(when K is even) in the last 2 end points I get WA (https://mirror.codeforces.com/contest/1981/submission/263673037) but if i keep the first and the last end points I get AC (https://mirror.codeforces.com/contest/1981/submission/263675186)
Can someone explain what is the cause ?
Ex. n = 9, we get k = 4
If i distribute the edges such that degree looks like this 5 4 4 5 I get AC but if I distribute it as 4 4 5 5 I get WA as in the Eularian Path there are 2 pairs with same product. Why is my implementation going wrong in this type of distribution.
I believe it's because for finding an euler path, it is important where you are starting.
If the number of vertices V is odd, it doesn't matter because each vertex has an even degree.
If the number of vertices V is even, you presumably remove the edges until only 2 of the nodes have an odd degree. In that case, you have to start the
dfsfrom some vertex with odd degree. The algorithm relies on the fact that if you start on a vertex with odd degree, you can only end on the other node with odd degree (all other nodes have even degree), because if you enter nodes with even degree through an edge, you are guaranteed to have another edge to exit the node from.Thank you very much, I did not know that. I changed the starting vertex to the last vertex and got AC.
Ignoring the difficulty, I think this round is more edu than edu round.
just found this submission for D, and to me it seems very random. Can anybody explain why this part is correct (if it is)
act=(act+seguentSalt[act]++)%midahttps://math.stackexchange.com/questions/16933/generating-a-eulerian-circuit-of-a-complete-graph-with-constant-memory ig this helps
thanks!
This mentions a different method, namely, constructing a Euler circuit by decomposing a complete graph into Hamiltonian paths.. The above submission clearly uses varying paths which need not be Hamiltonian.
Btw, I asked the question on stackexchange, since I was not able to figure it out. Someone gave a proof for it: https://math.stackexchange.com/questions/4926360/finding-an-eulerian-path-on-complete-graphs.
B was solvable. I was stuck finding the pattern, rather I should have just wrote k th term of ai :(
Can there be any easier approach for C. can someone suggest without tree and a more intuitive solution for this..??
i mean only the explanation for finding an array knowing both the ends(a1 and an-1) might suffice!
Check my submission: 265693364. It is quite intuitive in both logic and implementation. The idea is to find two non-negative elements and use two pointers to fill the in-between -1s by dividing the greater one by 2 and writing on the left/right side accordingly. Mathematically:
if(v[right] >= v[left]) {v[right - 1] = v[right] / 2;right--;}else { v[left + 1] = v[left] / 2; left++; }And to handle edge cases, I have defined a vector of size n + 2, putting 0s on either side.
in fleury algorithm dont we have to check if the edge we are traversing is a bridge or not ? i read the code above for problem D afew times and i still dont get how they are handling it
Hello, I had the same problem trying to implement my function to find an eulerian path. I believe the author's solution doesn't use Fleury after all. In fact, it's some sort of Hierholzer's algorithm. You can try seeing that this method returns a valid eulerian path (or cycle) given dfs is first called on a vertice with odd degree (if there is one).
Now I'll always remember this simple method of finding the eulerian tour.
i solved it using Hierholzer's algorithm but it doesnt seem like Hierholzer's algorithm because in Hierholzer's algorithm you have to remove the edge u add when m is odd cuz the algorithm only finds cycles and not paths but in the authors solution they dont seem to remove any edge iam so lost trying to understand the intuition behind the authors solution honestly
Here's what I came up with : You run a dfs starting on an odd degree. It will then end on the other odd degree. But your path may not be complete. In fact, you can see that, when exiting a call to dfs, the remaining calls to dfs will insert loops at the path you are currently in.
In the end you have a valid path that visits all the edges.
Now with your remark I remember that there may have been an easy method where you remove the first and last edges, indeed ... But it should be about as easy to implement.
i feel so dumb we forgot the fact that we are dealing with a complete graph thats why it'll always end with a complete path on the other odd vertex
Well, when you reach the first end of a dfs function, the path may not be complete. But it will for sure be on the other vertex with odd degree. That's because when you enter a vertex, if it initially had an even degree, then when you leave it it will have an even degree again : either 0 and you don't come back to it, or something positive and you will be able to exit it again.
Now when it backtracks through the dfs, it will find other paths that will have to be loops (similar proof).
it took me a minute there but i see what you mean, now i think the only time we need to add and edge between the odd vertices is when we are starting from an arbitrary vertex but if we are only starting from one of the 2 odd vertices then there is no need for me to add that extra edge
Sorry for making mistakes. We should use Hierholzer's algorithm in this problem.
Also, I've seen your code. Note that you don't need to binary search the right $$$m$$$ at the beginning. It's something that was suggested by the editorial I know, but in fact you can do a linear search ; the complexity is perfectly fine.
yea also another thing so weird i dont seem to understand is that if we use the Hierholzer's algorithm starting from an odd vertex without adding the edge that we remove later it'll work for some reason i cant seem to wrap my head around this algo
why does it need to be an Eulerian path?
may someone tell me why my code get wrong answer in the sample 1 1000000? https://mirror.codeforces.com/contest/1981/submission/264373070
I cannot understand this fact
The left$$$1$$$spreading to$$$a_n$$$takes$$$x+1$$$seconds, and the right$$$1$$$spreading to$$$a_n$$$takes$$$2^d−x$$$seconds. Suppose, I am taking 10001101 number in binary, then how the bits are spreading in it from left to right and right to left?Umm Actually we are talking about dth bit there so when x lies in range 0 <= x <= 2^d — 1 let say d = 2 here then 0 <= x <= 3 now imagine a number line from 0 to 3. x is the point where the number lies on that number line. on that number line -1 and 2^d will be only numbers whose dth bit will be set for more clear view
now see here for 2nd bit can only be set because of 4 and -1 now x is the point where you actually number lies in this number line (How far is it from 0) the distance is simply the time taken to set the bit as you can tell from left it will be x + 1 and from right it will be 2^d — x so basically we are just shifting some number to number line of 0 — (2^d — 1) . I hope this does not confuse you more I understood it this way. Correct me if I am wrong somewhere
Can anyone explain me the second solution of problem B?
How/Why [l / 2^(d + 1)] != [r / 2^(d + 1)], d-th bit of answer is 1? I'm confused at "flipped.
Thanks alot!
Consider ith bit (from right), we know the bit is off in l and r otherwise we would already include it in answer. Now for number between l-1 and r-1 (inclusive) we have to check whether ith bit is on any time. Notice when you write consecutive numbers, ith bit is on for 2^(i-1) times consecutively and then off for 2^(i-1) times (consecutively). For eg, look at the 3rd bit from right between the numbers 16 and 24
In this sequence the 3rd bit from right is on 4 times from 16 to 19 and then off for 4 times from 20 to 23 and the pattern repeats. You are given l and r such that ith bit is off in both of them. Thus if the numbers between l and r is greater than or equal to 2^(i-1) then the bit must have flipped in the range otherwise not.
You can check my submission I think it is clean
https://mirror.codeforces.com/contest/1981/submission/265039262
Oh! I understood. Thanks.
Still haven't got why in D we should remove m/2 — 1, not m/2. Can somebody explain?
Hi! Thanks for the tasks. Does anyone has thoughts/any references on how the proof for F can be generalized beyond chains? As I understand, we have proved that optimal solutions for chains it's $$$O(\frac{n}{ln{n}})$$$, but that argument doesn't fit for trees (for example, full binary trees consisting of ones).
We need some chains to cover a tree, and if for a single chain we need to consider MEX up to $$$O(\frac{n}{\ln n})$$$, then in the whole tree we also just need to consider MEX up to $$$O(\frac{n}{\ln n})$$$.
Thank you! Now it's clear.
.
why in solution 1 of problem B x <= 2 ^ d — 1, and not x <= 2 ^ (d + 1) — 1?