Thanks for joining us today! Here is the editorial for today's problems:
1478A - Nezzar and Colorful Balls
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(int)(n);++i)
#define rep1(i,n) for (int i=1;i<=(int)(n);++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int maxn=200007;
int t,n;
int cnt[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>t;
while (t--){
cin>>n;
rep1(i,n) cnt[i]=0;
rep1(i,n){
int u;
cin>>u;
cnt[u]++;
}
int mx=0;
rep1(i,n) mx=max(mx,cnt[i]);
cout<<mx<<"\n";
}
return 0;
}
1478B - Nezzar and Lucky Number
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int maxn=207;
int t,d,q;
bool dp[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>t;
while (t--){
memset(dp,0,sizeof(dp));
dp[0]=1;
cin>>q>>d;
if (!d) d+=10;
int mx=d*10;
for (int i=0;10*i+d<=mx;++i){
for (int j=0;10*i+d+j<=mx;++j){
dp[10*i+d+j]|=dp[j];
}
}
while (q--){
int u;
cin>>u;
if (u>=mx||dp[u]) cout<<"YES\n";
else cout<<"NO\n";
}
}
return 0;
}
1478C - Nezzar and Symmetric Array
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200007;
int t;
int n,a[maxn],b[maxn],d[maxn];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>t;
while (t--){
cin>>n;
for (int i=0;i<2*n;++i) cin>>a[i];
sort(a,a+2*n,greater<int>());
for (int i=0;i<n;++i){
if (a[i*2]!=a[i*2+1]){
cout<<"NO\n";
goto cont;
}
b[i]=a[i*2];
}
for (int i=1;i<n;++i){
if (b[i-1]==b[i]||(b[i-1]-b[i])%(2*(n-i))){
cout<<"NO\n";
goto cont;
}
d[i]=(b[i-1]-b[i])/2/(n-i);
}
for (int i=1;i<n;++i){
b[n-1]-=2*i*d[i];
}
if (b[n-1]<=0||b[n-1]%(2*n)) cout<<"NO\n";
else cout<<"YES\n";
cont:;
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200007;
int t;
int n,k;
int x[maxn];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>t;
while (t--){
cin>>n>>k;
for (int i=0;i<n;++i) cin>>x[i];
sort(x,x+n);
int g=0;
for (int i=1;i<n;++i){
g=__gcd(g,x[i]-x[0]);
}
if ((k-x[0])%g) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
1477B - Nezzar and Binary String
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(int)(n);++i)
#define rep1(i,n) for (int i=1;i<=(int)(n);++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int maxn=200007;
set<int> seg; // segment: [seg[i],seg[i+1])
int n,q,t,prv;
int l[maxn],r[maxn];
bool val[maxn];
string s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>t;
while (t--){
cin>>n>>q;
cin>>s;
rep(i,q) cin>>l[i]>>r[i], l[i]--;
reverse(l,l+q), reverse(r,r+q);
seg.clear();
rep(i,n) seg.insert(i), val[i]=s[i]-'0';
seg.insert(n);
auto add=[&](int u){
if (seg.find(u)==seg.end()){
auto ret=*prev(seg.upper_bound(u));
val[u]=val[ret];
seg.insert(u);
}
};
rep(i,q){
add(l[i]), add(r[i]);
vi remv;
remv.clear();
int sum[2];
memset(sum,0,sizeof(sum));
auto iter=seg.find(l[i]);
while (1){
if (*iter==r[i]) break;
int prev=*iter;
iter=next(iter);
if (*iter<r[i]) remv.pb(*iter);
sum[val[prev]]+=*iter-prev;
}
if (sum[0]==sum[1]){
cout<<"-\n";
goto cont;
}
if (sum[0]<sum[1]) val[l[i]]=1;
else val[l[i]]=0;
for (auto c:remv) seg.erase(c);
}
prv=0;
for (auto c:seg){
if (!c) continue;
for (int i=prv;i<c;++i) cout<<val[prv];
prv=c;
}
cout<<"\n";
cont:;
}
}
1477C - Nezzar and Nice Beatmap
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int maxn=6007;
int n;
int x[maxn],y[maxn];
vector<int> perm;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n;
for (int i=0;i<n;++i) cin>>x[i]>>y[i];
for (int i=0;i<n;++i){
perm.push_back(i);
for (int j=i;j>1;--j){
if (1ll*(x[perm[j]]-x[perm[j-1]])*(x[perm[j-1]]-x[perm[j-2]])+1ll*(y[perm[j]]-y[perm[j-1]])*(y[perm[j-1]]-y[perm[j-2]])>=0){
swap(perm[j],perm[j-1]);
}
else{
break;
}
}
}
for (auto c:perm) cout<<c+1<<" ";
}
1477D - Nezzar and Hidden Permutations
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int maxn=500007;
struct info{
int idx,val;
friend bool operator<(info u,info v){
return u.val==v.val?u.idx<v.idx:u.val<v.val;
}
};
struct stars{
int rt;
vector<int> leaves;
};
set<int> rv; // remained vertices
set<int> g[maxn]; // original graph
set<int> t[maxn]; // dfs tree
set<info> d;
int deg[maxn];
int n,m;
int perm1[maxn],perm2[maxn];
vector<stars> res;
void dfs(int u){
rv.erase(u);
int crt=0;
while (1){
auto iter=rv.upper_bound(crt);
if (iter==rv.end()) break;
int v=*iter;
crt=v;
if (g[u].find(v)!=g[u].end()) continue;
t[u].insert(v), t[v].insert(u);
dfs(v);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int tc;
cin>>tc;
while (tc--){
cin>>n>>m;
for (int i=1;i<=n;++i) g[i].clear(), t[i].clear();
rv.clear(), res.clear(), d.clear();
for (int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
g[u].insert(v), g[v].insert(u);
}
for (int i=1;i<=n;++i) rv.insert(i);
while (rv.size()>0){
int u=*(rv.begin());
dfs(u);
}
int rem=n;
for (int i=1;i<=n;++i){
deg[i]=t[i].size();
if (deg[i]){
d.insert((info){i,deg[i]});
}
else{
perm1[i]=perm2[i]=rem;
rem--;
}
}
while (d.size()){
int idx=(*(d.begin())).idx;
int f=*(t[idx].begin());
vector<int> leaves;
leaves.clear();
d.erase((info){f,deg[f]});
for (auto c:t[f]){
d.erase((info){c,deg[c]});
if (deg[c]==1) leaves.push_back(c);
else deg[c]--, d.insert((info){c,deg[c]}), t[c].erase(f);
}
res.push_back((stars){f,leaves});
}
int l=0,r=0;
for (auto c:res){
perm1[c.rt]=++l;
for (auto ls:c.leaves){
perm1[ls]=++l;
perm2[ls]=++r;
}
perm2[c.rt]=++r;
}
for (int i=1;i<=n;++i) cout<<perm1[i]<<" ";
cout<<"\n";
for (int i=1;i<=n;++i) cout<<perm2[i]<<" ";
cout<<"\n";
}
}
1477E - Nezzar and Tournaments
Tutorial
Tutorial is loading...
Solution
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(int)(n);++i)
#define rep1(i,n) for (int i=1;i<=(int)(n);++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
}
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
const int maxn=500007;
const int maxm=1000007;
int n,m,k,q,t;
ll sum;
int a[maxn],b[maxn];
struct S{
int cnt;
ll sum;
};
S e(){
return {0,0};
}
S op(S l,S r){
return {l.cnt+r.cnt,l.sum+r.sum};
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
segtree<S,op,e> seg_a(maxm),seg_b(maxm);
auto fa=[&](int x){
if (x>m||x<=0) cerr<<x<<endl;
assert(x<=m&&x>0);
return seg_a.max_right(0,[&](S l){return l.cnt<x;});
};
auto fb=[&](int x){
assert(x<=n&&x>0);
return seg_b.max_right(0,[&](S l){return l.cnt<x;});
};
auto solve=[&](int start,int coef){
// cerr<<"start coef:"<<start<<" "<<coef<<endl;
int mn=min(fa(1),fb(1));
if (start<=k+mn) return 1ll*(n-m)*start+sum;
auto ret=seg_b.prod(0,start-k);
// cerr<<"ret:"<<ret.cnt<<" "<<ret.sum<<endl;
return 1ll*coef*(start-k-mn)+1ll*(n-m)*start+sum+ret.sum-1ll*ret.cnt*(start-k);
};
cin>>m>>n>>q;
rep1(i,m) {cin>>a[i],sum+=a[i]; auto ret=seg_a.get(a[i]); ret.cnt++, ret.sum+=a[i], seg_a.set(a[i],ret);}
rep1(i,n) {cin>>b[i],sum-=b[i]; auto ret=seg_b.get(b[i]); ret.cnt++, ret.sum+=b[i], seg_b.set(b[i],ret);}
sum+=1ll*(m-n)*k;
auto res=[&](){
ll ans=-1e15;
ans=max(ans,solve(fb(1),m));
ans=max(ans,solve(fb(n),m));
ans=max(ans,solve(fa(1),m-1));
ans=max(ans,solve(fa(m),m-1));
int threshold=n>1?fb(n-1):0;
if (k+threshold<=1e6){
int pos=max(seg_a.prod(0,k+threshold).cnt,1);
ans=max(ans,solve(fa(pos),m-1));
int nxt_pos=seg_a.max_right(0,[&](S l){return l.cnt<=pos;});
if (nxt_pos<maxm) ans=max(ans,solve(nxt_pos,m-1));
}
cout<<ans<<"\n";
};
while (q--){
int op,idx,x;
cin>>op;
if (op==1){
cin>>idx>>x;
auto ret=seg_a.get(a[idx]);
ret.cnt--, ret.sum-=a[idx];
seg_a.set(a[idx],ret);
sum-=a[idx];
sum+=x;
a[idx]=x;
ret=seg_a.get(x);
ret.cnt++, ret.sum+=x;
seg_a.set(x,ret);
}
if (op==2){
cin>>idx>>x;
auto ret=seg_b.get(b[idx]);
ret.cnt--, ret.sum-=b[idx];
seg_b.set(b[idx],ret);
sum+=b[idx];
sum-=x;
b[idx]=x;
ret=seg_b.get(x);
ret.cnt++, ret.sum+=x;
seg_b.set(x,ret);
}
if (op==3){
cin>>k;
sum+=(m-n)*k;
res();
sum-=(m-n)*k;
}
}
return 0;
}
1477F - Nezzar and Chocolate Bars
Tutorial
Tutorial is loading...
Solution
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i,n) for (int i=0;i<(int)(n);++i)
#define rep1(i,n) for (int i=1;i<=(int)(n);++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
const ll mod = (119 << 23) + 1, root = 62; // = 998244353
// For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21
// and 483 << 21 (same root). The last two are > 10^9.
ll modpow(ll b, ll e) {
ll ans = 1;
for (; e; b = b * b % mod, e /= 2)
if (e & 1) ans = ans * b % mod;
return ans;
}
typedef vector<ll> vl;
void ntt(vl &a) {
int n = sz(a), L = 31 - __builtin_clz(n);
static vl rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, modpow(root, mod >> s)};
for(int i=k;i<2*k;++i) rt[i] = rt[i / 2] * z[i & 1] % mod;
}
vi rev(n);
for(int i = 0; i < n; ++i) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
for(int i = 0; i < n; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) for(int j = 0; j < k; ++j) {
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai - z + (z > ai ? mod : 0);
ai += (ai + z >= mod ? z - mod : z);
}
}
vl conv(const vl &a, const vl &b) {
if (a.empty() || b.empty()) return {};
int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B;
int inv = modpow(n, mod - 2);
vl L(a), R(b), out(n);
L.resize(n), R.resize(n);
ntt(L), ntt(R);
for (int i = 0; i < n; ++i) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod;
ntt(out);
return {out.begin(), out.begin() + s};
}
const int maxn=1007;
int n,k;
int l[maxn];
struct polynomial{
int n,m;
vector<vi> poly;
polynomial(vector<vi> &po):poly(po){
n = sz(poly) - 1, m = sz(poly[0]) - 1;
}
vi rsz(int nn,int mm){
assert(nn>n&&mm>m);
vi ret;
ret.resize(nn*mm+1,0);
for (int i=0;i<=n;++i){
for (int j=0;j<=m;++j){
ret[i*mm+j]=poly[i][j];
assert(poly[i][j]<mod&&poly[i][j]>=0);
}
}
return ret;
}
friend polynomial operator*(polynomial l,polynomial r){
vector<vi> po;
po.clear();
po.resize(l.n+r.n+1,vi(l.m+r.m+1,0));
auto lpo=l.rsz(l.n+1,l.m+r.m+1),rpo=r.rsz(r.n+1,l.m+r.m+1),res=conv(lpo,rpo);
// for (auto c:res) cout<<c<<" ";
// cout<<endl;
// cout<<sz(lpo)<<" "<<sz(rpo)<<" "<<sz(res)<<endl;
for (int i=0;i<=l.n+r.n;++i){
for (int j=0;j<=l.m+r.m;++j){
po[i][j]=res[i*(l.m+r.m+1)+j];
}
}
// cout<<"hi"<<endl;
return po;
}
};
vector<polynomial> poly;
int f[5007];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>k;
f[0]=1;
rep1(i,5000) f[i]=f[i-1]*i%mod;
int L=0;
rep(i,n) cin>>l[i], L+=l[i];
rep(i,n){
vi res0,res1;
res0.clear(), res1.clear();
res0.pb(1), res1.pb(0);
int sgn=1;
rep1(j,l[i]/k){
int tmp0,tmp1;
sgn=-sgn;
if (l[i]==k*j) {
tmp0=tmp1=0;
}
else{
tmp0=(modpow((l[i]-k*j)*modpow(L,mod-2)%mod,j)%mod)*modpow(f[j],mod-2)%mod, tmp1=(modpow((l[i]-k*j)*modpow(L,mod-2)%mod,j-1)%mod)*modpow(f[j-1],mod-2)%mod;
if (sgn<0) tmp0=(tmp0?mod-tmp0:tmp0), tmp1=(tmp1?mod-tmp1:tmp1);
}
// cerr<<i<<" "<<j<<":"<<tmp0<<" "<<tmp1<<endl;
res0.pb(tmp0), res1.pb(tmp1);
}
vector<vi> p({res0,res1});
polynomial po(p);
poly.pb(po);
}
for (int k=1;k<=n;k<<=1){
for (int i=k;i<n;i+=2*k){
poly[i-k]=poly[i]*poly[i-k];
}
}
int ans=0;
// x^{j-i}exp((1-k*j/L)) -> (j-i)!/((k*j/L)^{j-i+1}) = (j-i)!L^{j-i+1}/(k*j)^{j-i+1}
rep(i,poly[0].n+1){
rep(j,poly[0].m+1){
if (i>j) {assert(poly[0].poly[i][j]==0); continue;}
if (j==0) {assert(poly[0].poly[i][j]==1); continue;}
if (k*j==L) {assert(poly[0].poly[i][j]==0); continue;}
int num=f[j-i]*modpow(L,j-i+1)%mod,den=modpow(k*j,j-i+1)%mod;
// cerr<<i<<","<<j<<":"<<poly[0].poly[i][j]<<" "<<num<<" "<<den<<endl;
ans=(ans+(num*modpow(den,mod-2)%mod)*poly[0].poly[i][j]%mod)%mod;
}
}
if (ans>0) cout<<mod-ans<<endl;
else cout<<0<<endl;
return 0;
}
Please add comments in code solutions of editorials to make it more readable
The intent of the code is obvious to its writers and other experienced participates. No one will know which lines you don’t understand.
Understandable, but it can be quite tricky to understand for beginners, and I would think that the purpose of the editorial would be to help competitors, beginner or advanced. CP code is notorious for being unreadable.
Then it would make more sense to make editorial code readable rather than to add comments to unreadable code, but I don't see any readability issues in the code of this particular editorial.
Fair enough.
I thought that the problems were really nice. Kudos to all the authors! :)
div1C Furthest Points
Pick an arbitrary point, and in each iteration, select the furthest point from previously chosen point among all available points. Indeed, we can prove the correctness by contradiction.
what the f**k How did I miss that
WHat the fuck!
i thought this during contest and thought it is way too simple to be a solution to div1C
I should commit suicide
Extremely nice contest! Thank u for your work!
Should it be "let $$$g_0 = \gcd(x_2,x_3,\dots,x_{n-1})$$$"?
Thanks! We will fix it later.
How can we write $$$g$$$ using $$$g_0$$$ and $$$x_n$$$. And another question is even if we are able to write $$$g$$$, how can we generate all multiples of $$$g$$$ ?
(0,g) — > (0,g,2g)
2*(2g)-g = 3g -> (0,g,2g,3g) 2*(2g)-0 = 4g -> (0,g,2g,3g,4g) ....
But with (0,g0,xn) I can't generate g = xn-g0 for example where s=1, t=1
It's said that $$$g=sg_0+tx_n$$$, and there are multiple pairs $$$(s,t)$$$. An even $$$s$$$ is absolutely existed, so let's regard $$$s$$$ as an even one. With $$$0$$$, $$$x_n$$$, and $$$g_0$$$,it's easy to get $$$\frac{s}{2}g_0$$$ and $$$tx_n$$$, then $$$g=2\times \frac{s}{2}g_0+tx_n$$$.
Can you please explain why there always exits s that is even? By the way why we can substract x1 for every xi and does not Affect the answer?
I'm so sorry! I made a big mistake in my previous replication, $$$s$$$ can be odd! Fortunately, I've already got the true proof. Firstly, it's easily to get $$$pg_0$$$ and $$$qx_n$$$, $$$p,q\in\mathbb Z$$$. If $$$s$$$ is even, we can get $$$g$$$ with $$$\frac{s}{2}g_0$$$ and $$$tx_n$$$. If $$$t$$$ is even, we can get $$$g$$$ with $$$-\frac{t}{2}x_n$$$ and $$$-sg_0$$$. If $$$s$$$ and $$$t$$$ are both odd, there must exist $$$s'=s-\frac{x_n}{g}$$$ and $$$t'=t+\frac{g_0}{g}$$$ also satisfy $$$g_0s'-x_nt'=g$$$ by Bézout's Theorem; $$$s'$$$ and $$$t'$$$ mustn't be both odd since $$$\frac{x_n}{g}$$$ and $$$\frac{g_0}{g}$$$ are coprime and they mustn't be both even; the problem to construct $$$g_0s'-x_nt'$$$ is mentioned before.
if $$$\frac{x_n}{g}$$$ and $$$\frac{g_0}{g}$$$ are coprime then how can you say that $$$s'$$$ and $$$t'$$$ will be of different parity. For example, if $$$\frac{x_n}{g} = 3$$$ and $$$\frac{g_0}{g} = 5$$$ then $$$s'$$$ and $$$t'$$$ will be both $$$even$$$ provided $$$s$$$ and $$$t$$$ were both $$$odd$$$. But thanks for your explanation, as at least one of them must be $$$even$$$.
basically if we have: g = gcd(a,b), with some s0*a — t0*b = g by bezouts theorem, we can get any of the infinite solutions of (s,t) to bezouts theorem s*a — t*b = g with the following: s = s0 + k*(b/g), t = t0 + k*(a/g) because a corresponds with the s coefficient, what we're adding to the "s*a" term is: a * k * (b/g) and to the "t*b" term we're adding: b * k * (a/g) notice that the two terms we're adding are equivalent (by construction, i assume): k * a * (b/g) = k * b * (a/g) k * ab/g = k * ab/g if we take two numbers with difference g (the base equation s0*a — t0*b = g) adding the same thing to each term will preserve the difference g. now back to the original problem: our goal is just to get one of the coefficients to be even: if s0 is even or t0 is even, we're done, else they are both odd: we now want to see if there always exists a new pair (s,t) from one of the infinite bezouts theorem solutions s.t. either s or t is even (so we can construct our formula with the 2x — y operation) s = s0 + k * (b/g) since s0 is odd, we need k * (b/g) to be odd because odd + odd = even. only odd * odd = odd, so we need k to be odd and (b/g) to be odd. If (b/g) is odd just choose some odd k and we have an even s, otherwise try t: t = t0 + k * (a/g) following same reasoning, we need (a/g) odd. Notice that we cannot have both (b/g) and (a/g) to be even, otherwise g != gcd(a, b) because 2*g thus divides both b and a (since b/g and a/g are even). Therefore atleast one of (a/g) or (b/g) must be odd. so if (b/g) is even, then (a/g) must be odd and we can just choose k to be odd and get t0 (an odd) + k(odd) * (a/g)(odd) = t(even) -- (odd + odd = even) therefore, it is always possible to construct an equation s*a — t*b = g s.t. one of s or t is even. back to our problem: we have s*g0 — t*xn = g. we have g0 and xn on the board, and know that there exists a solution (s,t) to the above equation with one coefficient being even. WLOG suppose s is even, we just need to get s/2*(g0) on the board (by using x1 = 0 and doing 2*g0 — 0) we can get any multiple of g0 on the board including s/2*g0. by same logic we can get t*xn on the board. then, we just pick x = s/2*g0 and y = t*xn, then 2x — y is just 2*(s/2*g0) — t*xn = s*g0 — t*xn = g, therefore we have g on the board. and we know that if we can get a number x on the board, we can get any c*x on the board, where c in Z. therefore, anything divisible by g can be written on the board, and k must be divisible by g, therefore we return yes if and only if k is divisible by g.
How can we write 0 on board?
Dont think of it as zero. Note {a+nb,a+(n+1)b} can be used to make a+(n+2)b as follows
Now, if we have g divides k and
thus all we need to do is check if x1+g can be written. Now this x1 does not really matters as it will disappear in most eqations,you can write down yourself and see .
In the problem we can write for any x :
Thank you very much！
Can someone point out a mistake in this code? It gives WA on 10021st token. How is that even possible if total queries are 10000? https://mirror.codeforces.com/contest/1478/submission/105762283
With q = 10000, test cases t = 9 is also there. So total tokens can be upto 9*10000
and I have no way of getting the case right?
Try this test case.
1
1 2
89
Expected:YES o/p:NO
it's d = 2, a = 21.
21 itself is a lucky number.
Okay, Got it Thanks. But now I made a solution using unbounded knapsack/ subset sum where I basically used [d, d+10, d+20, ..] as the array to check if a value can be formed using the set. So for d = 2, and set [2,12,22,..] a = 21 cannot be formed right? But my code got accepted. So what is the catch in that? https://mirror.codeforces.com/contest/1478/submission/105780118.
21 itself has 2 in it. I don't get what you say.
Doesn't matter got it anyway 21 > 2*10 that's all.
An alternative solution for Problem Div 2 B — 1478B - Nezzar and Lucky Number
For given d, construct a sequence of elements of length s, that looks like
d, d + 10, d + 20, ..., d + (s — 1) * 10such thatd + (s — 1) * 10is strictly less than d * 10.Observation 1: For a[i] >= d * 10, it's always possible to construct a[i] as sum of lucky numbers.
Observation 2: For a[i] < d * 10, it's feasible to brute-force any possibilities of representing a[i] as sum of lucky numbers.
Can you please explain this? Observation 1: For a[i] >= d * 10, it's always possible to construct a[i] as sum of lucky numbers. UPD: Got it.
mercurist i read your code in problem B , i think use bruteforces of case vec[i] < 10 * d in this way help code run faster instead use dfs
Sorry my poor English.
good but all problem are ad-hoc
plz in next contests add algorithmic problems
how to avoid getting stuck on A and B in contests ?
UPD : It's genuine question.Do you people get stuck on those problems often and what are the reasons behind that ?
solve them.
if you feel like you are not making enough progress on a problem then you can try to solve some other problem and come back to that problem after some time.
Start from C
Yes, I too get stuck in critical observation type problems. Any help on how to improve on problems like that(B of today's contest for example) is appreciated.
Just code brute force solution and try to find out the relation(idk atleast that's generally works for me)
I used to brick my B quite often a few weeks back. I think you're talking about you are expecting yourself to do those questions quickly but you end up doing it wrong or can't get the idea at all. This is what I did, out of contest, I started practicing two problems from easier ranges(one 800-1200 the other 1300-1500 based on comfort level) and noted the time to solve(try to do it right) whenever I was averaging less than 10 mins in the easier range I increased the rating by 100 for those, same for the harder(1300-1500) ones when the avg. is less than 15. In contest, focus on doing it correctly and don't rush it for the next few contests. You will have a good idea of when you're rushing it as now you know very well how much time you take normally in those problems. It took me 4 to 5 more contests after I started practicing this way to eliminate those bad contests and get to a higher rating range.
Really nice problems！Though I miss the final time to submit div2F , which leads to a big loss //(ㄒoㄒ)//
I used bubble sort instead of insertion sorting in Div1C, but it seems that only when I sorted the points by their x-positions could I get accepted. Could you please help me find it out?
105754405
105754995
The 20000 in the second one doesn't matter.It will still get acceptted when I cange it to n.
Div1 C was quite beautiful, however it was the same as this problem
Randomized approach for D1C(D2F):
There is three points, $$$A,B$$$ and $$$C$$$ on the plane.
Of course, the three points form a triangle.(this triangle's area can be $$$0$$$)
Then, two of $$$\{A \rightarrow B \rightarrow C\ ,\ A \rightarrow C \rightarrow B\ ,\ B \rightarrow A \rightarrow C\}$$$ are nice beatmaps.
For this reason, the following algorithm will work.
Then, What is the probability of find a solution with this algorithm?
The answer is $$$(2/3) \times (8/9) \times (26/27) \times ...$$$
It seems that this value goes $$$\simeq 0.56$$$ (at least $$$n \le 5000$$$).
So, try this algorithm about $$$\frac{1}{0.56} \simeq 2$$$ times, then we can find a solution.
code : 105753764
If there is a hack case, please tell me.
As a music gamer, I like this problem!
Indeed, this product converges at $$$\approx 0.56$$$. You might want to read on q-Pochhammer symbol, it may act as a good probability estimate if you're not sure how many times to run the randomized solution.
Can you elaborate how did you get the answer, i.e. probability?
If there are $$$k$$$ points in a set $$$S$$$, the probability that there aren't any point $$$p$$$ in $$$S$$$ such that $$$X \rightarrow Y \rightarrow p$$$ ($$$X,Y$$$ are some points) is a good beatmap is $$$(1/3)^k$$$ ,thinking about the triangle $$$\Delta XYp$$$.
Then, the probability is $$$(1-(1/3)^1) \times (1-(1/3)^2) \times ...$$$
The estimation is very rough, so there maybe some hack case...
Actually all of three authors are osu player! :o
I'm also, but I'm an osu! mania player ><
(By the way, beatmap(s) or beatsmap(s)...? I always think about this when I want to talk about music games(,or rhythm games, music simulation ...?) in English)
I think it's "beatmap(s)" according to English version osu.
I thought that the problems were really nice. Kudos to all the authors!
In the problem Nezzar and Board, can anyone prove that if we have $$$[0, x, y]$$$ written on board, then we can construct $$$a*x+b*y$$$? What I was able to prove that we can construct $$$a*x$$$ and $$$b*y$$$ individually.
Thanks
Can you explain how to get $$$a*x$$$ that is any multiple of $$$x$$$ if $$$x$$$ is written on the board?
I can explain with an example, let's assume we have $$$[0, x]$$$ written, we want to construct some $$$a*x$$$. Assume $$$a = 2^z - 2^{j_1} - 2^{j_2} .. - 2^{j_k}$$$. We can write $$$a$$$ in this way using the binary expansion. Now let's take an example and see how to construct it.
Let's say we want to make $$$10*x$$$, $$$10 = 2^4 - 2^2 - 2^1$$$. We can obviously construct $$$2^b*x$$$ using $$$2*x$$$ repeatedly. Now $$$(2^4 - 2^2 - 2^1)x = 2*(2^3 - 2^1 - 1)x$$$, therefore we only want to construct $$$(2^3 - 2^1 - 1)x$$$ or $$$(2*(2^2 - 1) - 1)x$$$. This means we want to construct $$$(2^2 - 1)x$$$. Which can be constructed using $$$2*x$$$ and $$$x$$$. I hope you got the idea.
So in $$$a = 2^z - 2^{j_1} - 2^{j_2} .. - 2^{j_k}$$$, divide by $$$2^{j_k}$$$ and construct the remaining part which is $$$2^{z-j_k} - 2^{j_1-j_k} - .. - 2^{j_{k-1} - j_k}$$$ recursively.
Ok got it. One easier way would be to inductively generate all multiples of $$$x$$$. we can generate $$$2*x$$$ by simply using $$$y=0$$$. Than if we want to generate an even multiple of $$$x$$$, we can simply use the $$$a/2$$$ multiple and take $$$y=0$$$. for generating odd, eg $$$5$$$, we can take $$$3*x$$$ and $$$y=x$$$. This way we can generate both odd and even mutliples of x.
Yeah, could have proved using induction also. Can you think on that $$$a*x + b*y$$$ now? If $$$a$$$ or $$$b$$$ is even then it is easy. The problem that I am facing is when both are odd.
Actually, you don't need to construct the both-odd case:)
You can obtain $$$a$$$ and $$$b$$$ that satisfies $$$ax + by = \gcd(x, y)$$$ by extgcd. If both $$$a$$$ and $$$b$$$ happen to be odd, you can shift those coefficients, so: $$$(a - y')x + (b + x')y = \gcd(x, y)$$$ where $$$x' = \frac{x}{\gcd(x,y)}$$$ and $$$y' = \frac{y}{\gcd(x,y)}$$$.
Here $$$x'$$$ and $$$y'$$$ are coprime, so not both are even. Therefore you get $$$(a-y')$$$ and $$$(b+x')$$$ that are not both odd.
One of the best proofs ever .. Atleast for me personally. Just wanted to appreciate it.
Thanks!!
Awesome proof!!!!!!
Can you please explain why this is failing (https://mirror.codeforces.com/contest/1478/submission/106189636)
The sample is itself failing. The logic is also incorrect.
Can You explain why my logic is wrong, I am taking the GCD as written in the editorial and K should be divisible by GCD of all x's is written in the editorial.
Can you prove why K should be divisible by GCD? Also if it is divisible, how does it guarantee a "YES"? Give a proper mathematical proof.
2x-y is the reflection of y w.r.t x. You can do the following to get all multiple of x:
Reflect 0 w.r.t to x and get 2x
Reflect x w.r.t to 2x and get 3x
Reflect 2x w.r.t 3x and get 4x
and so on
As others have mentioned, the problem reduces to construct $$$x + y$$$ from the set $$$\{0, x, y\}$$$. Can someone come up with such construction? I've been running a simple program for a few minutes and cannot find it.
I can prove that it is impossible.
All our initial numbers are of the form $$$(nx+my)$$$. Where at least n or m is even.
Whenever you apply an operation, on $$$(n_1x+m_1y)$$$ and $$$(n_2x+m_2y)$$$, you get $$$(2n_1-n_2)$$$ and $$$(2m_1-m_2)$$$. It is easily provable by induction that both of the terms can never be odd.
Let me challenge red's proof:)
You can construct $$$\gcd(x,y)$$$ from $$$\{0, x, y \}$$$ without creating $$$x+y$$$.
Once you have $$$\gcd(x,y)$$$ in your set together with $$$0$$$, you can construct any multiple of it, including $$$x+y$$$.
We get contradiction with the proof... What's wrong?
$$$x + y$$$ is not always a multiple of gcd.
$$$Gcd(x,y)$$$ means it divides both $$$x$$$ and $$$y$$$. So why will it not divide $$$x+y$$$?
kekw, yeah, don't know what i meant. The thing is x + y = k * gcd = k1 * x + k2 * y, where one of the coefficients is even.
I was just explaining why his code "has been running for a few minutes and cannot find it"
So you didn't disprove my proof.
A kind of stupid question, but in the editorial code for D1C:
What exactly is that checking?
inner product of two vectors.
Can you explain the correctness of this solution?
it was mentioned here
Check out my explanation of problem C — solution
Thanks for the good contest -_-
Congratz, maroonrk!
We know there are many weird solutions for Div.1C/Div.2F can get AC when their correctness can't be proved. We had tried our best to construct tests already, but some of them are extremely hard to hack. If you come up with an excellent hack, welcome to share it!
UPD:
For example, 105780521, created by kzyKT and developed by us.
Pick a new base point $$$O'$$$ and sort all points by polar angle, then try to check point sequence $$$[1, \frac n2 + 1, 2, \frac n2 + 2, \dots]$$$ (and those permutations can be derived by shifting) or something similar if they can be valid answers. This pattern will make acute angels appear frequently.
if you can't find answer with the current $$$O'$$$, you can try many other $$$O'$$$. Some specially chosen $$$O'$$$ perform literally excellent, like:
So you will have a high chance to get a valid answer sequence if you check each of these $$$O'$$$.
We spend a long time hacking this solution, but it seems impossible. :(
I tried to hack the following solution:
Start sequence from $$$[1, 2]$$$, then for $$$i = 3\dots n$$$ try to insert $$$i$$$ at some place at the sequence so that all angles are $$$ \lt 90$$$.
But it can be proved! Indeed, pair of points $$$p[j], p[j+1]$$$ blocks us from inserting point $$$i$$$ in at most $$$1$$$ position — so at most $$$i-2$$$ positions are blocked. However, we have $$$i$$$ possible positions where to insert! (So we can insert all the points this way)
Yes, it's initial solution when triple_a comes up with this problem.
I construct sequence [1,n,2,n-1...], and it seems can be hacked easily :(
Alternative Solution for Div2B without DP 1478B - Nezzar and Lucky Number
If ai >= 10d then it is always achievable. Because it is possible to subtract a number with d on the ten's place and any number on the one's place. It is possible to choose the one's place number so that the subtracted result is divisible by d (meaning it can be obtained by the sum of d's).
If ai < 10d, it is only possible to subtract d from it. So after each subtraction of d, check if ai is divisible by d or ai is divisible by 10 (meaning k*10 + d can be subtracted).
105777562 For Div2C I solved it by getting back the original array a. Basically the same idea as tutorial except one more observation is that
d[2n] = 2n*a[n]Hello, I tried the same approach as you suggested, but I think that I'm missing something. I looked at the example from the problem statement:
We have that
Can you please help me figure out what? Thank you!
https://mirror.codeforces.com/blog/entry/87394 This blog explains it
I like how D had such a clean solution.
Why
k % gcd(x_1, x_2,.., x_n) == 0won't work in DIV2D/1A? Can someone please explain.How to prove that it's possible in Div1C to take farthest available point on each step?
You can prove it easily. Let's say you pick $$$B$$$ as the farthest point from $$$A$$$ .
1) If any point is outside the yellow region, it has to have greater distance from point $$$A$$$ than $$$B$$$, which is a contradiction. So there are no points outside the yellow region.
2) Any point in the yellow region satisfies the condition.
Sorry for the necroposting but this shit(proof) is so beautiful.
Even the insertion sort option doesn't seem so obvious to me since swapping two elements can effect both of the adjacent angles. Can you prove that?
see here
why? :(
OK, I guess it's because if we have an initial set {a, b, c} and we want to build k, by subtracting a from everything, nothing changes since every number we can build is also shifted by a. Namely:
{a, b, c} with target k, e.g. we can build 2b-c.
is equivalent to
{a-a, b-a, c-a} with target k-a, e.g. we can build 2(b-a)-(c-a) = (2b-c)-a.
Can someone sketch a proof at Div1C for injection sort?
see here
In problem D editorial , how subtracting $$$x_1$$$ from all other $$$x_i$$$ won't effect the answer i.e how to prove that if $$$k$$$ can be formed from $$$x_1,x_2,x_3$$$ then $$$k-x_1$$$ can also be formed from $$$0,x_2-x_1,x_3-x_1$$$?
Also can some one explain how we can write down $$$g$$$ by applying operation recursively ?
For an arbitrary interger $$$d$$$, $$$(2x-y)-d=2(x-d)-(y-d)$$$. That's why we can subtract $$$d$$$ from all the elements (including $$$k$$$).
From the proof of the editorial, we can get $$$g_0$$$ and $$$x_n$$$. Let we prove one fact that if we get $$$x$$$, we can also get $$$qx$$$ for all the intergers $$$q$$$. In fact, we can use $$$x$$$ and $$$0$$$ to make $$$2*0-x=-x$$$, so that we can add $$$2x$$$ and $$$-2x$$$ any times to any one element. (i.e. we can get $$$2*x-(-z)=z+2x$$$ and $$$2*(-x)-(-z)=z-2x$$$ with $$$z$$$) So the fact has already been proved.
Then we need to discuss about the parity of $$$s$$$ and $$$t$$$ such that $$$g_0s-x_nt=g$$$. If $$$s$$$ and $$$t$$$ are both even, we can just add $$$\pm 2g_0$$$ and $$$\pm 2x_n$$$ to $$$0$$$ some times. If one of $$$s$$$ and $$$t$$$ is odd, suppose that $$$s$$$ is odd, we can just add $$$\pm 2g_0$$$ and $$$\pm 2x_n$$$ to $$$g_0$$$ some times. If both of them are odd, we can just change $$$s$$$ and $$$t$$$ into $$$s+\frac{x_n}{\gcd(g_0,x_n)}$$$ and $$$t-\frac{g_0}{\gcd(g_0,x_n)}$$$. Because $$$\gcd(\frac{x_n}{\gcd(g_0,x_n)},\frac{g_0}{\gcd(g_0,x_n)})=1$$$, they can't be both even and it has already been changed into the situation we have talked about.
Given $$$g_0$$$ and $$$x_n$$$, then we can get $$$g_0 * s$$$ and $$$x_n * t$$$.
Now $$$x_1 = x_n * t$$$, $$$x_2 = g_0 * s$$$, we can subtract $$$x_1$$$ from all x. We get $$$0, g_0 * s - x_n * t = g$$$. And by induction, we can get $$$q * g$$$. Now we add $$$x_1$$$ back. Because $$$x_1$$$ is divide by $$$g$$$, suppose $$$x_1 = t * g$$$, so we can get $$$q * g + t * g$$$ for all $$$q$$$, that is equal to $$$q * g$$$.
So you proved that $$$g_0s$$$ and $$$-x_nt$$$ can be made individually using the operations . But how to prove that $$$g_0s - x_nt$$$ i.e $$$g$$$ can be made ?
My major doubt is how Bezout's Theorem used here ? In the editorial it's mentioned that we can make $$$g_0s$$$ snd $$$-x_nt$$$ but how does that proves that any number divisible by $$$g$$$ can be constructed ?
For example, $$$g_0 s=5g$$$ and $$$x_n t =4g$$$, now we could apply our operation to get $$$4g*2-5g = 3g$$$, and recursively we could finally get $$$g$$$, which could generate all possible numbers divisible by $$$g$$$.
Thanks for the example , it cleared my doubt regarding what actually editorial wants to say .
I have one more doubt , You have shown for one example that how $$$g$$$ can be constructed when $$$g_0s = 5g$$$ and $$$x_nt = 4g$$$ . How to prove in general that if we can make $$$g_0s$$$ and $$$x_nt$$$ then we can also make $$$g$$$ ?
Note that both $$$g_0s$$$ and $$$x_n t$$$ are divisible by $$$g$$$, and their difference is exactly $$$g$$$, therefore we may assume that $$$g_0s=(m+1)g$$$ and $$$x_n t=mg$$$ for some nonnegative integer $$$m$$$, which falls exactly into the same argument.
Thanks a lot . This really helped .
Please note that we can construct $$$g_0s+x_nt$$$ for all intergers $$$s$$$ and $$$t$$$ according to the proof above.
Nezzar Can you please give more mathematical proof for DIV1-C, how can we prove this with contradiction like it feels natural but how to prove this first method you suggested.
Consider three points $$$A$$$, $$$B$$$, $$$C$$$.
You are in $$$A$$$ currently. Assume that the furthest point is $$$B$$$, then $$$C$$$ is between $$$A$$$ and $$$B$$$ so $$$\angle ABC$$$ is acute; if $$$\angle ABC$$$ is not acute, the furthest point from $$$A$$$ should be $$$C$$$ instead of $$$B$$$.
I didn't understand the editorial of 1477A — Nezzar and Board Can someone please explain the editorial?
I also struggled to understand it. Here's my detailed understanding:
(1) Note that if you had zero available and another number $$$a$$$, then you can build every multiple (positive and negative) of $$$a$$$. For example, from $$$(0, a)$$$ you can get $$$-a$$$ and from $$$(-a, a)$$$ you can get $$$3a$$$ and so on.
(2) Note that shifting all numbers $$$x_i$$$ and $$$k$$$ by the same amount, does not change the answer. If you had numbers $$$x_0$$$, $$$x_1$$$ and $$$x_2$$$ and you wanted to obtain $$$k$$$, you could subtract $$$x_0$$$ from everything and every number obtained from this new process is also shifted by $$$x_0$$$. For example, you would get $$$x_0-x_0=0$$$, $$$x_1-x_0$$$, $$$x_2-x_0$$$ and $$$k-x_0$$$ and if you combined $$$x_1-x_0$$$ and $$$x_2-x_0$$$, you would end up with $$$2(x_1-x_0) - (x_2-x_0) = (2x_1-x_2)-x_0$$$.
(3) Note that since you can get 0 by shifting the input and you can get the multiples of all the remaining numbers, you can basically get every number of the form $$$u(x_i-x_0) + v(x_j-x_0)$$$, which is another way of saying that you can get every multiple of $$$gcd(x_1-x_0, x_2-x_0, ...)$$$, and nothing else. (See Bézout's identity).
(4) Finally, using the previous observations, if $$$k-x_0$$$ is a multiple of $$$gcd(x_1-x_0, x_2-x_0, ...)$$$ then the answer is "YES". Otherwise, it is "NO".
Sample Solution: 105781653
Can you prove point (3)? Given [0, x, y], try to construct x+y.
It is impossible, does this mean that the editorial is wrong?
https://mirror.codeforces.com/blog/entry/87294?#comment-754746
ok, we can write down $$$g_0, g_0s, x_nt$$$. Explain please, how we can write down $$$g_0s-x_nt$$$? if s is even, i understand, but if not
Let's say we want to get $$$x_{n}t$$$ and we have $$$t = 13$$$. Our operation is $$$2a - b$$$. We can set $$$a = 4x_n, b = x_n$$$, so it becomes $$$8x_n - x_n = 7x_n$$$. And then we set $$$a = 7x_n$$$ which we got before, and $$$b = x_n$$$, and it becomes $$$14x_n - x_n = 13x_n$$$. And of course, we can get any $$$kx$$$ being $$$k = (2^{exp})$$$ if we set $$$a = \frac{k}{2}x$$$ and $$$b = x_1$$$ (remember $$$x_1 = 0$$$ because of the shifting). That is to say, we can get $$$2x$$$ with $$$x$$$ and $$$0$$$, $$$4x$$$ with $$$2x$$$ and $$$0$$$, and so on.
i understand how to get $$$kx$$$ from $$$(0, x)$$$, if we have ((k-2)x, (k-1)x) then $$$2*(k-1)x - (k-2)x = kx$$$. Ok we got $$$g_0s, x_nt$$$, what we should do to get $$$g_0s - x_nt$$$?
Bézout's theorem states that there exists $$$x$$$ and $$$y$$$ so that $$$ax + by = gcd(a,b)$$$. So you can say having $$$g_0s-x_nt$$$ that there exists $$$s$$$ and $$$t$$$ such that it equals $$$gcd(g_0,x_n)$$$. Note that you only need to say if it's possible, not how would you get the number on the board. So once you get $$$g = gcd(g_0,x_n)$$$ (I call it $$$g$$$ to be consistent with the naming in the editorial, as $$$g_0 = gcd(x_2,x_3,x_4,\dots,x_{n-1})$$$) by some amount of operations on the board, it means $$$k$$$ has to be a multiple of $$$g$$$ to be possible to write in the board, and you would do it the same way you got all other gcds before. So that's why at the end we check if $$$k \equiv 0 \pmod{g}$$$.
Note that you only need to say if it's possible, not how would you get the number on the board.
we need prove it. By induction we got $$$g_0$$$,now we need get $$$g$$$. by Bézout's theorem states there're exist $$$s, t$$$ such that $$$g_0s - x_nt = g$$$, but why we can get $$$g$$$, using operatin $$$2x-y$$$ and some numbers already written down on board like $$$0, x_2, \dots , x_n-1,x_n, g$$$, previosly found gcd's and something else.
The editorial describes the process where you get to $$$g_0$$$ as "recursive". And as I far as I understand and was mentioned in the comments, it means first you had to get $$$x_2s-x_3t = gcd(x_2,x_3)$$$ on the board first, let's call it $$$v_1$$$. Then you got $$$v_2 = v_1s - x_4t = gcd(v_1,x_4)$$$, then $$$v_3 = v_2s - x_5t = gcd(v_2,x_5)$$$ and so on. With that method you got to the last step where in the same way you get to write $$$g$$$ on the board. Therefore, if $$$k$$$ is equal to $$$g$$$ or some multiple of it, it can be written on the board.
Also, thinking it logically, it makes sense. If all numbers previously written are multiple of some number, multiplying them by two and subtracting another of the numbers in an operation, means you'll never have a way to write some number which is not multiple of it. That's even what's in part described in the first direction of the proof in the editorial.
About making a really formal proof, I'm not used to making them, so unfortunately I'm unable to come up with one. But based on what's said in the editorial, what was commented by other people and with my logic, seems to work for me. If you still feel unconvinced of the correctness of the solution, you can try to prove it by yourself, try solving as many cases as you want to get to a conclusion. After all, I think it's pretty rare to be proving some solution during a contest, and it always depends more if you are convinced of a solution. Of course I'm also trusting that the authors have made all the possible things they could to be sure of the correctness of the solution. But nevertheless if you find some way it doesn't work, you can always point it out.
omg, it's common words about why this solution correct. I believe that it's correct, but me need a prove of correctness, only one part of it i don't understand. In induction we need to strictly prove base case and jump from $$$n$$$ to $$$n+1$$$, it does not matter that we assumed until $$$n$$$ we wrote down other gcd's not clear how.
$$$g$$$ should be written down on the board, then we can write down k
Great explanation thank you.
This is so much better than the editorial's explanation.
Nezzar For F, it looks like the coefficient of $$$x^{k-1}$$$ in $$$Q_j$$$ should have $$$1/(k-1)!$$$ instead of $$$1/k!$$$.
Thanks! it is fixed now.
Missed the part in DIV2C that integers of the array will be distinct. smh.
Can it be solved if elements of the array were not distinct?
Like, $$$d[] = 16, 16, 16, 18, 20, 22, 22, 26$$$
here, $$$a[] = 1, -1, -1, 2, -2, 3, 3, -3$$$
Please read the statement, array a[] should contain distinct numbers.
Yes. I'm just asking if the elements were not distinct could it be solved.
I think it technically can be solved but the code will be extremely diffcult to write or read.
Hey Nanako, check this. For it to be solved with non distinct elements, the statement should be modified as freq(0) is multiple of 2 and freq(i) should be equal to freq(-i) for each i in the A. Then, it would make sense.
can you please tell me what the array $$$a$$$ will be for the following case?
$$$d = [4,4,4,4]$$$
why the elements of $$$d$$$ shouldn't be distinct?
UPD : I just found out my mistake.sorry!
Div2D, what is the meaning of sentence "(Otherwise, we could subtract x1 for x1,x2,…,xn and k)"?
We can somehow transform x1 to 0, if yes, how?
You can imagine that he moves base point $$$O$$$ from $$$x = 0$$$ to $$$x = x_1$$$ in $$$x$$$-axis.
See here https://mirror.codeforces.com/blog/entry/86856?#comment-749352
The answer depends on the relative positions of $$$x[]$$$ and $$$k$$$ instead of the absolute positions, so substracting $$$x_1$$$ from all elements at the same time won't change the answer, then we get $$$x_1=0$$$.
can you please explain the last line of editorial of Div2 D ,
I didn't understood how to do that.
According to the editorial you can write down gcd of two numbers. "recursively" means then you can write down gcd of three numbers (by using the previous gcd and another number), and then gcd of more numbers, until gcd of $$$n$$$ numbers.
Isn't that saying that because we can make $$$g_0$$$ and $$$x_nt$$$ and thus we can some how make $$$g_0s-x_nt = g$$$ by applying the operations ?
In second part of proof we need to show that any number divisible by $$$g$$$ can be written down . If we show that $$$g$$$ can be written down then it's obvious that anything divisible by $$$g$$$ can written down by taking $$$y=0$$$ .
I think it means the same if you understand how to write down gcd of two numbers. The difference is, my explanation is from gcd of two numbers to gcd of n numbers, editorial is from gcd of n numbers to gcd of two numbers (cuz it's induction).
Ok , so you mean that because for $$$n=2$$$ our statement holds , thus we can say that $$$g$$$ can be created out of $$$g_0$$$ and $$$x_nt$$$ . And thus we can say that all number divisible by $$$g$$$ can be created .
So in last part of proof , we are using the fact for $$$n=2$$$.
Editorial derive $$$g$$$ from $$$g_0$$$ and $$$x_n$$$, and you can also imagine, before that, you derive $$$g_0$$$ from $$${g_0}_0=\gcd(x_2,\dots,x_{n-2})$$$ and $$$x_{n-1}$$$. Keep similar operation then you will realize the whole process is all correct.
I can't really get what makes you confused. Maybe learning "What is Induction" would help you.
"substract x1 from x1,x2,...,xn and k"
Lets say we have three numbers a, b, c. How can we construct 0 from them, by using that operation 2x-y?
You convert $$$(x_1, x_2, x_3, k)$$$ into $$$(0, x_2 - x_1, x_3 - x_1, k - x_1)$$$. They are equivalent because $$$2(a - x_1) - (b - x_1) = (2a - b) - x_1$$$
You can see that any solution in the transformed set is a solution in the original set because $$$2x - y$$$ is the reflection of $$$y$$$ over $$$x$$$, and these reflections are invariant to shifts such as in the transformed set.
omg, I thank you all for trying to explain ;) But such sentence with another 3 or 5 new terms is not helpful.
I understood that for some reason we can shift all numbers by any amount, and for another reason we do shift by x1, so we transform that element to 0.
Then, for some reason, we can directly use the gcd() of the remaining numbers to check if k is a multiple of it, which determines ans.
Try picking a couple $$$x$$$ and $$$y$$$ pairs and draw them in the number line, along with $$$2x−y$$$. Try to find a pattern there, it might be useful to get an intuition to why we can find a solution using the numbers with a fixed offset.
The reason we want one element to be $$$0$$$ is because then we can use it allows us to construct some more predictable and useful numbers. For example if we do the operation $$$2x−y$$$ with $$$x=0$$$, the result is $$$−y$$$, and if we do it with $$$y=0$$$ the result is $$$2x$$$, see some discussions above to more details on why this will help solve the problem. Also we can shift by any other number, not necessarily $$$x_1$$$.
The argument for the gcd I still have not figured it out. This editorial is pretty obscure (not surprising, sadly).
Operation we apply : $$$2x - y$$$ . Suppose we subtract $$$x_1$$$ from $$$x$$$ and $$$y$$$. Then $$$2*(x-x_1) - (y-x_1) = 2*x-y-x_1$$$ . So you can see that final answer is subtracted by $$$x_1$$$.
Thus converting to $$$k$$$ from $$$x$$$ and $$$y$$$ is same as converting to $$$k-x_1$$$ from $$$x-x_1$$$ and $$$y-y_1$$$.
I showed for only one operation but it's not hard to see for multiple operations.
1477B - Nezzar and Binary String can be solved without a segment tree. The idea is to keep subarrays with equal digits in a set. The complexity of the operations for each move is $$$O(\log(n))$$$ amortized.
AC submission: 105757658
You are right! Because of 896C - Willem, Chtholly and Seniorious some people would like to call it "Chtholly Tree". :)
I think my solution is deterministic: for each query, I add up to $$$3$$$ new intervals and I remove all the intervals I visit. Hence, I visit $$$n + 3q$$$ intervals in the worst case.
105785851 Why does this brute force sol work for div2 B? Shouldn't it give a TLE in the worst case?
Many numbers contain $$$d$$$ so it won't spend too much time finding a valid answer. I think this sol is also a correct sol.
problem D editorial proves the solution but doesn't gives any intuition behind coming up with the solution . Can some one tell their lane of thought which brought them to the solution ?
I can offer my thinking process in this problem.
Noticed that $$$2x-y=x+(x-y)$$$, so actually for a $$$x$$$ we can move it to $$$x + k \cdot dis(x, y)$$$ for any $$$k$$$ and available $$$y$$$. Then according to Bézout's Theorem, I found that $$$x$$$ can be moved to any $$$x + k \cdot \gcd(dis(x, others))$$$.
A fun observation is, in $$$2x-y$$$, coefficients are $$$2,-1$$$ and the sum of them is $$$1$$$. Actually, I think it seems impossiable to solve if we change it to $$$3x-y$$$, but $$$3x-2y$$$ or $$$3x-y-z$$$ or something seems much more solvable. I can't explain it well because my English suck, sorry.
Hey Nanako
I found that X can be moved to any X+K*gcd(dis(X,others)).
how you found that!?
What if the k*gcd is smaller than the diffs we can add !?
Example:
K=52
arr=[7, 27, 42] so the gcd(diffs)=gcd(20, 15)=5
42 + 2*5 = 52
to get 52 we need to add 2*5 to 42, but we can't do that using the real diffs (20, 15) I know we can get it using some (subtractions , additions) of these diffs but I'm not sure how I can think about it intuitively.
Sorry for replying lately. I guess it will become more and more intuitive after you solve more and more problems about Bézout's Theorem and ex-gcd (Chinese nickname of Extended Euclidean algorithm? lol) and other number theories. :)
Given x and y, we can get $$$x + t * (y - x)$$$ for all t. So this is an arithmetic sequence. We draw it on an axis.
Now given another number z. We find a closest point on the axis and draw the new arithmetic sequence produced by z and the closest point. If the distance of z and the closest point divides $$$y - x$$$, then all points is just one arithmetic sequence which is $$$z + t * distance(z, closest point)$$$. Otherwise, we can find another two more close points and produce more points. You can see that only when the distance of two closest points divides both $$$y - x$$$ and $$$z - x$$$ and $$$z - y$$$, the process will stop. So $$$z + t * gcd(y - x, z - y)$$$ can be produced.
You can draw it on a paper and get the intuition.
1477A — Nezzar and Board
Explain me how we can write down $$$g_0s-x_nt$$$ which is equal $$$g$$$?
video editorial for problem D, if theres anyone whos stuck! https://www.youtube.com/watch?v=yYxQ9_EL69Q
i still don't understand, how from (0, a, b) get $$$a * s - b * t = gcd(a, b)$$$ using $$$2x-y$$$ operation
If s is even, then we can get a * s/2 and b * t first, then $$$2 * (a * s/2) - b * t$$$ is $$$gcd(a,b)$$$. If s is odd, then we can get $$$2 * (a * (s+1)/2) - b * t$$$ is $$$a + gcd(a, b)$$$. Given a and $$$a + gcd(a, b)$$$, by induction, we can get $$$gcd(a, b)$$$.
thaks, i undertood) Really is it so obvious, that it's not required to point in editorial? Only how to get $$$gcd(a, b)$$$ from $$$a$$$ and $$$a+gcd(a, b)$$$ took me 5 minutes. We can get $$$a - gcd(a,b)$$$, than $$$a - 2*gcd(a,b)$$$ and so on until we get $$$gcd(a, b)$$$.
It is not obvious. They should include this comment in editorial.
for 1478B, here is my solution https://mirror.codeforces.com/contest/1478/submission/105779176 in a bit different style than author ;) , although I fucked up during the contst!:(
For problem B I assume that $$$x$$$ can be represented as $$$ x = y + w.d $$$. Then, $$$ y = x - w.d $$$ and just check that $$$y$$$ has at least one digit equal to $$$d$$$. By brute force I concluded that $$$w$$$ is at most $$$9$$$ because for $$$x \gt = 10.d $$$ the answer is always YES.
The system test of problem C is weak! Some people use
doubleandsqrtto calculate distance, it can be hacked, like this, but it passed the system test.I noticed this and resubmitted my code, after the contest, I know that the original code could pass, if I didn't resubmit, I'll be International Master! ):
update: This seems to work only for GNU C++17 (64).
Could anyone help me about this https://mirror.codeforces.com/blog/entry/87299 ? Thanks!
In problem D of div2, why always subtracting x1 from all other numbers works? Means the cases can't be there such that we need to subtract x2 from all the numbers and take gcd after that?
k is a linear combination of all x. And you can see that sum of coefficients is always 1. So subtracting x1 from all x results in subtracting x1 from k.
For anyone not knowing what WLOG means in editorial for Div.2 C,
WLOG = Without Loss Of Generality.
Very nice problems!
I like div.1C very much.
For Div2 B how can N=21 and D=2 gives answer yes?
If you are talking about taking some ai = 21 and d = 2, then 21 itself is a lucky number as it contains d = 2 in its representation already and doesn't need to be expressed as sum of other lucky numbers, So, answer is YES.
21 itself is lucky number.
Can someone tell the mistake in the following code of mine for Div2B: 105802694 For each integer i from 1 to 9 I stored the smallest integer 1<=j<=10, that give the unit digit (i*j)%10 when multiplied with as a[i][(i*j)%10] = j So if the number in query (say c) had a unit digit l that can be found in a multiple of d, I check if c is greater than or equal to the minimum multiple of d that gives that unit place. If yes, then I output YES as I think all such numbers can be represented using lucky numbers. Else, I output NO as d in unit places has minimum effect, so if we have even one d in tens place, then it becomes greater than c. Now if the units place l in c cannot be found in a multiple of d, then I check if c/10 is greater or equal to d. If yes then I print YES else no, as d cannot even come in tens place then. Can I get a testcase where this fails?
Your mistake is that you forgot to put a
continueaftercout << NO << endlin the firstifblock of your code :)Problem B :
say d = 7, so 70->79 already lucky, we can generate 80->89 as follows
similarly, we can generate 90-99 from 80-89 and so on ......
so, any number >= 10*d is lucky
Nezzar please explain DIV2C
Why in you solution following code gives $$$a_1$$$ in $$$b[n-1]$$$?
And why are you checking this condition
b[n-1]%(2*n)in the end?Nanako Can you please explain the relation in the editorial of Div2 C ? This one.. "More importantly, we have the following relation:".
Main observation is, when there are $$$n - x$$$ elements smaller than the current position and $$$n + x$$$ elements bigger than the current position, if you move left for 1 unit length, $$$\sum |curpos - a_i|$$$ will increase $$$2x$$$.
I found this contest really nice (especially div1 D). Thanks for the contest :)
Chinese round! Unfortunately I still can't take part in due to the time (.
On div2 D,
if((arr[0]%gcd) == (k%gcd)) printf("YES\n"); ... => WA
if((k-arr[0])%gcd == 0) printf("YES\n"); ... => AC
I really wonder why this thing happens.
https://stackoverflow.com/questions/11720656/modulo-operation-with-negative-numbers/11720975#11720975
I found the reason.
div2C symmetric array
I tried another approach:
Assume that the "d" array (the sum array) and the "a" array (initial array) are sorted. I redefined the "a" array so that it would only contains positive numbers.
Since the two arrays are sorted $$$a[n - 1]$$$ and $$$d[n - 1]$$$ would become the largest element of respective array. I observed that if we choose any index i (0 <= i < n), then the sum $$$|a[n - 1] - a[i]| + |a[n - 1] - (-a[i])|$$$ would become $$$|a[n - 1] - a[i]| + |a[n - 1] + a[i]| = a[n - 1] - a[i] + a[n - 1] + a[i] = 2a[n - 1]$$$ (since a[n — 1] is the largest element). This applies to every other index 0 <= j < n — 1.
Then a[n — 1], or the largest element of the "a" array (initial array) can be calculated using this formula: $$$d[n - 1] = a[n - 1] * 2(n - 1). $$$ By expanding more, I could also prove that: $$$d[n - 2] = 2a[n - 1] + 2(n - 2) * a[n - 2].$$$
Hence I could restore the initial array with following formula: $$$d[j] = \sum\limits_{i=j+1}^{n - 1}{2a[i]} + 2j * a[j]$$$, with j being the index in the sorted array. Furthermore, since all d[j] % 2 == 0 from above formula, I could throw away any cases that had any d[i] that is odd.
The problem is I can't make sure if the array constructed was right or wrong. So I tried calculating everything again from the constructed array, and also noticed if any element in that array was 0 it was wrong. Can anybody pls check it out lol
105799882
I used the same approach and got AC. To check if $$$a_i$$$ is correct, I checked that it was positive and it hadn't been found before.
snacache Err... Sir, I still haven't managed to debug my code. Would you bother helping me out?
UPD: got TLE on test case 19 106071246
You don't need that inner cycle to calculate $$$A_i$$$
In Div2 C how are we checking that whether a[0] can be made form d[0]. The a and d I am refering to are problem statement a and d.
Div1 D is awesome . Thank you!
It took me about 4 hour to come up with the solution . A very nice problem !
In Div1.A why can we assume $$$x_1=0$$$? I can't understand.
I understand is now by reading bkbtpout's comment, thanks
For Div1B (Nezzar and Binary String), could someone explain how the 3rd sample input test is possible? I've been thinking a while but I'm quite confused.
If we follow the editorial, we should work backwards starting at 0110001110, we need 6-10 to be the same before the last night's inspection so it becomes 0110011111. Then we need 3-5 to be the same so it becomes 0100011111. Then we need 1-7 to be the same so it becomes 0000000111. Then we need 5-9 to be the same and it becomes 0000000001. Finally we need 1-10 to be the same so it becomes 0000000000, but this is not 1111111111, so it doesn't seem to be possible?
Edit: Thanks Nezzar, I wrote the math for this out like 5 times on notebook paper and kept getting the same result, I have no idea how I missed that query every time..
You missed the 3rd query
I'm confused by some of the implementation in Div1 D. I think the
dfsfunction creates the spanning tree of the complement graph, is this right? The loop withwhile(d.size())seems to do the decomposition into stars, but if I'm not mistaken it doesn't use the same method described in the editorial. What I get from this is that you choose an unassigned node fromdinidx, then choose one of it's neighboursfto be the center of your star graph? Why this particular ordering of vertices ind?Sorry if it causes any inconvenience. Codes were written by me while tutorial for d1D was written by Nezzar.
Approach to decomposite spanning trees into stars in the code was to choose an arbitrary leaf in the tree, find its neighbor vertice $$$u$$$, and choose all neighbor vertices of $$$u$$$ with degree $$$1$$$ to form a star. It can be shown that the remaining graph after deletion of this chosen star is still a tree with more than $$$1$$$ vertices or empty.(Therefore, we could decompose tree into stars applying this method recursively.)
That makes sense, and is very simple. Thanks!
For div1F, the $$$m$$$-th coefficient of $$$Q_j$$$ should be $$$\frac{1}{m!}(1 - q_{m,j})\left(\frac{L_j}{L}\right)^m$$$
and the OGF of $$$k! \sum_{n \geq 0} \binom{n + k}{k}C^nx^{n+k} = k! \frac{x^k}{(1-Cx)^{k+1}}$$$
A much better solution for div2 B than DP is that if the number is $$$ \geq 10*d$$$ then it is always possible, otherwise we can observe that the only numbers less than $$$10*d$$$ that contain $$$d$$$ are, $$$10 + d, 20 + d, 30 + d, \dots$$$ Hence, if a number is feasible then it can be represented as: $$$10*x + d*y$$$ where $$$x$$$ and $$$y$$$ are variables.
I'm livid I didn't come up with this during the contest lol.
same as my approach
In Problem C : Can anyone explain why the biggest element in array d is always 2*n*(biggest element in d) supposing arrays d and a are sorted then a[n]*2*n=d[n] why?
Each element has a positive and negative value. Supposing the positive value is $$$ x $$$, and the absolute difference to $$$(y, -y)$$$ would be $$$| x - y | + | x + y | $$$. Similarly, for $$$ -x $$$, that would be $$$ |-x - y | + |-x + y |$$$, which is also $$$|x - y| + |x + y|$$$.
For $$$|x - y| + |x + y|$$$, we have two different cases. For $$$x \gt y$$$, $$$|x - y| + |x + y|$$$ would be $$$ 2 * x $$$. For $$$x \gt y$$$, $$$|x - y| + |x + y|$$$ would be $$$ 2 * y $$$. Now we know that $$$|x - y| + |x + y|$$$ = $$$2 * max(x, y)$$$.
For each $$$ d[i] $$$, it is the sum of each absolute differences from $$$a[i]$$$ to all integers. Combined with the previous finding, we got
Supposing the max element is $$$a[n]$$$. As $$$a[n]$$$ is greater than other elements, Then, we have
Therefore, you got $$$d[n] = a[n] * 2 * n $$$.
Can anyone please elaborately explain me B ( Lucky number one ) I'm struggling to understand the solution by Dp, I am a newbie so please be considerate, CF is extremely harsh and often hostile to beginners.
Try thinking about it like this: Suppose the number you are trying to check is $$$x$$$, If $$$x$$$ is achievable then it can be represented as $$$x = a + b$$$, where $$$a$$$ is a number with $$$d$$$ as one of it's digits and $$$b$$$ is a number that is also achievable.
The only possible values for $$$a$$$ are: $$$d, 10+d, 20+d, 30+d, \dots$$$
The line:
dp[10*i+d+j]|=dp[j];is checking just that! $$$10*i + d$$$ represents all possible values of $$$a$$$ and $$$j$$$ represents any number that is achievable. Hence, if $$$j$$$ is possible then $$$10*i + d + j$$$ is also achievable.Hope it helps!
Why "The only possible values for a are: d,10+d,20+d,30+d,…"?
If d = 4, for example, the lucky number 40 can't be represented in that way.
Div2D was a very nice task, but i miss a more detailed editorial's explanation.
For 1478D - Nezzar and Board, suppose we have the numbers 0, a, b, c. Then how can we generate 3a — b + 5c? Since we are using Bezout's Identity, then ax + by + cz = d must exist $$${\forall}$$$ x,y,z $$${\epsilon}$$$ $$$\mathbb{Z}$$$
In the Nezzar and Board problem, I find it difficult to understand why "If g = GCD(x1,x2,x3,....,xn) divides k, then YES, else NO" doesn't work, but the given logic in the Editorial does. Also, I am not able to comprehend the proof given. Can someone explain? Thanks in advance!
Unable to parse markup [type=CF_MATHJAX]
$
There is a more elegant (imo) way of finding stars in D1D: greedily remove an edge $$$(u, v)$$$ from the spanning tree, as long as both $$$u$$$ and $$$v$$$ have degrees strictly larger than 1. It can be proven that the remaining graph consists of stars. Great problem though!