Codeforces Round 906 Editorial

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	pajenegod	145
9	SecondThread	145

idea: Cocoly1990

Solution

Code

By Cocoly1990

// Time complexity O(nlogn) because of map
#include <bits/stdc++.h>

const int MX = 100 + 5;

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    std::map<int ,int> occ;
    for (int i = 1; i <= n; ++i) {
      int x;
      std::cin >> x;
      occ[x]++;
    }
    if (occ.size() >= 3) puts("No");
    else {
      if (std::abs(occ.begin()->second - occ.rbegin()->second) <= 1) {
        puts("Yes");
      } else {
        puts("No");
      }
    }
  }
  return 0;
}

1890B - Qingshan Loves Strings

idea: Imakf

Solution

Code

By Imakf

#include <bits/stdc++.h>

bool ok(std::string s) {
  for (size_t i = 1; i < s.length(); ++i)
    if (s[i] == s[i - 1])
      return false;
  return true;
}

void solve() {
  std::string s, t;
  int l1, l2;
  std::cin >> l1 >> l2;
  std::cin >> s >> t;
  if (ok(s)) {
    std::cout << "Yes" << std::endl;
    return;
  }

  if (!ok(t) || *t.begin() != *t.rbegin()) {
    std::cout << "No" << std::endl;
    return;
  }

  int zz = 0, oo = 0;
  for (size_t i = 1; i < s.length(); ++i) {
    if (s[i] == s[i - 1]) {
      if (s[i] == '0') zz = true;
      if (s[i] == '1') oo = true;
    }
  }

  if (zz && t[0] == '0') {
    std::cout << "No" << std::endl;
    return;
  }
  if (oo && t[0] == '1') {
    std::cout << "No" << std::endl;
    return;
  }  

  std::cout << "Yes" << std::endl;
  return;
}

int main() {
  int t;
  std::cin >> t;
  while (t--) solve();
  return 0;
}

1889A - Qingshan Loves Strings 2

idea: Imakf

Solution

Code

By Imakf

#include <bits/stdc++.h>

bool ok(std::string s) {
  for (size_t i = 1; i < s.length(); ++i)
    if (s[i] == s[i - 1])
      return false;
  return true;
}


std::string s;
void solve() {
  int n; std::cin >> n;
  std::cin >> s;
  int cnt0 = 0, cnt1 = 0;
  for (int i = 0; i < s.length(); ++i) {
    cnt0 += s[i] == '0';
    cnt1 += s[i] == '1';
  }
  if (cnt0 != cnt1) {
    std::cout << -1 << std::endl;
    return;
  }
  std::vector<int> z;
  std::deque<char> q;
  for (int i = 0; i < s.length(); ++i)
    q.push_back(s[i]);
  
  int d = 0;
  while (!q.empty()) {
    if (q.front() == q.back()) {
      if (q.front() == '0') {
        q.push_back('0');
        q.push_back('1');
        z.push_back(n - d);
      } else {
        q.push_front('1');
        q.push_front('0');
        z.push_back(0 + d);
      }
      n += 2;
    }
    while (!q.empty() && q.front() != q.back()) {
      q.pop_back();
      q.pop_front();
      ++d;
    }
  }

  std::cout << z.size() << std::endl;
  for (int i = 0; i < z.size(); ++i) {
    std::cout << z[i];
    if (i + 1 == z.size()) std::cout << std::endl;
    else std::cout << " ";
  }
}

int main() {
  int t;
  std::cin >> t;
  while (t--) solve();
  return 0;
}

1889B - Doremy's Connecting Plan

idea: Cocoly1990

Solution

Code

By Cocoly1990

#include<bits/stdc++.h>
using i64 = long long;
using namespace std;
const int N = 5e5 + 7;
int T, n, C, p[N]; i64 a[N];
void solve () {
	cin >> n >> C;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	iota (p + 1, p + n + 1, 1);
	sort (p + 1, p + n + 1, [&] (const int &u, const int &v) {
		return 1ll * u * C - a[u] < 1ll * v * C - a[v];
	});
	i64 now = a[1];
	for (int i = 1, u; i <= n; i ++) {
		u = p[i];
		if (u == 1) continue;
		if (1ll * u * C > now + a[u]) return cout << "No\n", void ();
		now += a[u];
	}
	return cout << "Yes\n", void ();
}
int main () {
	ios :: sync_with_stdio (false); cin.tie (0); cout.tie (0);
	cin >> T; while (T --) solve ();
}

1889C2 - Doremy's Drying Plan (Hard Version)

idea: waaitg, Imakf

Easy Solution

Hard Solution

Code

By Imakf

#include <bits/stdc++.h>

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define LL long long

const int MX = 2e5 + 23;
const int INF = 1e9;

void chkmax(int &x, int y) {
  x = std::max(x, y);
}

struct Interval {
  int l, r;
} I[MX];

bool cmp(int x, int y) {
  return I[x].l > I[y].l;
}

std::vector<int> add[MX], del[MX];
int n, m, k, ban[MX];

int st[21][MX][18], lg[MX];

