Idea: FieryPhoenix

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n,x;
int w[101];
cin>>n>>x;
int sum=0;
for (int i=0;i<n;i++){
cin>>w[i];
sum+=w[i];
}
//if the sum is x, we cannot avoid the explosion
if (sum==x){
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
//otherwise, the answer always exists
//we will keep adding elements from left to right
//if we can't add element i, we add element i+1 first by swapping the two
for (int i=0;i<n;i++){
if (x==w[i]){
//i+1 will always be less than n because otherwise, the total sum would be x
swap(w[i],w[i+1]);
}
cout<<w[i]<<' ';
x-=w[i];
}
cout<<endl;
return;
}
int main(){
int T; cin>>T;
while (T--)
solve();
return 0;
}
```

Idea: FieryPhoenix

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
bool isSquare(int x){
int y=sqrt(x);
return y*y==x;
}
void solve(){
int n;
cin>>n;
if (n%2==0 && isSquare(n/2))
cout<<"YES"<<endl;
else if (n%4==0 && isSquare(n/4))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
int main(){
int t; cin>>t;
while (t--)
solve();
}
```

Idea: FieryPhoenix

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int N,M,X;
int H[100001];
void solve(){
cin>>N>>M>>X;
cout<<"YES"<<endl;
set<pair<int,int>>s; //stores pairs of (height, index)
for (int i=1;i<=M;i++)
s.insert({0,i});
for (int i=0;i<N;i++){
cin>>H[i];
pair<int,int>p=*s.begin();
s.erase(p);
cout<<p.second<<' ';
s.insert({p.first+H[i],p.second});
}
cout<<endl;
}
int main(){
int T; cin>>T;
while (T--)
solve();
}
```

Idea: FieryPhoenix

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int N,L,R;
int C[200001];
int lcnt[200001],rcnt[200001];
void solve(){
cin>>N>>L>>R;
for (int i=1;i<=N;i++){
lcnt[i]=0;
rcnt[i]=0;
}
for (int i=1;i<=N;i++){
cin>>C[i];
if (i<=L)
lcnt[C[i]]++;
else
rcnt[C[i]]++;
}
//remove pairs that are already matching
for (int i=1;i<=N;i++){
int mn=min(lcnt[i],rcnt[i]);
lcnt[i]-=mn;
rcnt[i]-=mn;
L-=mn;
R-=mn;
}
if (L<R){
swap(lcnt,rcnt);
swap(L,R);
}
//now, there are at least as many left socks as right socks
int ans=0;
for (int i=1;i<=N;i++){
int extra=L-R; //always even
int canDo=lcnt[i]/2;
int Do=min(canDo*2,extra);
//turn "Do"/2 left socks of color i into right socks
ans+=Do/2;
L-=Do;
}
//turn extra lefts into rights, then adjust all colors
ans+=(L-R)/2+(L+R)/2;
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int T; cin>>T;
while (T--)
solve();
return 0;
}
```

Idea: FieryPhoenix

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD;
int N;
ll dp[405][405];
ll fastexp(ll b, ll exp){
if (exp==0)
return 1;
ll temp=fastexp(b,exp/2);
temp=(temp*temp)%MOD;
if (exp%2==1)
temp*=b;
return temp%MOD;
}
ll fact[405],inv[405],choose[405][405],pow2[405];
void precompute(){
fact[0]=1;
inv[0]=1;
for (int i=1;i<=N;i++){
fact[i]=(fact[i-1]*i)%MOD;
inv[i]=fastexp(fact[i],MOD-2);
}
for (int i=0;i<=N;i++)
for (int j=0;j<=i;j++)
choose[i][j]=((fact[i]*inv[j])%MOD*inv[i-j])%MOD;
for (int i=0;i<=N;i++)
pow2[i]=fastexp(2,i);
}
int main()
{
cin>>N>>MOD;
precompute();
dp[0][0]=1;
for (int i=0;i<N;i++){
for (int j=0;j<=i;j++){
for (int k=1;i+k<=N;k++){
dp[i+k+1][j+k]+=((dp[i][j]*pow2[k-1])%MOD*choose[j+k][k]);
dp[i+k+1][j+k]%=MOD;
}
}
}
ll ans=0;
for (int i=0;i<=N;i++)
ans=(ans+dp[N+1][i])%MOD;
cout<<ans<<endl;
return 0;
}
```

1515F - Phoenix and Earthquake

Idea: dragonslayerintraining

**Tutorial**

Tutorial is loading...

**Solution**

```
// Fix a spanning tree
// Pick a leaf, either merge it into its parent or postpone it to the end
#include <cstdio>
#include <vector>
#include <algorithm>
const int MAXV=300005;
const int MAXE=300005;
int N,M,X;
long long as[MAXV];
int elist[MAXE*2];
int head[MAXV];
int prev[MAXE*2];
int tot=0;
bool vis[MAXV];
int ans[MAXV];
int front,back;
void dfs(int u){
vis[u]=true;
for(int e=head[u];e!=-1;e=prev[e]){
int v=elist[e^1];
if(vis[v]) continue;
dfs(v);
if(as[u]+as[v]>=X){
as[u]+=as[v]-X;
ans[front++]=e>>1;
}else{
ans[--back]=e>>1;
}
}
}
int main(){
scanf("%d %d %d",&N,&M,&X);
long long total=0;
for(int i=0;i<N;i++){
scanf("%lld",&as[i]);
total+=as[i];
}
if(total<1LL*(N-1)*X){
printf("NO\n");
return 0;
}
std::fill(head,head+N,-1);
for(int i=0;i<M*2;i++){
int U;
scanf("%d",&U);
U--;
prev[i]=head[U];
head[U]=i;
elist[i]=U;
}
back=N-1;
dfs(0);
printf("YES\n");
for(int i=0;i<N-1;i++){
printf("%d\n",ans[i]+1);
}
}
```

Idea: dragonslayerintraining

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>
using ll = long long;
std::vector<std::pair<int,int> > fwd[200005];
std::vector<std::pair<int,int> > rev[200005];
int vis[200005];
int cc[200005];
ll offset[200005];
int ncc;
ll loop[200005];
std::vector<int> ord;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
void dfs_fwd(int x){
vis[x]=1;
for(auto e:fwd[x]){
int y=e.first;
if(vis[y]!=1){
dfs_fwd(y);
}
}
ord.push_back(x);
}
void dfs_rev(int x){
vis[x]=2;
for(auto e:rev[x]){
int y=e.first,l=e.second;
if(vis[y]!=2){
cc[y]=cc[x];
offset[y]=offset[x]+l;
dfs_rev(y);
}else if(cc[y]==cc[x]){
loop[cc[x]]=gcd(loop[cc[x]],std::llabs(offset[x]+l-offset[y]));
}
}
}
int main(){
int N,M;
scanf("%d %d",&N,&M);
for(int i=0;i<M;i++){
int A,B,L;
scanf("%d %d %d",&A,&B,&L);
A--,B--;
fwd[A].push_back({B,L});
rev[B].push_back({A,L});
}
for(int i=0;i<N;i++){
if(vis[i]!=1){
dfs_fwd(i);
}
}
std::reverse(ord.begin(),ord.end());
for(int i:ord){
if(vis[i]!=2){
cc[i]=ncc++;
offset[i]=0;
dfs_rev(i);
}
}
int Q;
scanf("%d",&Q);
for(int i=0;i<Q;i++){
int V,S,T;
scanf("%d %d %d",&V,&S,&T);
V--;
assert(0<=S&&S<T);
if(S%gcd(loop[cc[V]],T)==0){
printf("YES\n");
}else{
printf("NO\n");
}
}
}
```

