Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
#define O(x) cout<<#x<<" "<<(x)<<"\n"
inline int read(){
int x=0,f=1,c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=104;
int n,sum,a[N];
vector<pair<int,int> >ans;
inline void solve(){
n=read();
sum=0;
ans.clear();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++){
a[i]-=read();
sum+=a[i];
}
if(sum){puts("-1");return;}
for(int i=1;i<=n;i++){
for(int j=1;j<=a[i];j++){
for(int k=1;k<=n;k++)if(a[k]<0){
ans.push_back(make_pair(i,k));
++a[k];
break;
}
}
}
cout<<ans.size()<<"\n";
for(auto v:ans)cout<<v.first<<" "<<v.second<<"\n";
}
int main(){
for(int T=read();T--;)solve();
return 0;
}
Idea: Cirno_9baka
Tutorial is loading...
solution
#include <cstdio>
const int Maxn=1000000;
char s[Maxn+5];
char ans[Maxn+5];
int n,m;
void solve(){
scanf("%d%d",&n,&m);
n=(n<<1)-1;
for(int i=1;i<=m;i++){
ans[i]=0;
}
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++){
ans[j]^=s[j];
}
}
for(int i=1;i<=m;i++){
putchar(ans[i]);
}
putchar('\n');
}
int main(){
int T;
scanf("%d",&T);
while(T--){
solve();
}
return 0;
}
Idea: AquaMoon
Tutorial is loading...
solution
#include <bits/stdc++.h>
std::vector<int> a;
int cnt[100001][2];
int main() {
int n, T, flag;
scanf("%d", &T);
while(T--){
scanf("%d", &n), a.resize(n), flag = 0;
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]), ++cnt[a[i]][i % 2];
std::sort(a.begin(), a.end());
for (int i = 0; i < n; ++i)
--cnt[a[i]][i % 2];
for (int i = 0; i < n; ++i)
if (cnt[a[i]][0] != 0 || cnt[a[i]][1] != 0) {
puts("NO"), flag = 1;
break;
}
if (flag == 0) puts("YES");
a.clear();
for (int i = 0; i < n; ++i)
cnt[a[i]][0] = cnt[a[i]][1] = 0;
}
return 0;
}
Idea: Cirno_9baka
Tutorial is loading...
solution
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int MOD = 998244353;
char str[MAXN];
long long F[MAXN], rF[MAXN];
long long inv(long long a, long long m) {
if (a == 1) return 1;
return inv(m%a, m) * (m - m/a) % m;
}
int main() {
int T;
int n;
F[0] = rF[0] = 1;
for (int i = 1; i < MAXN; i++) {
F[i] = F[i-1] * i % MOD;
rF[i] = rF[i-1] * inv(i, MOD) % MOD;
}
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
scanf("%s", str);
int cg = 0;
int c0 = 0;
int c1 = 0;
for (int i = 0; i < n; i++) {
if (str[i] == '0') {
c0++;
} else if (i+1 < n && str[i+1] == '1') {
cg++;
i++;
} else {
c1++;
}
}
long long ans = F[cg + c0] * rF[c0] % MOD * rF[cg] % MOD;
printf("%d\n", (int) ans);
}
return 0;
}
Idea: Cirno_9baka
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
const long long mod=998244353;
typedef pair<int,int> pii;
int n,x,y,s,t;
int a[maxn*2+5][maxn+5],b[maxn+5][maxn+5],f[maxn+5];
vector <pii> v;
vector <int> c[maxn+5][maxn+5];
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
b[i][j]=0;
c[i][j].clear();
}
}
for (int i=1;i<=n*2;i++)
{
f[i]=0;
for (int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
b[j][a[i][j]]++;
c[j][a[i][j]].push_back(i);
}
}
int top=0,tail=0;
int cnt=0,idx=1;
long long ans=1;
v.clear();
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (b[i][j]==1)
{
tail++;
v.push_back(pii(i,j));
}
}
}
while (cnt<n)
{
if (top<tail)
{
x=v[top].first;
y=v[top].second;
if (b[x][y]!=1)
{
top++;
continue;
}
for (int i=0;i<c[x][y].size();i++)
{
if (f[c[x][y][i]]==0)
{
t=c[x][y][i];
break;
}
}
}
else
{
while (f[idx]!=0)
{
idx++;
}
t=idx;
ans=ans*2%mod;
}
f[t]=1;
cnt++;
for (int i=1;i<=n;i++)
{
b[i][a[t][i]]=0;
}
for (int i=1;i<=n;i++)
{
for (int j=0;j<c[i][a[t][i]].size();j++)
{
s=c[i][a[t][i]][j];
if (f[s]==0)
{
f[s]=2;
for (int k=1;k<=n;k++)
{
b[k][a[s][k]]--;
if (b[k][a[s][k]]==1)
{
tail++;
v.push_back(pii(k,a[s][k]));
}
}
}
}
}
top++;
}
s=0;
printf("%lld\n",ans);
for (int i=1;i<=n*2;i++)
{
if (f[i]==1)
{
s++;
if (s<n) printf("%d ",i); else printf("%d\n",i);
}
}
}
}
Idea: AquaMoon
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,k,ans1,ans2;
long long a[1010][1010];
long long c[1010],x,y,s,t,temp;
int main()
{
scanf("%d%d",&n,&m);
for (i=0;i<m;i++)
{
for (j=1;j<=n;j++)
{
scanf("%lld",&a[i][j]);
c[i]+=a[i][j];
}
}
x=(c[m-1]-c[0])/(m-1);
for (i=1;i<m;i++)
{
if ((c[i]-c[0])!=x*i)
{
ans1=i;
y=c[i]-c[0]-x*i;
break;
}
}
for (i=1;i<m-1;i++)
{
if (i-1!=ans1&&i!=ans1&&i+1!=ans1)
{
x=0;
for (j=1;j<=n;j++)
{
x+=a[i-1][j]*a[i-1][j]+a[i+1][j]*a[i+1][j]-a[i][j]*a[i][j]*2;
}
break;
}
}
i=ans1;
t=s=0;
for (j=1;j<=n;j++)
{
s+=a[i-1][j]*a[i-1][j]+a[i+1][j]*a[i+1][j];
t+=a[i][j]*a[i][j]*2;
}
s-=x;
for (j=1;j<=n;j++)
{
temp=t-a[i][j]*a[i][j]*2+(a[i][j]-y)*(a[i][j]-y)*2;
if (temp==s)
{
ans2=a[i][j]-y;
break;
}
}
cout<<ans1<<' '<<ans2<<endl;
}
Idea: AquaMoon
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
const int N=2000005,E=1000001;
struct str{
int l;
long long x;
int d;
long long las(){return x+(l-1)*d;}
}a[N];
int ch[N][2],fa[N],h[N],tot,hc,ls[N],siz[N],i;
struct seg{
int l,r,x;
bool operator <(const seg &a)const
{
return a.r>r;
}
};
set<seg> p;
void pushup(int i)
{
siz[i]=siz[ch[i][0]]+siz[ch[i][1]]+a[i].l;
}
void rotate(int x)
{
int y=fa[x];bool d=(ch[y][0]==x);
ch[y][!d]=ch[x][d];
if(ch[x][d]!=0)fa[ch[x][d]]=y;
fa[x]=fa[y];if(fa[y])ch[fa[y]][ch[fa[y]][1]==y]=x;
ch[x][d]=y;fa[y]=x;pushup(y);
}
void splay(int i,int x,int t=0)
{
for(int y=fa[x];y!=t;rotate(x),y=fa[x])
if(fa[y]!=t&&(ch[fa[y]][0]==y)==(ch[y][0]==x))
rotate(y);
pushup(x);
h[i]=x;
}
void Findmx(int x)
{
int i=h[x];
while(ch[i][1])
i=ch[i][1];
splay(x,i);
}
void Findmn(int x)
{
int i=h[x];
while(ch[i][0])
i=ch[i][0];
splay(x,i);
}
void MMerge(int x,int y)
{
if(h[y]==0||h[x]==0)
{
h[x]=h[y]=max(h[x],h[y]);
return;
}
int i=h[y];
for(;ch[i][0];i=ch[i][0]);
ch[i][0]=h[x];
fa[h[x]]=i;
splay(y,h[x]);
}
int Merge(int x,int y)
{
Findmx(x),Findmn(y);
if(abs(a[h[x]].las()-a[h[y]].x)<=1)
{
MMerge(x,y);
return x;
}
if(a[h[x]].las()>a[h[y]].x)
{
long long la=a[h[y]].x;
while(h[x]&&abs(a[h[x]].las()-la)>1)
{
if(a[h[x]].d==-1)
la+=a[h[x]].l;
else
{
if(la+a[h[x]].l<a[h[x]].x)
la+=a[h[x]].l;
else
{
int li=(a[h[x]].l-a[h[x]].x+la+2)/2;
la+=a[h[x]].l-li;
a[h[x]].l=li;
break;
}
}
h[x]=ch[h[x]][0];
fa[h[x]]=0;
Findmx(x);
}
h[++hc]=++tot;
a[tot]={(int)(la-a[h[y]].x),la,-1};
pushup(tot);
ls[hc]=ls[x];
MMerge(x,hc);
MMerge(hc,y);
}
else
{
long long la=a[h[x]].las();
while(h[y]&&abs(a[h[y]].x-la)>1)
{
if(a[h[y]].d==1)
la+=a[h[y]].l;
else
{
if(a[h[y]].las()>la+a[h[y]].l)
la+=a[h[y]].l;
else
{
int li=(a[h[y]].x-la)/2;
a[h[y]].x-=li;
a[h[y]].l-=li;
la+=li;
break;
}
}
h[y]=ch[h[y]][1];
fa[h[y]]=0;
Findmn(y);
}
h[++hc]=++tot;
a[tot]={(int)(la-a[h[x]].las()),a[h[x]].las()+1,1};
pushup(tot);
ls[hc]=ls[x];
MMerge(x,hc);
MMerge(hc,y);
}
return hc;
}
void Find(int n,int x,int w)
{
if(w<siz[ch[x][0]])
Find(n,ch[x][0],w);
else
if(siz[ch[x][0]]+a[x].l>w)
{
if(siz[ch[x][0]]==w)
{
splay(n,x,0);
return;
}
int tmp=ch[x][1];
ch[x][1]=++tot;
ch[tot][1]=tmp;
if(tmp)
fa[tmp]=tot;
fa[tot]=x;
a[tot].l=a[x].l-(w-siz[ch[x][0]]);
a[x].l=w-siz[ch[x][0]];
a[tot].x=a[x].x+a[x].d*a[x].l;
a[tot].d=a[x].d;
splay(n,tot,0);
return;
}
else
Find(n,ch[x][1],w-a[x].l-siz[ch[x][0]]);
}
void Update(int l,int x)
{
if(l==ls[x])
return;
int ti=l-ls[x];
ls[x]=l;
Findmn(x);
long long w=a[h[x]].x;
h[++hc]=++tot;
a[tot]={ti,w+ti,-1};
pushup(tot);
MMerge(hc,x);
while(1)
{
Findmx(x);
if(ti<a[h[x]].l)
{
a[h[x]].l-=ti;
break;
}
ti-=a[h[x]].l;
h[x]=ch[h[x]][0];
fa[h[x]]=0;
}
}
void Add(int ti,int l,int r)
{
h[++hc]=++tot;
a[tot]={r-l+1,1<<30,1};
pushup(tot);
seg t={l,r,hc};
ls[hc]=ti;
auto it=p.lower_bound(t);
if(it!=p.end()&&it->l==r+1)
{
Update(ti,it->x);
t.x=Merge(t.x,it->x);
t.r=it->r;
p.erase(it);
}
it=p.lower_bound(t);
if(it!=p.begin())
{
--it;
if(it->r==l-1)
{
Update(ti,it->x);
t.x=Merge(it->x,t.x);
t.l=it->l;
p.erase(it);
}
}
p.insert(t);
}
void Del(int ti,int l,int r)
{
seg t=*p.lower_bound({l,r,0});
p.erase(t);
Update(ti,t.x);
Find(t.x,h[t.x],l-t.l);
int u=ch[h[t.x]][0];
fa[u]=ch[h[t.x]][0]=0;
pushup(h[t.x]);
int v=0;
if(siz[h[t.x]]!=r-l+1)
{
Find(t.x,h[t.x],r-l+1);
v=ch[h[t.x]][0];
fa[v]=ch[h[t.x]][0]=0;
v=h[t.x];
}
if(l!=t.l)
{
h[++hc]=u;
ls[hc]=ti;
p.insert({t.l,l-1,hc});
}
if(r!=t.r)
{
h[++hc]=v;
ls[hc]=ti;
p.insert({r+1,t.r,hc});
}
}
int n,l,r,x,y,u,v,tree[N*4],lazy[N*4];
long long as=1<<30;
struct node{
int l,r;
};
vector<node> ad[E+5],de[E+5];
void modify(int i,int l,int r,int ll,int rr,int x)
{
if(l>=ll&&r<=rr)
{
lazy[i]+=x;
tree[i]+=x;
return;
}
int mid=l+r>>1;
if(mid>=ll)
modify(i<<1,l,mid,ll,rr,x);
if(mid<rr)
modify(i<<1|1,mid+1,r,ll,rr,x);
tree[i]=max(tree[i<<1],tree[i<<1|1])+lazy[i];
}
int Query(int i,int l,int r,int ll,int rr)
{
if(l>=ll&&r<=rr)
return tree[i];
int mid=l+r>>1,s=0;
if(mid>=ll)
s=max(s,Query(i<<1,l,mid,ll,rr));
if(mid<rr)
s=max(s,Query(i<<1|1,mid+1,r,ll,rr));
return s+lazy[i];
}
int Findmx(int i,int l,int r,int ll,int s)
{
if(s+tree[i]==0)
return -1;
if(l==r)
return l-1;
int mid=l+r>>1;
s+=lazy[i];
if(l>=ll)
{
int y=Findmx(i<<1,l,mid,ll,s);
if(y!=-1)
return y;
else
return Findmx(i<<1|1,mid+1,r,ll,s);
}
if(mid>=ll)
{
int y=Findmx(i<<1,l,mid,ll,s);
if(y!=-1)
return y;
}
return Findmx(i<<1|1,mid+1,r,ll,s);
}
int Findmn(int i,int l,int r,int rr,int s)
{
if(s+tree[i]==0)
return -1;
if(l==r)
return l+1;
int mid=l+r>>1;
s+=lazy[i];
if(r<=rr)
{
int y=Findmn(i<<1|1,mid+1,r,rr,s);
if(y!=-1)
return y;
else
return Findmn(i<<1,l,mid,rr,s);
}
if(mid<rr)
{
int y=Findmn(i<<1|1,mid+1,r,rr,s);
if(y!=-1)
return y;
}
return Findmn(i<<1,l,mid,rr,s);
}
void dfs(int i)
{
if(!i)
return;
as=min({as,a[i].x,a[i].las()});
dfs(ch[i][0]);
dfs(ch[i][1]);
}
int main()
{
scanf("%d",&n);
scanf("%d",&x);
for(i=1;i<=n;++i)
{
scanf("%d %d %d %d",&l,&r,&u,&v);
--l,++r;
de[l].push_back({u,v});
ad[r].push_back({u,v});
}
p.insert({0,E*2+5,++hc});
h[hc]=++tot;
a[tot]={E*2+5-x+1,0,1};
ch[tot][0]=2;
fa[++tot]=1;
a[tot]={x,x,-1};
pushup(2);
pushup(1);
for(i=0;i<=E+1;++i)
{
for(auto it:ad[i])
{
modify(1,0,E,it.l,it.r,-1);
auto ii=p.lower_bound({it.l,it.r,0});
int nr=ii->l-1;
--ii;
int nl=ii->r+1;
if(nl>nr)
continue;
int y=Findmx(1,0,E,nl,0);
if(y>=nr||y==-1)
Add(i,nl,nr);
else
{
if(y>=nl)
Add(i,nl,y);
int y=Findmn(1,0,E,nr,0);
if(y<=nr)
Add(i,y,nr);
}
}
for(auto it:de[i])
{
modify(1,0,E,it.l,it.r,1);
while(1)
{
auto y=p.lower_bound({0,it.l,0});
if(y!=p.end())
{
if(min(it.r,y->r)>=max(it.l,y->l))
Del(i,max(it.l,y->l),min(it.r,y->r));
else
break;
}
else
break;
}
}
}
dfs(h[p.begin()->x]);
cout<<as;
}
Idea: AquaMoon and mejiamejia
Tutorial is loading...
solution
// (insert magical incantation)
// (insert offerings for the Gods of codeforces judging servers)
//LXLORZ!!!!//rejudg
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define SQRTN 210
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1,
__c, qu[55];
int __f, qr, _eof;
#define Gc() \
(iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), \
(iS == iT ? EOF : *iS++)) \
: *iS++)
inline void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc(char &x) { x = Gc(); }
inline void pc(char x) {
*oS++ = x;
if (oS == oT)
flush();
}
inline void pstr(const char *s) {
int __len = strlen(s);
for (__f = 0; __f < __len; ++__f)
pc(s[__f]);
}
inline void gstr(char *s) {
for (__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)
__c = Gc();
for (; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc())
*s = __c;
*s = 0;
}
template <class I> inline bool gi(I &x) {
_eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) {
if (__c == '-')
__f = -1;
_eof |= __c == EOF;
}
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc())
x = x * 10 + (__c & 15), _eof |= __c == EOF;
x *= __f;
return !_eof;
}
template <class I> inline void print(I x) {
if (!x)
pc('0');
if (x < 0)
pc('-'), x = -x;
while (x)
qu[++qr] = x % 10 + '0', x /= 10;
while (qr)
pc(qu[qr--]);
}
struct Flusher_ {
~Flusher_() { flush(); }
} io_flusher_;
} // namespace io
using io::gc;
using io::gi;
using io::gstr;
using io::pc;
using io::print;
using io::pstr;
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using ll = long long;
using pii = pair<int, int>;
int n;
int a[MAXN], X[MAXN], Y[MAXN];
int Xa[MAXN], Ya[MAXN];
int dyn[SQRTN + 5];
bool dynp[MAXN];
int ps1[MAXN];
ll ps2[MAXN];
ll ps_7j[MAXN];
int fake_a[MAXN], fake_Xa[MAXN], fake_Ya[MAXN];
// TODO: replace with linked list
struct offl {
int val, id, nxt;
} detecpool[(SQRTN * SQRTN * 11) / 2 + 5];
int detec[MAXN];
// int detec7[MAXN];
int detec8f[MAXN];
int detecX[MAXN], detecY[MAXN];
int dryans[(SQRTN * SQRTN * 3) / 2 + 5];
int dryansX[(SQRTN * SQRTN) / 2 + 5];
int dryansY[(SQRTN * SQRTN * 4) / 2 + 5];
ll dryans_7[(SQRTN * SQRTN) / 2 + 5];
ll dryans_8_former[(SQRTN * SQRTN * 2) / 2 + 5];
ll ijk_static[MAXN];
void dryrun(vector<pii> ops) {
copy(a, a + n, fake_a);
copy(Xa, Xa + n, fake_Xa);
copy(Ya, Ya + n, fake_Ya);
memset(detec, -1, sizeof detec);
memset(detecX, -1, sizeof detecX);
memset(detecY, -1, sizeof detecY);
// memset(detec7, -1, sizeof detec7);
memset(detec8f, -1, sizeof detec8f);
int pooln = 0;
auto push_back = [&](int *ve, int pos, int va, int id) {
detecpool[pooln] = {va, id, ve[pos]};
ve[pos] = pooln;
pooln++;
};
int dryid = 0, dryidX = 0, dryidY = 0, dryid7 = 0, dryid8f = 0;
for (auto [opn, r] : ops) {
if (opn != -1) {
assert(dynp[opn]);
a[opn] = r;
Xa[opn] = X[r];
Ya[opn] = Y[r];
} else {
int mxdyn = 0;
for (int i = 0; dyn[i] <= r; i++)
mxdyn++;
for (int _j = 0; _j < mxdyn; _j++) {
int j = dyn[_j];
int pfx_xai_km1 = 0;
if (j != 0) {
// int pfx_ixaj_jm1 = dryans[dryid++];
// int pfx_iyaj_r = dryans[dryid++];
// int pfx_iyaj_j = dryans[dryid++];
push_back(detecX, j - 1, a[j], dryidX++);
push_back(detecY, r, a[j], dryidY++);
push_back(detecY, j, a[j], dryidY++);
int k = dyn[_j];
// pfx_xai_km1 = dryans[dryid++];
// int pfx_yak_km1 = dryans[dryid++];
push_back(detec, k - 1, Xa[k], dryid++);
push_back(detec, k - 1, Ya[k], dryid++);
// ll pfx_yak_km1 = dryans_7[dryid7++];
// push_back(detec7, k - 1, Ya[k], dryid7++);
}
int i = j;
if (i != r) {
// ll sfx_xai_ip1 = dryans_8_former[dryid8f++];
// ll sfx_xai_rp1 = dryans_8_former[dryid8f++];
// int pfx_xai_r = dryans[dryid++];
// int pfx_xai_i = pfx_xai_km1;
// int pfx_iyxai_n = dryans[dryid++];
// int pfx_iyxai_r = dryans[dryid++];
push_back(detec8f, i + 1, Xa[i], dryid8f++);
push_back(detec8f, r + 1, Xa[i], dryid8f++);
push_back(detec, r, Xa[i], dryid++);
push_back(detecY, n, Xa[i], dryidY++);
push_back(detecY, r, Xa[i], dryidY++);
}
}
}
}
for (int i = 0; i <= n; i++) {
if (i != n && !dynp[i]) {
ps1[a[i]]++;
}
for (int pid = detec[i]; pid != -1; pid = detecpool[pid].nxt)
dryans[detecpool[pid].id] = ps1[detecpool[pid].val];
}
memset(ps1, 0, n * (sizeof(int)));
ll cpsm = 0;
for (int i = 0; i <= n; i++) {
if (i != n && !dynp[i]) {
cpsm += ps_7j[Ya[i]];
ps_7j[a[i]] += ps1[a[i]];
ps1[Xa[i]]++;
}
ijk_static[i] = cpsm;
for (int pid = detecX[i]; pid != -1; pid = detecpool[pid].nxt) {
dryansX[detecpool[pid].id] = ps1[detecpool[pid].val];
dryans_7[detecpool[pid].id] = ps_7j[Y[detecpool[pid].val]];
}
}
memset(ps1, 0, n * (sizeof(int)));
for (int i = 0; i <= n; i++) {
if (i != n && !dynp[i]) {
ps1[Ya[i]]++;
}
for (int pid = detecY[i]; pid != -1; pid = detecpool[pid].nxt)
dryansY[detecpool[pid].id] = ps1[detecpool[pid].val];
}
memset(ps1, 0, n * (sizeof(int)));
memset(ps_7j, 0, n * (sizeof(ll)));
for (int i = n; i >= 0; i--) {
if (i != n && !dynp[i]) {
ps2[a[i]] += ps1[a[i]];
ps1[Ya[i]]++;
}
for (int pid = detec8f[i]; pid != -1; pid = detecpool[pid].nxt)
dryans_8_former[detecpool[pid].id] = ps2[detecpool[pid].val];
}
memset(ps1, 0, n * (sizeof(int)));
memset(ps2, 0, n * (sizeof(ll)));
copy(fake_a, fake_a + n, a);
copy(fake_Xa, fake_Xa + n, Xa);
copy(fake_Ya, fake_Ya + n, Ya);
}
int PfxGud3[MAXN], SfxGud4[MAXN];
void process(vector<pii> ops) {
set<int> mdfd;
for (auto [xx, b] : ops)
if (xx != -1)
mdfd.insert(xx);
int dync = 0;
memset(dyn, 1, sizeof dyn);
for (int i : mdfd)
dyn[dync++] = i;
memset(dynp, 0, sizeof dynp);
for (int i = 0; i < dync; i++)
dynp[dyn[i]] = 1;
dryrun(ops);
int dryid = 0, dryidX = 0, dryidY = 0, dryid6l = 0, dryid7 = 0, dryid8f = 0;
for (auto [opn, r] : ops) {
if (opn != -1) {
a[opn] = r;
Xa[opn] = X[r];
Ya[opn] = Y[r];
} else {
int mxdyn = 0;
for (int i = 0; dyn[i] <= r; i++)
mxdyn++;
ll P1 = ijk_static[r], P2 = 0, P3 = 0, P4 = 0, P5 = 0, P6 = 0, P7 = 0,
P8 = 0;
for (int _i = 0; _i < mxdyn; _i++) {
int i = dyn[_i];
PfxGud3[i] = ps1[a[i]];
P2 += ps2[Ya[i]];
ps2[a[i]] += ps1[a[i]];
ps1[Xa[i]]++;
}
for (int _i = 0; _i < mxdyn; _i++) {
int i = dyn[_i];
ps2[a[i]] = 0;
ps1[Xa[i]] = 0;
}
for (int _i = mxdyn - 1; _i >= 0; _i--) {
int i = dyn[_i];
SfxGud4[i] = ps1[a[i]];
ps1[Ya[i]]++;
}
for (int _i = 0; _i < mxdyn; _i++) {
int i = dyn[_i];
ps1[Ya[i]] = 0;
}
for (int _j = 0; _j < mxdyn; _j++) {
int j = dyn[_j];
int pfx_xai_km1 = 0;
if (j != 0) {
int pfx_ixaj_jm1 = dryansX[dryidX++];
int pfx_iyaj_r = dryansY[dryidY++];
int pfx_iyaj_j = dryansY[dryidY++];
P3 += PfxGud3[j] * (pfx_iyaj_r - pfx_iyaj_j);
P4 += pfx_ixaj_jm1 * SfxGud4[j];
P5 += 1ll * pfx_ixaj_jm1 * (pfx_iyaj_r - pfx_iyaj_j);
int k = dyn[_j];
pfx_xai_km1 = dryans[dryid++];
int pfx_yak_km1 = dryans[dryid++];
int pfxDyn_ixyak = ps1[Ya[k]];
ll pfxDyn_BAD_ixyak = ps2[Ya[k]];
ps1[Xa[k]]++;
ps2[Xa[k]] += pfx_xai_km1;
P6 += 1ll * pfx_yak_km1 * pfxDyn_ixyak - pfxDyn_BAD_ixyak;
P7 += dryans_7[dryid7++];
} else {
ps1[Xa[j]]++;
}
int i = j;
if (i != r) {
ll sfx_xai_ip1 = dryans_8_former[dryid8f++];
ll sfx_xai_rp1 = dryans_8_former[dryid8f++];
int pfx_xai_r = dryans[dryid++];
int pfx_xai_i = pfx_xai_km1;
int pfx_iyxai_n = dryansY[dryidY++];
int pfx_iyxai_r = dryansY[dryidY++];
P8 += (sfx_xai_ip1 - sfx_xai_rp1) -
1ll * (pfx_xai_r - pfx_xai_i) * (pfx_iyxai_n - pfx_iyxai_r);
}
}
for (int _i = 0; _i < mxdyn; _i++) {
int i = dyn[_i];
ps2[Xa[i]] = 0;
ps1[Xa[i]] = 0;
}
print(P1 + P2 + P3 + P4 + P5 + P6 + P7 + P8);
pc('\n');
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int m;
gi(n), gi(m);
for (int i = 0; i < n; i++) {
gi(a[i]);
a[i]--;
}
for (int i = 0; i < n; i++) {
gi(X[i]);
X[i]--;
}
for (int i = 0; i < n; i++) {
gi(Y[i]);
Y[i]--;
}
for (int i = 0; i < n; i++) {
Xa[i] = X[a[i]];
Ya[i] = Y[a[i]];
}
vector<pii> opq;
for (int qx = 0; qx < m; qx++) {
int op, v;
gi(op);
gi(v);
if (op == 1) {
int r;
gi(r);
opq.push_back({v - 1, r - 1});
} else {
opq.push_back({-1, v - 1});
}
if (opq.size() == SQRTN) {
process(opq);
opq.clear();
}
}
process(opq);
}
UPD: Chinese editorial can be found here.
A concise solution for Div1A/Div2C (in D):
Explanation:
Can you explain why you do that?
When a person is at position $$$i$$$ and looks right, they will look right at positions $$$\ldots$$$, $$$i - 4$$$, $$$i - 2$$$, $$$i$$$, $$$i + 2$$$, $$$i + 4$$$, $$$\ldots$$$, and will look left at positions of the other parity. It's easy to see when you consider the possibilities: the first swap involving that person will leave them on position $$$i - 1$$$ or $$$i + 1$$$ looking left, and the second swap will take them to position $$$i - 2$$$, $$$i$$$, or $$$i + 2$$$ looking right again.
As the persons at even positions have to look right at the end, they actually have to permute only among themselves.
On the other hand, every permutation of the persons at even positions is possible: it takes three swaps to exchange the persons at two adjacent even positions, without changing anything else.
So, let us place the persons at even positions in the best possible order: the sorted order.
All the same goes for the persons at odd positions.
What remains is to check that the whole array is then sorted.
in test 38
6
2 1 2 1 2 1
why answer is "NO"? if we imagine that +x is watching right side, -x left and at start we have
+2 +1 +2 +1 +2 +1
then
-1 -2 -1 -2 -1 -2
-1 +1 +2 +1 +2 -2
-1 +1 -1 -2 +2 -2 and now we have sorted array, but we have problem with direction and now we can do more operations
+1 -1 -1 +2 -2 -2
+1 +1 +1 +2 +2 +2 and we found answer please can you explain me this or maybe I'm not right about it?
The
-1 +1 -1 -2 +2 -2to
+1 -1 -1 +2 -2 -2step is wrong:
-1 +1transforms to-1 +1, not to+1 -1.oh I got it, thank you so much
ahh yes. both swap and change directions.
Video Editorials of this contest - Div.2A AquaMoon and Two Arrays
- Div.2B AquaMoon and Stolen String - Div.2C AquaMoon and Strange Sort
that's an amazing solution orz
Thank you for a very nice and simple explanation. I also stuck in test case no 38
That's exactly how I did it.
Better than Editorials solution! Can you explain why this condition is sufficient? Like why swapping an element with opposite parity element can never result in all elements looking right at the end?
What you're asking for is necessity.
If you have to exchange two elements with positions of opposite parities, then those two elements need to be swapped an odd number of times in total as you can only swap consecutive ones. Swapping an odd number of times means their direction changes to left.
Sir, can you please explain, what would be the solution to the problem, if in the end, we want everyone to face left?
Swap all pairs of consecutive positions and apply the same logic. Of course, this is not possible when the size of the list is odd.
It can also be done in C++ using valarray slices: 122360101
Nice to see that C++ is catching up!
Seems like the solution is almost able to sort a stride-2 slice in-place: the
valarrayclass is said to be able (sorry, cplusplus.com link with special characters) to do reference semantics. Is it possible to actually use the library for that, with a bit more knowledge or effort? If not, what is preventing a slice sort, conceptually?This has been in C++ for 23 years, its the programmers who should catch up, not the language.
Yeah, so actually, that's the feat.
Anyway... what about these two slices sorted in place, without a copy?
For some reason,
slice_arraydoesn't have begin/end iterators, so it can't be used insort. I'm not aware of a good reason why this is the case. Anyway it's possible to implement generic strided random access iterators.If this is how you provide editorials? People referring to the editorial are those who couldn't solve the problem or those who have a lot of questions in their minds. You must elaborate your solutions as much as possible.
If you say, that I must be that smart to figure out what you want to say, thank you very much!
It's not just B, the editorial of problem D gets the same remarks from me.
to be fair this problem is very simple and after getting the main idea it's not hard (the tricky part about the problem is just having the idea to store based on the position)
The editorial is bad though, it's just that it makes sense to be concise on B specifically
I can understand that you found this problem to be very easy. But it wasn't for me(and I know I am at fault here). But after all, I can expect a clean explanation so that I may know my mistakes(no matter how bad/silly they are I don't care).
I don't think the problem is "very easy" (in fact i skipped that problem when i read it the first time), i just think the hard part was having the initial idea and from that point forward you can figure out what to do without much trouble. I do agree that this editorial is bad (i edited my comment shortly after), im just playing devil's advocate
Too hard.
The solution for B can be found with XOR since every element except for only one is appeared in even number of time => their XOR will be 0 and the odd one out will be revealed https://codeforces.me/contest/1546/submission/122098007 But the idea of counting in the map is ok though
Thanks for this, I thought about this but didn't know I could have this easy of an implementation if I had gone this way. Personally learned a lot!!
It's an amazing solution!%%%
sro lxl orz
not ok
Atleast provide solutions also with explanation beginners find it difficult to understand
In my opinion the problems are too hard for a 2.5h-contest :(
For B you can solve for each position the typical problem of finding the missing number, i.e. sum(all) — sum(present) = missing. 122094011
Worst editorial
Nice pretests for Div2 C )
I too FSTd , used PBDS :(
hhh I think so !
Editorial to B is super weird xddd. "We can find that several operations mean we take out any group and insert it to any position to the chessboard." — what does that even mean xd?
Hey , could you please explain the idea for B in your words. I knew even groups of ones and zeros can always be arranged in all ways possible . I had a hard time convincing myself during the contest that single ones won't affect the solution OR that they are fully determined by the rest of the ordering . Couldn't yet find anything convincing yet.
hey man thanks , but I was actually asking about Div1 B
Transform the original array by scanning the elements from left to right. 0->a 10->b 11->c
e.g. 00111110011->aaccbac Then we could swap c with any adjacent element. ac=011=110=ca bc=1011=1110=cb So the order of a and b is fixed, and we could insert c into any position.
It's actually the best thing I saw about this problem. Thanks a ton!!
Beautiful :)
How would we transform something like: 11001? 11 becomes c, 0 becomes a, 0 becomes a, and now what about the last 1?
The last single 1 can't be moved, so we could just ignore it.
But why in the solution of authors we need just cntA and cntC, so
answer is choosing cntC positions from cntA + cntC.
Why cntB is ignored? Also if i use cntB to calculate the answer, answer becomes bigger than it should.
It didn't ignore cntB. In the original solution, cg is '11', c0 is '0' plus '10', c1 is '10'. So answer is C(cg + c0, c0) = C('11' + '0' + '10', '11')
Thanks
My submission for div2 B got TLE on PyPy and got accepted with exact same code in Python, wtf? I used flush in both as stated in the problem.
TLE solution: https://codeforces.me/contest/1546/submission/122117451
Same code in Python accepted: https://codeforces.me/contest/1546/submission/122117803
I wasted around 1 hour because of this first I implemented the logic with normal arithmetic operations got TLE, then reduced number of loops got TLE, then changed arithmetic operations to bitwise operations as they are faster, using xor to get that odd one out, then too TLE, then I thought of switching from PyPy -> Python and it worked.
Consider reading this post: https://codeforces.me/blog/entry/82989. I don't know if the explanation is here, but it definitely would be useful.
Great round but the pretests for div 2 C/div 1 A were not so strong.
Well... I tried Div1C and Div1D intensely for 2 hours. No programming — just writing on paper. In Div1D I could find the manipulated row, as described in the editorial and then I started choosing 3 consecutive unmanipulated arrays (such arrays always exist since $$$k \ge 7$$$ ) and search for arithmetic progressions/do some bipartite matching or stuff. In Div1C i tried connecting the arrays in a graph (two arrays are connected if they share an equal value) and then looking for subsets of $$$n$$$ arrays with no edge between them. But for both I couldn't find a real solution.
Now I read the editorial and the solutions are so beautiful! Really wonderful Problems.
I hope you enjoy Div1C, because it's quite hard for me to generate the test data of it. Meanwhile, as a tester of Div1D, it cost me 5 hours to think, finally get ispiration to AC. In fact, I suppose it's the best problem of the contest.
Using the ideas from the Editorial (Chosing rows greedy for Div1C and multiplying solutions by 2 if there is no unique greedy choice and sum of squares for Div1D) I was able to solve them both yesterday. Though I'm still thinking about the proof for C and my implementation for D is quite ugly still.
Oh yes, I guess it's difficult to find meaningful testcases for Div1C. I had problems writing small meaningful testcases on paper to understand the problem.
I really like both of them!
Div2 E and F were too hard, but I have to admit the solution is beautiful. Very clever problemseters!
Could someone explain B? I did not understand the editorial that much :c
Add all the occurencies of each letter in each index (both before and after they get jumbled). Let's say we're trying to find which letter is in the stolen string on index i. Because every letter on the non-stolen strings appear twice, the letter on the original stolen string is the only one that appears an odd number of times in that particular index. If you do that to every index you'll get the answer
My solution is a bit different but i imagine that's what the editorial was trying to say
If the characters 'a','b','c' are at the first position of 3 strings and the given 2 flipped strings have characters b,c at the first position then we know that the string which had character the 'a' in the first place is missing. We can do this for each index.
I took the sum of ASCII values of i'th(1<=i<=m) character of all the original strings and subtracted from it the sum of ASCII values of i'th(1<=i<=m) character of all the new strings.Then just accumulated the character for that value in a string.that's your output.Check my submission for clarity.
A simpler implementation that I used was to just XOR all the ((2*n)-1) strings' characters for each index separately. The final XOR would be the stolen string.
Since, every character except the ones in the stolen string occur a multiple of two times at their respective indices, the stolen string remains after XOR.
We have to work this out character by character, as given n*m does not exceed 10^5, so we can loop through every character. loop thorough each character [j] in each string [i],
Now for all the characters find that character which is not present at the jth index of the scrambled (n-1) lines. do this for every j 0-m, and you'll have a list of characters which are missing.
Print them out. https://codeforces.me/contest/1546/submission/122215500
Maaaan was I not ready for Div 1
from the comments i assume nobody was
How to solve problem div2 C, I don't understand the idea in the tutorial
The number of times a number is at an odd position(0 — indexed) in the original array should be equal to the number of times the number is at an odd position in the sorted array.
why is that, can you explain more?
Because we know that if something ends up as right, it has to swap between left and right an even amount of times. So even indicies must end up even and odd must end up odd.
waooo, this is probably the best explanation, thank you so much
Take three consecutive numbers. Suppose it's abc (RRR). Let's apply some operations. abc (RRR) -> bac (LLR) -> bca (LLR) -> cba (RRR). We reversed these three numbers and they're all to the right again. And reversing them just swapped a and c, and their new positions have the same parity as before, it won't change.
is this interpretation your way of reasoning to solve this problem, how do you prove that for n > 3 the same parity is still true
This was indeed my reasoning during the contest. I'm far from giving you a formal proof, I don't know how to show there's no way to change the parity doing other operations, but I just decided to try to code this and it worked. Maybe someone may prove it.
A quick question — what’s the point of tests, if they don’t tell you your solution is wrong? I could probably have submitted code from 3 rounds ago and gotten AC.
It's just a basic check if you're submitting to the right problem and if your complexity is more or less ok. If they tested everything on the pretests it would take longer to get the result than it already takes
He knows that, what he is basically trying to say is, they had > 10 pretests each with multitests. Still its just basically equivalent to having no tests at all.
prabh :ghosthug:
I’m well aware of it, my comment was more of an attempt to sarcastically imply the tests were shit.
I know that, and i mean what my comment said. Pretests are not meant to give you 100% certainty that your solution is correct. You can make a mistake in many different ways and the way they try to account for that is with the system tests, not the pretests. My pc wasn't turning on at the start of the contest but aparently there was a 4 minute queue at that time, they won't try every single way (or even many ways) to disprove your solution, especially in the first problems (especially a solution like yours to B that is correct in a lot of cases but not all of them).
Lol, this sounds like saying that Pretests are just scam
Wrong answer on test 38
but how to calculate the number of good subsets in div2E? how to construct one is an obvious thing lol
Can you explain your Solution of D ,I observed that 1 one from a pair of ones can be replaced with any zero , and then I tried out some random factorial formula which gave an AC , can you tell me how does the formula n+m C m come from ? where m is no. Of 1's duo and n is no. of zeroes
it's a well-known combinatoric formula for combinations with repetitions: check
How did you break this problem, so that it can be solved this technique? Can you explain please?
I observed that it's possible to consider that we can move any pair of ones to every zero(011->110) because there's a state from which we can do this move, so the problem can be simplified to "calculate a number of ways in which ones can be placed into zeroes(or swapped idk how clearer) using moves described above" or something like that which is solved by summation of
C_with_repetitions(number_of_onepairs, number_of_used_zeros)over the number of used zeroes. Generally, we can see at placing of several onepairs at one zero as 01111->11110, so we need repetitions. I hope my explanation at least a little bit clear:))I know this but how would you formulate it after the observation ?
tried to explain above:)
hey , that part is pretty clear i guess. That even pair of ones and zeros can be arranged in all possible ways. How do you deal with odd number of ones?
We can just skip them, they don't matter. They will be on different positions in different states, but for each state that position is only one
Does anyone have the the proof or intuition about the problem Div2 C . Please explain it
Lets say facing the right is position 0 and facing left is position 1, and say the person on index i gets to index j after sorting the array, which position would they be facing?
Well, for that to happen we need at least abs(j-i) swaps and therefore just by doing that movement from i to j we would be in position abs(j-1)%2. The question is, can we still do swaps in a manner that will put us back at position j but will do a 1 (mod 2) number of swaps? The answer is no, because if we do x swaps to one side, we will still need x swaps to get back, and therefore it will be 2*x = 0(mod 2) swaps.
Therefore if we store the indexes that a person of number x (in particular, the ammount of indexes with certain parity), we solve the problem because we just need to check if there are enough of those positions to acomodate all the people
Subtask : lets assume all elements are distinct
lets take one single element
its position in array is y(eg:7)
its position in sorted array is x(eg:4)
now to move its position from 7 to 4 it will have to make min 3 swaps.
NOTICE : if you would try to use one extra positon like 3 to reach 4 then it would have 5 swaps ( 7 to 4 , 4 to 3 and 3 to 4 ) . Thus we can confirm the parity of swaps dont change.
Odd swaps : don't maintain the direction So we need even swaps.
FINAL Task : Now elements are not distinct
// now we have an opportunity to select a final position ( of duplicates)
To make an even swap we can move from:
1) odd pos in original array to odd pos in sorted array OR
2) even pos in original array to even pos in sorted array
Thus we are counting the no of odd and even pos of each element in original and sorted array
How was there not even a single pretest for C where a[i] was greater than n?
Lack of luck on your part
it sucks even more when I had the chance to touch blue :Sadge:
well whatever..
But your performance was definitely worth a blue. Within few contests you'll easily reach blue.
The round was amazing!
Is it even realistic to solve problem F in the duration of 2 hours 30 mins? Just looking at the editorial make me feels sick...
I think there's a much simpler solution to F which is probably only a bit slower:
Like the editorial, let's process a block of $$$b$$$ queries at a time. Then, instead of grouping by static/dynamic index, let's group by static/dynamic value. There are only at most $$$6b$$$ different values which change, namely the 3 old values of $$$b_{a_i}$$$, $$$a_i$$$, and $$$c_{a_i}$$$, and the 3 new ones for each changed index. For a single value, we can think solve this using a simple 4-state DP. Then, we can find the contribution of all static values for each prefix in $$$O(n)$$$ time, and we can maintain a segment tree of 4x4 transition matrices for each dynamic value to answer those queries. Overall, this will take $$$O((m/b)(n + b^2 \log n))$$$ time, and the optimal choice of $$$b$$$ gives $$$O(m \sqrt{n \log n})$$$. The constant factor seems a little high, but it seems like the editorial probably has high constant factor too.
Actually, this solution can attain $$$O(m \sqrt{n})$$$ as well: just use a $$$\sqrt{n}$$$-time data structure instead of a $$$\log(n)$$$ time data structure, and make sure to compute do as much offline as possible.
Hey , could you please explain your idea about Div1 B. I can't convince myself that odd ones would not affect the solution.
Odd ones do affect the solution; you just need odd ones to end up in odd positions and even ones to end up in even positions, so you should just sort all the odds and sort all the evens.
Hey , thanks a lot for replying. But i was asking about the other problem in which we had a chess board and the possible arrangements were asked.
Oh whoops.
The best "proof" is to view it as 0's with 1's between them. Then 110 <-> 011 means that you can do $$$a_i -= 2$$$ and $$$a_{i+1} += 2$$$ or vice versa. That means the parity of the $$$a_i$$$ is fixed, and the extra odd one doesn't matter.
Thanks !! I really appreciate it
So if the problems are written by only two writers, why do you give such a long writers' list?
They are my friends and they helped me prepare these problems.
Good problems but bad contest.
Editorials for problem div2B and div2C could've been much better!
Why was problem B interactive?
Because we cannot check the legitimacy of the hack data.
Can anyone explain Div2/D? Didn't understand the editorial.
Same. I assume it's a known problem, so I'll ask someone i know afterwards (unless some kind soul explains it here)
tried to explain in this thread
In a single move, a pair of ones '11' will be moving towards left or right (try making some random test cases, you'll figure it out soon)
Now, start grouping 1s to find out such pairs, after doing so you will be left with some 0s, some 1s, and some 11s in the array.
Now the problem simply reduces to finding out different ways of arranging these elements in the array. Do note that the positions of 0s and 1s would remain fixed as only 11s can move left or right. So we need to find different ways of arranging these 11s around these fixed 1s and 0s.
One imp observation is that arranging 11s around 1s will lead to same results. Here's an example :- (11)(11)1(11) is the same as (11)1(11)(11)
So ultimately, we need to find different arrangements of 11s around 0s, the problem now reduces to famous STARS AND BARS problem, and can be solved using combinatorics.
If the number of 0s is k, and number of 11s is n, then we have k+1 positions where we can put these 11s, and number of ways to do so is given as,
(n + (k + 1) — 1) Combination n => (n + k) C n
"Do note that the positions of 0s and 1s would remain fixed as only 11s can move left or right".
I think there is an issue with this assumption. Suppose I have (11)10, another configuration I can get from this is 1011, which can be grouped like 10(11), but can I say that the 1 (with no group) stayed fixed?
When you have an odd number of 1s, pair the last 1 with 0. For 1110, think it as 2 pairs (11)(10).
What about 110010 and 100110? both of them have 2 groups but they cannot be transformed to each other?
The first one is (11)(0)(0)(10). The second one is (10)(0)(11)(0).
You can only move (11). (0) and (10) are fixed.
Yes, 1 which doesn't form a group will always stay at its position, as you can see in your example, the relative position of 1 and 0 isn't affected by movement of 11
yeah, so 1's and 0's stay fixed relative to each other and our created groups of 11's move around them. Now everything make sense. Thanks a lot guys.
Thankyou harshh3010 for an amazing explanation :)
Thank you understood the logic. Great explanation.
Can someone tell me that , have I done some mistake in understanding Div2 C's statement , because I think this can be a valid steps of solution for test case 38 of Div2 C https://ideone.com/JhSefY
I made the same mistake. The problem is that if you have three people: L R L.
Then you cannot swap the first two to make R L L, because after swapping the pair the sequence is R L L, and then the two people change direction, making the sequence L R L again. So you can only turn a pair L L in to R R.
Okk thanks :)
Notice that when you're swapping 1 and 2, you're swapping their positions, but this is wrong. The one on 2 would go to 1 and their position would go from L to R, and the opposite would occur with the 1 going to 2. The positions would remain unchanged
EDIT: one minute too late ._.
Still Thanks :)
Can someone help why this solution to Div2.B failed FST?
say the stolen string is the first one all of it's letters appears at least once in the other original strings, your program will fail
wrote similar solution and failed on same test case — comment. not sure what is wrong
Consider this test case:
1
3 5
abcde
fgche
abbdd
abche
fgbdd
Correct answer is: abcde
Your code gives: fgche
Changes in your code would be: interchange the i and j loop while finding the answer and build the required string.
This would help: 122135347
Greatest solution ever!!
Great observation
Can you plz. explain your approach.
Sure!!!
Just look column-wise.
Each character of jth col in original strings will be present in the swapped strings except the one character of which the string is absent.
Also, since the input given is valid the output produced will also be valid.
So first build the map of n-strings col-wise and then for each col check for n-1 swapped/changed strings and look for the extra character and build the answer string.
I hope you would have understood.
Regarding Problem Div2 C and test case 38, I am unable to understand why it's answer will to be "NO".
Rather than considering the positions, let's consider the number of adjacent swaps it takes to make the array non decreasing.
[I have made the elements I am swapping bold]
2 1 2 1 2 1
1 2 2 1 2 1
1 2 1 2 2 1
1 1 2 2 2 1
1 1 2 2 1 2
1 1 2 1 2 2
1 1 1 2 2 2
So the swaps each element had to undergo to reach the final array are: 1 2 3 3 2 1
So in terms of direction L and R it will be transformed to: L R L L R L
It can be further transformed by swapping adjacent equal elements once, as follows:
L R L L R L
R L L L R L
R R R L R L
R R R R L L
Finally, we will get: R R R R R R
So, I can achieve all R's in the end and it's still non-decreasing.
Please correct me if there is a mistake here.
You can't change L R L L R L to R L L L R L
Note that swapping L R leads to L R (no change)
Yes, I understand it now. Thanks!
I still dont see it. how does swapping LR leads to no change ?
Ah yes. Understood it now.
Thanks for nice contest.
For Div1D, changing every number so that $$$sum[y]$$$ is correct is not enough. Why is it enough to make $$$sum[y]$$$ and $$$sum2[y]$$$ have correct values?
Because you can change any values to make $$$sum[y]$$$ correct but there is exactly one value that makes both $$$sum[y]$$$ and $$$sum2[y]$$$ correct. It's not the same but it's quite similar to how there is exactly one solution for $$$x$$$ and $$$y$$$ when we know $$$x + y$$$ and $$$x^2 + y^2$$$.
I'm not sure why you introduced the irrelevant example of $$$x+y$$$ and $$$x^2+y^2$$$ when you can just use exactly what the problem itself uses: in this problem you know $$$x-y$$$ and $$$x^2-y^2$$$.
Think about the simplified version where $$$m = 2$$$. That's what my example refers to.
Look at an alternative problem. You have an array. And you have to choose a single number to increment by D, such that the target sum of squares is S.
This chosen number is unique. Why? Say we have two such numbers which when incremented give the same sum of squares x,y.
$$$x+(y+D)^2 = (x+D)^2+y^2\implies 2Dx = 2Dy \implies x=y$$$ because D isn't 0.
My solution for Div2. C (although it feels like an overkill now, I hope it will help those who are looking for some sort of "intuition" here).
First of all, we can calculate the minimum number of swaps all elements must undergo in order to make the array non-decreasing. This can be done easily with the help of inversion counting (more specifically, for some index $$$i$$$, counting the number of elements smaller than $$$A_i$$$ to the right of $$$i$$$, and the number of elements greater than $$$A_i$$$ to the left of $$$i$$$.
If some element $$$i$$$ undergoes an even number of swaps, it stays correctly oriented, otherwise it gets flipped (incorrectly oriented).
After arranging the array in non-decreasing order, it is clear that all elements which have the same value, are together.
Let us assume a segment {$$$a, a, a, a, a, a, a, a$$$}, which is oriented {$$$L, R, L, R, R, L, R, L$$$}.
Let us pick $$$2$$$ $$$L$$$s such that there is no $$$L$$$ between them. We can correctly orient them with swapping among themselves, if the number of $$$R$$$s between them is even. So, we notice that we cannot correctly orient $$$1$$$ and $$$3$$$, but we can correctly orient $$$3$$$ and $$$6$$$, and after doing that, we again have an even number of $$$R$$$s between $$$1$$$ and $$$8$$$, so we can correctly orient them as well, thus orienting the entire segment.
To implement this part, I used a stack, in which, whenever I encountered an $$$L$$$, if it was possible to "cancel" this $$$L$$$ with the previous $$$L$$$, I greedily did it, otherwise I simply pushed this $$$L$$$ to the stack. After iterating over a segment of equal values, if the stack is finally empty, then we can be sure that the segment can be correctly oriented, otherwise we can be sure that the segment cannot be correctly oriented.
Although some might find it messy, here is my code for the same : 122139852
Thanks for explaining I came up with pdbs part but second part of how to handle the change in equal numbers it was tough. Thanks to explain the later important part.
the pretest for C was so weak it made the contest not fair for some contestant
Can someone please tell me why my solution of A does not work?
122139278
Thank you
I was doing the same mistake, this technique doesn't guarantee that you have done atmost 100 operations.
The reason your solution is giving the wrong answer is, consider a case,
1
5
1 6 5 3 1
1 4 2 4 5.
So, the test case is valid, and when your outer loop will come at i=3, your inner loop will increase a[i] by one at j=1, so now the array will look like this,
a[]= 1 5 5 4 1,
and inner loop further goes on and increase a[i] by one at j=2, and array will look like,
a[]= 1 5 4 5 1,
Which is a completely unnecessary operation. Though we are not required to minimize the moves, we are supposed to complete it in 100 operations. That's why it is giving the wrong answer.
Solution: You can break the inner loop when a[i] becomes equal to b[i], Hope this solution would help, 122159718.
Thanks for the clear explanation!
Why this solution for problem B (Div2) gets tle for large m (tc4)
122133864
im gonna copy a comment i did to another person with the same problem
"I think the problem is that intead of
ans=ans+z.first;you should doans+=z.firstorans.append(z.first), because in your code you are first making a copy of ans, then summing it with z.first, and only then atributing that value to ans. This is O(n^2) because for each iteration making the copy takes O(n).I think depending on the compiler your code could work though"
How to break D into a "Stars and Bar" technique problem?
let the number of 0 be x and let the no of consecutive 2 ones be y (eg-> 1110 -> 11 1 0-> y=1,x=1) now consider x: as bars and y :as stars.(i hope u get it)
I guess I should switch for programming microwaves.
Format of editorials with hints is much better
Как человек, у которого упало две задачи на систестах, выражаю недовольство этим раундом
Alternate approach for Div2 B. Just keep a count of characters appearing at indexes before and after the operation. The missing character would be a part of the answer for that index,
link- https://codeforces.me/contest/1546/submission/122093074
Any better explanation or intuition behind div2 D? Maybe some kind of strict proof.
Edit: I understand the part that the number of groups (if you calculate every time the way it is shown in the editorial solution) remains the same no matter what you do. But I wonder why would someone come up with such an idea? Was it a result of some observations?
Hope this helps
Kept getting WA on 38th test case,Question C.Anyone else?
just check out this test case (38th case)
1
6
2 1 2 1 2 1
expected output: NO
I had also got the WA on the 38th case.
Think of if 3 equal no. are there with directions L R L, we cannot convert it to R R R.
And then change your logic according to the problem.
Here is a different way of approaching Div2D-
Lets call the ones between a 0 and the next 0 as 'gaps'. For example 110011101 has 4 gaps containing 2, 0, 3 and 1 ones respectively (assume that there are dummy zeroes in the beginning and at the end). Now notice how the one move in pairs and whenever an operation is applied, the number of ones in a gap decreases by 2 and number of ones in another gap increases by 2. This means that the parity of the number of ones in all gaps will remain consistent regardless of the state.
Count how many gaps have even parity and how many gaps have odd parity. Now we just need to count the number of ways to distribute the ones in the gaps such that the parities are maintained.
Lets assume that we have decided to distribute $$$x$$$ ones among the even gaps and $$$c$$$-$$$x$$$ ones among the odd gaps where c is the total number of ones.
If there are $$$e$$$ gaps with even parity, the number of ways to distribute the ones would be the same as finding the number of non negative integral solutions of the equation $$$a_1 + a_2 + ... + a_e = x$$$ such that all $$$a_i$$$ are even. This is the same thing as the stars and bars method.
Similarly if there are $$$o$$$ odd parity gaps, you need to find the number of solutions of $$$a_1 + a_2 + ... + a_o = c-x$$$ such that all $$$a_i$$$ are odd. The product of these two answers will be the number of distributions for a single value of $$$x$$$.
Iterate over all $$$x$$$ from 0 to $$$c$$$ and sum up the product of the two answers for each $$$x$$$.
Link to my submission
Is there are no prefix optimum solution in D (chess) ? I tried to use DP here but its incorrect.
Woah, i didn't expected that Div1C and Div1D are so beautiful before reading editorial. Thanks!
Oh wow, it was rather easy to mess up m and k in Div1D and because of that I wrote a solution that works for at least 5 consecutive times instead of at least 7 (in which case it gets a lil bit easier cause I can take 3 consecutive valid measurements). I interpolated quadratic polynomial in my code and used doubles along the way ;p.
My solution is a bit different as well. As a "hash" of a multiset of integers $$${x_1, \ldots, x_n }$$$ I take $$$(\sum x_i, \sum (x_i-x_j)^2)$$$. You can see easily see that second value is a quadratic function of $$$t$$$ if we make variables $$$x_i$$$ linearly dependent on $$$t$$$, so by interpolating quadratic polynomial I can retrieve changed variable. Tbh I think my solution is just strictly worse than one from editorial ;p. But not by much.
Here's another pretty simple solution that works for $$$4 \leq k$$$ just like the one above.
Let $$$p_t$$$ be the array of captured coordinates at time $$$t$$$.
Then, let's define $$$two_t=\sum p_{t,i}^2$$$. We can see that
We already know $$$\sum x_i^2=two_0$$$, so we only need to find $$$\sum x_iv_i$$$ and $$$\sum v_i^2$$$.
Now find any two different times $$$t_1,t_2 \not\in \{ 0,y\} $$$ (this is where $$$4 \leq k$$$ comes from).
Then using the expansion of $$$two_t$$$ from earlier, we just get a system of two linear equations with two unknowns:
Solving, we get
and then just get $$$\sum x_iv_i$$$ from one of the equations.
Now, we can just get the unmodified $$$two_y$$$ from the earlier expansion $$$\sum x_i^2 + 2y \sum x_iv_i + y^2\sum v_i^2$$$ , and solve the problem (the rest of the solution is the same as the one in the editorial): 122165319.
Actually mine works for k=4 too, but I said k>=5, because during the contest I was thinking this is the actual constraint :D
Oh, yeah it does, sorry:(, fixed the wording to make it obvious yours works for $$$k=4$$$ as well (it was super late when I was posting the comment, so I didn't check). I was actually about to post my solution as a separate comment, but then saw your comment, and decided to just reply to yours instead, so that the solutions would be grouped together (since our comments seem to be the only ones talking about Div1D's solution).
I think Div.1 A & B are interesting problems, because I have been gained -87 rating changes because of them. TwT
The problem are great!But they are too hard :(
Same :(
Same :<
Weak pretests of Div2.C...
In Problem B, why does running n*m where n >= 1e5 and m >= 1e5 doesn't get TLE? I was stuck because of this.
if you read the problem carefully, it says "the sum of n⋅m over all test cases does not exceed 1e5"
Oh, I didn't see that, thanks for your clarification.
Please , someone make me understand Div2 A What is wrong in my submission 122158130
I think it's because you made operations so many times. Please makesure that the operation time is not more than 100.
You are checking a[i]>b[i] outside the inner for loop. Let's say a[i] was bigger than b[i] by 1 but there were >1 j's where a[j] was less than b[j] then you will end up decreasing one extra element from a[i]. Better to check both conditions inside inner for loop.
For problem E, it seems that the tutorial just gives the solution but I'm having a hard time understanding why it is correct. Can someone explain?
Proof for div1b-
First we will add 2 zeroes one at the beginning and one at the end.let x be the number of zeroes.let ai be the number of ones between the ith and (i+1)th zero for all 1<=i<=x-1 .Notice that the operation is same as subtracting 2 from one index(which has value atleast 2) and adding it to 2 to one of its neighboring index so the invariant is parity of ai.
I love the problems. Very nice ideas, and the solution is clear and easy to understand.
Thank you very much <3
(Actually I'm quite sad right now because I've just demoted to Specialist)
Can I get 46th test for Div 2 problem C?
It starts with: 1 100000 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
But when I locally run test with "1 2" repeated 50.000 times I don't observe any performance problems. It seems the test is different from "1 2" repeated 50.000 times.
simple explanation of problem c with proper examples, u will definitely understand. and test case 46 will also become clear. https://www.youtube.com/watch?v=YPdTqbGxPMY
Thanks but I do understand editorial solution. I don't understand why my original solution doesn't pass test 46. That's why I want to get input data for this test.
This may be an easy-to-understand Chinese editorial to C problem https://blog.csdn.net/qq_45863710/article/details/118674749?spm=1001.2014.3001.5502
Can someone help me to prove the author's solution for div2E div2.E problem E div2 div.2
Why the algorithm described above works?
And why is this? "If there not exists such an array discribed above, according to the Pigeonhole Principle, all numbers of the unchosen arrays must appear exactly twice on their columns" (typo btw :()
Any help will be highly appreciated. Thank you very much!
We have the Chinese version of the prove, but we do not have the ability to translate it into English.
Thank you! I will look at the math symbols to guess (I don't know Chinese). Nice problems btw.
By the way, you can click the link to the Chinese editorial in the original post, and then if you open it in Chrome, Google has a "Translate to english" option. I'm still trying to understand the proof myself but that version of the proof has more detail than the English editorial here.
It's good to know!
Here is a proof on "If there not exists such an array discribed above, according to the Pigeonhole Principle, all numbers of the unchosen arrays must appear exactly twice on their columns".
We first list some definitions for convenience.
Then we prove some propositions.
Proposition 1. A unique row must be one of the original rows.
Proof. Otherwise the original rows cannot form a Latin square.
Proposition 2. A unique row must be chosen to form a Latin square.
Proof. Otherwise the chosen arrays cannot form a Latin square.
We say a row is eliminated if it coincides with a unique row at some position.
Proposition 3. An eliminated row must not be chosen.
Proof. Similarly as above.
Proposition 4. If there are $$$a$$$ unique rows, then there are at least $$$a$$$ eliminated rows.
Proof. For any unique row, if it was the $$$i$$$-th original row, then it at least eliminates the $$$i$$$-th additional row.
Proposition 5. Let $$$A$$$ be the new matrix with all unique rows and eliminated rows removed (nothing else is changed). Then for any column in $$$A$$$, each integer appears exactly twice in this column.
Proof. Suppose there are $$$a$$$ unique rows in the original matrix. There are no more than $$$2n-2a$$$ rows in $$$A$$$, by Proposition 4.
For any $$$1\le i \le n$$$, denote the $$$i$$$-th column of $$$A$$$ as $$$c_i$$$. We have
So each integer in $$$c_i$$$ appears exactly twice in this column.
Could you explain more details about "Each integer in $$$c_i$$$ appears at most twice, by the Pigeonhole Principle"?
A unique row will not be an eliminated row.
Suppose there are $$$a$$$ unique rows in the original matrix. For any column $$$c_i$$$ in $$$A$$$, there are at least $$$n-a$$$ different integers in it (otherwise the original rows cannot form a Latin square). Also, we know that each integer in $$$c_i$$$ appears at least twice. Then if some integer appears three times in $$$c_i$$$, there will be at least $$$2(n-a) + 1$$$ integers in $$$c_i$$$, which is contradicted with the fact that there are no more than $$$2(n-a)$$$ rows in $$$A$$$.
This is very good analysis, thanks!
Just put them all in a spoiler so that it doesn't occupy much room :)
Nice advice. Thank you :)
Div1 C:
Situation 1: If an array have a number which appears exactly once at its column, then the array must choose, we can delete least two arrays(The array and arrays which with the array have common elements).
Situation 2: All numbers of the unchosen arrays appear exactly twice on their columns. If not have situation 1. Then must is situation 2. In situation 2, we can choose any an array and delete the array and arrays which with the array have elements, meanwhile multiply the answer by $$$2$$$.
Proof:
Let the remained arrays set are $$$Q={array_1,array_2,...,array_{2*k}}$$$。 First we redefine Latin square：A $$$n*m$$$ matrix so that not any row or any column have common elements($$$n$$$ can not equal $$$m$$$).
Then we define Two Latin square: A arrays set $$$Q$$$ of size $$$2*k$$$ so that we can divide it to two $$$k*m$$$ Latin square.
Proof $$$Q$$$ is a Two Latin square: The conditions of the problem make we must can choose $$$k$$$ arrays from $$$Q$$$ so that the $$$k$$$ arrays is a Latin square. We consider the remained $$$k$$$ arrays, all number in a column appears exactly once, all row are a permutation of $$$1$$$ to $$$n$$$, the the remained $$$k$$$ arrays also is a Latin square.
Define Minimal Two Latin square: Give a arrays set $$$Q$$$ of size $$$2*k$$$ which is a Two Latin square，we have an arrays set $$$A\subseteq Q$$$, let $$$B$$$ is the minimal arrays set so that $$$A\subseteq B\subseteq Q$$$ and $$$B$$$ is a Two Latin square. We call $$$B$$$ is the Minimal Two Latin square general by set $$$A$$$ and $$$Q$$$.
We set $$$A={array_x,array_y}$$$($$$array_x$$$ and $$$array_y$$$ have common elements), obviously $$$array_x$$$ and $$$array_y$$$ can't choose same time. Let $$$B$$$ be the Minimal Two Latin square general by set $$$A$$$ and $$$Q$$$. Then $$$B$$$ can be divide to two Latin square unique. We choose $$$array_x$$$ or $$$array_y$$$ can uniquely determine the set reserved in $$$B$$$. And our choice will not affect how $$$Q-B$$$ chooses. We just need know set $$$B$$$ multiple the answer by $$$2$$$, and continue to choose from set $$$Q-B$$$.
In your last paragraph above, can you describe what is set A? Does A have just two rows, or can it have more than two rows?
If A is a set which has two rows, isn't B just equal to A?
General speaking, we can divide $$$Q$$$ to some Minimal Two Latin square $$$B_1,B_2,...,B_t(B_i\cup B_j =\varnothing$$$ for $$$i\neq j)$$$, so that the answer is $$$2^t$$$.
In each $$$B_i(1\le i\le t)$$$, we can find a $$$A_i={array_{x_i},array_{y_i}}$$$ so that $$$A_i\subseteq B_i$$$ and $$$array_x,array_y$$$ can't be choose same time. Use $$$array_x$$$ or $$$array_y$$$, we can uniquely make sure a choose way in $$$B_i$$$.
Can anyone please help to point out the mistake in my submission Div2C https://codeforces.me/contest/1546/submission/122161335 I would be thankful for pointing out what i am missing. Thanks
There seems to be an out of bounds array access bug in your code, because you do
a[i + 1]indexing without ensuring thati + 1 < n. However this is not the real reason for getting a WA verdict.Please consider
7L 7R 7R 7Lpattern as a part of your sorted array. Your code will report that the answer is NO after checking the first two elements. But the real answer is YES, because we can swap the middle two elements to get7L 7L 7L 7Land then swap the first two elements to get7R 7R 7L 7L. After that, the last two elements can be swapped too:7R 7R 7R 7RYes, Thanks a lot. Now I get that I was not considering this case. Thanks once again.
Div1 C:
Situation 1: If an array have a number which appears exactly once at its column, then the array must choose, we can delete least two arrays(The array and arrays which with the array have common elements).
Situation 2: All numbers of the unchosen arrays appear exactly twice on their columns. If not have situation 1. Then must is situation 2. In situation 2, we can choose any an array and delete the array and arrays which with the array have elements, meanwhile multiply the answer by $$$2$$$.
Proof:
Let the remained arrays set are $$$Q={array_1,array_2,...,array_{2*k}}$$$。 First we redefine Latin square：A $$$n*m$$$ matrix so that not any row or any column have common elements($$$n$$$ can not equal $$$m$$$).
Then we define Two Latin square: A arrays set $$$Q$$$ of size $$$2*k$$$ so that we can divide it to two $$$k*m$$$ Latin square.
Proof $$$Q$$$ is a Two Latin square: The conditions of the problem make we must can choose $$$k$$$ arrays from $$$Q$$$ so that the $$$k$$$ arrays is a Latin square. We consider the remained $$$k$$$ arrays, all number in a column appears exactly once, all row are a permutation of $$$1$$$ to $$$n$$$, the the remained $$$k$$$ arrays also is a Latin square.
Define Minimal Two Latin square: Give a arrays set $$$Q$$$ of size $$$2*k$$$ which is a Two Latin square，we have an arrays set $$$A\subseteq Q$$$, let $$$B$$$ is the minimal arrays set so that $$$A\subseteq B\subseteq Q$$$ and $$$B$$$ is a Two Latin square. We call $$$B$$$ is the Minimal Two Latin square general by set $$$A$$$ and $$$Q$$$.
We set $$$A={array_x,array_y}$$$($$$array_x$$$ and $$$array_y$$$ have common elements), obviously $$$array_x$$$ and $$$array_y$$$ can't choose same time. Let $$$B$$$ be the Minimal Two Latin square general by set $$$A$$$ and $$$Q$$$. Then $$$B$$$ can be divide to two Latin square unique. We choose $$$array_x$$$ or $$$array_y$$$ can uniquely determine the set reserved in $$$B$$$. And our choice will not affect how $$$Q-B$$$ chooses. We just need know set $$$B$$$ multiple the answer by $$$2$$$, and continue to choose from set $$$Q-B$$$.
How would we solve problem B of div2 if it was asked that every person in the end will look towards left?
I think you mean Div 2 C, "AquaMoon and Strange Sort".
We can do the same odd/even counting technique, but flip the parity for the sorted array.
can anyone could give me intution for div2D i can understand why are we not including no of groups also ? why only '0' and '11' are considered why not '1' also
because it cannot propagate imagine a string "001010" the no of combinations of it is 1 (itself) but now add just one pair of 11 in the string lets just add it in the beginning "11001010"
and now see its transformation
01101010 00111010 00101110 00101011
Looking at a simple example would be the simplest i guess. E.g.
..11...1..has these possible states:We can see, this looks likes this: we have one state with all 3 ones touching. Every other state has a single
1and a double11. Let's mark the first1of a11group with XNow let's delete every
1in this diagram.We only have left the
Xand it occupies all possible states. You can make the same with some more complicated example, which I will put in a spoiler. Hope this gives you the Intuition about how the pairs behave!Let's take
.111.11. It has these states:Let's mark the first
1of a11group with XNow let's delete every
1in this diagram.We have two
Xs which iterate all possible permutations.Problem D(div 2) solution, what's mean "—" ?
Can anyone translate the Chinese editorial for E into english? https://www.cnblogs.com/invisible-eyes/p/15003033.html
It seems like the Chinese editorial has much more detail than the English editorial for that problem. I am still struggling to understand how to solve E. Thanks in advance.
use google translate extension
An English proof for a missing part of Div1C is at: https://codeforces.me/blog/entry/92799
the worst round, i've ever seen.
can anyone explain div.2 D in a better way pleasE?
this comment helped me: https://codeforces.me/blog/entry/92739?#comment-815195
Ah, it's very friendly for me to write a Chinese editorial:)
Why "NO" in 6 2 1 2 1 2 1
Consider it +2 +1 +2 +1 +2 +1
now swap (1,2) -1 -2 +2 +1 +2 +1
now swap(3,4) -1 -2 -1 -2 +2 +1
now swap(2,3) -1 +1 +2 -2 +2 +1
now swap(5,6) -1 +1 +2 -2 -1 -2
now swap(4,5) -1 +1 +2 +1 +2 -2
now swap(3,4) -1 +1 -1 -2 +2 -2
now swap(2,3) -1 -1 +1 -2 +2 -2
now swap(1,2) +1 +1 +1 -2 +2 -2
now swap(4,5) +1 +1 +1 +2 -2 -2
now swap(5,6) +1 +1 +1 +2 +2 +2
and its sorted with all right
can anyone tell
After the 7-th swapping operation, the sequence should be -1 +1 -1 -2 +2 -2.
I will write down the intuition I got from Div2E/Div1C so that I can get it fixed in my brain.
Consider that the latin square we will choose is something like this (have numbers 1,...,n as the first column):
1----------
2----------
3----------
...
n----------
And the corresponding dirty square is something like this (have numbers a1,...,an between 1 and n as the first column):
a1----------
a2----------
a3----------
...
an----------
If i appear only once in the first column of the the 2n x n matrix, then we know that the row
i----------
belongs to a latin square. Indeed, if it was in a dirty square, then there would also exist a row
i++++++
in the latin square (because the latin square must have all elements 1,..n in its first column), what is a contradiction.
If no element appear only once in the first column of the 2n x n matrix, then each element must appear twice. Indeed, suppose an element appear k > 2 times in this column. One of these times must be inside of a latin square and the other k-1 times must be in the corresponding dirty square. But now it rest only n-(k-1) places in the first column of the dirty square. So we can only put at most n-(k-1) different elements from 1,..n at these places. So at least one number i from 1,..,n have no place to go inside the first column of the dirty square, which means that it only appears in the latin square (necessarily once), what is a contradiction to our initial hypotheses that no element appear only once in the first column of the 2n x n matrix.
This can be extended to any column.
What the algorithm proposed in the editorial do is construct a solution greedily. It keeps a set A with the choosen rows and a set B with the trash rows. If there is a row that is necessarily in a latin square, it picks it, put it in A and put in B all rows that can't be in a latin square with it.
If all elements appear twice in its column at some point (when we have 2*k elements), it means we have at least two latin squares. Suppose two of them are of the form
1----------
2----------
...
k----------
Then we know that all other latin squares generated by this configuration is an exchange of blocks
i----------
...
j----------
between these two initial latin squares. So we know the total number is something of the form $$$2^x$$$, but we just pick one factor two and continue breaking because we will have the other factor twos when we arrive to this situation again later.
I solved D without proving