int query(int d, int l, int r) {
  int len = lg[r - l + 1];
  return std::max(st[d][l][len], st[d][r - (1 << len) + 1][len]);
}

void change(int d, int p, int val) {
  chkmax(st[d][p][0], val);
  for (int i = 1; p - (1 << i) + 1 >= 0; ++i) {
    st[d][p - (1 << i) + 1][i] = std::max(
          st[d][p - (1 << i) + 1][i - 1],
          st[d][p - (1 << (i - 1)) + 1][i - 1]);
  }
}

void init() {
  lg[0] = -1;
  for (int i = 1; i <= n + 1; ++i)
    lg[i] = lg[i - 1] + ((i & -i) == i); 
  for (int i = 1; i <= m; ++i) ban[i] = false;
  for (int i = 1; i <= n + 1; ++i) {
    add[i].clear();
    del[i].clear();
  }
  for (int i = 0; i <= k; ++i)
    for (int j = 0; j <= n; ++j)
      for (int _k = 0; _k < 18; ++_k)
        st[i][j][_k] = -INF;
}

void solve() {
  scanf("%d%d%d", &n, &m, &k);
  init();
  for (int i = 1; i <= m; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    I[i] = (Interval){l, r};
    add[l].push_back(i);
    del[r + 1].push_back(i);
  }
  
  std::vector<int> cur, tmp;

  change(0, 0, 0);
  
  int uncover = 0, ans = 0;
  int cnti = 0;
  for (int i = 1; i <= n; ++i) {
    for (auto j : add[i]) {
      cur.push_back(j);
      ++cnti;
    }

    for (auto j : del[i]) {
      ban[j] = true;
      --cnti;
    }

    if (cnti > k) {
      for (int j = 0; j <= k; ++j)
        change(j, i, -INF);
      continue;
    }

    tmp.clear();
    for (auto j : cur) {
      if (!ban[j]) {
        tmp.push_back(j);
      }
    }
    cur = tmp;
    std::sort(cur.begin(), cur.end(), cmp);
    
    if (cur.empty()) {
      for (int j = 0; j <= k; ++j)
        change(j, i, -INF);
      ++uncover;
      continue;
    }
    
    if (I[cur[0]].l <= i - 1)
      for (int g = 0; g <= k; ++g) {
        int z = query(g, I[cur[0]].l, i - 1);
        chkmax(ans, z + 1);
        change(g, i, z + 1);
      }
    else {
      for (int g = 0; g <= k; ++g) {
        change(g, i, -INF);
      }
    }
    int cp = I[cur[0]].l - 1;
    

    for (int j = 0; j < cur.size(); ++j) {
      if (j + 1 != cur.size() && I[cur[j]].l == I[cur[j + 1]].l)
        continue;
      int np = (j + 1 == cur.size() ? 0 : I[cur[j + 1]].l);
      for (int g = j + 1; g <= k; ++g) {
        int z = query(g - (j + 1), np, cp);
        chkmax(ans, z + 1);
        change(g, i, z + 1);
        // change(root[g], i, z + 1);
      }
      cp = np - 1;
    }
  }
  printf("%d\n", ans + uncover);
}

int main() {
  int t; scanf("%d", &t);

  while (t--) solve();
  return 0;
}

1889D - Game of Stacks

idea: waaitg

Solution

Code

By waaitg

#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005;
stack<int>s[maxn];
int re[maxn],st[maxn],vis[maxn],tp;
int dfs(int u){
    if(re[u])
        return re[u];
    if(s[u].empty())
        return u;
    if(vis[u]){
        st[tp+1]=0;
        while(st[tp+1]!=u){
            s[st[tp]].pop();
            vis[st[tp]]=0;
            --tp;
        }
        return dfs(u);
    }
    st[vis[u]=++tp]=u;
    return dfs(s[u].top());
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int k;scanf("%d",&k);
        while(k--){
            int c;scanf("%d",&c);
            s[i].push(c);
        }
    }
    for(int i=1;i<=n;++i){
        tp=0;int ok=dfs(i);
        for(int j=1;j<=tp;++j)
            re[st[j]]=ok;
        printf("%d%c",ok," \n"[i==n]);
    }
    return 0;
}

1889E - Doremy's Swapping Trees

idea: waaitg

Solution

Code