Idea: dragonslayerintraining

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <cstdio>
#include <cassert>
#include <utility>
#include <functional>
//numbers up to 2^MAXLOGX-1
const int MAXLOGX=20;
template<int k>
struct Trie{
Trie<k-1>* chd[2];
int cnt;
int lazy;
int has[2];
int get_cnt(){
assert(this!=NULL);
return cnt;
}
int get_has(int d){
assert(this!=NULL);
push();
assert(has[d]<(1<<(k+1)));
return has[d];
}
Trie(Trie<k-1>* l,Trie<k-1>* r):chd{l,r},cnt(0),lazy(0),has{0,0}{
if(l){
cnt+=l->get_cnt();
has[0]|=l->get_has(0)|(1<<k);
has[1]|=l->get_has(1);
}
if(r){
cnt+=r->get_cnt();
has[0]|=r->get_has(0);
has[1]|=r->get_has(1)|(1<<k);
}
assert(has[0]<(1<<(k+1)));
assert(has[1]<(1<<(k+1)));
}
void push(){
assert(lazy<(1<<(k+1)));
if(!lazy) return;
//handle kth bit
if(lazy&(1<<k)){
std::swap(chd[0],chd[1]);
if((has[0]^has[1])&(1<<k)){
has[0]^=(1<<k);
has[1]^=(1<<k);
}
lazy^=(1<<k);
}
//handle rest of bits
int flip=(has[0]^has[1])&lazy;
has[0]^=flip;
has[1]^=flip;
if(chd[0]) chd[0]->lazy^=lazy;
if(chd[1]) chd[1]->lazy^=lazy;
lazy=0;
assert(has[0]<(1<<(k+1)));
assert(has[1]<(1<<(k+1)));
}
};
template<>
struct Trie<-1>{
int lazy;
Trie():lazy(0){
}
int get_cnt(){
assert(this!=NULL);
return 1;
}
int get_has(int d){
assert(this!=NULL);
return 0;
}
};
template<int k>
Trie<k>* create(int x){
if(x&(1<<k)){
return new Trie<k>(NULL,create<k-1>(x));
}else{
return new Trie<k>(create<k-1>(x),NULL);
}
}
template<>
Trie<-1>* create(int x){
return new Trie<-1>();
}
template<int k>
std::pair<Trie<k-1>*,Trie<k-1>*> destruct(Trie<k>* a){
assert(a!=NULL);
a->push();
auto res=std::make_pair(a->chd[0],a->chd[1]);
delete a;
return res;
}
template<int k>
Trie<k>* join(Trie<k-1>* l,Trie<k-1>* r){
if(l==NULL&&r==NULL) return NULL;
return new Trie<k>(l,r);
}
template<int k>
Trie<k>* merge(Trie<k>* a,Trie<k>* b){
if(!a) return b;
if(!b) return a;
auto aa=destruct(a);
auto bb=destruct(b);
Trie<k-1>* l=merge<k-1>(aa.first,bb.first);
Trie<k-1>* r=merge<k-1>(aa.second,bb.second);
return join<k>(l,r);
}
template<>
Trie<-1>* merge<-1>(Trie<-1>* a,Trie<-1>* b){
if(!a) return b;
if(!b) return a;
delete b;
return a;
}
template<int k>
//<thres and >=thres
std::pair<Trie<k>*,Trie<k>*> split(Trie<k>* a,int thres){
if(a==NULL){
return {NULL,NULL};
}
if(thres<=0) return {NULL,a};
if(thres>=(1<<(k+1))) return {a,NULL};
assert(k>=0);
auto aa=destruct(a);
if(thres<(1<<k)){
Trie<k-1>* l,*r;
std::tie(l,r)=split<k-1>(aa.first,thres);
return std::make_pair(join<k>(l,NULL),join<k>(r,aa.second));
}else if(thres>(1<<k)){
Trie<k-1>* l,*r;
std::tie(l,r)=split<k-1>(aa.second,thres-(1<<k));
return std::make_pair(join<k>(aa.first,l),join<k>(NULL,r));
}else{
return std::make_pair(join<k>(aa.first,NULL),join<k>(NULL,aa.second));
}
}
template<>
std::pair<Trie<-1>*,Trie<-1>*> split<-1>(Trie<-1>* a,int thres){
assert(0);
}
template<int k>
Trie<k>* update(Trie<k>* a,int val){
if(a==NULL) return NULL;
a->push();
assert(val<(1<<(k+1)));
if((val&a->has[0]&a->has[1])==0){
a->lazy^=(val&a->has[0]);
return a;
}
Trie<k-1>* l,*r;
std::tie(l,r)=destruct(a);
l=update<k-1>(l,val&~(1<<k));
r=update<k-1>(r,val&~(1<<k));
if(val&(1<<k)){
return join<k>(NULL,merge<k-1>(l,r));
}else{
return join<k>(l,r);
}
}
template<>
Trie<-1>* update<-1>(Trie<-1>* a,int val){
return a;
}
int main(){
Trie<MAXLOGX-1>* root=NULL;
int N,Q;
scanf("%d %d",&N,&Q);
for(int i=0;i<N;i++){
int A;
scanf("%d",&A);
root=merge(root,create<MAXLOGX-1>(A));
}
for(int i=0;i<Q;i++){
int T,L,R;
scanf("%d %d %d",&T,&L,&R);
Trie<MAXLOGX-1>* left,*right;
std::tie(left,root)=split(root,L);
std::tie(root,right)=split(root,R+1);
if(T==4){
printf("%d\n",root?root->cnt:0);
}else{
int X;
scanf("%d",&X);
if(root!=NULL){
if(T==1){
root->lazy^=((1<<MAXLOGX)-1);
root=update(root,X^((1<<MAXLOGX)-1));
root->lazy^=((1<<MAXLOGX)-1);
}else if(T==2){
root=update(root,X);
}else if(T==3){
assert(X<(1<<MAXLOGX));
root->lazy^=X;
}
}
}
root=merge(root,left);
root=merge(root,right);
}
}
```

Idea: dragonslayerintraining

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <cstdio>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <cassert>
using ll=long long;
const ll INF=1e18+7;
struct Diamond{
int w,v,t;
ll a;
}diamonds[200005];
int index[200005];
int N;
struct Node{
ll sum_w[31];//sum of weights of all diamonds with weight <2^k
ll sum_v[31];//sum of values of all diamonds with weight <2^k
ll one_w[31];//sum of weights of light+first heavy when restricted to <2^k
ll one_v[31];//sum of values of light+first heavy when restricted to <2^k
}st[800005];
void rebuild(int w,int L,int R,int a,int b){
if(a>=R||b<=L) return;
if(R-L==1){
for(int k=1;k<=30;k++){
st[w].sum_w[k]=diamonds[L].a*diamonds[L].w*(diamonds[L].w<(1<<k));
st[w].sum_v[k]=diamonds[L].a*diamonds[L].v*(diamonds[L].w<(1<<k));
st[w].one_w[k]=INF;//query capacity never exceed INF
st[w].one_v[k]=INF;
if(diamonds[L].w>=(1<<(k-1))&&diamonds[L].w<(1<<k)&&diamonds[L].a>0){
st[w].one_w[k]=diamonds[L].w;
st[w].one_v[k]=diamonds[L].v;
}
}
}else{
int M=(L+R)/2;
rebuild(w*2+1,L,M,a,b);
rebuild(w*2+2,M,R,a,b);
for(int k=1;k<=30;k++){
st[w].sum_w[k]=st[w*2+1].sum_w[k]+st[w*2+2].sum_w[k];
st[w].sum_v[k]=st[w*2+1].sum_v[k]+st[w*2+2].sum_v[k];
if(st[w*2+1].one_w[k]<st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k]){
st[w].one_w[k]=st[w*2+1].one_w[k];
st[w].one_v[k]=st[w*2+1].one_v[k];
}else{
st[w].one_w[k]=st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k];
st[w].one_v[k]=st[w*2+1].sum_v[k-1]+st[w*2+2].one_v[k];
}
}
}
}
//only consider weights <2^k
//take maximal prefix possible
void query_all(int w,int L,int R,int& i,int k,ll& cap,ll& value){
assert(i>=L&&i<=R);
assert(R-L>0);
if(i==R) return;
if(i==L&&st[w].sum_w[k]<=cap){
cap-=st[w].sum_w[k];
value+=st[w].sum_v[k];
i=R;
}else if(R-L>1){
int M=(L+R)/2;
if(i<M){
query_all(w*2+1,L,M,i,k,cap,value);
}
if(i>=M){
query_all(w*2+2,M,R,i,k,cap,value);
}
}
}
std::array<ll,2> query_one_range_simpl(int w,int L,int R,int a,int b,int k){
if(a>=R||b<=L) return {INF,0};
if(a<=L&&b>=R){
return {st[w].one_w[k],st[w].sum_w[k-1]};
}else{
int M=(L+R)/2;
std::array<ll,2> lsum,rsum;
lsum=query_one_range_simpl(w*2+1,L,M,a,b,k);
rsum=query_one_range_simpl(w*2+2,M,R,a,b,k);
if(lsum[0]<lsum[1]+rsum[0]){
return {lsum[0],lsum[1]+rsum[1]};
}else{
return {lsum[1]+rsum[0],lsum[1]+rsum[1]};
}
}
}
std::array<ll,4> query_one_range(int w,int L,int R,int a,int b,int k){
if(a>=R||b<=L) return {INF,INF,0,0};
if(a<=L&&b>=R){
return {st[w].one_w[k],st[w].one_v[k],st[w].sum_w[k-1],st[w].sum_v[k-1]};
}else{
int M=(L+R)/2;
std::array<ll,4> lsum,rsum;
lsum=query_one_range(w*2+1,L,M,a,b,k);
rsum=query_one_range(w*2+2,M,R,a,b,k);
if(lsum[0]<lsum[2]+rsum[0]){
return {lsum[0],lsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]};
}else{
return {lsum[2]+rsum[0],lsum[3]+rsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]};
}
}
}
//returns min j such that one_w[i..j) <= cap, or -1 if none exist
//reduce cap by weight of light in [max(i,L),R)
int query_one_range_search_(int w,int L,int R,int& i,int k,ll& cap){
assert(i>=L&&i<=R);
assert(R-L>0);
if(i==R) return -1;
if(i==L&&st[w].one_w[k]>cap){
cap-=st[w].sum_w[k-1];
i=R;
return -1;
}else if(R-L==1){
assert(i==L);
assert(st[w].one_w[k]<=cap);
cap-=st[w].sum_w[k-1];
i=R;
return R;
}else{
int M=(L+R)/2;
int res=-1;
if(i<M){
res=query_one_range_search_(w*2+1,L,M,i,k,cap);
}
if(res!=-1) return res;
if(i>=M){
res=query_one_range_search_(w*2+2,M,R,i,k,cap);
}
return res;
}
}
int query_one_range_search(int i,int k,ll cap){
//note this copy of cap will be modified
return query_one_range_search_(0,0,N,i,k,cap);
}
void query_one(int& L,int k,ll& cap,ll& value){
int high=query_one_range_search(L,k,cap);
//v[high]<=cap
if(high!=-1){
auto v=query_one_range(0,0,N,L,high,k);
L=high;
cap-=v[0];
value+=v[1];
}
}
ll query(ll cap){
ll value=0;
int i=0;
for(int k=30;k>0;k--){
query_all(0,0,N,i,k,cap,value);
if(i==N) break;
ll take=std::min(diamonds[i].a,cap/diamonds[i].w);
cap-=take*diamonds[i].w;
value+=take*diamonds[i].v;
i++;
query_one(i,k,cap,value);
}
return value;
}
int main(){
int Q;
scanf("%d %d",&N,&Q);
for(int i=0;i<N;i++){
scanf("%lld %d %d",&diamonds[i].a,&diamonds[i].w,&diamonds[i].v);
diamonds[i].t=i;
}
std::sort(diamonds,diamonds+N,[](Diamond x,Diamond y){
return (x.v!=y.v)?(x.v>y.v):(x.w<y.w);
});
for(int i=0;i<N;i++){
index[diamonds[i].t]=i;
}
rebuild(0,0,N,0,N);
for(int i=0;i<Q;i++){
int T;
scanf("%d",&T);
if(T==1){
int K,D;
scanf("%d %d",&K,&D);
D--;
diamonds[index[D]].a+=K;
rebuild(0,0,N,index[D],index[D]+1);
}else if(T==2){
int K,D;
scanf("%d %d",&K,&D);
D--;
diamonds[index[D]].a-=K;
assert(diamonds[index[D]].a>=0);
rebuild(0,0,N,index[D],index[D]+1);
}else{
ll C;
scanf("%lld",&C);
printf("%lld\n",query(C));
}
}
}
```

