Thank you for participating! We hope you find our problems interesting.
1981A - Turtle and Piggy Are Playing a Game
Idea: zltzlt
What is Piggy's optimal strategy?
What does $$$2l \le r$$$ mean?
#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
Consider each bit separately.
Calculate the time when the $$$d$$$-th bit of $$$a_n$$$ becomes $$$1$$$.
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.
#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;
}
#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
Figure out the case where $$$a'_1 \ne -1, a'_n \ne -1$$$ and $$$a'_2 = a'_3 = \cdots = a'_{n - 1} = -1$$$ first.
Imagine a full binary tree. Consider the sequence as a walk on the full binary tree.
#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
$$$a_i$$$ should take different primes.
Transform it into a graph problem.
#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.
Stop thinking about Boruvka.
Most of the edges in the graph are useless.
#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!
Try some dp that takes $$$O(n^2)$$$ time.
What's the maximum MEX in the optimal good set of paths?
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}$$$.
The time complexity of this algorithm is $$$\mathcal{O}(n \log n)$$$.
#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 : i);
}
return;
}
if ((int)G[u].size() == 1) {
int v = G[u][0];
dfs(v);
int mn = inf;
for (int i = 1; i <= m; ++i) {
if (i != a[u]) {
mn = min(mn, f[v][i]);
}
}
for (int i = 1; i <= m; ++i) {
f[u][i] = min(f[v][i], mn + (u > 1 ? i : 0));
}
if (a[u] <= m) {
f[u][a[u]] = inf;
}
return;
}
int v = G[u][0], w = G[u][1], mn1 = inf, mn2 = inf, mn3 = inf;
dfs(v);
dfs(w);
for (int i = 1; i <= m; ++i) {
if (i != a[u]) {
mn1 = min(mn1, f[v][i] + f[w][i] - i);
mn2 = min(mn2, f[v][i]);
mn3 = min(mn3, f[w][i]);
}
}
for (int i = 1; i <= m; ++i) {
f[u][i] = min({mn1 + (u > 1 ? i : 0), mn2 + mn3 + (u > 1 ? i : 0), mn2 + f[w][i], mn3 + f[v][i]});
}
if (a[u] <= m) {
f[u][a[u]] = inf;
}
}
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);
printf("%d\n", *min_element(f[1] + 1, f[1] + m + 1));
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
#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
*/