By waaitg

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct Edge{
    int v,nt;
    Edge(int v=0,int nt=0):
        v(v),nt(nt){}
}eG[maxn*160];
int hdG[maxn*40],numG;
void qwqG(int u,int v){
    eG[++numG]=Edge(v,hdG[u]);hdG[u]=numG;
}
int tot;
struct AnTree{
    struct Edge{
        int v,nt;
        Edge(int v=0,int nt=0):
            v(v),nt(nt){}
    }e[maxn*2];
    int hd[maxn],num;
    void qwq(int u,int v){
        e[++num]=Edge(v,hd[u]),hd[u]=num;
    }
    int n;
    void init(int n){
        this->n=n;
        for(int i=1;i<n;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            qwq(u,v);qwq(v,u);
        }
    }
    int pa[maxn][20],id[maxn][20],dp[maxn];
    void dfs(int u,int p){
        if(p==0)dp[u]=0;
        for(int i=1;(1<<i)<=dp[u];++i)
            pa[u][i]=pa[pa[u][i-1]][i-1];
        for(int i=hd[u];i;i=e[i].nt){
            int v=e[i].v;
            if(v==p)continue;
            dp[v]=dp[u]+1;
            pa[v][0]=u;
            id[v][0]=++tot;
            dfs(v,u);
        }
    }
    int getid(int u,int d){
        int&re=id[u][d];
        if(re)return re;
        re=++tot;
        qwqG(re,getid(u,d-1));
        qwqG(re,getid(pa[u][d-1],d-1));
        return re;
    }
    void link(int x,int u,int v){
        if(dp[u]<dp[v])swap(u,v);
        for(int t=dp[u]-dp[v],cn=0;t;t>>=1,++cn)
            if(t&1)qwqG(x,getid(u,cn)),u=pa[u][cn];
        if(u==v)return;
        int t=0;while(dp[u]>>t)++t;
        while(t--){
            if(pa[u][t]!=pa[v][t]){
                qwqG(x,getid(u,t));
                qwqG(x,getid(v,t));
                u=pa[u][t];v=pa[v][t];
            }
        }
        qwqG(x,getid(u,0));
        qwqG(x,getid(v,0));
    }
    void erase(void){
        for(int i=1;i<=n;++i){
            hd[i]=0,dp[i]=0;int j=0;
            while(pa[i][j])pa[i][j++]=0;
            j=0;while(id[i][j])id[i][j++]=0;
        }
        num=0;
    }
    int parent(int u){
        return pa[u][0];
    }
    int identity(int u){
        return id[u][0];
    }
}T1,T2;
int dfn[maxn*40],low[maxn*40],cnt;
int st[maxn*40],tp,in[maxn*40];
int scc[maxn*40],scn;
int vis[maxn*40];
void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    in[st[++tp]=u]=true;
    for(int i=hdG[u];i;i=eG[i].nt){
        int v=eG[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++scn;
        st[tp+1]=0;
        while(st[tp+1]!=u){
            in[st[tp]]=false;
            scc[st[tp]]=scn;
            --tp;
        }
    }
}
const int mod=1e9+7;
int power(int a,int x){
    int re=1;
    while(x){
        if(x&1)re=1ll*re*a%mod;
        a=1ll*a*a%mod,x>>=1;
    }
    return re;
}
void solve(void){
    int n;scanf("%d",&n);
    T1.init(n);T2.init(n);
    T1.dfs(1,0);T2.dfs(1,0);
    int rec=tot;
    for(int i=2;i<=n;++i){
        T2.link(T1.identity(i),i,T1.parent(i));
        T1.link(T2.identity(i),i,T2.parent(i));
    }
    for(int i=1;i<=tot;++i)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=rec;++i)
        ++vis[scc[i]];
    int ANS=0;
    for(int i=1;i<=scn;++i){
        if(vis[i])++ANS;
        vis[i]=0;
    }
    for(int u=1;u<=rec;++u){
        if(eG[hdG[u]].nt==0){
            int v=eG[hdG[u]].v;
            if(u<v&&eG[hdG[v]].nt==0){
                if(eG[hdG[v]].v==u){
                    --ANS;
                }
            }
        }
    }
    ANS=power(2,ANS);
    printf("%d\n",ANS);
    for(int i=1;i<=tot;++i){
        hdG[i]=0;
        dfn[i]=low[i]=scc[i]=0;
    }
    tot=cnt=scn=numG=0;
    T1.erase();T2.erase();
}
int main(){
    // freopen("test","r",stdin);
    // freopen("out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}

1889F - Doremy's Average Tree

idea: waaitg, Imakf

Solution

Code

By waaitg

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	static char c;static int f;
	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f;
}
template<typename T>void write(T x){
	static char q[64];int cnt=0;
	if(x==0)return pc('0'),void();
	if(x<0)pc('-'),x=-x;
	while(x)q[cnt++]=x%10+'0',x/=10;
	while(cnt--)pc(q[cnt]);
}
long long gcd(long long a,long long b){
	if(b==0)return a;
	return gcd(b,a%b);
}
struct Frac{
	long long a;
	int b;// a/b
	Frac(long long a=0,int b=1):
		a(a),b(b){}
	bool operator < (const Frac o)const{
		return a*o.b<o.a*b;
	}
	bool operator > (const Frac o)const{
		return a*o.b>o.a*b;
	}
	bool operator == (const Frac o)const{
		return a*o.b==o.a*b;
	}
	void output(){
		printf("%lld/%d",a,b);
	}
};
const int inf=0x3f3f3f3f;
struct Val{
	int p1,p2;Frac v1,v2;
	Val(int p1=inf,int p2=inf,Frac v1=Frac(),Frac v2=Frac()):
		p1(p1),p2(p2),v1(v1),v2(v2){}
	void output(void){
		printf("%d : ",p1);v1.output();puts("");
		printf("%d : ",p2);v2.output();puts("\n");
	}
};
Val Comb(Val A,Val B){
	if(A.p1>B.p1)swap(A,B);
	if(B.v1==A.v1)
		return Val(A.p1,A.p2<B.p2?A.p2:B.p2,A.v1,A.p2<B.p2?A.v2:B.v2);
	return Val(A.p1,A.p2<B.p1?A.p2:B.p1,A.v1,A.p2<B.p1?A.v2:B.v1);
}
const int maxn=10005,maxk=505;
struct Edge{
	int v,nt;
	Edge(int v=0,int nt=0):
		v(v),nt(nt){}
}e[maxn*2];
int hd[maxn],num;
void qwq(int u,int v){
	e[++num]=Edge(v,hd[u]),hd[u]=num;
}
long long sm[maxn];int sz[maxn];
int dp[maxn][maxk],wp[maxn][maxk],k,n;
Val va[maxn][maxk];
void Merge(int x,int l,int r,int L,int R){
	wp[x][0]=0;
	va[x][0]=Comb(va[l][0],va[r][0]);
	L=min(L,k);R=min(R,k);
	int up=min(L+R,k);
	for(int i=1;i<=up;++i){
		int t=wp[x][i]=min(L,i),cl=inf,cr=inf;
		while(t>0&&i-t<R){
			cl=min(cl,dp[l][t]);--t;
			cr=min(cr,dp[r][i-t]);
			if(cr<cl)wp[x][i]=t,cl=cr=inf;
		}
		t=wp[x][i-1];cl=cr=inf;
		if(wp[x][i-1]<wp[x][i]){
			while(t<wp[x][i])cl=min(cl,dp[l][++t]);
			dp[x][i]=cl;
		}
		else{
			while(i-t-1<i-wp[x][i])cr=min(cr,dp[r][i-(t--)]);
			dp[x][i]=cr;
		}
		va[x][i]=Comb(va[l][wp[x][i]],va[r][i-wp[x][i]]);
	}
}
int MN[maxn],rsz[maxn];
long long val[maxn];
void dfs(int u,int p){
	int l=0,fa=0;sm[u]=val[u];
	sz[u]=0;rsz[u]=1;MN[u]=0;
	for(int i=hd[u];i;i=e[i].nt){
		int v=e[i].v;
		if(v==p){fa=i;continue;}dfs(v,u);
		Merge(i,i^1,l,sz[v],sz[u]);
		sm[u]+=sm[v],sz[u]+=sz[v];
		rsz[u]+=rsz[v];
		l=i;
	}
	if(sz[u]==0){
		++sz[u];MN[u]=1;
		va[fa][0]=va[fa][1]=Val(u,inf,val[u]);
		dp[fa][1]=inf;
	}
	else{
		int up=min(sz[u],k);
		for(int i=0;i<=up;++i)
			va[fa][i]=Comb(va[l][i],Val(u,inf,val[u])),dp[fa][i]=dp[l][i];
		Frac tmp(sm[u],rsz[u]);
		for(int i=1;i<=up;++i)
			if(va[fa][i].v1>tmp||(va[fa][i].v1==tmp&&va[fa][i].v2>tmp))
				va[fa][i]=Val(va[fa][i].p1,inf,tmp),MN[u]=i;
		if(MN[u]){
			if(va[fa][0].v1==va[fa][1].v1)
				dp[fa][1]=va[fa][0].p2;
			else
				dp[fa][1]=va[fa][0].p1;
			for(int i=2;i<=MN[u];++i)
				dp[fa][i]=inf;
			if(MN[u]<up){
				if(va[fa][MN[u]].v1==va[fa][MN[u]+1].v1)
					dp[fa][MN[u]+1]=va[fa][MN[u]+1].p2;
				else
					dp[fa][MN[u]+1]=va[fa][MN[u]+1].p1;
			}
		}
	}/*
	int up=min(sz[u],k);
	printf("%d MN:%d\n",u,MN[u]);
	for(int i=1;i<=up;++i)
		printf("dp %d = %d\n",i,dp[fa][i]);*/
}
int st[maxn],ts;
int que[maxn],cnt;
void solve(int u,int p,int sk){
	if(sk==0)return;sk=min(sk,sz[u]);
	if(sk<=MN[u])return st[++ts]=u,void();
	int tnc=cnt;
	for(int i=hd[u];i;i=e[i].nt){
		int v=e[i].v;
		if(v==p)continue;
		que[cnt++]=i;
	}
	for(int j=cnt-1;j>=tnc;--j){
		int i=que[j];
		solve(e[i].v,u,wp[i][sk]);
		sk-=wp[i][sk];
	}
}
void imple(void){
	int r;
	read(n),read(r),read(k);
	for(int i=1;i<=n;++i)
		read(val[i]);
	qwq(r,0);
	for(int i=1;i<n;++i){
		int u,v;read(u),read(v);
		qwq(u,v);qwq(v,u);
	}
	dfs(r,0);
	solve(r,0,k);
	printf("%d\n",ts);
	for(int i=1;i<=ts;++i)
		printf("%d%c",st[i]," \n"[i==ts]);
	for(int i=0;i<=n;++i)hd[i]=0;
	num=cnt=ts=0;
}
int main(){
	// freopen("test","r",stdin);
	int T;read(T);
	while(T--)imple();
	return 0;
}