Thanks for the nice problems!

LUNCHBOX OTZ

Downvoting because he used OTZ instead of orz, which is clearly superior.

downdooted for needlessly downvoting people

sto c8kbf orz

orz does not work as in caps it would be ORZ

When you are typing in all caps, it is better to use OTZ or OFZ

How about OГZ

Hmm Tutorials here pretty fast. I guess those edu rounds require some sort of godly Sacrifice before they release solutions.

They have a 12 hour open hacking, so cant release solutions. lol

Even after those 12 hours they make us wait. atleast in prev edu round

Maybe its bcoz edu round setters have to write lot of problems in a month, so they get late in writing editorial.

ok makes sense. it may be they have solutions but either they got that wrong or someone came up with better solution which may get updated in editorial. Lol from now on i will take a chill pill after a contest

Actually even though such delay makes sense AFAIR it was mentioned that there is no requirement to delay editorial until the end of the hacking and it is up to the authors.

Phoenix and Editorial.

Thanks :')

Thanks for the nice problems!

Am I missing something for B? A 3x3 square can be formed with 14 pieces with one 4 piece and five 2 pieces.

nope they cant be. You can't cut or deform isosceles triangles to fit in square

Ah, I subconsciously assumed 2 * short side of triangle = longer side. This is embarrassing...

