Idea: StarSilk. Solution: StarSilk. Preparation: SSerxhs, StarSilk.
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int T,n,i,ans;
for(cin>>T;T>0;T--)
{
cin>>s;n=s.size();
ans=0;
for(i=0;i<n;i++)ans+=s[i]-'0';
cout<<ans<<'\n';
}
return 0;
}
Code (Python)
for _ in range(int(input())):
print(input().count('1'))
Idea: StarSilk. Solution: StarSilk. Preparation: SSerxhs, StarSilk.
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int T,n,i,t,flag;
for(cin>>T;T>0;T--)
{
cin>>n;
flag=0;
for(i=0;i<n;i++)
{
cin>>t;
if(t<=i*2||t<=(n-i-1)*2)flag=1;
}
if(flag)cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
Code (Python)
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
if a[i]<=max(i,n-i-1)*2:
print('NO')
break
else:
print('YES')
Idea: Yakumo_Ran. Solution: Yakumo_Ran. Preparation: Yakumo_Ran, SSerxhs, mejiamejia.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
long long a[1010];
int main(){
int t;
cin >> t;
while (t--){
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int now = n;
long long ans = -1e18;
for (int i = 1; i <= n; i++){
long long sum = 0;
for (int i = 1; i <= now; i++) sum = (sum + a[i]) ;
if (i == 1) ans = max(ans, sum);
else ans = max(ans, max(sum, ( - sum) ));
for (int i = 1; i < now; i++) a[i] = (a[i + 1] - a[i]) ;
now--;
}
cout << ans << endl;
}
return 0;
}
Code (Python)
from math import *
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
ans=sum(a)
while n>1:
n-=1
a=[a[i+1]-a[i] for i in range(n)]
ans=max(ans,abs(sum(a)))
print(ans)
Idea: StarSilk, SSerxhs. Solution: StarSilk, SSerxhs. Preparation: SSerxhs.
Solution
Tutorial is loading...
Code (C++)
#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(),(x).end()
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T;
while (T--)
{
int n, i;
cin >> n;
vector<int> l(n), r(n), a(n);
for (i = 0; i < n; i++) cin >> l[i] >> r[i];
vector e(n, vector<int>(0));
for (i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
--u, --v;
e[u].push_back(v);
e[v].push_back(u);
}
long long ans = 0;
function<void(int)> dfs = [&](int u) {
int mx = l[u];
for (int v : e[u])
{
erase(e[v], u);
dfs(v);
mx = max(mx, a[v]);
}
a[u] = min(mx, r[u]);
for (int v : e[u]) ans += max(0, a[v] - a[u]);
};
dfs(0);
cout << ans + a[0] << "\n";
}
}
Code (Python)
for _ in range(int(input())):
n = int(input())
l,r=[],[]
for i in range(n):
L,R=map(int,input().split())
l.append(L)
r.append(R)
e=[[] for i in range(n)]
for i in range(n-1):
u,v=map(int,input().split())
e[u-1].append(v-1)
e[v-1].append(u-1)
stk=[0]
f=[-1]*n
nfd=[]
while stk:
u=stk.pop()
nfd.append(u)
for v in e[u]:
if v!=f[u]:
f[v]=u
stk.append(v)
nfd.reverse()
ans=0
for u in nfd:
for v in e[u]:
if f[v]==u:
l[u]=max(l[u],l[v])
l[u]=min(l[u],r[u])
for v in e[u]:
if f[v]==u:
ans+=max(0,l[v]-l[u])
print(ans+l[0])
2062E1 - The Game (Easy Version)
Idea: Yakumo_Ran. Solution: Yakumo_Ran. Preparation: Yakumo_Ran,mejiamejia,SSerxhs.
Solution
Tutorial is loading...
Code (C++)
#include "bits/stdc++.h"
using namespace std;
const int N=1e6+5;
vector<int> e[N];
int w[N],dfn[N],nfd[N],pre[N],suf[N],low[N];
bool ed[N];
int id;
void dfs(int u)
{
if (ed[u]) return;
ed[u]=1;
dfn[u]=++id;
nfd[id]=u;
for (int v:e[u]) dfs(v);
ed[u]=0;
low[u]=id;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cout<<fixed<<setprecision(15);
int T; cin>>T;
while (T--)
{
int n,m,i,j;
cin>>n;
for (i=1; i<=n; i++)
{
e[i].clear();
id=0;
}
for (i=1; i<=n; i++) cin>>w[i];
for (i=1; i<n; i++)
{
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1);
for (i=1; i<=n; i++) pre[i]=max(pre[i-1],w[nfd[i]]);
suf[n+1]=0;
for (i=n; i; i--) suf[i]=max(suf[i+1],w[nfd[i]]);
int mx=0;
for (i=1; i<=n; i++) if (max(pre[dfn[i]-1],suf[low[i]+1])>w[i]&&w[i]>w[mx]) mx=i;
cout<<mx<<'\n';
}
}
Code (Python)
for _ in range(int(input())):
n = int(input())
w=[int(x) for x in input().split()]
wb=[[] for i in range(n)]
for i in range(n):
w[i]-=1
wb[w[i]].append(i)
e=[[] for i in range(n)]
for i in range(n-1):
u,v=map(int,input().split())
e[u-1].append(v-1)
e[v-1].append(u-1)
stk=[0]
f,dfn=[-1]*n,[0]*n
nfd=[]
while stk:
u=stk.pop()
dfn[u]=len(nfd)
nfd.append(u)
for v in e[u]:
if v!=f[u]:
f[v]=u
stk.append(v)
sz=[1]*n
nfd.reverse()
for u in nfd:
if u==0:
continue
sz[f[u]]+=sz[u]
wb.reverse()
mx=-1;mn=n+1
for v in wb:
for u in v:
if mn<dfn[u] or mx>dfn[u]+sz[u]-1:
print(u+1)
break
else:
for u in v:
mn=min(mn,dfn[u])
mx=max(mx,dfn[u])
continue
break
else:
print(0)
2062E2 - The Game (Hard Version)
Idea: SSerxhs. Solution: StarSilk,SSerxhs,PaperCloud,fallleaves01. Preparation: SSerxhs,mejiamejia.
Solution
Tutorial is loading...
Code (C++)
#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(),(x).end()
const int N = 5e5 + 2;
vector<int> e[N];
int dfn[N], nfd[N], low[N];
int id, n;
void dfs(int u)
{
nfd[dfn[u] = ++id] = u;
for (int v : e[u]) erase(e[v], u), dfs(v);
low[u] = id;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cout << fixed << setprecision(15);
int T; cin >> T;
while (T--)
{
int n, m, i, j;
cin >> n;
vector w(n, vector<int>());
vector<int> c(n + 1), ans;
for (i = 1; i <= n; i++)
{
e[i].clear(); id = 0;
cin >> j;
w[j - 1].push_back(i);
}
for (i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1);
int l = n + 1, r = 0;
set<int> s;
for (i = n - 1; i >= 0; i--)
{
if (s.size())
{
for (int u : w[i])
{
int mx = 0;
for (j = dfn[u] - 1; j; j -= j & -j) mx = max(mx, c[j]);
if ((*s.begin() < dfn[u] || *s.rbegin() > low[u]) && mx <= low[u] && dfn[u] <= l && low[u] >= r)
ans.push_back(u);
}
for (int u : w[i])
{
int mn = *s.begin(), mx = *s.rbegin();
int L = dfn[u], R = low[u];
if (mn >= L && mx <= R) continue;
if (mn >= L && mn <= R) mn = *s.upper_bound(R);
if (mx >= L && mx <= R) mx = *prev(s.lower_bound(L));
auto fun = [&](int x, int y) {
if (x > y) swap(x, y);
l = min(l, y), r = max(r, x);
for (j = x; j <= n; j += j & -j) c[j] = max(c[j], y);
};
fun(mn, dfn[u]);
fun(mx, dfn[u]);
}
}
for (int u : w[i]) s.insert(dfn[u]);
}
sort(all(ans));
cout << ans.size();
for (int x : ans) cout << ' ' << x;
cout << '\n';
}
}
Idea: StarSilk. Solution: StarSilk. Preparation: SSerxhs, StarSilk.
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
struct apos{
long long a;
long long b;
friend bool operator<(apos a,apos b){
return a.b-a.a<b.b-b.a;
}
}ap[3000];
long long dp[3001][3],tdp[3001][3],ans[3001],inf=1000000000000000000LL;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int T,n,i,j,t;
for(cin>>T;T>0;T--)
{
cin>>n;
for(i=0;i<n;i++)cin>>ap[i].a>>ap[i].b;
sort(ap,ap+n);
for(i=0;i<=n;i++)
{
for(j=0;j<3;j++)
{
dp[i][j]=inf;
tdp[i][j]=inf;
}
ans[i]=inf;
}
for(i=0;i<n;i++)
{
tdp[1][0]=min(tdp[1][0],ap[i].a*2);
tdp[1][1]=min(tdp[1][1],ap[i].a);
for(j=1;j<n;j++)
{
for(t=0;t<3;t++)tdp[j+1][t]=min(tdp[j+1][t],dp[j][t]+ap[i].a+ap[i].b);
tdp[j+1][1]=min(tdp[j+1][1],dp[j][0]+ap[i].b);
tdp[j+1][2]=min(tdp[j+1][2],dp[j][1]+ap[i].a);
ans[j+1]=min(ans[j+1],dp[j][1]+ap[i].b);
ans[j+1]=min(ans[j+1],dp[j][2]+ap[i].b*2);
}
for(j=1;j<=n;j++)
{
for(t=0;t<3;t++)
{
dp[j][t]=min(dp[j][t],tdp[j][t]);
tdp[j][t]=inf;
}
}
}
for(i=2;i<=n;i++)cout<<ans[i]<<' ';
cout<<'\n';
}
return 0;
}
Code (Python)
class Q:
def __init__(this,x,y):
this.x,this.y=x+y,x-y
def __lt__(this,rhs):
return this.y<rhs.y
for _ in range(int(input())):
n=int(input())
a=[0]*n
for i in range(n):
x,y=map(int,input().split())
a[i]=Q(x,y)
a.sort()
l=[10**18]*(n+1)
sl=l.copy();slt=l.copy();slrt=l.copy()
s=10**18
for m,t in enumerate(a):
x,y=t.x,t.y
for i in range(m,0,-1):
slrt[i+1]=min(slrt[i+1],sl[i]+x+y,slt[i]+x*2+y*2)
slt[i+1]=min(slt[i+1],slt[i]+x*2,sl[i]+x-y)
sl[i+1]=min(sl[i+1],sl[i]+x*2,l[i]+x+y)
l[i+1]=min(l[i+1],l[i]+x*2)
sl[1]=min(sl[1],x-y)
l[1]=min(l[1],x*2-y*2)
print(*[x//2 for x in slrt[2:]])
Idea: StarSilk. Solution: StarSilk. Preparation: StarSilk, SSerxhs.
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
struct linex{
int v;
int w;
int nxt;
int c;
};
int head[210],cnt,cpos[210],vis[210],qvis[210],totc,dis[210],inf=1000000000;
linex l[21000];
queue<int>que;
void add(int u,int v,int w,int c){
l[cnt].nxt=head[u];
head[u]=cnt;
l[cnt].v=v;
l[cnt].w=w;
l[cnt].c=c;
cnt++;
l[cnt].nxt=head[v];
head[v]=cnt;
l[cnt].v=u;
l[cnt].w=0;
l[cnt].c=-c;
cnt++;
}
int spfa(int st,int en,int n){
int i,j,t;
for(i=0;i<n;i++)
{
vis[i]=0;
dis[i]=inf;
cpos[i]=head[i];
}
que.push(st);
dis[st]=0;
vis[st]=1;
qvis[st]=1;
while(!que.empty())
{
t=que.front();
que.pop();
qvis[t]=0;
for(j=head[t];j!=-1;j=l[j].nxt)
{
if(l[j].w>0&&dis[l[j].v]>dis[t]+l[j].c)
{
dis[l[j].v]=dis[t]+l[j].c;
vis[l[j].v]=1;
if(!qvis[l[j].v])
{
que.push(l[j].v);
qvis[l[j].v]=1;
}
}
}
}
return vis[en];
}
long long dfs(int p,int en,int curr){
int x,j,flow=0;
if(p==en)return curr;
for(j=cpos[p];j!=-1&&flow<curr;j=l[j].nxt)
{
cpos[p]=j;
qvis[p]=1;
if(l[j].w>0&&dis[l[j].v]==dis[p]+l[j].c&&!qvis[l[j].v])
{
x=dfs(l[j].v,en,min(curr-flow,l[j].w));
flow+=x;
l[j].w-=x;
l[j^1].w+=x;
totc+=l[j].c*x;
}
qvis[p]=0;
}
return flow;
}
int p[100],q[100],id[100][100];
int cabs(int x){
if(x<0)x=-x;
return x;
}
struct point{
int x;
int y;
int tx;
int ty;
}pc[100];
vector<int>ansv[2];
int main(){
ios::sync_with_stdio(false),cin.tie(0);
srand(time(0));
int T,n,i,j,flow,flag;
for(cin>>T;T>0;T--)
{
cin>>n;
for(i=0;i<n;i++)
{
cin>>p[i];
p[i]--;
}
for(i=0;i<n;i++)
{
cin>>q[i];
q[i]--;
}
for(i=0;i<n*2+2;i++)head[i]=-1;
cnt=0;
totc=0;
flow=0;
for(i=0;i<n;i++)
{
add(n*2,i,1,0);
add(i+n,n*2+1,1,0);
for(j=0;j<n;j++)
{
id[i][j]=cnt;
add(i,j+n,1,cabs(i-j)+cabs(p[i]-q[j]));
}
}
while(spfa(n*2,n*2+1,n*2+2))flow+=dfs(n*2,n*2+1,inf);
for(i=0;i<n;i++)
{
pc[i].x=i;
pc[i].y=p[i];
for(j=0;j<n;j++)
{
if(l[id[i][j]].w==0)
{
pc[i].tx=j;
pc[i].ty=q[j];
}
}
}
while(1)
{
flag=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(pc[j].tx<=pc[i].x&&pc[i].x<pc[j].x&&pc[j].x<=pc[i].tx)
{
ansv[0].push_back(pc[i].x);
ansv[1].push_back(pc[j].x);
swap(pc[i].x,pc[j].x);
flag=1;
}
}
}
if(!flag)break;
}
while(1)
{
flag=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(pc[j].ty<=pc[i].y&&pc[i].y<pc[j].y&&pc[j].y<=pc[i].ty)
{
ansv[0].push_back(pc[i].x);
ansv[1].push_back(pc[j].x);
swap(pc[i].y,pc[j].y);
flag=1;
}
}
}
if(!flag)break;
}
cout<<ansv[0].size()<<'\n';
for(i=0;i<ansv[0].size();i++)cout<<ansv[0][i]+1<<' '<<ansv[1][i]+1<<'\n';
ansv[0].clear();
ansv[1].clear();
}
return 0;
}
Idea: StarSilk. Solution: StarSilk. Preparation: StarSilk.
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
string s;
long long dp[15][15][1<<14],vl[200],sgvl[15][15][15][15];
long long dp2[15][1<<14],dpvl2[15][1<<14];
int psum[15][15];
long long getvl(long long l,long long r,long long x,long long y){
if(l>=r||x>=y)return 0;
return vl[psum[r][y]-psum[l][y]-psum[r][x]+psum[l][x]];
}
long long f(long long l,long long r,long long x,long long y){
long long ans=0,i,c,tl,tr,tx,ty;
for(i=0;i<16;i++)
{
c=0;
tl=l;
tr=r;
tx=x;
ty=y;
if(i&1)
{
c^=1;
tl++;
}
if(i&2)
{
c^=1;
tr--;
}
if(i&4)
{
c^=1;
tx++;
}
if(i&8)
{
c^=1;
ty--;
}
if(c)ans=(ans+mod-getvl(tl,tr,tx,ty))%mod;
else ans=(ans+getvl(tl,tr,tx,ty))%mod;
}
return ans;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int T,n,i,j,t,p,l,r,len,cmsk;
long long ans;
for(cin>>T;T>0;T--)
{
cin>>n;
vl[0]=0;
for(i=1;i<=n*n;i++)vl[i]=(vl[i-1]*2+1)%mod;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)psum[i][j]=0;
}
for(i=0;i<n;i++)
{
cin>>s;
for(j=0;j<n;j++)psum[i+1][j+1]=s[j]-'0';
}
for(i=0;i<n;i++)
{
for(j=0;j<=n;j++)psum[i+1][j]+=psum[i][j];
}
for(i=0;i<=n;i++)
{
for(j=0;j<n;j++)psum[i][j+1]+=psum[i][j];
}
for(l=0;l<=n;l++)
{
for(r=l+1;r<=n;r++)
{
for(i=0;i<=n;i++)
{
for(j=i+1;j<=n;j++)sgvl[l][r][i][j]=f(l,r,i,j);
}
}
}
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
for(t=0;t<(1<<n);t++)dp[i][j][t]=0;
}
}
for(i=0;i<=n;i++)dp[i][i][0]=1;
for(len=1;len<=n;len++)
{
for(l=0;l+len<=n;l++)
{
r=l+len;
for(i=l+1;i<r;i++)
{
for(j=1;j<(1<<n);j++)
{
for(t=0;t<n;t++)
{
cmsk=j;
for(p=t;p<n&&(j>>p&1^1);p++)
{
cmsk|=(1<<p);
dp[l][r][cmsk]=(dp[l][r][cmsk]+dp[l][i][j]*sgvl[i][r][t][p+1])%mod;
}
}
}
}
for(j=1;j<(1<<n);j++)
{
for(i=0;(j>>i&1^1);i++);
for(t=n-1;(j>>t&1^1);t--);
sgvl[l][r][i][t+1]=(sgvl[l][r][i][t+1]+mod-dp[l][r][j])%mod;
}
for(i=0;i<n;i++)
{
cmsk=0;
for(t=i;t<n;t++)
{
cmsk|=(1<<t);
dp[l][r][cmsk]=(dp[l][r][cmsk]+sgvl[l][r][i][t+1])%mod;
}
}
if(len==1)continue;
for(j=0;j<(1<<n);j++)dp[l][r][j]=(dp[l][r-1][j]+dp[l][r][j])%mod;
}
}
for(i=0;i<=n;i++)
{
for(j=0;j<(1<<n);j++)
{
dp2[i][j]=0;
dpvl2[i][j]=0;
}
}
dp2[0][0]=1;
for(l=0;l<n;l++)
{
for(j=0;j<(1<<n);j++)
{
dp2[l+1][j]=(dp2[l+1][j]+dp2[l][j])%mod;
dpvl2[l+1][j]=(dpvl2[l+1][j]+dpvl2[l][j])%mod;
}
for(r=l+1;r<=n;r++)
{
for(j=0;j<(1<<n);j++)
{
for(i=0;i<n;i++)
{
cmsk=j;
for(t=i;t<n&&(j>>t&1^1);t++)
{
cmsk|=(1<<t);
dp2[r][cmsk]=(dp2[r][cmsk]+dp2[l][j]*sgvl[l][r][i][t+1])%mod;
dpvl2[r][cmsk]=(dpvl2[r][cmsk]+(dp2[l][j]+dpvl2[l][j])*sgvl[l][r][i][t+1])%mod;
}
}
}
}
}
ans=0;
for(j=1;j<(1<<n);j++)ans=(ans+dpvl2[n][j])%mod;
cout<<ans<<'\n';
}
return 0;
}
In Editorial of C :
Unable to parse markup [type=CF_MATHJAX]Fixed
Unable to view Editorial for problem C
We're not beating the speedforces allegations with this one!
In all seriousness I enjoyed A-C even if they were rather guessable, but there really should have been a problem in between C and D/E1
why so serious
gay
D>>>>>>>>>>>>>>>>>>>>>E1
The score for E1 was less than for D
well yeah, i didnt expect E to be easier
nah, no way, I got C wrong cus I forgot to use LL
303138777 and 303120425
same, spent like 20 min trying to find the mistake, but got it eventually
same. i spent almost 2 hours + 5 WAs.. T_T
First time i solved a b AND c in div1+2. Hope to get +ve delta :). thank you!
Your consistency is just awesome
Me too! (Although this was my first Codeforces contest...)
yeah I saw your profile too, what a consistent account, keep it up.. really awesome
Can't believe I reached specialist! Ngl I think I will now do a few virtuals and solve 16-1800s now I guess, before my next contest
Great to see your progress brother. And the consistency is really inspiring. Congratulations for becoming specialist
Congratulations for consistency
for B should the condition be
ti>2max(i−1,n−i)We are fixing it
I think for C, one could additionally use the fact that in an array of length $$$n$$$, the sum of differences is $$$a_n - a_1$$$. Thus if $$$a_n < a_1$$$, we reverse else not.
Exactly, that's why I had done too!
In the editorial for B it should be max instead of min
There should be a row with the average and median. ^_^;
I like the variance in predictions
I'd like to update it after the actual rating comes out and calculating the errors together
On the contrary, I'm surprised that the variance isn't higher, I personally would have rated H < G < E2 (unfortunately, I spent most of the contest debugging my approach for E2).
C clearly had more than expected solves in the contest. shame on these cheaters.
800 800 800 2400 1600 ? 2700 ? ?
The editorial for C and D is not very clear. What does fa mean in D?
The father of $$$u$$$.
not convinced(or did not fully understand) the proof of problem C. please help.
Assuming that in the optimal answer the sequence of operations is
1211121221.so, are we proving that instead of doing
1211121221we can simply do1111112222? Then we may need to do negation of all elements based on number of12operation swaps?and of course since
111111->no-opwe might as well only do2222?I think I understand now. However please let me know if I understood something incorrectly. thanks!
No, the argument is that operation 1 simply negates each term of the array, thereby all it does is change the sign of the sum. Thus, it is enough to perform operation 2 and take the absolute value of the sum at each step (Because if the sum was negative then you could have performed operation 1 before and gotten $$$-sum$$$)
Sorry for mixing up 1 and 2. It has been corrected now, and your understanding is correct.
Got it, Thanks!
But why doesn't it matter what the array looked like before you perform operation 1 or 2? The 12 -> 21 negating sum condition only applies to the sum right. But we can get different sums by performing operation 2 on different arrays (different elements at each index). Am I wrong?
For example, applying 2 to 1212 gives you a different individual elements than applying it to 2121. Wouldn't it?
Think 2121 gives same output as 11
Yeah, I was wondering exactly that, and the editorial lacks so much explanation that you really can't assume that the negative of the array won't generate possibly new (and larger) sums after you apply some other operations on it. That's why I wrote a comment explaining it with proofs of (almost) everything (except trivial things). I think you could like my explanation, so, please, take a look at my comment (somewhere below on this comment section).
I feel like the editorial for B is incomplete, especially for beginners. The most crucial part of the solution is that there never exists a part of the sequence that goes: {i...i+1 ...i... i+1} without visiting both ends of the array which allows one to show that the only optimal sequence is one in which we bounce back and forth from opposite ends of the array.
What does this mean?
there never exists a part of the sequence that goes: {i...i+1 ...i... i+1} without visiting both ends of the array
Imagine we visited {...2, 3, 2, 3...} at some point in our traversal. This is sub-optimal as the clocks after the first two moves are the same as after the fourth moves, but in the later all other clocks are two less. Hence we should delete the second {2,3};
This logic can be extended to any subsequence of the form {i, i+1, ...i+k,i+k-1,...i+1, i, i+1, ... i+k} where we can delete the everything after the first i+k and get a strictly better solution.
What is meant by "Since 2 does not change the sum of the sequence" in C's editorial? Doing the operation changes the sum right?
Same as above, sorry for mixing up 1 and 2. I have corrected it, but it takes some time to update.
dp solution of problem C
[Check303116516..]Can anybody explain why this is got WA. I can't understand the editorial for problem C. Here's the submission of c — https://codeforces.net/contest/2062/submission/303119038
B>>>>>>>>>C
I did B in like 5 min and 40 minutes for C, why people with good ratings are fumbling in B? even CM in friendlist got 3WA on B. Overthinking?
B is nice problem , but it was not harder then c
Quite helpful. Thank you
poor contest and even worse editorial
The editorial for D is made for people who have successfully solved the problem in the contest. The editorial is not clear at all !
Even I feel so,Can Someone Please provide a more detailed explanation.
The operation can be rephrased as follows: choose any edge in the tree, consider the two subtrees resulting from removing that edge, choose one of those subtrees, and increment all values in it by 1.
Consider any assignment of initial values to the nodes. For any two nodes connected by an edge, if they have different initial values, they can only become equal if we perform the operation selecting the edge between them, and incrementing the subtree of the smaller node.
Now, consider what the value of node i will be in the end. We can find this value by rooting the tree at i. The final value after the tree becomes balanced will be val[i] + sum(max(0, val[u] — val[par[u]])). Basically if val[par[u]] < val[u], we will need to increment everything above u.
We can prove that actually rooting at any node j != i will yield the same result as i. One way to prove this is by considering what happens to the result when we move from i to a neighbor.
Finally, this means we can just root arbitrarily, and greedily minimize sum(max(0, val[u] — val[par[u]])).
I hope there was an option to pin a comment!
This really helped. Thanks :)
I think it's quite clear for me. Can u explain which part made u confused pls?
Hi, I really don't understand the second part of the editorial. I don't see how we get to the conclusion that au should always be no less than the maximum value of its child nodes av. The proof involves something about decreasing ai and I don't know why do we need to decrease anything?
hmm just have a look to the formula ig. let u be the father and v be one of its child,and it's $$$\sum \max(a_v-a_u,0)$$$. let $$$M$$$ be the maximum value of a's among all these $$$v$$$. if we have $$$a_u$$$ smaller than $$$M$$$, just consider what will happen if we "push" the value of $$$a_u$$$ to bigger side(and of course,smaller than $$$r_u$$$). if we set $$$a_u\rightarrow a_u+1$$$, the value of $$$\sum \max(a_v-a_u,0)$$$ will decrease at least one, while the value of $$$\max(a_u-a_{fa},0)$$$ will increase at most one. thus it's not worse than the previous $$$a_u$$$. so it's always optimal to set $$$a_u$$$ bigger when $$$a_u\le M$$$, which lead to the observasion in the editorial.
Thanks a lot
"decrease" means comparing taking the maximum with maximum -1
I love you
Thanks, but it's okay now. One of my friends already explained it to me.
Please don't use symbols that are hard to understand in editorials like in E1 for example:
w,dfn,nfd,pre,suf,lowI am really trying to understand the solution, but I can't really fathom it due to them.
Yes. I can't identify/understand which algorithm is being used in the solutions for E1, and the variable names are far from helpful.
lowis definitely not a good name as a variable since it collides with thelowin tarjan algorithm. maybe usingendoredwill be better?For people learning tarjan algorithm, they often come up with
lowbecause it has similar operations (max thedfn).dfnstands for dfs number, which is the order of the DFS process in the algorithm. e.g.,dfn[root] = 1.lowstands for the maximundfnin the subtree. e.g.,low[root] = n.I use
lowas the variable name too and I just come up with the name myself. Is this a coincidence?well maybe it's just different to everyone :D
Not sure why you're being downvoted. I thought the same thing.
I am also not able to make sense of techniques used to find greater elements in subtree from the code, but now the editorial has been updated and it explains what they are doing.
It is actually pretty clear now after they updated.
Can someone explain why this code fails:
https://codeforces.net/contest/2062/submission/303155437
Can someone tell me why it doesn't get TLE? I literally brute-forced the operations and memoized the array itself. Submission Thanks
All the second operation does is multiply the array by -1 after the next operation of the first type, this means applying the second operation twice undoes itself no matter how many operations of type one are performed inbetween. Hence you only have 2*N states.
I somehow misread the problem B and thought we need to spend an additional second if we want to reset the clock. Does anyone know if this version of the problem is solvable?
I'm pretty sure the strategy of simply walking back and forth still is optimal, so you can solve the problem by updating the length of the walk as you have to reset an additional clock each cycle.
It doesn't really work, e.g. in test like
10 100 100 100 100you can just restart "big" clocks one by one between restarting the small one and the answer would beYES, whereas your strategy fails.Below I explain the solution to exercise C, doing exactly what the editorial didn't do.
Let's call the reverse instruction as '1' and the difference instruction as '2'. Let's create a new instruction, the "negative" instruction, that I will call from here on as '3'. That instruction multiplies each element of the input array by -1.
Theorem 1) Applying operation 1 two consecutive times is the same as not doing anything (proof omitted)
Theorem 2) Applying operation 3 two consecutive times is the same as not doing anything (proof omitted)
Theorem 3) Applying operation 1 does not change the sum of the input array (proof omitted)
Theorem 4) Applying operations "12" to a sequence is the same as applying operations "231".
Proof:
Let the input array be
[a1, a2, a3, ..., an]. Applying "12" on it leads to:After 1:
[an, a(n-1), a(n-2), ..., a1]After 2:
[a(n-1)-an, a(n-2)-a(n-1), ..., a1-a2]Applying "231" to
[a1, a2, a3, ..., an]:After 2:
[a2-a1, a3-a2, ..., an-a(n-1)]After 3:
[a1-a2, a2-a3, ..., a(n-1)-an]After 1:
[a(n-1)-an, a(n-2)-a(n-1), ..., a1-a2]So, the sequences of operations "12" and "231" are equivalent.
Theorem 5) Applying operations "23" to a sequence is the same as applying operations "32".
Proof:
Let the input array be
[a1, a2, a3, ... an]. Applying "23" on it leads to:After 2)
[a2-a1, a3-a2, ..., an-a(n-1)]After 3)
[a1-a2, a2-a3, ..., a(n-1)-an]And applying "32" to
[a1, a2, a3, ... an]:After 3)
[-a1, -a2, -a3, ..., -an]After 2)
[a1-a2, a3-a2, ..., a(n-1)-an]So, the sequences of operations "23" and "32" are equivalent.
===================
With those theorems in hand, let's solve the exercise.
Let
sbe any sequence of operations that leads to the maximum possible sum. For example,smay look something like this:s = 11112221212212112111According to Theorem 1, I can remove every pair of consecutive 1's, which would give me the following sequence:
s = 222121221221According to Theorem 3, I can remove the last 1 of the sequence:
s = 22212122122Now, from the left to the right of the sequence, let's change any appearance of "12" to "231". That won't change the final sum because Theorem 4 says those instructions are equivalent. If, while changing "12" to "231", we end up with consecutive 1's, we simply remove them (because of Theorem 1). If we end up with a 1 on the end, we simply remove it (because of Theorem 3). Below I simulate that process:
s = 22212122122s = 222231122122(Theorem 4)s = 2222322122(Theorem 1)s = 22223222312(Theorem 4)s = 222232223231(Theorem 4)s = 22223222323(Theorem 3)As you can see, we ended up with a sequence made only of 2's and 3's. Now, let's apply Theorem 5 several times and move all the 3's to the end:
s = 22222222333And now let's remove consecutive pairs of 3's, because Theorem 2 allows us to:
s = 222222223This simulation gives us a general idea of what any optimal sum sequence looks like: it is either:
An empty sequence (
s = "")A sequence of 1 or more 2's followed by none or only one 3 (
s = "222...2223",s = "22...2", etc)Now, our algorithm should simply try all of those sequences and grab the one with the highest sum, as shown here: (303162845)
Thank you for such clear explanation.
I'm happy it was helpful =)
is there any solution for E2 using small to big and segment tree
this is my attempt for this problem. if anyone can explain why my code gives me wa or gives a corner case for my code thanks.
https://codeforces.net/contest/2062/submission/303162086
Sadly i was not aware that if we resubmit a accepted qestion then the time of resubmition will be considered for that problem and my rank droped by 4000.
Can anyone recommend me some resources to solve E1? I got the idea in the contest but the editorial isn't clear about how to achieve the idea. Looking at others solutions, I feel like there's a gap in my knowledge somewhere on the topic.
I have updated more detailed information on how to achieve it.
Thanks! That helps a lot.
I didn’t solve D just because I didn’t consider the tree with only one point, which resulted in me doing nothing for the last hour. That's funny.
Thanks for the excellent contest. Problems D,E and F are all intersting!
How is the construction of array $$$a$$$ in Problem D’s editorial optimal?
problem C, the case 9 9 7 9 -9 9 -8 7 -8 9 why the answer is 2056?
Can someone who have solved E1 tell how they solved it and came to the conclusion their method was right?
At first we need to sort all node by their weight, then our strategy is choosing second biggest node (when it sorted by weight), and checking if in its subtree contains all bigger weight node or not, if not we will choose it, next player will choose the biggest, so there will be no other option, so we win. If it contains all, just check next smaller weights, until we find answer. If we dont find it, then there no answer. I solved that intuitively, that's why I wasn't sure if its correct or not :)
Problem D: Anyone getting Runtime Error in Test 8? Please help me how my solution got accepted in 7 test cases but runtime error in test 8?
https://codeforces.net/contest/2062/submission/303196494
I found the answer, thanks to Eunha His code helped me understand the problem. The recursion limit in Python is too low for test case 8 so we have to use a stack.
Surprisingly adding sys.setrecursionlimit(500000) is also not solving the problem.
Anyone knows any other way of increasing recursion limit? To do this without stack using recursive dfs?
https://codeforces.net/blog/entry/91490#comment-800269
Found a way to run recursive dfs in problem D.
See my solution: 303208534
PS: pajenegod you are the python god!
How does the C++ solution of D work?
Why does this line
erase(e[v], u);not TLE?Should it not be $$$O(n^2)$$$?
The total time these
eraseoperations take throughout the whole DFS is $$$\mathcal{O}(E)$$$, because this operation is done for each vertex only once and for each vertex it takes time proportional to the number of edges attached to it. Since this is a tree, it's also $$$\mathcal{O}(V)$$$.Got it.
Is there any proof for B ?
why O(n^2) gives TLE in E1, even when time limit is 4 sec ?
N^2 is about 1e10 operations, which will be done in 100 seconds.
thanks
Is the reason why the first comparison in question C did not take an absolute value compared to the prefix sum without operation?
2062B Clockwise ans in c++ is wrong my code is also similar except var name . testcase 1 both code passed but testcase 2 failed both.
This had such an uneducative C, the previous round's B was better than this round's C. Just simple observation that sum of differences is an-a1,solves this.
Anyone have material For understanding E1 problem i see sol but that is beyond my understanding since some are using eulertour or something can someone provide problem resource for this pls
I solved it with small to large trick, it was needed to maintain how many nodes V in subtree U satisfy this condition: w[U] < w[V]. Here you can read more details about it.
Thanks bro!
E1 editorial says "Additionally, we can enumerate the nodes in descending order of wi and maintain their lowest common ancestor (LCA). If the LCA of all v satisfying wv>wu is not a descendant of u, then there must exist a node v outside the subtree of u that satisfies wv>wu."
what if there are n/2 nodes with maximum w[v] and we need to check each one of them with every other w[u] to find the answer and exactly the last one we check is the answer?
isn't it O(n^2lg)? or even O(n^2)?
can someone explain if I'm wrong?
Yakumo_Ran
Don't know if anyone can't understand the implementation of E2 from official editorial but here is my own code, based totally on what the editorial said, using LCA and basic data structures. maybe it's easier to understand?
I will give it a try!! Thank you!
You can also use Small To Large for problem E1.
Idea : - If the current value don't contain the previous larger values then the node containing it is definitely winnable. Or if it does contain, if the previous larger values do exist outside of the subtree of this node then it is also a winnable node.
This is my code :
https://codeforces.net/contest/2062/submission/303225889
Does anyone have proof for why solution for D actually works?
imho, I don't see myself looking at D and thinking ohh well this should work. (maybe my skill issue).
Apart from that I wanted to say that I loved problem F.
I will explain how i approached the problem:
Lets root the tree at node $$$1$$$. We need to find the minimum value $$$V_u$$$ for the subtree of some node $$$u$$$. (we can always increase the value later if we need)
Assume the subtree of all of the children of $$$u$$$ have an equal value $$$V_i$$$. we have two cases:
$$$V_i \leq R_u$$$, we can just increase that subtree till $$$L_u \leq V_i$$$
$$$V_i > R_u$$$, we need to increase all of the tree except that subtree, the final answer increases by the difference $$$V_i - R_u$$$ and $$$V_i$$$ "decreases" till its at most $$$R_u$$$ (the only thing that changes is their relative difference)
The minimum value of the node $$$u$$$ is the maximum value among $$$V_i$$$ and the minimum value of a leaf is just $$$L_u$$$.
Code
The thing that is bugging me is why choosing any root for this operation is fine?
Consider an operation: root the tree at node $$$u$$$ and increase the subtree of node $$$v$$$ ($$$u \neq v$$$). we can always move the root $$$u$$$ towards $$$v$$$ as long as $$$u \neq v$$$ and the operation will have the same effect.
So the operations can be simplified to two adjacent nodes (an edge) or equal nodes (which just increases the entire tree).
That means if we root at any node $$$u$$$, the operation can be done on some edge and increase either the entire tree, the entire tree except a subtree or only the subtree. so we can just consider one root.
Hello, pls someone help me to find mistake in my solution of D: My idea is that I am taking a leaf and its parent and trying to make them equal in minimal amount of steps, then just deleting leaf, cause it will behave like its parent
my submission
the editorialist must explain in the D, why taking any node as root for the greedy strategy yields in same answer.
Bottom up pull DP for C -> Click
The DP of F is fun, but I have a question. How do you approach the required transformation of the
max? Are these transformations common? I don't think I can come up with one even if I think about it for a week. I wonder how the rankers came up with it.