int mx1 = -1, mx2 = -1; rep(j,i,to){ if(sz(rain[j]) == 0) continue; if(j != i){ if(mx2 == -1 || rain[mx2].back() <= rain[j].back()){ mx2 = j; if(mx1 == -1 || rain[mx1].back() <= rain[mx2].back()) swap(mx1,mx2); } } int ct = rain[j].back(); int c2 = pre[min(ct,to)][2]-pre[j-1][2]; c2 += pre[max(ct,to)][1]-pre[i-1][1]; two = max(two, c2); }

Комментарии (90)

Написать комментарий?

CallmeSourav

6 месяцев назад, # |

-15

i love solving observation problems like c , i just tried some cases and came up with the soluion .

→ Ответить

Traverser_25

6 месяцев назад, # ^ |

Your implementation for c is very straightforward,can you explain me the approach?

I just checked for the extreme ends of string and if one end is 1 and other is 0 or vice versa then that means they are in correct position and we can forget about them , now we will have some new extreme points if the extreme points are 0 and 0 then it means we have to do something, so inserting 0 1 to last will help us and again after inserting we can remove the extreme characters, same for 1 1 but this time insert 0 1 at the beginning. I hope I was able to convey my approach

lightmon

-8

but i tried many cases without caming up a solution:\

deque is a good tool