Nope you cant form 3x3 with 14 pieces, either form 3x3 with 2pieces which will require 18 pieces(2) or form 3x3 with 4 pieces which will require 36 pieces(4). Refer to first and second test case explanation for better understanding,also check the side lengths of both of the test cases.

Variation of

Problem D: We are only given number of left and right socks and not which color sock is left or right. We would have to answer for worst possible case of assignment of left and right. What would be approach in this question?thats exactly what my fix function is doing in the code

https://codeforces.com/contest/1515/submission/114942890

help yourself as i am still salty for not solving problem 5

PS: By worst case i assumed max operations which would occur if no pairs with same color occur in your test case for the above variation

You can actually AC with a O(n^4) solution on E using a very stupid method: you can precompute all values up to 400 without any mods locally (takes a few minutes), convert them to a larger base using ASCII characters, and store the large values (ones where n^4 is too slow) in a string that is just under 64kb in size :P

Accepted

I doubt so if this was a hacking phase. Someone might be friend you now just for the sake of hacking solutions in later edu rounds. Just Saying

took 37 minutes to me

Wow man this is just crazy!!

I like the way you think :)

Also here is a pure

O(n^4)solution getting accepted comfortably, with a little bit of pruning and unrolling.I passed with a pure $$$O(n^4)$$$ too 114926425.

Let $$$f_{i,j}$$$ be the number of ways to cover a segment of length $$$i$$$ using $$$j$$$ steps.

We can get an $$$O(n^4)$$$ approach by finding the last to take over all.

At first I used dfs, which took about $$$120s$$$.

Then I changed it to a dfs-free approach, which took about $$$60s$$$.

Then we can see that if $$$f_{x,y}$$$ is zero when $$$y<x/2$$$ or $$$y>x$$$,then it took $$$30s$$$.

When you know the last place to choose, you also have to know how many steps you are going to use in the left part. Just check the places with non-zero values, then it took $$$15s$$$.

Then I replaced some mod in my code and it took $$$8s$$$.

If we are calculating $$$f_{n,m}$$$,let $$$x$$$ be the last position to choose, the answer is the same if we choose $$$n-x+1$$$, it took $$$4s$$$.

Then I used Fast_Mod instead of regular mod,it took $$$3s$$$ on my PC.

Submitted it and it passed in less than 2 seconds!

Haha sounds exactly like the way I solved it. Was a bit skeptical whether it could be done in this way but CF is quite fast.

woah, never thought of that. Very smart approach :)

No, it's a stupid insecure method instead

I also passed with $$$O(n^4)$$$, with heavy constant optimization and precomputation. It ran locally in ~$$$1.45s$$$ and got accepted in $$$2854ms$$$ (was $$$2932ms$$$ in pretests and I got scared it might FST)

All I did was precompute all nCr terms and restrict the bounds of looping on the dp array to not compute useless cells.

Code: 114943295

Anybody understand E solution

Could someone explain me 3rd in detail ? I would be thankful.

u need to make m towers with the n blocks of various sizes none of which exceed size x now pick 2 towers abs( height tower 1 — height tower 2) <= x if the above is not correct for your arrangement then your arrangement is wrong

other wise just print which block went in which tower

cheers

Thanks mate :)

In third problem, the idea is to greedily put the next block in the smallest tower so far. Which can be done using a set as a set stores elements in sorted order, so the first element would be the smallest (in this case it would be the smallest tower's height and index), then we can just add the current block to this tower, and update its height (by removing it from the set and inserting the modified one).

PS: The way this greedy approach works is that, if we don't add the current block to the smallest tower we would be increasing the difference in their heights, which might get bigger than x, so adding to the smallest tower always ensures that, the difference will never exceed x as the heights of all the blocks is not greater than x.

I hope this helps :D

Yep, thanks I got the problem statement now :)

see this 114972329

any clues what's wrong in C problem ? 114955920

Maybe this helps Link

Problem I was pretty similar to this one: 1439C - Greedy Shopping

Was $$$n$$$ set to $$$400$$$ in E to cut the precalc solutions (the minimal file size to decode all the answers is 66kb while cf accepts only 65kb files)?

This person says they did use pre-calculation and got the file size to 64kb and their solution got accepted. Maybe they found a work-around. https://codeforces.com/blog/entry/90236?#comment-786797

They stored the values starting from $$$100$$$ which fits in $$$64$$$ kb; storing all the values doesn't fit

No, it fits: 114952738

Furthermore, I have used only 100 different symbols.

which $$$100$$$ symbols? are the ones below $$$32$$$ allowed?

Yes, surprisingly, you can use them. The only exceptions are '\n', which I've used as a separator and '$' — I had troubles escaping it in kotlin. So, I have used symbols with codes 14..113 plus 127 instead of dollar sign.

Problem Ehas $$$O(n^2)$$$ solution. The formula:$$$l$$$ denotes amount computers turn on manually and $$$z$$$ — turn on automatically.

submission: https://codeforces.com/contest/1515/submission/114961141Is your formula inclusion, exclusion. Please explain

more detailed solution

Can anyone explain

Problem Bin detail? please!!Youve to form a square with given pieces if it's possible then print yes otherwise no

Link to Explanation

Thank you :)

Even after completion of system testing, it is showing pretest passed in B and a negative in standings. What should I do? https://codeforces.com/contest/1515/standings/friends/true

E can also be solved in $$$O(N^2)$$$.

We're solving for $$$ans(N)$$$

Brief: Let $$$f(k)$$$ be the number of ways to solve when the computers can be split into k non empty subarrays. i,e, $$$k-1$$$ computers aren't turned on manually.

The goal is to solve for each $$$k$$$ in $$$O(n)$$$ and add them separately.

Let's call the number of size $$$m$$$ sequences that contribute to the $$$ans(n)$$$ be equal to $$$g(m,n)$$$

$$$g(n,n) = 2^{n-1}$$$ (Observe the reverse direction of turning on computers. We optionally increment the suffix or prefix)

