idea: Cocoly1990
Solution
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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)
Easy Solution
Tutorial is loading...
Hard Solution
Tutorial is loading...
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;
}
idea: waaitg
Solution
Tutorial is loading...
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
Tutorial is loading...
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;
}
Solution
Tutorial is loading...
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;
}
i love solving observation problems like c , i just tried some cases and came up with the soluion .
but i tried many cases without caming up a solution:\
deque is a good tool
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
Very fast editorial!
Thanks for the super fast editorial and great round ! As usual, here is my advice about the problems I solved :)
That's one of the best, if not the best, div2 A I've ever seen! It requires a very small idea, have simple implementation, and it's kinda cute. Like even if the idea is simple, it is still somewhat interesting
Maybe a bit too easy for a div2 B ? It's very hard to get the right difficulty for these problems as it should be a little bit harder than A, but not too much harder. The problem is still cool though.
It felt a bit too easy for div2 C ? Although I liked the problem.
That's a great problem ! It felt very natural: as there are too much edges, there must be a way to restrict the construction by considering nodes with special properties (such as smallest i).
Well I somehow have a bug in my implementation but the problem was cool (noticing that there is only O(n) intersections to check if you want to remove some rain that comes from 2 ranges).
UPD: funny how my bug was just writting
if () { } else { do x }
instead of if () { } else { } do x
E2 looks neat too, although I have no clue of how to do it :))
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 :/
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.
5+4 = 9, so answer should be no.
good contest — good problems, except b was kinda troll (i found it funny though)
Div. 1 B and C1 are great! (Maybe also C2 but I didn't solve it) I like the way to optimize the algorithm.
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).
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.
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?
Assume $$$i < j < k$$$.
Now the condition for $$$i$$$ can't form an edge with $$$k$$$, but $$$j$$$ can form an edge with $$$k$$$ :
$$$a[j] + a[k] >= c*j*k$$$
$$$c*i*k > a[i] + a[k] $$$
Adding both inequalities,
$$$a[j] - a[i] > c*(j-i)*k$$$
So for a fixed $$$i$$$ and $$$j$$$, it's always good to choose least $$$k$$$, which will be $$$k = j + 1$$$ in this case.
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.
the problems are so smart that I feel like I'm idiot D: anyway, that is a good round, thanks!
In Div2C/Div1A, I didn't understand why would it take at most 300 operations. I'd be grateful if someone can explain.
Because the problem tells you
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
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:
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.
C1 (easy) unlucky for python, same solution accepted in C++ (even a slower version). Yes there were people who solved it, but only 3.
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?
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.
Can someone explain how in problem Div. 1 D the idea for the easy version is extended to the original problem?
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
You check check my implementation. https://codeforces.net/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
Please someone explain Div2 E1 solution with the code. I couldn’t understand the editorial.
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
Take a look at Ticket 17118 from CF Stress for a counter example.
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 ?
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.
Can someone help me where my code is failing for Div 2 C problem? Submission id 230209550
This was a wonderful contest Problems were mainly based on observations and less on standard techniques. Thank you for such contest.
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
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]$$$
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:(
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!!
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$$$).
$$$a_i + a_j ≥ ijc$$$ (given)
$$$a_i + a_j ≥ 2jc$$$ (because $$$i ≥ 2$$$)
$$$2a_j ≥ 2jc$$$ (because $$$a_i ≤ a_j$$$)
$$$a_j ≥ jc$$$ (QED)
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.
Amazing proof !!!
اي قلة ادب دي
صاحب الكمنت دا لازم يتحاسب
I don't see how to "see" the solution for Div2C... Can someone explain the intuition?
.
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 becomesfor...., s[i] != s[s.size()-i-1]
. Now consider a case when length of the string isODD
. 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.
In problem D of div-2 does the given constant actually have any impact ? Like whats the significance of c?
With $$$c = 1$$$ the tests would be weak.
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
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)
Could somebody explain Div1C2/Div2E2 in more detail, after we understood dp in O(n^2k)?
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)
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!
Could you please explain how the sparse tree with updates works? I am confused on this array example:
The sparse tree looks like
After updating the index 3 to 10 based on the solution's implementation the sparse tree becomes
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
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.
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://codeforces.net/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...
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".
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://codeforces.net/blog/entry/48994
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.
https://codeforces.net/contest/1889/submission/239421653 can anybody stress test it pls
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?
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.