The5threich

5 месяцев назад, # ^ |

← Rev. 2 →

I remember doing it without deque, but it was a mess to implement, used a set to keep track of occurrences of 0s and 1s.
Got 4 WAs on the way (During the contest!) :(
Submission for reference — 230261688

bit-trie

Very fast editorial!

bestial-42-centroids

← Rev. 3 →

+21

Thanks for the super fast editorial and great round ! As usual, here is my advice about the problems I solved :)

Thank you for the round, looking forward to take part in another one

I felt C was difficult to implement, maybe I suck at implementation and have more admiration for mathematical problems.
Back to specialist now :/

aadarshaheb.singh

7 недель назад, # ^ |

But for the Problem A what if the input is 6 2 3 5 4 4. Then the idea that is given in the editorial is wrong.

wavelets

good contest — good problems, except b was kinda troll (i found it funny though)

yeminghan

Div. 1 B and C1 are great! (Maybe also C2 but I didn't solve it) I like the way to optimize the algorithm.

peltorator

I think in C2 segments where dp transition works the same way can only be merged together or a new one may be created at the end. So to support maximums on segments we don't need any data structure, we just need to store these segments and merge them sometimes (there are at most $$$10$$$ segments, so we can do it by just storing an array of these segments and deleting elements from it).

+44

My mind went blank and did not notice the $$$i=1$$$ thing in B so I accidentally solved a more complicated version of the problem where indices of vertices may be arbitrary numbers. I think it is a good exercise if you wish to think about it.

hackerbhaiya

Is it something like only edges from $$$(1,2),(1,3),....,(1,n)$$$ and $$$(2,3),(3,4),...,(n-1,n)$$$ edges matter?
I solved using this approach, kept on deleting the edge having the least value of $$$c*i*j - a[i] - a[j]$$$, and updating the edge values.
Or it's even more complicated?

Proof of the approach

Liuxizai

+10

I think your approach won't work for the generalized version. In your proof, the condition $$$a_j - a_i > c\cdot (j-i)\cdot k$$$ is just necessary but not sufficient. For example, if we have $$$(5, 1), (6, 25), (7, 1), (8, 25)$$$, you'll find that we can only connect 6 and 8 in the first step.

Misuki

+16

the problems are so smart that I feel like I'm idiot D: anyway, that is a good round, thanks!

parveen1981

In Div2C/Div1A, I didn't understand why would it take at most 300 operations. I'd be grateful if someone can explain.

skye_

We can show that under the constraints in this problem, if an answer exists, there is always an answer that requires at most 300 operations.

Because the problem tells you

Soultaker

Technically that doesn't tell you that this particular algorithm produces a solution with at most 300 insertions (or that it terminates at all).

I know it's common to meta-game problems like this (I do it myself too) along the lines of: “Hmm, this problem is div1-A, so it can't be too difficult. There must be a solution that is not too hard. I've come up with an approach that gives the right answer for the samples and a few other cases I can think of, so it's probably the correct algorithm, so I'll just submit it and hope the pretests warn me if it's wrong.”

This often works, but it's not the same as proving that it works.

You perform at most one insertion per character originally in the string

+17

The clue is in this sentence: “This operation is actually equivalent to moving the last 1 to the front or moving the first 0 to the end.”

The algorithm can be summed up as:

0s1 → s
1s0 → s
0s0 → 0s001 (append "01") → s00 (apply rule 1)
1s1 → 011s1 (prepend "01") → 11s (apply rule 1)

The problem is that the third and fourth rule, even after expanding them as I did above, do not reduce the problem size. This raises the question if the algorithm terminates at all, and if so, how many insertions there can be.

The key is to observe that the rule 3 effectively does a left rotation (0s0 → s00) and rule 4 a right rotation (1s1 → 11s). Since s contains an equal number of 0s and 1s, you can do at most $$$|s|/2-1$$$ rotations before the first and last character are different (example: $$$s=000001111110$$$ takes 5 turns), and you can reduce the problem size with rule 1 or 2. This shows that the algorithm does terminate, and you can already infer a quadratic upper bound on the number of insertions.

But this can be improved to $$$\mathcal{O}(N)$$$ as follows. When you've applied rule 3 $$$n$$$ times in a row, then you know that $$$s$$$ ends with at least $$$n$$$ 0s, and you cannot apply rule 4 until all those zeros have been removed, which can only happen by applying rule 1. This shows that every application of rule 3 and 4 must be paired with an eventual application of rule 1.

That's how we know we need at most $$$|s|/2-1 = 49$$$ insertions in total.

Woowww! You and your explanation are amazing. Thanks a lot. I'd been having headache over this since the contest.

Cosmoss

Because at first point 1) if count of zeroes = count of ones, then only the answer is possible. 2) So if thats not the case no matter how many times you perform the operation its not going to be good string. 3) So they have given at max we can do 300 operations i guess. Correct me if i was wrong!