For a given sequence of lengths of subsegments, $$$S_1, S_2, S_3..S_k$$$, we can solve for each subsegment independently (for each subsegment, it would be $$$g(S, S)$$$ and multiply this product by $$$\frac{(\sum{S_i})!}{\Pi(S_i!)}$$$, where $$$S_i>0$$$. And, also, $$$\sum_{0\leq i \leq k}{S_i} = N - k + 1$$$ (k — 1 is the count of automatically turned on computers)

So, $$$f(k) = \sum_{valid \space set \space of\space sequences \space S}(\Pi_{0 \leq i \leq k}{g(S_i, S_i)} \cdot \frac{(\sum S_i)!}{\Pi(S_i!)})$$$,

Given $$$k$$$, $$$\Pi_{0 \leq i \leq k}{g(S_i, S_i)} = 2^{n-2k+1}$$$

$$$h(k) = \sum_{valid \space set \space of\space sequences \space S}\frac{1}{\Pi_{0 \leq i \leq k}(S_i!)}$$$ for $$$S_i > 0$$$

$$$f(k) = 2^{n-2k+1} * (n - k + 1)! * h(k)$$$

$$$h(k)$$$ is the coefficient of $$$x^{n-k+1}$$$ in $$$(\frac{x^1}{1!} + \frac{x^2}{2!} + ...)^k = (e^x — 1)^k$$$.

Using this, $$$h(k)$$$ can be calculated in $$$O(k)$$$ if we expand $$$(e^x - 1)^k$$$ in binomial terms, and similarly $$$f(k)$$$.

$$$ans(n) = \sum f(k)$$$

code

Is this a fft solution?

Doesn't use fft. Sorry if I wasn't clear with expanding $$$(e^x - 1)^k$$$. It's equal to $$$\sum_{0\leq i \leq k} {\binom{k}{i}e^{ix}(-1)^{k-i}}$$$.

And, coefficient of $$$x^r$$$ in $$$(e^x - 1)^k$$$ would be $$$\sum_{0\leq i \leq k} {\binom{k}{i}\cdot\frac{i^r}{k!}(-1)^{k-i}}$$$

I don't understand the part where you just defined h(k). Is it a known mathematical fact? How did you come up with that, also it doesn't talk about how for a given k you consider all the possible ways of dividing array in k parts, which I think by stars and bars is n-k+1Ck-1

Not only partitioning but the order in which the operations are performed is important here e.g. you can perform an operation in Si and then in Sj (i != j) but the order of operations within a segment is not important assuming the order is fixed (all the orders are considered in 2^(n-2*k+1) ).

Hope it clarifies.

The part where you talk about Sj(!=j) is why he is multiplying it by the factor \Pi_{0 \leq i \leq k}{g(S_i, S_i)} \cdot \frac{(\sum S_i)!}{\Pi(S_i!)}. According me this incorporates for a particular partition. There can be a lot of partitions which I don't know how he is accounting them

That was my bad, I corrected my comment now.

It's the sum over all such partitions of size $$$k$$$. Not just for a single arbitrary partition.

Each valid partition of size $$$k$$$ is being accounted in the coefficient of $$$x^{n-k+1}$$$ in $$$(\frac{x^1}{1!} + \frac{x^2}{2!} + ...)^k$$$. Look at how the coefficient is incremented by $$$\frac{1}{\Pi_{0 \leq i \leq k}(S_i!)}$$$ for each partition.

$$$\frac{x^{S_1}}{S_1!}$$$ from the first $$$e^x-1$$$, $$$\frac{x^{S_2}}{S_2!}$$$ from the second $$$e^x-1$$$ and so on subject to $$$\sum S_i = n - k + 1$$$

I guess the given mod on E is to stop fft solutions, though 114961513 it can be passed easily, sadly i finished some minutes after the end :(

I think the main reason for variable mod was to avoid people from solving it in $$$O(n^4)$$$ offline and storing all 400 answers.

Yeah that's probably the real reason, but it killed my $$$O(n^3 log n)$$$ fft solution, so i had to squeeze it in $$$O(n^3)$$$.

Actually,look at this:

A crazy approach

Can some explain problem E in an easier way ? Editorial is difficut to understand for me.

Can anyone please tell me the test case where my code is failing. https://codeforces.com/contest/1515/submission/114957794

Why my submission of C got pretest passed but did not enter the system test phase? submission during the contest

After the system test I submit the same code and get AC.114960806

UPD: solved

Anybody please explain E in easier way

..

x=1, although there in the array there is 6, which doesn't respect (x>=a[i], for every 1<=i<=n)

Note, though, that there are very few cases when such grave mistakes are allowed to pass through the coordinator's 'radar' and be part of a contest. And in this case, this problem got solved by thousands. It's very unlikely for all of those to solve the problem without a correct and rational basis. Before posting something like this, try prove their demonstration wrong, check yourself, and repeatbecause your input is incorrect. If will give correct input, it will give correct answer))

