Editorial for Bedao Grand Contest 13 - MAGICSHOP
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Trước hết bạn cần đọc về XOR basis ở blog này.
Trong bài toán này có thể thấy rằng mỗi bộ sưu tập là một cơ sở (basis) của không gian vector con của ~\mathbb{Z}_2^{64}~ chứa các vector ~c_1,c_2,\ldots,c_n~.
Một số định nghĩa:
- Một vector v được gọi là tổ hợp tuyến tính của tập ~S=\{s_1,s_2,\ldots,s_k\}~ nếu tồn tại cách biểu diễn ~v=c_1s_1\oplus c_2s_2\oplus\ldots c_ks_k~ sao cho ~c_i\in \{0,1\}~.
- Tập vector ~S~ được gọi là độc lập tuyến tính nếu vector ~0~ không phải một tổ hợp tuyến tính của ~S~.
- ~\text{span}(S)=\text{span}\{s_1,s_2,\ldots,s_k\}~ là không gian vector chứa tất cả các tổ hợp tuyến tính của tập ~S~. Nếu ~S~ độc lập tuyến tính thì ~S~ được gọi là một cơ sở của không gian vector trên.
Một số tính chất: Giả sử các tập vector trong ~\text{span}~ dưới đây độc lập tuyến tính.
- Nếu ~\text{span}\{u_1,u_2,\ldots,u_k,x\}=\text{span}\{v_1,v_2,\ldots,v_k,x\}~ thì ~\text{span}\{u_1,u_2,\ldots,u_k\}=\text{span}\{v_1,v_2,\ldots,v_k\}~.
- Nếu ~\text{span}\{u_1,u_2,\ldots,u_k\}=\text{span}\{v_1,v_2,\ldots,v_k\}=V~ và ~u_i\ne v_j~ với mọi ~i,j~ thì tồn tại ~i,j~ sao cho ~\text{span}\{u_1,u_2,\ldots,u_{i-1},v_j,u_{i+1},\ldots,u_k\}=V~ (thay ~u_i~ bởi ~v_j~).
- Nếu ~\text{span}\{u_1,u_2,\ldots,u_k,x\} = \text{span}\{u_1,u_2,\ldots,u_k,y\}=V~ thì ~\text{span}\{v_1,v_2,\ldots,v_k,x\}=V\Leftrightarrow \text{span}\{v_1,v_2,\ldots,v_k,y\}=V~ với mọi tập.
Từ tính chất ~3~ ta có thể đơn giản hoá điều kiện của bài toán: Gọi ~f_i~ là giá của món đồ ~i~ sau khi thay đổi.
- Xét tập ~A~, nếu thay ~a_i~ bởi ~c_j~ mà ~A~ vẫn là một cơ sở thì ~f_{a_i}\le f_j~ sau khi thay đổi giá.
- Xét tập ~B~, nếu thay ~b_i~ bởi ~c_j~ mà ~B~ vẫn là một cơ sở thì ~f_{b_i}\ge f_j~ sau khi thay đổi giá.
Ta xây dựng một đồ thị ~G~, với mỗi ~x,y~ ta có cạnh từ ~x~ đến ~y~ nếu ~f_x\le f_y~.
Đây là bài toán "Partially Ordered Isotonic Regression". Một lời giải của bài toán này được đề cập trong blog codeforces SRM 720. Lưu ý rằng ta cần sửa công thức "đạo hàm" trong bài toán.
Code mẫu
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; #define fi first #define se second typedef unsigned long long u64; typedef long long ll; const ll INF=1e16; struct Dinic{ struct edge{ int to;ll cap;int rev; edge(int to,ll cap,int rev): to(to),cap(cap),rev(rev) {} }; vector<edge>g[1005]; int n,lev[1005],iter[1005]; bool vis[1005]; void init(int N){ n=N;for(int i=1;i<=N;i++)g[i].clear(); } void addedge(int u,int v,ll w){ g[u].push_back(edge(v,w,g[v].size())); g[v].push_back(edge(u,0,g[u].size()-1)); } void bfs(int s){ memset(lev,-1,(n+2)<<2); queue<int>que;lev[s]=0,que.push(s); while(!que.empty()){ int u=que.front();que.pop(); for(int i=0;i<g[u].size();i++){ edge x=g[u][i]; if(x.cap==0||lev[x.to]>=0)continue; lev[x.to]=lev[u]+1,que.push(x.to); } } } ll dfs(int x,int t,ll F){ if(x==t)return F; for(int &i=iter[x];i<g[x].size();i++){ edge &e=g[x][i]; if(lev[e.to]>lev[x]&&e.cap>0){ ll d=dfs(e.to,t,min(F,e.cap)); if(d>0){e.cap-=d;g[e.to][e.rev].cap+=d;return d;} } } return 0; } ll maxflow(int s,int t){ ll ret=0;for(;;){ bfs(s);if(lev[t]<0)return ret; memset(iter,0,(n+2)<<2);ll f; while((f=dfs(s,t,INF))>0)ret+=f; } } vector<pii>getCut(int s,int t){ vector<pii>v; bfs(s); for(int i=1;i<=n;i++)if(lev[i]!=-1) for(int j=0;j<g[i].size();j++){ edge E=g[i][j]; if(lev[E.to]==-1&&E.cap==0&&(i==s||E.to==t)) v.push_back({i,E.to}); } return v; } }Gr; int n,m,v[1005],A[70],B[70]; u64 c[1005];bool ina[1005],inb[1005]; vector<int>g[1005];ll ans; int id[1005],tg[1005],cnt; ll ta[1005],tb[1005];bool res[1005]; void sol(int l,int r,vector<int>vec){ if(vec.empty())return; if(r-l==1){ int tot=2,S=1,T=2;++cnt; for(int i=0;i<vec.size();i++){ int x=vec[i]; ta[x]=(ll)(v[x]-l)*(v[x]-l),tb[x]=(ll)(v[x]-r)*(v[x]-r); id[x]=++tot,tg[x]=cnt; } Gr.init(tot); for(int i=0;i<vec.size();i++){ int x=vec[i]; ll d=tb[x]-ta[x]; if(d<0)Gr.addedge(S,id[x],-d),res[id[x]]=1; else Gr.addedge(id[x],T,d),res[id[x]]=0; for(int j=0;j<g[x].size();j++){ int y=g[x][j]; if(tg[y]==cnt)Gr.addedge(id[x],id[y],INF); } } Gr.maxflow(S,T); vector<pii>CUT=Gr.getCut(S,T); for(int i=0;i<CUT.size();i++){ pii x=CUT[i]; if(x.fi==S)res[x.se]=0; if(x.se==T)res[x.fi]=1; } for(int i=0;i<vec.size();i++){ int x=vec[i]; if(res[id[x]]==0)ans+=ta[x]; if(res[id[x]]==1)ans+=tb[x]; } return; } int md=(l+r)>>1,tot=2,S=1,T=2;++cnt; for(int i=0;i<vec.size();i++)id[vec[i]]=++tot,tg[vec[i]]=cnt; Gr.init(tot); for(int i=0;i<vec.size();i++){ int x=vec[i];ll d=2*(md-v[x]); if(d<0)Gr.addedge(S,id[x],-d),res[id[x]]=1; else Gr.addedge(id[x],T,d),res[id[x]]=0; for(int j=0;j<g[x].size();j++){ int y=g[x][j]; if(tg[y]==cnt)Gr.addedge(id[x],id[y],INF); } } Gr.maxflow(S,T); vector<pii>CUT=Gr.getCut(S,T); for(int i=0;i<CUT.size();i++){ pii x=CUT[i]; if(x.fi==S)res[x.se]=0; if(x.se==T)res[x.fi]=1; } vector<int>vl,vr; for(int i=0;i<vec.size();i++){ int x=vec[i]; if(res[id[x]]==0)vl.push_back(x); if(res[id[x]]==1)vr.push_back(x); } sol(l,md,vl),sol(md,r,vr); } u64 bsa[64],bsb[64]; void ins(u64 *a,u64 x){ for(int i=63;~i;i--)if((x>>i)&1){ if(!a[i]){a[i]=x;break;} x^=a[i]; } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%llu",&c[i]); for(int i=1;i<=n;i++)scanf("%d",&v[i]); for(int i=1;i<=m;i++)scanf("%d",&A[i]),ina[A[i]]=1; for(int i=1;i<=m;i++)scanf("%d",&B[i]),inb[B[i]]=1; for(int i=1;i<=m;i++){ for(int j=0;j<64;j++)bsa[j]=bsb[j]=0; for(int j=1;j<=m;j++)if(i!=j) ins(bsa,c[A[j]]),ins(bsb,c[B[j]]); for(int j=1;j<=n;j++){ u64 va=c[j],vb=c[j]; for(int k=63;~k;k--){ if((va^bsa[k])<va)va^=bsa[k]; if((vb^bsb[k])<vb)vb^=bsb[k]; } if(va&&!ina[j])g[A[i]].push_back(j); if(vb&&!inb[j])g[j].push_back(B[i]); } } vector<int>vec; for(int i=1;i<=n;i++)vec.push_back(i); sol(0,1e6,vec);printf("%lld",ans); }
Comments