NOI 2025
I did this contest to try and fix my sleep schedule. Been sleeping like 9am - 5pm for like a week. So the previous day I managed to take a nap until 1am then managed to stay awake until 12mn. But after that basically slept for 16 hours straight, messing up sleep cycle. I just woke up at like 7am just now to write this blog… will see if I mange to fix sleep cycle.
Anyways, actual comments on NOI is that the difficulty curve felt very flat. In my opinion 1=2=3=4««5 in terms of theory solve. Unlike previous year’s P5 where the difficulty was due to the problem being super tedious and disgusting, this year’s P5 was quite pleasant to solve (and also hard!).
I managed to get 428 points in 2 hours and spent another 1.5 hours getting the remaining points so I think this year is also much easier than previous years to get high points on. I think it’s good cause previous years were just too brutal.
P1 - Monsters
I actually had to think for this problem. I think it is a bit problematic if someone of my skill level has to spend time thinking for the Q1 of NOI. Like the problem did not even seem solvable when I first read it.
Stupid problem ngl.
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m;
ii arr[200005];
int brr[200005];
set<int> s1,s2;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>m;
rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
rep(x,1,m+1) cin>>brr[x];
sort(brr+1,brr+m+1);
brr[0]=-1e18,brr[m+1]=1e18;
int ans=0;
rep(x,1,n+1){
auto it=lb(brr,brr+m+2,arr[x].fi)-brr;
int a=1+min(abs(brr[it-1]-arr[x].fi),abs(brr[it]-arr[x].fi));
int b=arr[x].se;
if (a<=b){
a=abs(brr[it-1]-arr[x].fi);
b=abs(brr[it]-arr[x].fi);
// cout<<x<<" "<<a<<" "<<b<<" "<<it<<endl;
if (a==b) s2.insert(it-1);
else if (a<b) s1.insert(it-1);
else s1.insert(it);
ans+=min(a,b);
}
else{
ans+=arr[x].se;
}
}
ans+=sz(s1);
for (auto it:s2){
if (s1.count(it) || s1.count(it+1)) continue;
s1.insert(it+1);
ans++;
}
cout<<ans<<endl;
}
P2 - Thumper
When you read this problem, you kind have to assume that the moves are purposely made such that the relative positions of any pair of rabbits do not change. This fact is not very hard to prove. Just show that diagonals are invariant.
So one realizes that the order of operations does not matter. So this becomes some data structure problem.
There are probably smarter ways to write the code but using linesweep and fenwick tree after rotating the grid by $45 \degree$ was the first thing that came to my mind.
Nice problem, but I didn’t have fun writing the DS.
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct FEN{
int fen[500005]={};
void upd(int i,int k){
while (i<500005){
fen[i]+=k;
i+=i&-i;
}
}
int query(int i){
int res=0;
while (i){
res+=fen[i];
i-=i&-i;
}
return res;
}
int query(int i,int j){
return query(j)-query(i-1);
}
} fen1,fen2;
int n,q;
ii arr[500005];
ii brr[500005];
int cnt[500005];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>q;
rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
rep(x,1,q+1){
int a; cin>>a;
cnt[a]++;
}
rep(x,1,n+1) brr[x].fi=arr[x].fi+arr[x].se,brr[x].se=arr[x].fi-arr[x].se;
vector<int> uni;
rep(x,1,n+1) uni.pub(brr[x].se);
sort(all(uni));
rep(x,1,n+1) brr[x].se=lb(all(uni),brr[x].se)-uni.begin()+1;
vector<int> idx;
rep(x,1,n+1) idx.pub(x);
sort(all(idx),[](int i,int j){
return brr[i].fi>brr[j].fi;
});
rep(x,1,n+1) fen2.upd(brr[x].se,cnt[x]);
while (!idx.empty()){
vector<int> idx2;
int X=brr[idx.back()].fi;
while (!idx.empty() && X==brr[idx.back()].fi){
idx2.pub(idx.back());
idx.pob();
}
sort(all(idx2),[](int i,int j){
return brr[i].se<brr[j].se;
});
for (auto it:idx2) fen2.upd(brr[it].se,-cnt[it]);
for (auto it:idx2){
int a=fen1.query(1,brr[it].se-1);
int b=fen1.query(brr[it].se,brr[it].se);
int c=fen1.query(brr[it].se+1,500004);
arr[it].fi+=2*a+b;
arr[it].se+=2*c+b;
}
for (auto it:idx2){
int a=fen2.query(1,brr[it].se-1);
int b=fen2.query(brr[it].se,brr[it].se);
int c=fen2.query(brr[it].se+1,500004);
arr[it].fi-=2*c+b;
arr[it].se-=2*a+b;
}
int pref=0,suf=0;
for (auto it:idx2) suf+=cnt[it];
for (auto it:idx2){
suf-=cnt[it];
arr[it].fi+=pref-suf;
arr[it].se+=suf-pref;
pref+=cnt[it];
}
for (auto it:idx2) fen1.upd(brr[it].se,cnt[it]);
}
rep(x,1,n+1) cout<<arr[x].fi<<" "<<arr[x].se<<endl;
}
P3 - Reachability
I think for this problem, it really helps to consider the case where all roads are one-way.
Then it is sufficient and necessary to check that there is an assignment to edges such that $a_u = 1 + \sum\limits_{u \to v \in E} a_v$.
We can clearly do that using dp. Like $dp[u][k]$ denotes whether it is possible to assign edges on the subtree of $u$ such that the condition on all descendant on $u$ is satisfied and $k$ is the sum of $\sum\limits_{u \to v \in E} a_v$ where $v$ is restricted to the children of $u$. Then when we try to combine the dp the the parent of $u$, we need to account for the case where there is an edge $u \to p_u$ so we can add $a_{p_u}$ to $k$.
Then it is not too hard to modify this dp to the full case where we allow edges to be bidirectional. Unfortunately, this requires us to do convolution on the dp values. Luckily, we can represent each $dp[u]$ as a bitset, so convolution is only $O(\frac{n^2}{w})$. But it does not pass.
Now, you were supposed to realize that $dp[u][k]$ can only be true if $k \leq sz_u$, so you can distribution dp.
But there is actually a scammy way to do that with bitsets in $O(\frac{n^2 \log n}{w})$. Like suppose that the number of set bits of the bitsets is $b_1$ and $b_2$ respectively. Then we can do the convolution in $O(\frac{\min(b_1,b_2) \cdot n}{w})$.
Then because of set-merging, if we do the convolution in that complexity, the sum of $\min(b_1,b_2) \leq \min(sz_a,sz_b)$ is $O(n \log n)$ due to set-merging time complexity proof.
I thought that my method was $O(\frac{n^3}{w})$ and I scammed, but really it is $O(\frac{n^2 \log n}{w})$.
So I’ve always thought distribution dp was kinda crazy for speeding up $O(n^3)$ to $O(n^2)$ but now that I think about it, it’s not super crazy as set-merging time complexity proof actually gives us $O(n^2 \log n)$ already.
Classical problem.
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
int arr[5005];
bitset<5005> bm[5005]; //shitset
vector<int> al[5005];
void dfs(int i,int p){
bm[i][0]=1;
for (auto it:al[i]){
if (it==p) continue;
dfs(it,i);
bitset<5005> res;
if (bm[it][arr[it]]) res|=bm[i]|(bm[i]<<arr[it]);
if (arr[it]>=arr[i] && bm[it][arr[it]-arr[i]]) res|=bm[i];
if (arr[it]==arr[i]){
if (bm[it].count()<bm[i].count()){
rep(y,0,5005) if (bm[it][y]) res|=bm[i]<<y;
}
else{
rep(y,0,5005) if (bm[i][y]) res|=bm[it]<<y;
}
}
bm[i]=res;
}
bm[i]<<=1;
// cout<<i<<endl;
// rep(y,1,11) cout<<bm[i][y]<<" "; cout<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n;
rep(x,1,n+1) cin>>arr[x];
rep(x,1,n){
int a,b; cin>>a>>b;
al[a].pub(b);
al[b].pub(a);
}
dfs(1,-1);
if (bm[1][arr[1]]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
P4 - Robots
If you consider the final positions of the each robot, it is monotonic. Therefore, it makes sense to consider asking if for each range $[l,r]$ of robots, we can make it end up in the same position. Actually it is sufficient to check only robot $l$ and $r$ due to the monotonic condition.
Then we just need to find the minimum and maximum positions $mn_i$ and $mx_i$ that each robot $i$ can end up in. Then $[l,r]$ can end up in the same position if $mn_r \leq mx_l$.
It is clear that a greedy strategy would work for this problem. That is, for the range $[a,b]$, find the maximum $b’$ such that $[a,b’]$ is a valid range and remove those robots. To speed it up, use binary lifting.
Again, classical problem.
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int p[200005];
int val[200005];
int par(int i){
if (p[i]==i) return i;
else return p[i]=par(p[i]);
}
int h,w,q;
int arr[200005];
ii range[200005];
int nxt[200005][20];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>h>>w;
rep(x,1,w+1) cin>>arr[x];
rep(x,1,h+1) p[x]=x,val[x]=x;
rep(x,1,w+1){
int lo=1,hi=h+1,mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (val[par(mi)]<=arr[x]) lo=mi;
else hi=mi;
}
lo=par(lo);
if (val[lo]==arr[x]) val[lo]--;
if (lo!=1 && val[par(lo-1)]==val[lo]) p[lo]=par(lo-1);
}
rep(x,1,h+1) range[x].fi=val[par(x)];
rep(x,1,h+1) p[x]=x,val[x]=x;
rep(x,1,w+1){
int lo=0,hi=h,mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (val[par(mi)]>=arr[x]) hi=mi;
else lo=mi;
}
hi=par(hi);
if (val[hi]==arr[x]) val[hi]++;
if (hi!=h && val[par(hi+1)]==val[hi]) p[hi]=par(hi+1);
}
rep(x,1,h+1) range[x].se=val[par(x)];
int curr=1;
rep(x,1,h+1){
while (curr<=h && range[curr].fi<=range[x].se) curr++;
nxt[x][0]=curr;
}
nxt[h+1][0]=h+1;
rep(y,0,19){
rep(x,1,h+2){
nxt[x][y+1]=nxt[nxt[x][y]][y];
}
}
cin>>q;
while (q--){
int a,b; cin>>a>>b; b++;
int ans=0;
rep(x,20,0) if (nxt[a][x]<b){
a=nxt[a][x];
ans+=1<<x;
}
cout<<ans+1<<endl;
}
}
P5 - Flooding
As I understand from the problem author, only $4$ people got at least $60$ points and only I got a legitimate $O(n^{2+o(1)})$ solution it seems, everyone else scammed with $O(n^3)$ or something.
Actually, the $O(n^2 \log n)$ I coded did not pass the time limits. After checking now, it only fails on $2$ testcases. So during contest I changed it to what I thought was $O(n^3)$ and it got AC. But I think problem author claims that the part I thought was $O(n^3)$ is actually $O(n^2)$ or something. So good for me I guess?
The idea for this problem is that for each empty cell $(x,y)$ we need to find the smallest rectangle $(x_1,x_2,y_1,y_2)$ such that $(x_1-1,y)$ and $(x_2+1,y)$ are all non-empty for $y_1 \leq y \leq y_2$ and $(x,y_1-1)$ and $(x,y_2+1)$ are all non-empty for $x_1 \leq x \leq x_2$. Also the rectangle should cover point $(x,y)$ so we have $x_1 \leq x \leq x_2$ and $y_1 \leq y \leq y_2$.
Note that minimizing $x_2-x_1$ also minimizes $y_2-y_1$.
It is not too hard to solve this problem in $O(hw (h+w))$. Just try to expand the rectangle greedily.
So solve it in $O(n^2 \log n)$ realize that there are only $O(n^2)$ rectangles that you care about.
Like if $(x_1,x_2,y_1,y_2)$ and $(x_1,x_3,y_1,y_2)$ are both valid rectangles with $x_1<x_2<x_3$, then $(x_2,x_3,y_1,y_2)$ is also a valid rectangle and $(x_1,x_3,y_1,y_2)$ is useless.
For this reason, if we fixed $x_2,y_1,y_2$, we only need to consider the maximum $x_1$ that forms a valid rectangle as the rest will be useless.
It is not too hard to find this $x_1$ in $O(\log n)$ with some data structures. You can make it a single binary search so it is low constant.
Now, let us fix the value of $x_2$. Let’s also define $U_{x,y}$ as the number of consecutive cells $(x-1,y), (x-2,y), \ldots$ that are non-empty.
I claim that we should only consider $(\cdot,x_2,y_1,y_2)$ as a valid rectangle if $\min(U_{x,y_1},U_{x,y_2}) > \max(U_{x,y_1+1},\ldots,U_{x,y_2-1})$.
Otherwise, suppose $y_1 < y < y_2$ and WLOG $U_{x,y_1} \leq U_{x,y}, U_{x,y_2}$.
Then we consider the rectangle $(x,x_2,y_1,y_2)$. We should note that if $(x,x_2,y_1,y_2)$ is a valid rectangle, then so is $(x,x_2,y_1,y)$. Then $(x,x_2,y_1,y_2)$ is a useless rectangle since $(x,x_2,y_1,y)$ is valid.
Then we know from using min-stack that the number of such $(y_1,y_2)$ pair for each $x$ is $O(n)$. So there are only $O(n^2)$ of such triples $(\cdot,x_2,y_1,y_2)$.
Then now we have $O(n^2)$ rectangles. We need to find the minimum area of a rectangle that a point is contained inside. This is not too hard to do using segment trees in $O(n^2 \log n)$ but I got constant time TLE.
During contest, I coded $O(n^2)$ loop for each rectangle. Like $mn_{(x,y)}$ is the minimum area of the the rectangle that contains point $(x,y)$. So when we find a rectangle $(x_1,x_2,y_1,y_2)$, we do a $O(n^2)$ loop to update $mn_{(x,y)}$ for all $x_1 \leq x \leq x_2, y_1 \leq y \leq y_2$. This surprisingly gets $n=2000$ subtask. real?
Anyways, so I guess that $\sum x_2-x_1$ is probably small (or at least small in the testcases) and I just coded that and it got AC. I’m not sure why it’s not $O(n^3)$ but author says he has a proof that it is $O(n^2)$ or something?
Anyways, good problem, but tests funny.
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct NODE{
const int BUF=5005;
ii arr[10010];
void update(int i,int k){
arr[i+BUF]={k,i};
i+=BUF;
while (i){
i>>=1;
arr[i]=max(arr[i<<1],arr[i<<1|1]);
}
}
ii query(int i,int j){
i+=BUF,j+=BUF+1;
ii res={0,0};
while (i<j){
if (i&1) res=max(res,arr[i++]);
if (j&1) res=max(res,arr[--j]);
i>>=1,j>>=1;
}
return res;
}
} root;
int n,m;
string s[5005];
int U[5005][5005];
int L[5005][5005];
vector<int> idx[5005];
int ans=0;
vector<int> AA[5005];
void proc(int x,int y1,int y2){
if (y2-y1==1) return;
// cout<<"---"<<endl;
// cout<<x<<" "<<y1<<" "<<y2<<endl;
// for (auto it:idx[y2]) cout<<it<<" "<<L[it][y2-1]<<endl;
int lo=-1,hi=sz(idx[y2]),mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (L[idx[y2][mi]][y2-1]>=(y2-y1-1)) lo=mi;
else hi=mi;
}
if (lo==-1) return;
int h=idx[y2][lo];
if (min(U[x-1][y1],U[x-1][y2])<(x-h-1)) return;
// cout<<y1<<" "<<y2<<" "<<h<<" "<<x<<endl;
// rep(i,h+1,x) rep(j,y1+1,y2) mn[i][j]=min(mn[i][j],(x-h-1)*(y2-y1-1));
int l=y1+1,r=y2;
rep(idx,l,r+1){
while (AA[idx].back()>h){
ans+=(x-h-1)*(y2-y1-1);
AA[idx].pob();
}
// root.update(idx,AA[idx].back());
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>m;
rep(x,1,n+1) cin>>s[x],s[x]="1"+s[x]+"1";
s[0]=s[n+1]=string(m+2,'1');
n+=2,m+=2;
// rep(x,0,n) cout<<s[x]<<endl;
rep(x,0,n) rep(y,0,m) if (s[x][y]=='1'){
U[x][y]=1;
if (x) U[x][y]+=U[x-1][y];
}
rep(x,0,n) rep(y,0,m) if (s[x][y]=='1'){
L[x][y]=1;
if (y) L[x][y]+=L[x][y-1];
}
rep(y,0,m) AA[y].pub(0);
rep(x,0,n){
vector<int> stk;
rep(y,0,m){
if (x){
if (s[x-1][y]=='0'){
AA[y].pub(x-1);
// root.update(y,AA[y].back());
}
while (!stk.empty() && U[x-1][stk.back()]<=U[x-1][y]){
proc(x,stk.back(),y);
stk.pob();
}
if (!stk.empty()) proc(x,stk.back(),y);
}
if (s[x][y]=='0') stk.clear();
if (x){
stk.pub(y);
}
if (y){
while (!idx[y].empty() && L[idx[y].back()][y-1]<=L[x][y-1]){
idx[y].pob();
}
}
if (s[x][y]=='0') idx[y].clear();
if (y){
idx[y].pub(x);
}
}
}
cout<<ans<<endl;
}