E could also be solved easily in O(n^2) using connected components DP (If you don't know what that is refer to this blog.

Code: https://codeforces.com/contest/1515/submission/114935154

cool,can you explain your idea .I did thought of cc dp during the contest but couldn't quite get it to work

Thanks for sharing! I reuploaded your code with English comments (used autotranslator). Posting here so others may find useful:

https://codeforces.com/contest/1515/submission/115660316

Thanks for comments in code!

They're actually in Portuguese so I don't know if they'll be of any help at all. I guess you can always throw them at a translator and see what you get.

can anyone help me i don't know why it is showing WA in problem A

## include

using namespace std; int main() { int t; cin>>t; while(t--) { int n,x; cin>>n>>x; int arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; int ans[n]; int fw=0; int indexoffw=0; int f=0; int i=0; do{

}

Problem solved

Is that an isosceles triangle?

no it's not thank you I understood the idea

Because the triangles are right isosceles triangles.

The triangles are isosceles triangles

I made the same mistake, which is assuming that all types of triangles are allowed. Didn't read the statement properly :/

Is pair stored in set in sorted form? If yes then sorted by first or second?

Yes std::set is always sorted. It compares by first, if it is the same, only then it compares by second

You can also solve A by randomly shuffling the array.

My solution to the problem I is similar with the author's one, but slightly differs, so I describe it here.

First of all, again, we sort all diamonds first by price, then by weight, now the guy will take them from left to right. After this we'll need the data structure which can do this:

Given an array $$$w_i$$$, we consider points $$$(i, w_i)$$$ on the plane and do queries "add $$$x$$$ to a single point $$$(i, w_i)$$$", "calculate the sum on $$$[0, x)\times[0, y)$$$" and "given $$$c$$$ and $$$x$$$, find the greatest $$$y$$$ so that the sum on $$$[0, x)\times[0, y)$$$ does not exceed $$$c$$$". It's already pretty standard.

Queries of type

`1`

and`2`

are straightforward. To handle query`3 c`

, let's see what happens. We can ignore all diamonds of weight $$$> c$$$, we take zero of them. For each other diamond we either grab the whole pile of it, or we can't do so. Let's find the first pile which we cannot take. It means answering the question "what is the greatest $$$i$$$ so that the sum on $$$[0, i)\times[0, c)$$$ is at most $$$c$$$". When we find this $$$i$$$, we take as much as we can from the $$$i$$$-th pile of diamonds and proceed further: if we are now at position $$$pos$$$ and we have $$$c'$$$ space remaining, we find out "what is the greatest $$$i$$$ so that the sum on $$$[0, i)\times[0, c')$$$ is at most $$$pre + c'$$$", where $$$pre$$$ is the sum on $$$[0, pos)\times[0, c')$$$. After each taking as much as we can, but not the whole pile, our space becomes $$$c\to (c\pmod{w_i})$$$, that is, reduces at least twice.Now it seems to me that the complexity of this is $$$O(q\log{C}\log^2{n})$$$ without and $$$O(q\log{C}\log{n})$$$ with fractional cascading, but my first attempt without fc (segment tree of fenwick trees) and optimizations in general got ac in 3.5s (unfortunately, I didn't manage to debug it in time).

Ah yes, my code: 114960373, feel free to hack

Did you rely on the fact that either query segments are small, or number of operations would be small? It looks like this solution has good constant because of the things above. Also I came up with the same solution, however with something like sqrt decomposition by queries. Then you could make a query of $$$w$$$ with persistent segment tree with precalc before each query block, $$$O(q \sqrt q \log q)$$$.

UPD: I guess I had something different in my mind when I came up with my solution, although it was requiring the same queries as yours. Anyway, your solution runs in $$$O(nq)$$$ on the test with weights equal to $$$1, c, 1, c-1, \ldots$$$, since you would make one query for each $$$1$$$.

Video Editorial for problem C: https://youtu.be/5S6mjYYkdOA

Can someone please explain why my solution to C works in the context of the logic given in the editorial? I have implemented a greedy solution using sorting without using heap.

https://codeforces.com/contest/1515/submission/114944125

I have sorted the array in the reverse order. Then I have greedily assigned first m blocks to m towers and then the next m blocks to m towers but in reverse ans so on. The assigned towers will be 1...m m....1 1....m and so on. If the blocks were 5 3 3 2 1 and there are 2 towers my answer would be 1 2 2 1 1. Here blocks are not being assigned to towers with the least height.

Can anyone please prove the logic behind this AC approach to the problem C, which neither uses set nor min heap?

lld : long long int

st : first

nd : second

all(x) : x.begin(),x.end()

Link to the accepted solution: 114961797I think it's a smart way of putting the "next" block in the smallest tower currently. (just like the editorial says)

You sort h (so it is now h[1]<=h[2]<=...<=h[n]). If you assign the first m heights to different towers in the end the smallest tower will be the one that got the h[1] height, that is why you give it h[m+1], but now the smallest tower is the one that got h[2] that's why you give it h[m+2] etc.

Another way to see it is to observe that when, as described in the editorial, you remove the smallest tower from the bottom of the sorted list and add a block to it, it becomes the highest and goes to the top of the list, so the list of towers is effectively rotating.

Yeah! understood your point, thanks a lot! $$$\ddot\smile$$$

You can prove it, if take subsequences of two different towers and summarize difference of pair corresponding blocks.

Bad tests in problem A. My wrong solution passed all the tests, although it should have failed on test: 5 5 1 2 2 2 2 (My solution outputs NO)

All weights are distinct.Check hereSo, you test case is incorrect.

Oh, really, I'm sorry. Thank you

Video Editorial for Problem D: https://youtu.be/e4U4_W9T7Xk

I confirm mine is the easiest solve for problem D.Feel free to check it out.

P.S. 114917152

https://codeforces.com/contest/1515/submission/114909875

why did this give tle ??i have used sqrt time only to check sqaure? plz tell........

Your time complexity became: $$$10^4*sqrt(10^9) \approx 316227766$$$

So TLE is obvious.

But editorial mentions sqrt approach and many people have ac in sqrt approach only..

They are using inbuilt sqrt function which takes constant time.

What they are really doing is finding the sqrt of that number rounded down(let x), if it was a perfect square then x*x must be equal to n.

Why don't you use inbuilt sqrt function or binary search for square root?

People have got ac with same function as I have written..

Can you link a submission which got accepted with this?

https://codeforces.com/contest/1515/submission/114909506 You can look at this one..

I think you got TLE because of using '%' operation. Simple boolean operations would pass your solution.

How does this make a diff at all??I should get ac in this one ..is there any wat to get that now?

'%' operations are a lot slower. I just changed a line and it got ac 115016226

i should have got ac in this one..that one line took it away..will use set from next time

Bro what do you want? Do you want candle march for you so that you can get justice XD

https://codeforces.com/contest/1515/submission/114909875 \ why does this give tle ??on problem b sqrt n is accepted as mentioned in editorial... i tried to again submit after contest with fast /io but again it gave tle...plz tell

You're calculating isPerfectSquare() for each n, this gives you a complexity of O(t*sqrt(n)). You can precalculate this squares before all the tests and store them on a set, this gives you a complexity of O(t*log(number of squares)).

Editorial has mentioned a sqrtn solution also.. Plz see if

People have ac with square root solution also

IN C does it make sense to include "NO" in the question or it was just there to create a confusion.

The answer is always "YES", it's explained in the editorial why that is

thankyou!!

someone please explain why i am getting wrong answer in test 3 in D here's my submission https://codeforces.com/contest/1515/submission/114967116

Video editorial for Problem D

Please tell me how you can quickly calculate (n + m!) / n! / m! % MOD (This is in problem E). In some solutions I've seen some "ifact" counting besides the usual factorial, but I can't figure out what it is.

Precompute the factorials from 1 to (n+m) in O(N+M) time and store it in an array, which you can do with a for loop. Also calculate the "modular inverse" of each of the factorials. Instead of dividing, multiply by the modular inverse.

Geeks for geeks for modular inverse: https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

My code for E where I do exactly this: 114939759

Can you please explain your approach for the problem E ?

It is exactly the same as the editorial.

Basically, you have "blocks" of computers where you manually turn them all on (none are automatically turned on). For a block of size n, there are 2^(n-1) ways to turn them on so that none of the computers are not turned on automaticallly, as detailed in the editorial.

You can think of a final answer as a series of blocks where there is exactly 1 computer turned on automatically between each block.

There are O(N^2) states in the dp and O(N) transitions. dp[n][m] = answer for the first n numbers, where m of those computers were manually turned on. At each point have another for loop to add a block to the end where you left off. I use choose to account for the fact that you don't have to do the blocks in order, or do finish one block before starting another.

Then you end up with the formula in the editorial.

Can you explain how does the "exactly 1 computer turned on automatically between each block" even work? Since 1 5 3 would simultaneously turn on 2 and 4. Am I missing something?

Nevermind I'm stupid the statement meant location-wise, not time-wise

Thank you so much!

Can anyone try to hack 114954966. I think it should have given TLE.

I don't see why it should TLE, because it has only one

`for`

loop which runs $$$\sqrt{n}$$$ times for each test case. Correct me if I am wrong.What a Nice Contest!

Phoenix and Positive Rating

Yes,hah

Question on problem H: How do you split/merge tries?

https://codeforces.com/blog/entry/49446

can anyone kindly explain why greedily adding the 2 smallest values in the array not work in c.

like if we have [2,4,7,9,10] and if we want 3 block just add the smallest 2 and replace, by this we get [6,7,9,10] and then again do the same thing, thus getting [13,9,10] the max difference is 4 which is okay, if we were to do any further operation we would have done that to 9,10

but this gives WA, can anyone suggest a counter example

x = 1

a = [1, 1, 1, 1, 1, 1]

after the first four operations, you'll have [2, 4], and the difference is > 1

Thanks man

In the proof of problem $$$B$$$, in general, the triangle shorter side length can be irrational, hence the square area can be irrational as well. We can say that if the shorter side length is $$$x$$$, the square area will be: $$$(a+\sqrt{2}b)^2x^2$$$, if we divided this by the area of one triangle $$$\dfrac{1}{2}x^2$$$ to get the number of triangles constituting the square we will get $$$2(a+\sqrt{2}b)^2$$$, which is irrational if $$$a$$$ and $$$b$$$ are both non-zeros, and triangles count can not be so.

Problem 1515C: Can you please check out this solution and see if it is the correct one. The logic sort all the heights in decreasing order and then assign the heights to the towers in a spiral manner, i.e. first k blocks are assigned in increasing order of tower numbers and the next k in decreasing order and then the next k in increasing and so on.

I am attaching a link to my solution, if possible can you please see it.

114893372

This solution uses O(NlogN) sorting and then assigning the heights in O(N) rather than the one given in the tutorial, which will be slower than mine.

If the solution is wrong can you please provide a test case that will fail my solution.

Yes, your method is correct.

We can add imaginary blocks of height 0 at the end of the sequence so that the total number of blocks is a multiple of $$$m$$$, such that in each pass, every tower is assigned a block. After sorting, consider the difference between the maximum and minimum height added in each pass of the towers. The sum of these differences is less than or equal to $$$x$$$.

Therefore, the maximum difference of heights of the constructed towers is less than or equal to the sum of differences in each pass, which is less than or equal to $$$x$$$.

Thanks, actually I did the math roughly during the contest and got a little nervous about it as I wasn't able to hardproof the solution. Thanks for the contribution.

I was wondering why rating changes for global rounds are very fast whereas educational rounds and div 3 rounds take a lot of time?

It is because of the 12 hour open hacking phase after educational and div 3 rounds. The successful hack tests are added to the main system test cases and then all the solutions are re-judged. So it takes 12 hours to completely judge the solutions and update the ranks

Nice Round!

A proof for the solution of problem $$$D$$$:

Assuming $$$l\geq r$$$, we only need to consider recoloring and moving $$$\dfrac{l-r}{2}$$$ socks from $$$l$$$ to $$$r$$$. Moving any $$$sock_i$$$ from $$$r$$$ to $$$l$$$ should be accompanied with moving $$$sock_j$$$ from $$$l$$$ to $$$r$$$, which is equivalent to recoloring $$$sock_i$$$ to $$$c_j$$$ and $$$sock_j$$$ to $$$c_i$$$, so we do not need to consider this type of operations.

For the step of moving $$$\dfrac{l-r}{2}$$$ socks from $$$l$$$ to $$$r$$$, we need to so in a way that minimizes the recolorings. So, we need to do it in way that maximizes $$$\sum_{i=1}^n min(l_{count_i}, r_{count_i})$$$ for all colors $$$i$$$. Which is equivalent to first matching the pairs that are ready for matching between $$$l$$$ and $$$r$$$, then moving and matching pairs with same colors in $$$l$$$, as mentioned in the editorial.

Problem D :My code is giving runtime error on tc 3 . Someone please help — > https://ideone.com/veYC42Please HelpVery Nice Contest ! Had interesting problems rather than some wierd and boring problems ! Thanks for the round! Hope to see this type of round even more !

Thanks for the nice problems

Can anyone please help in figuring out what is wrong with this solution for problem c: https://codeforces.com/contest/1515/submission/114996358 I have tried taking the two minimum heights and merge them until the remaining elements are exactly m.

can C be done using priority queue?

Yes, I have done using priority Queue. Link to my Priority Queue based Submission

thanks a lot for the approach

Nice Contest

In the first approach for problem F, when two disjoint sets are merged, then the list of edges of the two sets are also merged. It seems that this merging operation is very costly and would lead to TLE, but in practice it didn't. Is there an explanation for why this is the case?

For problem E, how is the answer for the case $$$n = 4$$$ given as $$$20$$$. I can come up with only $$$16$$$

1.

`xx-x`

($$$2!\times 2^1 \times 2^0 = 4$$$ ways)2.

`x-xx`

($$$2! \times 2^0 \times 2^1 = 4$$$ ways)3.

`xxxx`

($$$2^3 = 8$$$ ways)Here

`x`

denotes the positions turned on manually and`-`

denotes those that appear automatically.For the first two conditions, it is C(3, 2), not 2!.

For the first 2 cases, it should be 6 ways. In the first case:

`xx-x`

it is 2^1 for`xx`

2^0 for`x`

and since we can rearrange the steps of left and right side, i.e. 3C2.(1 2 4) all combination = 3! = 6 ways

(1 3 4) -------------------- = 6 ways

(1 2 3 4) = 8 ways

Total : 20 ways

how did you calculate for 1 2 3 4 case ?

You can understand like this.

No of ways to turn on all computers(1,2,3,4) are

by turning on 1 computer = 0 ways

by turning on 2 computer = 0 ways

by turning on 3 computer = 12 ways (as explained in the above comment)

by turning on 4 computer = 8 ways

total : 20 ways.

So, finally we have the following formula : Let total number of

`x`

is $$$X$$$ and length of segments are $$$x_1$$$, $$$x_2$$$ upto $$$x_k$$$, where $$$k$$$ is the number of segments. Then the number of arrangements are $$$\frac{X!}{x_1! x_2!\dots x_k!}2^{x_1-1}2^{x_2-1}\dots2^{x_k-1}$$$.Yes, $$$X!$$$ in the numerator, right ?

yup!

For problem E, I have an O(N^2) solution which is extremely, extremely easy to write. It uses a technique similar to one used in CEOI 2016 Kangaroo.

Denote

`dp[i][j]`

as the number of ways you can have`i`

places "filled in", with j separate contiguous segments. These "segments" must have a space of at least two between them (or else the one space in between would be automatically filled in).Then, you can run an O(N^2) dp with O(1) transition. For example, each time you can merge two segments, add to one segment, or create a new segment. There are just 5 cases to handle.

Code: 115003639

Nice!

Nice solution. Bud i can't understand the transition

dp[i+2][j] = (dp[i+2][j]+dp[i][j]*(j<<1))%mod;

We have j separate contiguous segments with i turn on . How we can jump j segments and i+2 turn on and why multiplier j<<1?

what this means is, you can increase the length of a segment by two.

Let's say I have something like

In one move, I can turn it into

by filling in the leftmost

`X`

.This way, there are j*2 ways to do this, by picking either of the j segments to increase in length, and for each segment choosing left or right. (j<<1 just means j*2, sorry this is not very intuitive but it is a habit)

oh yeah, i understood, thanks

In Problem C, mistakenly, I was solving a different problem. How to solve this?

We have to put those n blocks in m tower such that the sum of blocks in any tower does not exceed X.

I think it is NP-Hard.

How to formally say it though ? Can you explain ?

https://en.wikipedia.org/wiki/Bin_packing_problem

Isn't

`Bin Packing`

different from this question ?No. It is exactly what starboy_jb described.

Ohh my bad, I read it wrong. How about this then :

Given n items

`A[n]`

with no restriction on`1<= A[i] < 1e+9`

, is there a way to partition these items into K bins, such that the`difference between the max and min bin values <= x`

.Is this polynomial-time solvable ?

I am unsure. However it feels like as if there is none...

You'll have to ask someone more skilled than me to prove it is NP-Hard or come up with a polynomial time solution.

No, consider $$$K=2, x=0$$$.

Ahhh yes of course

What was the revelation ? As far as I know this can be solved with Knapsack Dp. But can we say for every K and x it is possible ?

No, the knapsack dp works in $$$O(n^2*max(a_i))$$$, which clearly doesn't work for $$$a_i \leq 10^9$$$; $$$max(a_i)$$$ isn't polynomial in input size.

I think for m = 2, this becomes something of the kind of partition problem that we can solve by

`DP`

. Not sure how to do for m > 2.Problem Statement : Given N numbers, partition these into 2 sets(S1, S2) such that the difference between S1 and S2 is minimised. If this difference <= x, then it is possible else not possible,

https://codeforces.com/contest/1515/submission/114949655 can anyone help me to figure out why is this logic wrong?

Uh,If you have duplicate numbers in problem A,how to solve it?

I have an idea,and this is the link that I accepted.

I don't know if it's correct. If anybody knows,please tell me,thanks a lot.

sorry,my English is poor :(

explain C again..its code not able to understand

Great contest! Missed first 2 ques by some silly mistakes and got demotivated to try more :(

Thanks for the cool problems.

PROBLEM Asolution goes wrong for 3 6 6 6 6`All weights are distinct.`

My solution for C is almost same logic mentioned above. Fist I take all the heights and push them into a priority queue .Then I pop the two shortest height from the queue and push their sum back to the queue until the size of queue is not equal to m. I also maintain the indexes.

But this idea is wrong is some test case. This idea gives the result of two towers that their height's difference is greater than x in some test case. Why it is happening? Can anyone help?

My solution: https://codeforces.com/contest/1515/submission/114950963

Consider this case :

1

6 2 2

2 2 2 2 2 2

Got it. Thanks.

Consider 6 blocks of size x, and number of resulting towers=2.

So you will make, in that order, towers of size 2x, 2x, 2x, 4x.

Then diff is 2x, which is bigger than x.

Thanks.

Can someone tell the solution to problem E in detail?

I think you want to understand this transition

dp[len+k+1][cnt+k] += dp[len][cnt] ⋅ (ncr(cnt+k,k)) ⋅ power(2,k-1)

dp[len+k+1][cnt+k] = number of ways to on (len+1)th computer automatiacally and from len+2 to len+k+1(total k computers) on manually

dp[len][cnt] = number of ways from len = 1 to len = len and we manually on cnt computers now we have dp[len][cnt] and we know the number of ways to on all k computers manually (from len+2 to len+k+1) is power(2,k-1) and to select these k computers we multiply it by ncr(cnt+k,k)

Thanks

IN Q Phoenix and Gold ...if we put test case 1... 8 56.... 34 22 22 34 34 34 34 34 Answer is wrong as it gives ... YES..... 34 22 22 34 34 34 34 34 hece weight will explode.

Anyone has a proof for E? Wouldn't the case 1 5 3 (manual turning on) not be part of the count for the solutions? since 1 5 3 would lead to the simultaneous automatic turning on of 2 and 4. While we're building the solution thinking about several manual computers, one automatic computer, several manual computers, and so on.

Nevermind I'm starting to think I have some sort of idea why it works even if sometimes it can be 2 at once. Suppose 2 6 4. Then we can take 2 6 4 as activated manually and 5 activated automatically. We then don't really care if 3 is activated automatically or manually. Why? The elements smaller than 3 (1) are allowed to be anywhere after 3 in the next sequence. The elements bigger than 3 will be placed just as in an activated manually sequence. So it doesn't really matter. Why can we get away with the case for 1 2 3 4 5 as similar to other cases such as 2 3 4 5 6 or 1 4 6 7 8? The 1 2 3 4 5 can be considered the order if we were to sort the elements. And the principle remains the same.

Can anyone briefly explain why there will always a solution exist in

Problem C?? Why will we never get a max difference greater than`x`

if we always merge with the smallest height deck?"A single block never exceeds the height of x".

`"A single block never exceeds the height of x".`

that is true but how does it imply that themax differencebetween two decks will also not exceed x.Why this soln is

notworking?? Collect all the N towers in the set, merge the two smallest heights till the size of set is greater than m.If a single block cannot exceed the height of x, the only way the difference between two blocks can be greater than x is if you add a block to a taller tower. If we always add a block to the shortest tower, the height of that tower increases by only the height of the added block, which is less than x.

Sorry I do not understand your approach.

How would one approach C if a single block could exceed the height of x? Would the same greedy strategy work? I am having a hard time with the proofs.

Nope it would not and it's NP Hard. See the above comments from here : https://codeforces.com/blog/entry/90236?#comment-787072

Can anyone please tell me what's wrong in my code for problem D? https://codeforces.com/contest/1515/submission/115072254

Nevermind, I found the mistake. This is my AC: https://codeforces.com/contest/1515/submission/115072573

Can someone please explain D, editorial is too messy and so many variable is used in them.I can't able to figure it out as a whole. Thanks in advance

Hi, can anyone please help me in understanding where am I going wrong in my code for problem F. I am getting WA on test 16 saying

wrong output format Unexpected end of file — int32 expected.Here is the link to MY CODE

I know it may be too late but in 1515C time complexity for each test case can be precise to $$$O(n \log{m})$$$. That's because a set or a heap are built from $$$m$$$ pairs.

I understood the first part of the editorial for problem E but I am not able to understand how the segments are merged using binomial coefficients, can somebody explain it to me.

E can be solved in $$$O(n^2)$$$ time.

Let $$$f_{n,m}$$$ be the ways to complete $$$m$$$ paragraphs, where these paragraphs contain $$$n$$$ computers totally.

The answer is $$$f_{n,1}$$$.

(1) merge two adjacent paragraphs:

(2) lengthen a paragraph by one or two:

(3) add a paragraph:

Can you plz elaborate more, I didn't even get what is paragraph.

a series of consecutive opened computers

Could someone tell me why this solution for F would TLE? I tjust looks like nlogn with a big constant factor. Shouldn't that still easily pass for n=3e5? Submission

The complexity is $$$O(n^2 log(n))$$$ after selecting each edge it takes $$$O(nlog(n))$$$ time to update the graph, consider a tree where all vertices are connected to the 1st vertex.

Yea thanks, I just realised this

`Thus, one approach is to repeatedly find the city with the most asphalt and merge it with any of its neighbors`

What if we pick the city with the current maximum asphalt (and it is $$$< x$$$) but the neighbors don't have enough to make the sum $$$\geq x$$$, i.e. all my neighbors have very little asphalt.

UPD : Misread the editorial. Understood now.

I've often requested for more data structure and algorithmic problems, so now that we just had two great problems in I and H, I want to give a big thank you to the organisers of this round :)