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 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...
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.net/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
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
Thanks man. I was unable to understand the solution until I read your comment.
see this 114972329
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.net/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 E has $$$O(n^2)$$$ solution. The formula:
$$$l$$$ denotes amount computers turn on manually and $$$z$$$ — turn on automatically.
submission: https://codeforces.net/contest/1515/submission/114961141
Is your formula inclusion, exclusion. Please explain
more detailed solution
Can anyone explain Problem B in detail? please!!
Youve to form a square with given pieces if it's possible then print yes otherwise no
Link to Explanation
Even after completion of system testing, it is showing pretest passed in B and a negative in standings. What should I do? https://codeforces.net/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.net/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 repeat
because 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.net/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.net/contest/1515/submission/115660316
In this case, what constitues the connected component?
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.
Problem solved
Is that an isosceles triangle?
Because the triangles are right isosceles triangles.
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
and2
are straightforward. To handle query3 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.net/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: 114961797
I 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]\leq h[2]\leq \dots \leq 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 here
So, 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.net/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.net/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.net/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)).
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
someone please explain why i am getting wrong answer in test 3 in D here's my submission https://codeforces.net/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.net/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.
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.
Can anyone please help in figuring out what is wrong with this solution for problem c: https://codeforces.net/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
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 forxx
2^0 forx
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 havei
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 on1<= A[i] < 1e+9
, is there a way to partition these items into K bins, such that thedifference 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.
https://codeforces.net/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
Thanks for the cool problems.
PROBLEM A solution 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.net/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)
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.
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 :)
How would we have solved 1515C, if the constraint hi <= x was not given... I mean if hi > x was possible.
Sorry for commenting on this old blog, but for problem D — Phoenix and Socks, the editorialists solution gives WA for the following test case —
The actual answer is 1 ( you can change the colour of the second left sock to 4). But the editorial's solution gives 2 as the answer. Am I missing something?
That input is invalid because the colors of the socks may not exceed $$$n=4$$$.
oh ok, I didn't notice that constraint when reading the problem, thanks a lot.
The solution for F can also be proved in another (slightly retarded) manner. If we just prove that , if at any moment of time, some road is repairable, repairing at that moment of time is never suboptimal, then we arrive to the first solution described in the editorial. (we can prove it by contradiction and some case work on the values of the vertices of considered repairable road)
Can someone Give a counter test case for this solution of Problem-D