LMeyling

C1 (easy) unlucky for python, same solution accepted in C++ (even a slower version). Yes there were people who solved it, but only 3.

fahadhossainbabor2103114

I tried my best to came up with a solution for at least 1 problem. I almost solved the 1st Problem. Man i feel so demotivated now !! (:

abdulla.bin.ah

It's just beginning my brother. If you remember this day, message me after 6 month. You might be in pupil then inshallah.

sai-17

In Div2 E1/ Div1 C1 if we take test case
5 3 2
1 4
2 5
2 4
According to editorial [1 4] and [2 5] should not be considered as they intersect and there is no position i which is covered by exactly these two intervals, but the answer is obtained by taking these two segments. Can someone correct me if I am wrong?

vgtcross

In the "no intersection" case we aren't considering only pairs which don't intersect, but any pairs of segments. Since we don't know if they intersect, we assume they don't and calculate the answer based on that. If those segments did in fact intersect in a way that made the answer larger, it would get counted in the second case anyway.

GusFring

Can someone explain how in problem Div. 1 D the idea for the easy version is extended to the original problem?

DuongForeverAlone

In Div2E1 editorial, I still haven't figure out how to handle the case when two interval intersect using array or set. Could someone explain for me this case, or it could be nice to see the actual implementation

adityagamer

You check check my implementation. https://mirror.codeforces.com/contest/1890/submission/230287888 It currently runs in O(3*n). But with casework on mx1,mx2 and using the fact from editorial that there are at most n useful intersection. You bring it to O(n)

Could you explain this part:

This part is searching through all intersection of rain starting from i. In the second part of code, I am calculating the answer as number of 2s on intersection part + number of 1 in entire covered part. In the first part I am trying to find the next rain index to search. Among all rain with rightEnd >= to, You only care about the largest two ending points, because all other will always have > 2 intersection. I have stored it as mx1 and mx2. You can ignore the search on mx1 and mx2 if its right end is before "to". In my implementation, I am not ignoring

Arth2022

Please someone explain Div2 E1 solution with the code. I couldn’t understand the editorial.

RauPro

Any advice on How to solve problem D using UnionFind and counting the population with DFS?

My submission: 230232830

I know that it can be solved using PQ, but I have the doubt if it is possible to solve it with this approach

variety-jones

Take a look at Ticket 17118 from CF Stress for a counter example.

Thanks!, can u test with this one? 230397805

fishcurry

why does s_i + s_j >= i + j — 1 imply that either s_i >= i and s_j >= j have to be true, why cant s_i >= j and s_j >= i ?

avnithv

You say $$$s_i \geq j$$$ and $$$s_j \geq i$$$.

If $$$i \leq j$$$, then $$$s_i \geq i$$$.

If $$$i \geq j$$$, then $$$s_j \geq j$$$.

So either $$$s_i \geq i$$$ or $$$s_j \geq j$$$ is true.

ZeroPointTwo

Problem B is easier than I expected in Div 2 :D

sathwik2822

Can anyone please explain the logic behind problem A. I’m completely confused about how the code is written.

_Untrackable_

In div1 C1/div2 E1 how to optimise the taking best interval and taking intersection of intervals. you should have also posted the implementation code of the solution

Ramaman_22

Can someone help me where my code is failing for Div 2 C problem? Submission id 230209550

itzzRaghav

This was a wonderful contest Problems were mainly based on observations and less on standard techniques. Thank you for such contest.

chanandler_bong_

:((

saurav76

-13

Please go through the given youtube video for the explanation of problem A(Doremy's Paint 3) with proof asked in codeforces round 906 div 2! https://youtu.be/Dt0L3vhSToU?si=CCXd_fzo2_ILvpHm

Please go through the given youtube video for the explanation of 1890B — Qingshan Loves Strings with proof asked in codeforces round 906 div 2! https://youtu.be/Pk83WXo1eUY?si=6iIO5NdPG6o_TtZZ

rahulbhandari

1889A — Qingshan Loves Strings 2 In this question we are allowed to insert only "01" then why it the tutorial suggesting to insert "10".

typo

NeMo.Andrey

Can smb explain what this mean in D from div2 906? iota (p + 1, p + n + 1, 1); I read the solution and it wasn't mention there, so I'm a little bit confused

https://en.cppreference.com/w/cpp/algorithm/iota

TL;DR: the array $$$p$$$ will be initialized as $$$p = [\text{unaffected}, 1, 2, 3,\dots, n-1, n]$$$

874641984

in problem c1(easy) i cant understand this word "In the "no intersection" case, we can just simply pick two best intervals."
i don't think it can solve simply:(

nikhil09.dixit

for problem D we say that I always connect with the 1st city to minimize the multiplication i * j * c , but how can i be certain that this always right since taking other two cities may have a bigger Sum(ak)?

can anyone please explain this!!

+12

Let's consider a pair of singleton vertices $$$i$$$ and $$$j$$$. The claim is that if we can connect $$$i$$$ and $$$j$$$, then we can connect either $$$i$$$ or $$$j$$$ to $$$1$$$. If $$$i=1$$$ or $$$j=1$$$ that's trivially true. Otherwise, we know $$$i, j ≥ 2$$$ and we can assume without loss of generality that $$$a_i ≤ a_j$$$ (otherwise just swap $$$i$$$ and $$$j$$$).

We want to prove $$$a_i + a_j ≥ ijc$$$ implies $$$a_1 + a_j ≥ 1jc$$$ or simpler $$$a_j ≥ jc$$$ (since worst case, $$$a_1 = 0$$$).

steps of proof

The same logic also works for sums of connected components, but we don't even need it, because the above shows that it's enough to connect singleton vertices to vertex 1.

michaelmonir

-6

Amazing proof !!!

Faris_mohamed007

-14

اي قلة ادب دي

صاحب الكمنت دا لازم يتحاسب

utkarsh_b

How will I be able to intuitively think this in the context?

goadf90a

I don't see how to "see" the solution for Div2C... Can someone explain the intuition?

SNX03

So sorry, I meant Div2C

For C you can observe the fact that the condition described in the problem is opposite of what the condition for palindrome is i.e for each i : [0, s.size()/2], s[i] == s[s.size()-i-1]. Keeping this in mind the condition for problem becomes for...., s[i] != s[s.size()-i-1]. Now consider a case when length of the string is ODD. In this case you can observe that no matter what you do the character at the position (s.size())/2 will always be equal to itself hence you have to give up i.e for odd string or for strings that only have unique character that answer can never be formed.

Now when the answer can be formed, Notice two things:

1. when s[i] == s[n-i-1], s[i] == '0', in this case the only thing you can do is add "01" at the n-i-1 position making -> s[i] = '0' s[new] = '1'.

2. when s[i] == s[n-i-1], s[i] == '1', in this case you have to add "01" before the ith position making s[new] = '0' and s[n-i-1] = '1'.

Keep doing the above for 301 iterations, if in the end the result array has a size > 300, that means answer was never possible otherwise it print the answer.

Spoiler

Thank you very much!

In problem D of div-2 does the given constant actually have any impact ? Like whats the significance of c?

TheScrasse

With $$$c = 1$$$ the tests would be weak.

ok thanks.

I9O0

why does this not work, if we sort the array based on c = 1 from which we are getting the order and then check if we can build the tree using that order? here is my submission for the same.

It works, but giving $$$c = 1$$$ in the statement would mean that it's harder to kill wrong solutions.

It is not working I have tried or I have done something wrong but I am unable to find any mistakes in my solution so I am still confused as to why it is not working can you have a look at my solution

Everule

← Rev. 4 →

+54

For div1 F, we can solve it faster in $$$O(n\log{n})$$$. To get a prefix of an array $$$a_1, a_2, a_3, \ldots a_t$$$, where $$$a_i$$$ is the value on node $$$i$$$, we should consider all valid nodes, and find if there exists a covering with $$$\le k$$$ nodes. A node covers all nodes in it's subtree.

Then to do this fast, we consider an auxillary graph. We should only consider the nodes, such that they're on the path $$$[a, r]$$$ for $$$1 \le a \le t$$$. We can see, that since $$$a$$$ is forced, all the valid nodes on the path from $$$a$$$ to $$$r$$$ must have the same value. So this leads us into splitting the path of $$$[t+1, n]$$$ into 2 parts. The one already in auxillary tree, and the one that isn't. For the part that isn't, we can simply find it and work with it directly, since it is amortised $$$O(n)$$$. We can easily find the closest ancestor valid node in the auxillary tree too.

Now we consider 3 cases, either no operation, an operation with the value of the path in the auxillary tree, or an operation with a value of the added path.

For no operation, we should invalidate as usual, and mark this path as unneeded, i.e. it doesn't need to be covered, but it can be.

For an operation with the value of the added path, we need to remove all the nodes in path to the current node. We can notice that this is a simple function of the degrees of the needed nodes of ancestor, as we split each old cover into the children covers. Additionally, if we have to delete them, we can do so directly as it again amortises to $$$O(n)$$$.

For an operation with the value of the auxllary tree, we can simply connect it to the auxillary tree. If the auxillary tree currently doesn't need a covering, we need a covering now, so we can make the values force need it. Again, doing this explicitly amortises to $$$O(n)$$$.

Most of the difficulty is maintaining the moving parts, but here is a full implementation 230451211 (My implementation is 400 lines :p)

isirazeev

Could somebody explain Div1C2/Div2E2 in more detail, after we understood dp in O(n^2k)?

iamavalon

I ended up using k splay trees to keep the dp stored and find the max. the t-th splay tree contains all dp values that need exactly t segment removals. so, whenever a new segment [l,r] is being processed, all the dp[l][t] up to dp[r][t] are moved from splay tree t to splay tree t+1 (for all t from 0 to k), because now they need 1 more removal of a segment to be reachable. and now i calculate dp[r+1][t] = 1 + max value in splay tree t.

because these removals are log n amortized, the complexity is also O(n k log n)

pkqs90

Wow. Just learned from div1c one can simply use a sparse table instead of a segment tree to handle this kind of dp. Really nice!

FuelTheBurn

Could you please explain how the sparse tree with updates works? I am confused on this array example:

3, 1, 4, 1, 5, 9, 2, 6

The sparse tree looks like

3, 1, 4, 1, 5, 9, 2, 6
3, 4, 4, 5, 9, 9, 6
4, 5, 9, 9, 9
9

After updating the index 3 to 10 based on the solution's implementation the sparse tree becomes

3, 1, 4, 10, 5, 9, 2, 6
3, 4, 10, 5, 9, 9, 6
10, 5, 9, 9, 9
9

Querying the max of (1,7) will return max(st[1,2],st[4,2])=max(4,9)=9, the answer should be 10. It seems to me that you need to update all ranges in the sparse tree that include index 3, making the sparse tree look like this

3, 1, 4, 10, 5, 9, 2, 6
3, 4, 10, 10, 9, 9, 6
10, 10, 10, 10, 9
10

However, this is O(n) (maybe even O(nlogn)) causing TLE, and not how it is implemented in the solution.

Never mind, I figured it out. The change function is only used in the construction of the sparse tree, so changes in the middle of the sparse tree will never happen.

Munneb_Sheikh

Can someone explain Div2D or Div1B

__HACKER__

I think div2 C statement could be more clear.

Super_Misha

I think in E1 they meant that you can just go throw all segments after making prefix sums, then, if there at least one index between right and left border of segment, which covered by only two segments, you just iterate throw letf to right border of segment and when there is index i, where prefix[i] == 2, you just fix that on index i you can delete this segment. It probably works in O(4*n) and take not many space

lew2018

Can anyone provide me with the code of div2 D's easy version?

piyuagr

In Problem 1889B Deremy's connecting path, My code is failing for test case 4th and in that, 81st test is failing. i couldn't seem to resolve the problem because I cannot see that 81st test of the test case 4th. I don't think there is a overflow problem because I am using double and my algorithm seems to be correct. i think there is some corner case missing. 1. My algorithm: I will divide the array a by c( to reduce c=1) I will first find the maximum index (1<=i<= n) such that one can make edge (1,i). i will take the sum from 1st to ith index. then i will iterate from i+1 to n, and as soon as I find an index j such that edge (1,j) can be formed with (sum+a[j]) >= 1.j then I will update the sum till jth starting from 1st. Could anyone please help?

Just for reference: My Submission https://mirror.codeforces.com/contest/1890/submission/232326341

Take a look at Ticket 17144 from CF Stress for a counter example.

Thank you so much!! actually, a=2 and b=4 for c = 2 and i=1,j=3 I wanted to check if (a+b) >= 1*3*2 but I was actually checking (a/c + b/c) >= 1*3 which was giving wrong answer because of decimal thing.

Problem E in div1 is great, but the limitations are incredibly strict for completely no reason...

prayas123

5 месяцев назад, # |

For problem C1(easy version), can someone elaborate on the proof of the statement "In the "intersection" case, there are at most n useful interval".

Sedmoklasnikut

Div1 Problem C2 could be solved without sparse tables. Instead we observe that when you query an interval, it is the same as getting the minimum dp value from the leftmost element in the interval up until the current position i. These minimums could be store using Arpa trick. Here is a link: https://mirror.codeforces.com/blog/entry/48994

moradiya84

I was solving Div1 B Doremy's connecting plan but i was getting wrong answer in testcase 3 token 576 can you please provide me this perticular token's data.

ASHWANTH_K

4 месяца назад, # |

https://mirror.codeforces.com/contest/1889/submission/239421653 can anybody stress test it pls

7 недель назад, # |

What if the input given is 4 4 5 3 1 7 6 2. Then this solution will be not correct for the problem A how we are going to get the solution for this question?

heyguysitsme

6 недель назад, # |

There is another and an elegant approach to solve E1 . we can first find the points which are covered by either 1 or 2 intervals and also the index of the interval which covers them . Now our problem boils down to finding the largest subarray with 2 unique values.

Блог пользователя Imakf