Codeforces Round #684[Div1 and Div2] Editorial

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

We want to mention BamiTorabi who we thank for helping us with translating the problems and writing the tutorials, and also we apologize for div1 A2 and B hopefully you will forgive us :( .

Tutorial is loading...

Prepared by Mohammad.H915 Editorial by Mehrdad_Sohrabi

official solution

//                                In The Name Of Allah
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define ll long long
#define ld long double
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std; 

const int N = 3e5 + 100, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;
typedef pair <int, int> pii;

void solve() {
	int n, c0, c1, t;
	string s;
	cin >> n >> c0 >> c1 >> t >> s;
	int ans = 0;
	for(auto u : s) {
		if(u == '0') 
			ans += min(c0, c1 + t);
		else 
			ans += min(c1, c0 + t);
	}
	cout << ans << endl;
}

int32_t main() {
	int t;
	cin >> t;
	while(t--)
		solve();
	return 0;
}

Tutorial is loading...

Prepared by Mohammad.H915 Editorial by Mehrdad_Sohrabi

official solution

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int , int >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=2e5+100;
ll a[N];
int Main(){
    ll n, k;
    cin >> k >> n;
    for (int i=1;i<=n*k;i++){
        cin >> a[i];
    }
    ll x=(k+1)/2 - 1;
    x = k - x;
    ll z=n*k+1;
    ll ans=0;
    while(n--){
        z-=x;
        if (z<=0) break;
        ans+=a[z];
    }
    cout << ans << endl;
}
int32_t main(){
    ll t;
    cin >> t;
    while(t--){
        Main();
    }
}

Tutorial is loading...

Prepared by Mohammad.H915 Editorial by Mehrdad_Sohrabi

official solution

//                             In The Name Of Allah
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std; 

const int N = 200, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;
typedef pair <int, int> pii;
char c[N][N];
bool cnt[N][N];

struct node {int x1, y1, x2, y2, x3, y3;} p[5];
vector <node> v;

void upd(int x, int y, int tp, bool is) {
    if(is)
        v.pb({x + p[tp].x1, y + p[tp].y1, x + p[tp].x2, y + p[tp].y2, x + p[tp].x3, y + p[tp].y3});
    else 
        cnt[x + p[tp].x1][y + p[tp].y1] ^= 1, cnt[x + p[tp].x2][y + p[tp].y2] ^= 1, cnt[x + p[tp].x3][y + p[tp].y3] ^= 1;
}

void solve() {
	int n, m, od = 0;
	v.clear();
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> c[i][j];
			if(c[i][j] == '1')
				od++, cnt[i][j] = true;
			else
			    cnt[i][j] = false;
		}
	}
	if(od == 0) {
		cout << 0 << endl;
		return;
	}
	if(n == 1 || m == 1) {
		cout << -1 << endl;
		return;
	}
    for(int i = 1; i <= n - 2; i++) {
		for(int j = 1; j <= m; j++) {
			if(cnt[i][j]) {
			    if(j != m) {
			        v.pb({i, j, i + 1, j, i + 1, j + 1});
			        cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j + 1] ^= 1;
			    } 
			    else {
			        v.pb({i, j, i + 1, j, i + 1, j - 1});
			        cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j - 1] ^= 1;
			    }
			}
		}
	}
	for(int i = 1; i <= m - 2; i++) {
	    if(cnt[n - 1][i]) {
	        v.pb({n - 1, i, n - 1, i + 1, n, i + 1});
	        cnt[n - 1][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; 
	    }
	    if(cnt[n][i]) {
	        v.pb({n, i, n - 1, i + 1, n, i + 1});
	        cnt[n][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; 
	    }
	}
	for(int msk = 0; msk < (1 << 4); msk++) {
	    for(int j = 0; j < 4; j++) 
	       if(msk & (1 << j))
	           upd(n - 1, m - 1, j, 0);
	    if(!cnt[n - 1][m - 1] && !cnt[n - 1][m] && !cnt[n][m - 1] && !cnt[n][m]) {
	        for(int j = 0; j < 4; j++) 
	            if(msk & (1 << j))
	                upd(n - 1, m - 1, j, 1);
	        break;
	    }
	    for(int j = 0; j < 4; j++)
	        if(msk & (1 << j))
	            upd(n - 1, m - 1, j, 0);
	}
	cout << (int)v.size() << endl;
	for(auto u : v)
        cout << u.x1 << " " << u.y1 << " " << u.x2 << " " << u.y2 << " " << u.x3 << " " << u.y3 << endl;
}

int32_t main(){
	use_fast;
    p[0] = {0, 0, 0, 1, 1, 0}, p[1] = {0, 1, 0, 0, 1, 1}, p[2] = {1, 0, 1, 1, 0, 0}, p[3] = {1, 1, 0, 1, 1, 0};
	int t;
	cin >> t;
	while(t--)
		solve();
	return 0;
}

Tutorial is loading...

Prepared by AliShahali1382 Editorial by Amoo_Safar

official solution

//                             In The Name Of Allah                                           
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
//#define int long long
#define ld long double
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std; 
const int N = 1e5 + 100, OO = 1e9 + 7, T = 22, M = 1e9 + 7, P = 6151, SQ = 1300, lg = 22;
typedef pair <int, int> pii;
int mark[N], deg[N], ct[N];
bool ans[N], can[N];
vector <int> v[N], A;
vector <pii> ch[N];
bool cmp(int x, int y) {
	return mark[x] < mark[y];
}

void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	A.clear();
	for(int i = 0; i <= n; i++)
	    v[i].clear(), ch[i].clear(), mark[i] = deg[i] = ct[i] = 0, ans[i] = can[i] = false;
	for(int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	if(k > 500) {
	   cout << -1 << endl;
	   return;
	}
	set <pii> st;
	for(int i = 1; i <= n; i++)
		st.insert({deg[i] = (int)v[i].size(), i});
	int cnt = 1;
	while((int)st.size()) {
		pii p = *st.begin();
		if(p.ff >= k) {
			cout << 1 << " " << (int)st.size() << endl;
			for(auto u : st)
				cout << u.ss << " ";
			cout << endl;
			return;
		}
		else {
			st.erase(p);
			mark[p.ss] = cnt;
			for(auto u : v[p.ss])
				if(!mark[u])
					st.erase({deg[u], u}), st.insert({--deg[u], u});
			A.pb(p.ss);
		}
		cnt++;
	}
	for(auto i : A) {
		int nxt = 0;
		for(auto u : v[i]) 
			if(mark[u] > mark[i])
				ct[nxt++] = u, can[u] = true;
		for(auto u : ch[i]) 
			if(!can[u.ff])
				ans[u.ss] = false;
		for(int j = 0; j < nxt; j++)
			can[ct[j]] = false;
		if(nxt != k - 1)
			continue;
		ans[i] = true;
		sort(ct, ct + nxt, cmp);
		for(int j = 0; j < nxt; j++)
			for(int k = j + 1; k < nxt; k++)
				ch[ct[j]].pb({ct[k], i});
	}
	for(auto i : A) {
		if(!ans[i])
			continue;
		cout << 2 << endl;
		cout << i << " ";
		for(auto u : v[i])
			if(mark[u] > mark[i])
				cout << u << " ";
		cout << endl;
		return;
	}
	cout << -1 << endl;
	return;
}

int32_t main() {
	use_fast;
	int t;
    cin >> t;
    while(t--)
        solve();
	return 0;
}

Tutorial is loading...

prepared by Mehrdad_Sohrabi Editorial by Mehrdad_Sohrabi

official solution

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=200010, LOG=20;

ll n, m, k, u, v, x, y, t, a, b, ans;
ll A[MAXN];
ll seg[MAXN<<2], lazy[MAXN<<2];
int Mn[MAXN<<2], Mx[MAXN<<2];

void Build(int id, int tl, int tr){
	if (tr-tl==1){
		Mn[id]=Mx[id]=seg[id]=A[tl];
		return ;
	}
	int mid=(tl+tr)>>1;
	Build(id<<1, tl, mid);
	Build(id<<1 | 1, mid, tr);
	Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);
	Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);
	seg[id]=seg[id<<1] + seg[id<<1 | 1];	
}
inline void add_lazy(int id, int len, ll val){
	Mn[id]=val;
	Mx[id]=val;
	lazy[id]=val;
	seg[id]=len*val;
}
inline void shift(int id, int tl, int tr){
	if (!lazy[id]) return ;
	int mid=(tl+tr)>>1;
	add_lazy(id<<1, mid-tl, lazy[id]);
	add_lazy(id<<1 | 1, tr-mid, lazy[id]);
	lazy[id]=0;
}
void Maximize(int id, int tl, int tr, int pos, ll val){
	if (pos<=tl || val<=Mn[id]) return ;
	if (tr<=pos && Mx[id]<=val){
		add_lazy(id, tr-tl, val);
		return ;
	}
	shift(id, tl, tr);
	int mid=(tl+tr)>>1;
	Maximize(id<<1, tl, mid, pos, val);
	Maximize(id<<1 | 1, mid, tr, pos, val);
	Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);
	Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);
	seg[id]=seg[id<<1] + seg[id<<1 | 1];
}
int BS1(int id, int tl, int tr, int pos, ll val){
	if (tr<=pos || val<Mn[id]) return tr;
	if (tr-tl==1) return tl;
	shift(id, tl, tr);
	int mid=(tl+tr)>>1, tmp=BS1(id<<1, tl, mid, pos, val);
	if (tmp==mid) return BS1(id<<1 | 1, mid, tr, pos, val);
	return tmp;
}
int BS2(int id, int tl, int tr, ll val){
	if (seg[id]<=val) return tr;
	if (tr-tl==1) return tl;
	shift(id, tl, tr);
	int mid=(tl+tr)>>1, tmp=BS2(id<<1, tl, mid, val);
	if (tmp<mid) return tmp;
	return BS2(id<<1 | 1, mid, tr, val-seg[id<<1]);
}
ll Get(int id, int tl, int tr, int l, int r){
	if (r<=tl || tr<=l) return 0;
	if (l<=tl && tr<=r) return seg[id];
	shift(id, tl, tr);
	int mid=(tl+tr)>>1;
	return Get(id<<1, tl, mid, l, r) + Get(id<<1 | 1, mid, tr, l, r);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<=n; i++) cin>>A[i];
	Build(1, 1, n+1);
	while (m--){
		cin>>t>>x>>y;
		if (t==1) Maximize(1, 1, n+1, x+1, y);
		else{
			ans=0;
			while (1){
				x=BS1(1, 1, n+1, x, y);
				if (x==n+1) break ;
				ll val=y+Get(1, 1, n+1, 1, x);
				int xx=BS2(1, 1, n+1, val);
				// buy [x, xx)
				ans+=xx-x;
				y-=Get(1, 1, n+1, x, xx);
				x=xx;
			}
			cout<<ans<<"\n";
		}
	}
	
	return 0;
}

Tutorial is loading...

prepared by Mehrdad_Sohrabi Editorial by Mehrdad_Sohrabi

official solution

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int MAXN=505, LOG=20;

ll n, m, k, u, v, x, y, t, a, b, ans, mod;
ll dp1[MAXN], dp2[MAXN];
ll dp3[MAXN][MAXN], dp4[MAXN][MAXN];
ll C[MAXN][MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>mod;
	
	for (int i=0; i<MAXN; i++){
		C[i][0]=C[i][i]=1;
		for (int j=1; j<i; j++) C[i][j]=(C[i-1][j] + C[i-1][j-1])%mod;
	}
	dp1[0]=1;
	for (int n=1; n<MAXN; n++){
		for (int i=1; i<=n; i++) dp1[n]=(dp1[n] + dp1[i-1]*dp1[n-i]%mod*C[n-1][i-1])%mod;
		dp1[n]=(n+1)*dp1[n]%mod;
		for (int i=1; i<=n; i++){
			dp2[n]=(dp2[n] + (n+1)*C[n-1][i-1]%mod*((dp1[i-1]*dp2[n-i] + dp2[i-1]*dp1[n-i])%mod))%mod;
			dp2[n]=(dp2[n] + C[n-1][i-1]*dp1[i-1]%mod*dp1[n-i]%mod*((i*(i-1)/2+(n-i)*(n-i+1)/2)%mod))%mod;
		}
	}
	
	dp3[0][0]=1;
	for (int n=1; n<MAXN; n++){
		for (int m=0; m<n; m++){
			dp3[n][m]=dp3[n-1][m];
			dp4[n][m]=dp4[n-1][m];
			for (int i=1; i<=m; i++){
				dp3[n][m]=(dp3[n][m] + dp3[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;
				dp4[n][m]=(dp4[n][m] + dp3[n-i-1][m-i]*dp2[i]%mod*C[m][i])%mod;
				dp4[n][m]=(dp4[n][m] + dp4[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;
			}
		}
		dp3[n][n]=dp1[n];
		dp4[n][n]=dp2[n];
	}

	cout<<dp4[n][m]<<"\n";	
	
	return 0;
}

O(n2) solution

// And you curse yourself for things you never done
// Shayan.P  2020-08-29

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 510, inf = 1e9 + 10, mod=1e9+7;

ll n, m;

ll Pow(ll a, ll b){
    b = (b + (mod-1)) % (mod-1); // to handle b == -1
    int ans=1;
    for(; b; b>>=1, a=a*a%mod) if (b&1) ans=ans*a%mod;
    return ans;
}
inline void add(ll &a, ll b){
    a = (a + b) % mod;
}
    
ll fac[maxn], ifac[maxn];

ll C(ll n, ll k){
	if (n<k || k<0) return 0;
	return fac[n]*ifac[k]%mod*ifac[n-k]%mod;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
    
    fac[0] = 1;
    for(int i = 1; i < maxn; i++) fac[i]=fac[i-1]*i%mod;
    ifac[maxn-1] = Pow(fac[maxn-1], mod-2);
    for(int i = maxn-2; i >= 0; i--) ifac[i]=ifac[i+1]*(i+1)%mod;
    
    cin >> n >> m;
    ++n; //!
    
	int ans = 0;
    for(ll bef = 0; bef < m; bef++){
		for(ll w = 1; w + bef < m; w++){ // corner case : bef == 0
			ll cnt1=Pow(w+1, w-1)*Pow(2, w)%mod;
			ll cnt2=Pow(n-w-1, bef-1)*Pow(2, bef)%mod*(n-w-1-bef)%mod;
			ll cnt=cnt1*cnt2%mod*C(w+bef, bef)%mod;
			ll score=w*(w+1)%mod*n%mod;
			ll after=Pow(n, m-bef-w-1)*Pow(2, m-bef-w-1) % mod;
			ans=(ans + cnt*score%mod*after) % mod;
		}
    }    
    cout << 1ll * (n-m) * ans % mod * Pow(n, -1) % mod << "\n";
    return 0;
}

Tutorial is loading...

Prepared by AliShahali1382 Editorial by AliShahali1382

official solution

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=400010, LOG=30;

int n, m, k, u, v, x, y, t, a, b, root, ans;
pii A[MAXN], V[MAXN];
int par[MAXN], sum[MAXN];
bool is[MAXN];
vector<int> G[MAXN], grundy;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int GetH(pii p){ return p.first+p.second;}
inline pii GetPar(pii p, int k){
	int x=p.first, y=p.second;
	while (k){
		int xx=(x&-x), yy=(y&-y);
		if (!xx) xx=2*inf;
		if (!yy) yy=2*inf;
		int tmp=min(k, min(xx, yy));
		k-=tmp;
		if (xx<yy) x-=tmp;
		else y-=tmp;
	}
	return {x, y};
}
inline int Zone(pii p, int n){
    if (p.first&(1<<(n-1))) return 2;
    if (p.second&(1<<(n-1))) return 1;
    return 0;
}
void dfs_order(vector<pii> &vec, int n=LOG) {
	if (n==0 || vec.size()==0) return ;
	vector<pii> v[3];
	for (pii p:vec) {
		int z=Zone(p, n);
		p.first&=(1<<(n-1))-1;
		p.second&=(1<<(n-1))-1;
		v[z].pb(p);
    }
	vec.clear();
	for (int i:{0, 1, 2}) dfs_order(v[i], n-1);
	for (pii p:v[0]) if (!p.first) vec.pb(p);
    for (pii p:v[1]) vec.pb({p.first, p.second|(1<<(n-1))});
    for (pii p:v[0]) if (p.first) vec.pb(p);
    for (pii p:v[2]) vec.pb({p.first|(1<<(n-1)), p.second});
}
pii Lca(pii u, pii v, int n=LOG) {
	if (n==0) return {0, 0};
	int zu = Zone(u, n), zv = Zone(v, n);
	if (zu > zv) swap(u, v), swap(zu, zv);
	u.first&=(1<<(n-1))-1;
	u.second&=(1<<(n-1))-1;
	v.first&=(1<<(n-1))-1;
	v.second&=(1<<(n-1))-1;
	if (zu == 1 && zv == 2) return {0, 0};
	if (zu == 2 && zv == 2){
		pii A = Lca(u, v, n-1);
		return {A.first+(1<<(n-1)), A.second};
	}
	if (zu == 1 && zv == 1) {
		pii A = Lca(u, v, n-1);
		return {A.first, A.second+(1<<(n-1))};
	}
	if (zv == 1) return Lca(u, {0, (1<<(n-1))-1}, n-1);
	if (zv == 2) return Lca(u, {(1<<(n-1))-1, 0}, n-1);
	return Lca(u, v, n-1);
}
inline int GetId(pii p){
	return lower_bound(V, V+n, p)-V;
}
inline bool IsPar(pii u, pii v){
	if (GetH(u)>GetH(v)) return 0;
	return GetPar(v, GetH(v)-GetH(u))==u;
}
int dfs(int node){
	for (int v:G[node]) sum[node]+=dfs(v);
	return sum[node];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	vector<pii> vec;
	cin>>m;
	for (int i=0; i<2*m; i++) cin>>A[i].first>>A[i].second, vec.pb(A[i]);
	sort(all(vec));
	vec.resize(unique(all(vec))-vec.begin());
	dfs_order(vec);
	for (int i=vec.size()-1; i; i--) vec.pb(Lca(vec[i], vec[i-1]));
	sort(all(vec));
	vec.resize(unique(all(vec))-vec.begin());
	dfs_order(vec);
	n=vec.size();
	
	debug("sorted")
	
	for (int i=0; i<n; i++) V[i]=vec[i];
	sort(V, V+n);
	vector<int> stk={root=GetId(vec[0])};
	for (int i=1; i<n; i++){
		int v=GetId(vec[i]);
		while (!IsPar(V[stk.back()], V[v])) stk.pop_back();
		par[v]=stk.back();
		G[stk.back()].pb(v);
		stk.pb(v);		
	}
	
	for (int i=0; i<2*m; i+=2){
		int u=GetId(A[i]), v=GetId(A[i+1]), lca=GetId(Lca(A[i], A[i+1]));
		sum[u]++;
		sum[v]++;
		sum[lca]-=2;
		is[lca]=1;
	}
	dfs(root);
	for (int v=0; v<n; v++){
		if (sum[v]){
			grundy.pb(GetH(V[par[v]])+1);
			grundy.pb(GetH(V[v])+1);
		}
		else if (is[v]){
			grundy.pb(GetH(V[v]));
			grundy.pb(GetH(V[v])+1);
		}
	}
	sort(all(grundy));
	vec.clear();
	int last=-1;
	for (int x:grundy){
		if (last==-1){
			if (vec.empty() || vec.back().second<x) last=x;
			else{
				last=vec.back().first;
				vec.pop_back();
			}
		}
		else{
			if (last<x) vec.pb({last, x});
			last=-1;
		}
	}
	ans=2*vec.size();
	if (ans && vec[0].first==0) ans--;
	cout<<ans<<"\n";
	
	return 0;
}

// In The Name Of Allah #include <bits/stdc++.h> #define ss second #define ff first #define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define ret(n) return cout << n, 0 #define se(n) cout << setprecision(n) << fixed #define pb push_back #define ll long long #define ld long double #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") #pragma GCC optimize("no-stack-protector,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; const int N = 200, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20; typedef pair <int, int> pii; char c[N][N]; bool cnt[N][N]; struct node {int x1, y1, x2, y2, x3, y3;} p[5]; vector <node> v; void upd(int x, int y, int tp, bool is) { if(is) v.pb({x + p[tp].x1, y + p[tp].y1, x + p[tp].x2, y + p[tp].y2, x + p[tp].x3, y + p[tp].y3}); else cnt[x + p[tp].x1][y + p[tp].y1] ^= 1, cnt[x + p[tp].x2][y + p[tp].y2] ^= 1, cnt[x + p[tp].x3][y + p[tp].y3] ^= 1; } void solve() { int n, m, od = 0; v.clear(); cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> c[i][j]; if(c[i][j] == '1') od++, cnt[i][j] = true; else cnt[i][j] = false; } } if(od == 0) { cout << 0 << endl; return; } if(n == 1 || m == 1) { cout << -1 << endl; return; } for(int i = 1; i <= n - 2; i++) { for(int j = 1; j <= m; j++) { if(cnt[i][j]) { if(j != m) { v.pb({i, j, i + 1, j, i + 1, j + 1}); cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j + 1] ^= 1; } else { v.pb({i, j, i + 1, j, i + 1, j - 1}); cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j - 1] ^= 1; } } } } for(int i = 1; i <= m - 2; i++) { if(cnt[n - 1][i]) { v.pb({n - 1, i, n - 1, i + 1, n, i + 1}); cnt[n - 1][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; } if(cnt[n][i]) { v.pb({n, i, n - 1, i + 1, n, i + 1}); cnt[n][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; } } for(int msk = 0; msk < (1 << 4); msk++) { for(int j = 0; j < 4; j++) if(msk & (1 << j)) upd(n - 1, m - 1, j, 0); if(!cnt[n - 1][m - 1] && !cnt[n - 1][m] && !cnt[n][m - 1] && !cnt[n][m]) { for(int j = 0; j < 4; j++) if(msk & (1 << j)) upd(n - 1, m - 1, j, 1); break; } for(int j = 0; j < 4; j++) if(msk & (1 << j)) upd(n - 1, m - 1, j, 0); } cout << (int)v.size() << endl; for(auto u : v) cout << u.x1 << " " << u.y1 << " " << u.x2 << " " << u.y2 << " " << u.x3 << " " << u.y3 << endl; } int32_t main(){ use_fast; p[0] = {0, 0, 0, 1, 1, 0}, p[1] = {0, 1, 0, 0, 1, 1}, p[2] = {1, 0, 1, 1, 0, 0}, p[3] = {1, 1, 0, 1, 1, 0}; int t; cin >> t; while(t--) solve(); return 0; }

// In The Name Of Allah #include <bits/stdc++.h> #define ss second #define ff first #define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define se(n) cout << setprecision(n) << fixed #define pb push_back //#define int long long #define ld long double #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") #pragma GCC optimize("no-stack-protector,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; const int N = 1e5 + 100, OO = 1e9 + 7, T = 22, M = 1e9 + 7, P = 6151, SQ = 1300, lg = 22; typedef pair <int, int> pii; int mark[N], deg[N], ct[N]; bool ans[N], can[N]; vector <int> v[N], A; vector <pii> ch[N]; bool cmp(int x, int y) { return mark[x] < mark[y]; } void solve() { int n, m, k; cin >> n >> m >> k; A.clear(); for(int i = 0; i <= n; i++) v[i].clear(), ch[i].clear(), mark[i] = deg[i] = ct[i] = 0, ans[i] = can[i] = false; for(int i = 0; i < m; i++) { int x, y; cin >> x >> y; v[x].pb(y); v[y].pb(x); } if(k > 500) { cout << -1 << endl; return; } set <pii> st; for(int i = 1; i <= n; i++) st.insert({deg[i] = (int)v[i].size(), i}); int cnt = 1; while((int)st.size()) { pii p = *st.begin(); if(p.ff >= k) { cout << 1 << " " << (int)st.size() << endl; for(auto u : st) cout << u.ss << " "; cout << endl; return; } else { st.erase(p); mark[p.ss] = cnt; for(auto u : v[p.ss]) if(!mark[u]) st.erase({deg[u], u}), st.insert({--deg[u], u}); A.pb(p.ss); } cnt++; } for(auto i : A) { int nxt = 0; for(auto u : v[i]) if(mark[u] > mark[i]) ct[nxt++] = u, can[u] = true; for(auto u : ch[i]) if(!can[u.ff]) ans[u.ss] = false; for(int j = 0; j < nxt; j++) can[ct[j]] = false; if(nxt != k - 1) continue; ans[i] = true; sort(ct, ct + nxt, cmp); for(int j = 0; j < nxt; j++) for(int k = j + 1; k < nxt; k++) ch[ct[j]].pb({ct[k], i}); } for(auto i : A) { if(!ans[i]) continue; cout << 2 << endl; cout << i << " "; for(auto u : v[i]) if(mark[u] > mark[i]) cout << u << " "; cout << endl; return; } cout << -1 << endl; return; } int32_t main() { use_fast; int t; cin >> t; while(t--) solve(); return 0; }

#include <bits/stdc++.h> #pragma GCC optimize ("O2,unroll-loops") #pragma GCC optimize("no-stack-protector,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<pii, int> piii; typedef pair<ll, ll> pll; #define debug(x) cerr<<#x<<'='<<(x)<<endl; #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} #define all(x) x.begin(), x.end() #define pb push_back #define kill(x) return cout<<x<<'\n', 0; const int inf=1000000010; const ll INF=10000000000000010LL; const int mod=1000000007; const int MAXN=200010, LOG=20; ll n, m, k, u, v, x, y, t, a, b, ans; ll A[MAXN]; ll seg[MAXN<<2], lazy[MAXN<<2]; int Mn[MAXN<<2], Mx[MAXN<<2]; void Build(int id, int tl, int tr){ if (tr-tl==1){ Mn[id]=Mx[id]=seg[id]=A[tl]; return ; } int mid=(tl+tr)>>1; Build(id<<1, tl, mid); Build(id<<1 | 1, mid, tr); Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]); Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]); seg[id]=seg[id<<1] + seg[id<<1 | 1]; } inline void add_lazy(int id, int len, ll val){ Mn[id]=val; Mx[id]=val; lazy[id]=val; seg[id]=len*val; } inline void shift(int id, int tl, int tr){ if (!lazy[id]) return ; int mid=(tl+tr)>>1; add_lazy(id<<1, mid-tl, lazy[id]); add_lazy(id<<1 | 1, tr-mid, lazy[id]); lazy[id]=0; } void Maximize(int id, int tl, int tr, int pos, ll val){ if (pos<=tl || val<=Mn[id]) return ; if (tr<=pos && Mx[id]<=val){ add_lazy(id, tr-tl, val); return ; } shift(id, tl, tr); int mid=(tl+tr)>>1; Maximize(id<<1, tl, mid, pos, val); Maximize(id<<1 | 1, mid, tr, pos, val); Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]); Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]); seg[id]=seg[id<<1] + seg[id<<1 | 1]; } int BS1(int id, int tl, int tr, int pos, ll val){ if (tr<=pos || val<Mn[id]) return tr; if (tr-tl==1) return tl; shift(id, tl, tr); int mid=(tl+tr)>>1, tmp=BS1(id<<1, tl, mid, pos, val); if (tmp==mid) return BS1(id<<1 | 1, mid, tr, pos, val); return tmp; } int BS2(int id, int tl, int tr, ll val){ if (seg[id]<=val) return tr; if (tr-tl==1) return tl; shift(id, tl, tr); int mid=(tl+tr)>>1, tmp=BS2(id<<1, tl, mid, val); if (tmp<mid) return tmp; return BS2(id<<1 | 1, mid, tr, val-seg[id<<1]); } ll Get(int id, int tl, int tr, int l, int r){ if (r<=tl || tr<=l) return 0; if (l<=tl && tr<=r) return seg[id]; shift(id, tl, tr); int mid=(tl+tr)>>1; return Get(id<<1, tl, mid, l, r) + Get(id<<1 | 1, mid, tr, l, r); } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); cin>>n>>m; for (int i=1; i<=n; i++) cin>>A[i]; Build(1, 1, n+1); while (m--){ cin>>t>>x>>y; if (t==1) Maximize(1, 1, n+1, x+1, y); else{ ans=0; while (1){ x=BS1(1, 1, n+1, x, y); if (x==n+1) break ; ll val=y+Get(1, 1, n+1, 1, x); int xx=BS2(1, 1, n+1, val); // buy [x, xx) ans+=xx-x; y-=Get(1, 1, n+1, x, xx); x=xx; } cout<<ans<<"\n"; } } return 0; }

#include <bits/stdc++.h> #pragma GCC optimize ("O2,unroll-loops") //#pragma GCC optimize("no-stack-protector,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<pii, int> piii; typedef pair<ll, ll> pll; #define debug(x) cerr<<#x<<'='<<(x)<<endl; #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} #define all(x) x.begin(), x.end() #define pb push_back #define kill(x) return cout<<x<<'\n', 0; const ld eps=1e-7; const int inf=1000000010; const ll INF=10000000000000010LL; const int mod=1000000007; const int MAXN=400010, LOG=30; int n, m, k, u, v, x, y, t, a, b, root, ans; pii A[MAXN], V[MAXN]; int par[MAXN], sum[MAXN]; bool is[MAXN]; vector<int> G[MAXN], grundy; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); inline int GetH(pii p){ return p.first+p.second;} inline pii GetPar(pii p, int k){ int x=p.first, y=p.second; while (k){ int xx=(x&-x), yy=(y&-y); if (!xx) xx=2*inf; if (!yy) yy=2*inf; int tmp=min(k, min(xx, yy)); k-=tmp; if (xx<yy) x-=tmp; else y-=tmp; } return {x, y}; } inline int Zone(pii p, int n){ if (p.first&(1<<(n-1))) return 2; if (p.second&(1<<(n-1))) return 1; return 0; } void dfs_order(vector<pii> &vec, int n=LOG) { if (n==0 || vec.size()==0) return ; vector<pii> v[3]; for (pii p:vec) { int z=Zone(p, n); p.first&=(1<<(n-1))-1; p.second&=(1<<(n-1))-1; v[z].pb(p); } vec.clear(); for (int i:{0, 1, 2}) dfs_order(v[i], n-1); for (pii p:v[0]) if (!p.first) vec.pb(p); for (pii p:v[1]) vec.pb({p.first, p.second|(1<<(n-1))}); for (pii p:v[0]) if (p.first) vec.pb(p); for (pii p:v[2]) vec.pb({p.first|(1<<(n-1)), p.second}); } pii Lca(pii u, pii v, int n=LOG) { if (n==0) return {0, 0}; int zu = Zone(u, n), zv = Zone(v, n); if (zu > zv) swap(u, v), swap(zu, zv); u.first&=(1<<(n-1))-1; u.second&=(1<<(n-1))-1; v.first&=(1<<(n-1))-1; v.second&=(1<<(n-1))-1; if (zu == 1 && zv == 2) return {0, 0}; if (zu == 2 && zv == 2){ pii A = Lca(u, v, n-1); return {A.first+(1<<(n-1)), A.second}; } if (zu == 1 && zv == 1) { pii A = Lca(u, v, n-1); return {A.first, A.second+(1<<(n-1))}; } if (zv == 1) return Lca(u, {0, (1<<(n-1))-1}, n-1); if (zv == 2) return Lca(u, {(1<<(n-1))-1, 0}, n-1); return Lca(u, v, n-1); } inline int GetId(pii p){ return lower_bound(V, V+n, p)-V; } inline bool IsPar(pii u, pii v){ if (GetH(u)>GetH(v)) return 0; return GetPar(v, GetH(v)-GetH(u))==u; } int dfs(int node){ for (int v:G[node]) sum[node]+=dfs(v); return sum[node]; } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); vector<pii> vec; cin>>m; for (int i=0; i<2*m; i++) cin>>A[i].first>>A[i].second, vec.pb(A[i]); sort(all(vec)); vec.resize(unique(all(vec))-vec.begin()); dfs_order(vec); for (int i=vec.size()-1; i; i--) vec.pb(Lca(vec[i], vec[i-1])); sort(all(vec)); vec.resize(unique(all(vec))-vec.begin()); dfs_order(vec); n=vec.size(); debug("sorted") for (int i=0; i<n; i++) V[i]=vec[i]; sort(V, V+n); vector<int> stk={root=GetId(vec[0])}; for (int i=1; i<n; i++){ int v=GetId(vec[i]); while (!IsPar(V[stk.back()], V[v])) stk.pop_back(); par[v]=stk.back(); G[stk.back()].pb(v); stk.pb(v); } for (int i=0; i<2*m; i+=2){ int u=GetId(A[i]), v=GetId(A[i+1]), lca=GetId(Lca(A[i], A[i+1])); sum[u]++; sum[v]++; sum[lca]-=2; is[lca]=1; } dfs(root); for (int v=0; v<n; v++){ if (sum[v]){ grundy.pb(GetH(V[par[v]])+1); grundy.pb(GetH(V[v])+1); } else if (is[v]){ grundy.pb(GetH(V[v])); grundy.pb(GetH(V[v])+1); } } sort(all(grundy)); vec.clear(); int last=-1; for (int x:grundy){ if (last==-1){ if (vec.empty() || vec.back().second<x) last=x; else{ last=vec.back().first; vec.pop_back(); } } else{ if (last<x) vec.pb({last, x}); last=-1; } } ans=2*vec.size(); if (ans && vec[0].first==0) ans--; cout<<ans<<"\n"; return 0; }

#include <algorithm> #include <iostream> using namespace std; #define all(x) (x).begin(), (x).end() int main() { int q; cin >> q; while (q-->0) /// For each query { /// Input int n, m; cin >> n >> m; string s[n]; for (int i = 0; i < n; ++i) cin >> s[i]; /// Calculation int cnt = 0; for (int i = 0; i < n; ++i) /// For each '1' appear cnt += 3 * count(all(s[i]), '1'); /// We use 3 operations to turn off it /// These operations are independent /// Output the result cout << cnt << '\n'; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (s[i][j] == '1') { int cx = i + 1; /// +1 because we use 0-based loop int cy = j + 1; /// +1 because we use 0-based loop int px = (cx < n) ? cx + 1 : cx - 1; /// Next row int py = (cy < m) ? cy + 1 : cy - 1; /// Next col /// Notice that these operation are independent /// They wont affect others cells, just turn off [i][j] cout << px << ' ' << cy << ' '; /// X O | + + | O X cout << cx << ' ' << py << ' '; /// O O | + _ | X O cout << cx << ' ' << cy << '\n'; /// Operation: 1 -> 2 cout << px << ' ' << cy << ' '; /// O X | + _ | X X cout << px << ' ' << py << ' '; /// X O | + + | O X cout << cx << ' ' << cy << '\n'; /// Operation: 2 -> 3 cout << cx << ' ' << py << ' '; /// X X | + + | O O cout << px << ' ' << py << ' '; /// O X | _ + | O O cout << cx << ' ' << cy << '\n'; /// Operation: 3 -> 0 } } } } return 0; }

#include <algorithm> #include <iostream> #include <vector> using namespace std; #define all(x) (x).begin(), (x).end() /// Each line of the answer struct node { int a, b, c, d, e, f; node (int a, int b, int c, int d, int e, int f) : a(a), b(b), c(c), d(d), e(e), f(f) {} }; vector<node> res; vector<vector<int> > a; void flip(const node &x) { a[x.a][x.b] ^= 1; a[x.c][x.d] ^= 1; a[x.e][x.f] ^= 1; res.push_back(x); } int main() { int q; cin >> q; while (q-->0) /// For each query { /// Input int n, m; cin >> n >> m; /// Initalization res.clear(); a.assign(n + 1, vector<int>(m + 1, 0)); for (int i = 1; i <= n; ++i) { string s; cin >> s; for (int j = 1; j <= m; ++j) a[i][j] = s[j - 1] - '0'; /// Convert string to array } /// Odd column elimination if (m & 1) { for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once { if (a[i0][m] == 0) continue; int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1); if (a[i1][m]) flip(node(i0,m-0 , i1,m-0 , i0,m-1)); else flip(node(i0,m-0 , i0,m-1 , i1,m-1)); } --m; /// <- Last col eliminated } /// Row Elimination: n * m -> 2 * m remaining while (n > 2) { for (int j0 = 1; j0 <= m; ++j0) /// Eliminate 2x1 cells by once { if (a[n][j0] == 0) continue; int j1 = (j0 == m) ? (j0 - 1) : (j0 + 1); if (a[n][j1]) flip(node(n-0,j0 , n-0,j1 , n-1,j0)); else flip(node(n-0,j0 , n-1,j0 , n-1,j1)); } --n; /// <- Last row eliminated } /// Col Elimination: 2 * m -> 2 * 2 remaining while (m > 2) { for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once { if (a[i0][m] == 0) continue; int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1); if (a[i1][m]) flip(node(i0,m-0 , i1,m-0 , i0,m-1)); else flip(node(i0,m-0 , i0,m-1 , i1,m-1)); } --m; /// <- Last col eliminated } /// Cells Elimination: 2 * 2 -> 0 * 0 remaining int x = 0, y = 0, z = 0, t = 0; if (a[1][1]) x ^= 0, y ^= 1, z ^= 1, t ^= 1; if (a[2][1]) x ^= 1, y ^= 0, z ^= 1, t ^= 1; if (a[1][2]) x ^= 1, y ^= 1, z ^= 0, t ^= 1; if (a[2][2]) x ^= 1, y ^= 1, z ^= 1, t ^= 0; if (x) flip(node(2,1 , 1,2 , 2,2)); if (y) flip(node(1,1 , 1,2 , 2,2)); if (z) flip(node(1,1 , 2,1 , 2,2)); if (t) flip(node(1,1 , 2,1 , 1,2)); /// Output the result cout << res.size() << '\n'; for (const node &x : res) { cout << x.a << ' ' << x.b << ' '; cout << x.c << ' ' << x.d << ' '; cout << x.e << ' ' << x.f << '\n'; } } return 0; }

#include <algorithm> #include <iostream> #include <vector> using namespace std; #define all(x) (x).begin(), (x).end() /// Each line of the answer struct node { int a, b, c, d, e, f; node (int a, int b, int c, int d, int e, int f) : a(a), b(b), c(c), d(d), e(e), f(f) {} }; int counter = 0; vector<vector<int> > a; void flip(const node &x) { a[x.a][x.b] ^= 1; a[x.c][x.d] ^= 1; a[x.e][x.f] ^= 1; ++counter; } int main() { int QN, QM; cin >> QN >> QM; int total = 0, res = 0, bestgen = 0; int lim = 1 << min(20, QN * QM); for (int mask = 0; mask < lim; ++mask) { /// Initalization int n = QN; int m = QM; counter = 0; a.assign(n + 1, vector<int>(m + 1, 0)); int gen = mask; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { a[i][j] = gen & 1; gen >>= 1; } } /// Odd column elimination if (m & 1) { for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once { if (a[i0][m] == 0) continue; int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1); if (a[i1][m]) flip(node(i0,m-0 , i1,m-0 , i0,m-1)); else flip(node(i0,m-0 , i0,m-1 , i1,m-1)); } --m; /// <- Last col eliminated } /// Row Elimination: n * m -> 2 * m remaining while (n > 2) { for (int j0 = 1; j0 <= m; ++j0) /// Eliminate 2x1 cells by once { if (a[n][j0] == 0) continue; int j1 = (j0 == m) ? (j0 - 1) : (j0 + 1); if (a[n][j1]) flip(node(n-0,j0 , n-0,j1 , n-1,j0)); else flip(node(n-0,j0 , n-1,j0 , n-1,j1)); } --n; /// <- Last row eliminated } /// Col Elimination: 2 * m -> 2 * 2 remaining while (m > 2) { for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once { if (a[i0][m] == 0) continue; int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1); if (a[i1][m]) flip(node(i0,m-0 , i1,m-0 , i0,m-1)); else flip(node(i0,m-0 , i0,m-1 , i1,m-1)); } --m; /// <- Last col eliminated } /// Cells Elimination: 2 * 2 -> 0 * 0 remaining int x = 0, y = 0, z = 0, t = 0; if (a[1][1]) x ^= 0, y ^= 1, z ^= 1, t ^= 1; if (a[2][1]) x ^= 1, y ^= 0, z ^= 1, t ^= 1; if (a[1][2]) x ^= 1, y ^= 1, z ^= 0, t ^= 1; if (a[2][2]) x ^= 1, y ^= 1, z ^= 1, t ^= 0; if (x) flip(node(2,1 , 1,2 , 2,2)); if (y) flip(node(1,1 , 1,2 , 2,2)); if (z) flip(node(1,1 , 2,1 , 2,2)); if (t) flip(node(1,1 , 2,1 , 1,2)); /// Checker for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (a[i][j] == 1) { cout << "Program failed at this gen:\n"; for (int i = 1; i <= QN; ++i) { for (int j = 1; j <= QM; ++j) { cout << (mask & 1); mask >>= 1; } cout << '\n'; } return 0; } } } /// Analizer total += counter; if (res < counter) { res = counter; bestgen = mask; } } /// Analizer cout << "You used " << total << " times of flipping !\n"; cout << "It need " << res << " times for this gen:\n"; for (int i = 1; i <= QN; ++i) { for (int j = 1; j <= QM; ++j) { cout << (bestgen & 1); bestgen >>= 1; } cout << '\n'; } cout << "Compared to expected number = " << res << " / " << QN * QM; return 0; }

#include <algorithm> #include <iostream> #include <vector> using namespace std; #define all(x) (x).begin(), (x).end() /// Each line of the answer struct node { int a, b, c, d, e, f; node (int a, int b, int c, int d, int e, int f) : a(a), b(b), c(c), d(d), e(e), f(f) {} }; int counter = 0; vector<vector<int> > a; void flip(int x, int y, int u, int v) { a[x][y] ^= 1; a[u][v] ^= 1; counter += 2; } int main() { int QN, QM; cin >> QN >> QM; int total = 0, res = 0, bestgen = 0; int lim = 1 << min(20, QN * QM); for (int mask = 0; mask < lim; ++mask) { /// Initalization int n = QN; int m = QM; counter = 0; a.assign(n + 1, vector<int>(m + 1, 0)); int gen = mask; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { a[i][j] = gen & 1; gen >>= 1; } } int counter = 0; auto perform = [&](pair<int, int> start, pair<int, int> leave) { for (auto x : {start.first, start.first + 1}) for (auto y : {start.second, start.second + 1}) { if (x == leave.first && y == leave.second) continue; a[x][y] = 1 + 0 - a[x][y]; } ++counter; }; // if (n == 2 && m == 2) auto pick_and_perform = [&](int x, int y, int c) { for (auto dx : {0, 1}) for (auto dy : {0, 1}) if (a[x + dx][y + dy] == c) { perform({x, y}, {x + dx, y + dy}); return; } }; auto solveblock = [&](int x, int y) { vector<pair<int, int>> ones; for (auto dx : {0, 1}) for (auto dy : {0, 1}) if (a[x + dx][y + dy] == 1) ones.push_back({x + dx, y + dy}); int i = x, j = y; if (ones.size() == 1) { pick_and_perform(i, j, 0); pick_and_perform(i, j, 1); pick_and_perform(i, j, 0); } else if (ones.size() == 2) { pick_and_perform(i, j, 1); pick_and_perform(i, j, 0); } else if (ones.size() == 3) pick_and_perform(i, j, 0); else if (ones.size() == 4) { pick_and_perform(i, j, 1); pick_and_perform(i, j, 0); pick_and_perform(i, j, 1); pick_and_perform(i, j, 0); } }; for (size_t i = 0; i + 2 < n; i += 1) { for (size_t j = 0; j + 1 < m; j += 2) { if (a[i][j] == a[i][j + 1]) { if (a[i][j] == 1) perform({i, j}, {i + 1, j}); } else if (a[i][j] == 1) perform({i, j}, {i, j + 1}); else if (a[i][j + 1] == 1) perform({i, j}, {i, j}); } if (m & 1) { if (a[i][m - 1] == 1) perform({i, m - 2}, {i, m - 2}); } } int i = n - 2; for (size_t j = 0; j + 2 < m; j += 1) { if (a[i][j] == a[i + 1][j]) { if (a[i][j] == 1) perform({i, j}, {i, j + 1}); } else if (a[i][j] == 1) perform({i, j}, {i + 1, j}); else if (a[i + 1][j] == 1) perform({i, j}, {i, j}); } solveblock(n - 2, m - 2); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == 1) { cout << "Program failed at this gen:\n"; for (int i = 0; i < QN; ++i) { for (int j = 0; j < QM; ++j) { cout << (mask & 1); mask >>= 1; } cout << '\n'; } return 0; } } } total += counter; if (res < counter) { res = counter; bestgen = mask; } } cout << "You used " << total << " times of flipping !\n"; cout << "It need " << res << " times for this gen:\n"; for (int i = 0; i < QN; ++i) { for (int j = 0; j < QM; ++j) { cout << (bestgen & 1); bestgen >>= 1; } cout << '\n'; } cout << "Compared to expected number = " << res << " / " << QN * QM; return 0; }

#include <algorithm> #include <iostream> #include <vector> using namespace std; #define all(x) (x).begin(), (x).end() /// Each line of the answer struct node { int a, b, c, d, e, f; node (int a, int b, int c, int d, int e, int f) : a(a), b(b), c(c), d(d), e(e), f(f) {} }; int counter = 0; vector<vector<int> > a; void flip(const node &x) { a[x.a][x.b] ^= 1; a[x.c][x.d] ^= 1; a[x.e][x.f] ^= 1; ++counter; } int main() { int QN, QM; cin >> QN >> QM; int total = 0, res = 0, bestgen = 0; int lim = 1 << min(20, QN * QM); for (int mask = 0; mask < lim; ++mask) { /// Initalization int n = QN; int m = QM; counter = 0; a.assign(n + 1, vector<int>(m + 1, 0)); int gen = mask; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { a[i][j] = gen & 1; gen >>= 1; } } /// Odd column elimination if (m & 1) { for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once { if (a[i0][m] == 0) continue; int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1); if (a[i1][m]) flip(node(i0,m-0 , i1,m-0 , i0,m-1)); else flip(node(i0,m-0 , i0,m-1 , i1,m-1)); } --m; /// <- Last col eliminated } /// Row Elimination: n * m -> 2 * m remaining while (n > 2) { for (int j0 = 1; j0 <= m; ++j0) /// Eliminate 2x1 cells by once { if (a[n][j0] == 0) continue; int j1 = (j0 == m) ? (j0 - 1) : (j0 + 1); if (a[n][j1]) flip(node(n-0,j0 , n-0,j1 , n-1,j0)); else flip(node(n-0,j0 , n-1,j0 , n-1,j1)); } --n; /// <- Last row eliminated } /// Col Elimination: 2 * m -> 2 * 2 remaining while (m > 2) { for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once { if (a[i0][m] == 0) continue; int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1); if (a[i1][m]) flip(node(i0,m-0 , i1,m-0 , i0,m-1)); else flip(node(i0,m-0 , i0,m-1 , i1,m-1)); } --m; /// <- Last col eliminated } /// Cells Elimination: 2 * 2 -> 0 * 0 remaining int x = 0, y = 0, z = 0, t = 0; if (a[1][1]) x ^= 0, y ^= 1, z ^= 1, t ^= 1; if (a[2][1]) x ^= 1, y ^= 0, z ^= 1, t ^= 1; if (a[1][2]) x ^= 1, y ^= 1, z ^= 0, t ^= 1; if (a[2][2]) x ^= 1, y ^= 1, z ^= 1, t ^= 0; if (x) flip(node(2,1 , 1,2 , 2,2)); if (y) flip(node(1,1 , 1,2 , 2,2)); if (z) flip(node(1,1 , 2,1 , 2,2)); if (t) flip(node(1,1 , 2,1 , 1,2)); /// Checker for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (a[i][j] == 1) { cout << "Program failed at this gen:\n"; for (int i = 1; i <= QN; ++i) { for (int j = 1; j <= QM; ++j) { cout << (mask & 1); mask >>= 1; } cout << '\n'; } return 0; } } } /// Analizer total += counter; if (res < counter) { res = counter; bestgen = mask; } } /// Analizer cout << "You used " << total << " times of flipping !\n"; cout << "It need " << res << " times for this gen:\n"; for (int i = 1; i <= QN; ++i) { for (int j = 1; j <= QM; ++j) { cout << (bestgen & 1); bestgen >>= 1; } cout << '\n'; } cout << "Compared to expected number = " << res << " / " << QN * QM; return 0; }

// In The Name Of Allah // Mohammad Hosseini #include <bits/stdc++.h> #define ss second #define ff first #define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define se(n) cout << setprecision(n) << fixed #define pb push_back //#define int long long #define ld long double #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") #pragma GCC optimize("no-stack-protector,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; const int N = 1e5 + 100, OO = 1e9 + 7, T = 22, M = 1e9 + 7, P = 6151, SQ = 1300, lg = 22; typedef pair <int, int> pii; int mark[N], deg[N], ct[N]; bool ans[N], can[N]; vector <int> v[N], A; vector <pii> ch[N]; bool cmp(int x, int y) { return mark[x] < mark[y]; } void solve() { int n, m, k; cin >> n >> m >> k; A.clear(); for(int i = 0; i <= n; i++) v[i].clear(), ch[i].clear(), mark[i] = deg[i] = ct[i] = 0, ans[i] = can[i] = false; for(int i = 0; i < m; i++) { int x, y; cin >> x >> y; v[x].pb(y); v[y].pb(x); } if(k > 500) { cout << -1 << endl; return; } set <pii> st; for(int i = 1; i <= n; i++) st.insert({deg[i] = (int)v[i].size(), i}); int cnt = 1; while((int)st.size()) { pii p = *st.begin(); if(p.ff >= k) { cout << 1 << " " << (int)st.size() << endl; for(auto u : st) cout << u.ss << " "; cout << endl; return; } else { st.erase(p); mark[p.ss] = cnt; for(auto u : v[p.ss]) if(!mark[u]) st.erase({deg[u], u}), st.insert({--deg[u], u}); A.pb(p.ss); } cnt++; } // start of finding clique for(auto i : A) { int nxt = 0; for(auto u : v[i]) if(mark[u] > mark[i]) ct[nxt++] = u, can[u] = true; for(auto u : ch[i]) if(!can[u.ff]) ans[u.ss] = false; for(int j = 0; j < nxt; j++) can[ct[j]] = false; if(nxt != k-1) continue; ans[i] = true; sort(ct, ct + nxt, cmp); for(int j = 0; j < nxt; j++) for(int k = j + 1; k < nxt; k++) ch[ct[j]].pb({ct[k], i}); } // end for(auto i : A) { if(!ans[i]) continue; cout << 2 << endl; cout << i << " "; for(auto u : v[i]) if(mark[u] > mark[i]) cout << u << " "; cout << endl; return; } cout << -1 << endl; return; } int32_t main() { use_fast; int t; cin >> t; while(t--) solve(); return 0; }

#include <bits/stdc++.h> #pragma GCC optimize ("O2,unroll-loops") //#pragma GCC optimize("no-stack-protector,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<pii, int> piii; typedef pair<ll, ll> pll; #define debug(x) cerr<<#x<<'='<<(x)<<endl; #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} #define all(x) x.begin(), x.end() #define pb push_back #define kill(x) return cout<<x<<'\n', 0; #define SZ(x) ((int)x.size()) const ld eps=1e-7; const int inf=1000000010; const ll INF=10000000000000010LL; const int mod=998244353; const int MAXN=100010, LOG=18, N=(1<<LOG); typedef vector<ll> Poly; ll n, m, k, u, v, x, y, t, a, b, ans; ll dp1[MAXN], dp2[MAXN]; ll F[MAXN], I[MAXN]; int rev[N]; Poly A, B, C, constant; ll powmod(ll a, ll b){ if (a==1) return 1; if (b<0) b+=mod-1; ll res=1; for (; b; b>>=1, a=a*a%mod) if (b&1) res=res*a%mod; return res; } ll nCr(ll n, ll r){ if (r<0 || r>n) return 0; return F[n]*I[r]%mod*I[n-r]%mod; } ll Solve(ll n, ll m){ return powmod(2, m)*powmod(n+1, m-1)%mod*(n+1-m)%mod; } void NTT(Poly &A, bool inv){ int n=A.size(), lg=0; while ((1<<lg)<n) lg++; for (int i=1; i<n; i++){ rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1)); if (rev[i]<i) swap(A[i], A[rev[i]]); } for (int ln=1; ln<n; ln<<=1){ ll wn=powmod(5, mod/2/ln); if (inv) wn=powmod(wn, mod-2); for (int i=0; i<n; i+=2*ln){ ll w=1; for (int j=i; j<i+ln; j++){ ll x=A[j], y=A[j+ln]*w; A[j]=(x+y)%mod; A[j+ln]=(x-y)%mod; w=w*wn%mod; } } } if (inv){ ll invn=powmod(n, mod-2); for (int i=0; i<n; i++) A[i]=A[i]*invn%mod; } } Poly Mul(Poly X, Poly Y){ /* Poly Z(SZ(X)+SZ(Y)-1, 0); for (int i=0; i<SZ(X); i++) for (int j=0; j<SZ(Y); j++) Z[i+j]=(Z[i+j] + X[i]*Y[j])%mod; return Z; */ int n=SZ(X)+SZ(Y)-1; while (n&(n-1)) n+=(n&-n); X.resize(n, 0); Y.resize(n, 0); NTT(X, 0); NTT(Y, 0); for (int i=0; i<n; i++) X[i]=X[i]*Y[i]%mod; NTT(X, 1); return X; } void divide(int tl, int tr){ if (tr-tl==1){ dp2[tl]=(2*(tl+1)*dp2[tl] + constant[tl-1])%mod; dp2[tl]=dp2[tl]*F[tl-1]%mod; return ; } int mid=(tl+tr)>>1; divide(tl, mid); A.resize(tr-tl+1, 0); B.resize(mid-tl); for (int i=0; i<SZ(A); i++) A[i]=dp1[i]*I[i]%mod; for (int i=0; i<SZ(B); i++) B[i]=dp2[tl+i]*I[tl+i]%mod; C=Mul(A, B); for (int i=0; i<SZ(C); i++){ int x=tl+i+1; if (x<mid || tr<=x) continue ; dp2[x]=(dp2[x] + C[i])%mod; } divide(mid, tr); } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); F[0]=1; for (int i=1; i<MAXN; i++) F[i]=F[i-1]*i%mod; I[MAXN-1]=powmod(F[MAXN-1], mod-2); for (int i=MAXN-1; i; i--) I[i-1]=I[i]*i%mod; A.resize(MAXN+1); B.resize(MAXN); for (int n=0; n<MAXN; n++){ dp1[n]=powmod(n+1, n-1)*powmod(2, n)%mod; A[n]=dp1[n]*I[n]%mod; B[n]=A[n]*n%mod*(n+1)%mod; } constant=Mul(A, B); divide(1, MAXN); cin>>n>>m; for (int len=1; len<=m; len++){ ll res=nCr(m, len)*dp2[len]%mod; // res=res*(n+1)%mod; res=res*Solve(n+1-len-2, m-len)%mod; ans=(ans + res)%mod; } ans=ans*(n-m+1)%mod; if (ans<0) ans+=mod; cout<<ans<<"\n"; return 0; } /* 100 50 ans: 221097228 */

Комментарии (111)

Показать архивные | Написать комментарий?

Mehrdad_Sohrabi

4 года назад, # |

Auto comment: topic has been updated by Mehrdad_Sohrabi (previous revision, new revision, compare).

→ Ответить

Mohammad.H915

4 года назад, # ^ |

+26

Codes of Problems

1440A

1440B

1440C, 1439A

1440D, 1439B

1440E, 1439C

1439D

1439E

manoj_269

← Rev. 2 →

-8

Hi, Can you tell me whats wrong in my code 98818397 for problem E (div 2).

UPD: I have misread the question, mybad.

cup_cake

can you please provide the codes?? :)

+31

Now is 2 am In Tehran, We will done it tomorrow as soon as possible.

+11

ok no problem.

thank you :)

lrvideckis

I've honestly never found much value in problem setter's code. I always just try to implement the ideas described in the editorial.

Anyways why not look at contestant's code?

SPyofgame

← Rev. 19 →

-26

Here are some implementations, I will update these more

Problem A - O(n * k) solution - Bruteforces

#include <algorithm>
#include <iostream>

using namespace std;

template<typename T> void maximize(T &res, T val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, T val) { if (res > val) res = val; }
int main()
{
    int q;
    cin >> q;
    
    while (q-->0) // For each query
    {
        int n, c0, c1, h;
        cin >> n >> c0 >> c1 >> h;
        
        string s;
        cin >> s;
        int n0 = count(s.begin(), s.end(), '0'); /// n0 = number of zeros
        int n1 = count(s.begin(), s.end(), '1'); /// n1 = number of ones

        int res = 1e9; /// +INF
        for (int t = 0; t <= n0; ++t) minimize(res, t * h + (n0 - t) * c0 + (n1 + t) * c1); /// Change t times (0->1)
        for (int t = 0; t <= n1; ++t) minimize(res, t * h + (n0 + t) * c0 + (n1 - t) * c1); /// Change t times (1->0)
        cout << res << '\n';
    }
    return 0;
}

Problem A - O(n) solution - Math

#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int q;
    cin >> q;
    
    while (q-->0) // For each query
    {
        int n, c0, c1, h;
        cin >> n >> c0 >> c1 >> h;
        
        string s;
        cin >> s;
        int n0 = count(s.begin(), s.end(), '0'); /// n0 = number of zeros
        int n1 = count(s.begin(), s.end(), '1'); /// n1 = number of ones
        
        int none_change = n0 * (c0 + 0) + n1 * (c1 + 0); /// Current cost
        int change_to_0 = n0 * (c0 + 0) + n1 * (c0 + h); /// Cost when change all to zeros
        int change_to_1 = n0 * (c1 + h) + n1 * (c1 + 0); /// Cost when change all to ones
        cout << min({none_change, change_to_0, change_to_1}) << '\n';
    }
    return 0;
}

Problem B - O(n*k) Offline solution

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int q;
    cin >> q;
    
    while (q-->0)
    {
        /// Input
        int n, k;
        cin >> n >> k;
        
        vector<int> a(n * k);
        for (int &x : a) cin >> x;
        



        /// Calculation
        int shift = n / 2 + 1; /// Median
        long long res = 0;
        for (int i = 1; i <= k; ++i)
            res += a[a.size() - i * shift]; /// Find median of ith group
        
        cout << res << '\n';
        
    }
    return 0;
}

Problem B - O(n*k) Online Solution

#include <algorithm>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main()
{
    int q;
    cin >> q;
    
    while (q-->0) /// For each query
    {
        int n, k;
        cin >> n >> k;

        int length = n * k;
        int median = n / 2 + 1;

        /// We dont need array, but it only work if the array have been already sorted
        long long res = 0;
        int pos = k * (n - median); /// Next median
        for (int index = 0; index < length; ++index)
        {
            int value;
            cin >> value;

            if (index == pos)
            {
                res += value;  /// Sumation of medians
                pos += median; /// Find next median
            }
        }
        
        cout << res << '\n';
    }
    return 0;
}

Problem C1 - O(nm) solution - operations <= 3nm - Simple Greedy

Problem C2 - O(nm) solution - operations <= nm - Greedy

Problem C2 analizer for above AC code

Problem C2 analizer report for all cases with (n = 5, m = 4)

You used 8192000 times of flipping !
It need 12 times for this gen:
1001
0000
0000
0000
1010
Compared to expected number = 12 / 20

tumhari_mummy

+46

I may get downvotes, but O(3nm) and O(3nm/4) are the same. If you want to compare constants don't use big O notation.

Ok then, but actually the result is also ≈ $$$O(f(x))$$$, what should I write then

kartik8800

try this
Problem C2 <= (3nm/4) operations solution

I updated and also add an extra solution

Shahraaz

this is an overkill but we can in fact solve each row in $$$\frac{m+1}{2}$$$ steps,

idea is to consider in each row as many columns of size 2 and solve each block of size 2 as follows

11 : chose block with left most point at i,j and dont flip i+1,j

01 : chose block with left most point at i,j and dont flip i,j

10 : chose block with left most point at i,j and dont flip i,j+1

00 : chill

code

    for (size_t i = 0; i + 2 < n; i += 1)
    {
        for (size_t j = 0; j + 1 < m; j += 2)
        {
            if (vecc[i][j] == vecc[i][j + 1])
            {
                if (vecc[i][j] == '1')
                    perform({i, j}, {i + 1, j});
            }
            else if (vecc[i][j] == '1')
                perform({i, j}, {i, j + 1});
            else if (vecc[i][j + 1] == '1')
                perform({i, j}, {i, j});
        }
        if (m & 1)
        {
            if (vecc[i][m - 1] == '1')
                perform({i, m - 2}, {i, m - 2});
        }
        db(vecc[i], res.size());
    }

Overkilled solution 98789649

So over all number of operations will be atmost $$$ \frac{m+1}{2}*(n-2) + (m-2)+4 $$$

← Rev. 3 →

I used your code and make this checker, it seems my code is overkill too

Checker of your solution

Checker of my solution

Checker of your code report for (5, 4)

You used 8388608 times of flipping !
It need 12 times for this gen:
1011
0000
0000
0000
0001
Compared to expected number = 12 / 20

My checker report for (5, 4)

Now that's what I call stress testing XD.

greedyai

SPyofgame can you please explain use of x,y,z, and t in the 2*2 block code ... are you checking for the number of moves through them?

← Rev. 4 →

In C1, we know that we can turn off only one cell by $$$3$$$ operations

Then in $$$2x2$$$ cells, we have to use $$$3x4$$$ operations

However, by using xor operator, you will reduce the number of calls upto 4 times ! Since the same cells are called will be ignored

For simpler thinking (ignore the complex math part), here is an example, you need to flip {$$$o2, o3, o4$$$} to turn off {$$$p1$$$} and flip {$$$o1, o2, o4$$$} to turn off {$$$p2$$$}, then you actually need to flip {$$$o1, o3$$$} in order to turn off both {$$$p1, p2$$$}

Bitactro

check out anyone's code in submission.

KnightKnight

Does this work for C2 Hard version , let's go to each element of our matrix except the last row and last column and try to fix them by flipping , Requies only one move so we have exhausted nm-n-m moves till now lets try to fix our bottom most row and rightmost column by the brute force way we used for C1 easy Version,It works? If anyone has a counter example?

150iq

111
110
101

What about this?

Bhosideke

Lodu contest

martins

+17

I'd like to see an official Java solution for Div1B.

There was one, right?

Bojack_human

[deleted]

0xF5

ㅤ

new_dawn

Please somebody help.I dont know why this solution 98723050 for 1440A - Buy the String is showing Time limit exceeded on pretest 3. Thank you!!!

_hq8398_

I'm not sure whether this's the problem but the size of the string might be 1000 which is greater than ur dp's size

ishank162

The size of your DP if just 100, but the size of string can be up to 1000, so it might be undefined behavior.

weapon_x

+16

Codeforces Round #50000000 Div2 C — So just enumerate all $$$2^{256}$$$ cases and handle them individually...

SkyDreams

But wait you have a overflow here.

+12

Can't even make a joke without getting Memory Limit Exceeded error! XD

arpitP

can pls someone explain sum of medians

For each of the $$$k$$$ partitions, greedily fill up the part from the end to the median first, using the largest available numbers. Then calculate the sum of the medians.

See this submission here — 98706701

NitinGpt

I couldn't understand how to solve for the last nth row in binary table question. Can someone plssss help me out....

amurto

how would you make the bottom right cell 0 in case of odd n and odd m?

ForeverGray

Problem with the Div.2 taskE, my approach with the editorial: When the man wants to eat:

First the man only eats for log(maxY) consecutive things so the time complexity for this is O(log(maxY))

Second we binary search for the place he starts to eat which takes at most O(log(n))

Third we find how much he will eat and this also takes O(log(n))

And to implement the above things I used a segment tree to maintain range_max, range_min, range_sum, so each range-query takes O(log(n))

So for each query of the second type will take O( log(maxY) * ( log(n) + log(n) ) * log(n) ) So it leads to TLE

Can someone please tell me how to boost my algorithm, thanks in advance.

generic_placeholder_name

+23

You can binary search on a segment tree for O(log n). Start at the root, if the left subtree is not good, go to the right subtree, else go to the left subtree.

More specifically, in this problem, you have 2 different binary searches, one for starting place and one for ending place.

The first binary search is for min i so that a[i] <= x. This is simple.

The second binary search is for max i so that sum(a[l], a[i]) <= x. This is the same as finding max i so that sum(a[0], a[i]) <= x + sum(a[0], a[l-1]). This binary search is also simple.

bekzhan29

You can get rid of binary search in both operations. For example you want to find leftmost position p, such that a[p]<=y. You can store minimum on segments in your segment tree. Imagine that you are standing in the root. You know that minimum in left subtree is larger or equal than maximum in right subtree. So if minimum from left subtree is smaller or equal to y you can go left, otherwise go right. You can do similar thing to remove second binary search.

But I also want my p to be greater than the current begin point, so going left might not be able to take a usable minimum.

So I'll have to iterate almost every vertex of my seg tree which again makes me TLE.

Thanks for ur time and patience BTW.

What’s the problem of taking p=max(p,x)? Because our array is non-increasing. If p is good, then every index after p is good too.

Oh wow I misunderstood the statement. I thought the modification was for only one position. Again, thanks for ur help and patiences.

code_warrior

-42

Div2 C1/C2 was the most complex implementation problem. Upvote if you agree!

-9

Btw nice way of losing contribution.

jhasaurav215

In the contest dashboard, there isn't the option of "Tutorials(en)" in the contest material section. please look into it.

Thank you :)

Where is the editorial for div2 C1 (easy version of binary table)?

-10

You can refer to this

The main idea is for every cell in a 2 × 2 you can change it without change other cells.

int128.

+10

Nice problemset.

moniMono

⠀

TechNite

Mohammad.H915 In div1B How do we check if it is a clique or not in O(k^2). I know one way which takes O(k^2*log(n)) but I am not able to understand editorial's approach. can you please elaborate a bit more. Thanks

tkacper

You can store neighbours of each vertice in an unordered_set.

stan.ros

got AC with unordered_set with 810ms and 530ms when eliminated duplicated checks

bmerry

I've tried unordered_set but I'm still getting TLE :-(

Make sure to break from both cycles as early as you found it is not clique. https://mirror.codeforces.com/contest/1440/submission/99096912 811ms https://mirror.codeforces.com/contest/1440/submission/99097347 529ms

Already doing that: https://mirror.codeforces.com/contest/1439/submission/99119972

And if anything it should be faster than what you're doing because my iteration is over a vector rather than an unordered_set (I do some complicated things to maintain vectors of neighbours as edges are deleted).

Check it ofline for each vertex that have more than or equal to k-1 we see thier Neighbors, now if you want to know v and u is adjacen just set a new vector for v or u then when you want see neighbors of v just check it adjance with u or not,

My code

asfd221

what does "— 1" part do (tried googling it but all i get is HTML blah ..)?

K-1 mean

me3tazzzz

I've never seen an if statement like this if(nxt != k — 1), can you tell me what it does exactly? Thanks in advance.

Forgive me when such a bug probably occurred while copying

spookywooky

B formulars: Consider using \cdot multiplication sign instead of a simple dot.

$$$n\cdot{k}$$$ vs $$$n.k$$$

see http://www.malinc.se/math/latex/basiccodeen.php

menjihuang

+19

Could you please take a look at hack 678765? I'm getting "Unexpected Verdict".

Usually it means that the model solution is giving TLE or something.

Trgt_2021_explosion

for Div2D/Div1B in the editorial they have put random full stop in sentences and I an not able to understand for checking clique part. How they are assigning 0 and 1 to vertices?

Can anyone please tell how to check for the clique after checking the other one(non empty subset) does not exist?

You can just store neighbours of each vertice in an unordered_set. If you have a vertice with $$$k-1$$$ edges, you iterate over all of it's neighbours to check if they form a clique.

WaterColor2037

For Div1 B, I don't understand this part:

for checking clique candidates fast, iterate over vertices and name current vertex $$$v$$$. then for neighbors of $$$v$$$ set $$$nei_v$$$ to 1 and 0 otherwise. for each clique candidate that contains $$$v$$$ like $$$C$$$, we check edge between $$$v$$$ and $$$u \in C$$$ in $$$O(1)$$$ using array $$$nei$$$.

Especially, what does "name current vertex" mean, and what does $$$nei$$$ do?

I tried implementing similar solution but I got TLE.

-17

We want to check cliques offline so we fix a vertex and check all the edges for that vertex

Does "check cliques offline" means that we check for cliques after removing vertices as much as possible, while recording the vertices with $$$k-1$$$ outgoing edges, and check for cliques after reaching to the end (when we could not find any $$$k$$$-neighbor graph)?

Yep

Oh yes, then that way we can make sure that we inspect only once each for all edges right? Now I understood, thanks a lot.

Errichto

So do you gather all candidates for cliques? Then it's $$$O(n^{1.5})$$$ space complexity, seems very dangerous. Can I see your code?

Wrong

Oops, I mean, the number of vertices added to the list is at most twice as large as the number of edges, so the spacial complexity is $$$O(m)$$$, perhaps?

Oh, you are right. Thanks.

In Binary Table (hard version) editorial, I am not able to understand how you are performing operations. Like you have written we can use one operation on it, its left neighbour and the two cells above to fix this cell , can someone please explain this. I am also not able to comprehend solution posted by SPyofgame

you might find this useful(for c1 and c2): https://www.youtube.com/watch?v=qHVt2ulsVxY

resharing prev comment

At which part you feel hard to understand ? I will add some other approachs later and extra comments & proves

I appreciate your solution, but I am finding difficulty in understanding the logic like why you are eliminating the last row, last column. And also how using bitwise XOR solves 2*2 boxes, being a tyro I am not able to grasp the logic, if you can add some explanations it would be very useful for everyone

:( If not using XOR to implement, you will have to check 4 if-else

Devil

+106

I forgot to sort the adjacency list to perform binary search after i switched from set to vector (because the amazing tle) and it somewhat passed even the system test, amazing tests too ;)

https://mirror.codeforces.com/contest/1439/hacks/678778

To be honest seems more hard to create tests where my solution is correct than where it's wrong, but you guys did it, unbelievable.

AriaH

well ive change my vector to unordered_set and i got Ac, thats weird!

kasparovian

In div1 C if we binary search on the segment tree and there are logY segments then the complexity becomes O(n*logY*logn*logn) , I came up with this solution but it should give TLE. Is there a faster way to binary search on the segment tree?

I just checked, the same has already been answered in the comments!

Halit

-21

LGM Errichto orz

LJF007

Maybe the Div1 D tutorial has any problem? dp1_i=(n+1)\sum_{j=0}^i dp1_{j-1}dp1_{i-j}\binom{n-1,i-1} thx.

AM_I_Learning

An intuitive way and short clean code to solve Div2 C2 Hard version solution hope you understand 98807026 Thank you.

Anyone help me find whats wrong in my submission 98818397 for problem E (div 2).Thanks in advance!!

There are some mistakes in the second paragraph of tutorial of 1439D.

$$$dp2_j\times dp1_{i-j-1}+dp2_{i-j-1}\times dp1_j$$$ should be $$$dp2_{j-1}\times dp1_{i-j}+dp2_{i-j}\times dp1_{j-1}$$$.

$$$(\binom j2+\binom{i-j}2)dp1_j\times dp1_{i-j-1}$$$ should be $$$(\binom j2+\binom{i-j+1}2)dp1_{j-1}\times dp1_{i-j}$$$.

Thanks. I updated the blog

um_p

how to solve div2 E if the array was unsorted?

ChickenInKitchen

In Div1 B i dont understand how to implement the nei array . i used map and i got TLE which makes sence . however doesnt array nei have size of N * N ? doesnt it get MLE ? or if you only consider the candidates how can can you find out that there is an edge between to vertices that both are not candidates in O(1) ?

swapnil159

For div1A editorial

We can do this for the first n−2 cells in the row

It should be m-2 cells.

notkamil

In the analysis of problem 1439B is it is written that

If d(u) > k, remaining vertices will form a subset that every vertex have at least k neighbors in the subset, so we'll print this subset as answer.

If d(u) = k − 1, we consider u and all neighbors of u as candidate for clique of size k. then we erase u and all edges attached to it.

So, what we do when d(u) = k? Maybe there is typo here and first condition should be d(u) ≥ k?

maroonrk

Could someone explain $$$O(N\log N)$$$ solution for 1D? I came up with $$$O(N^2)$$$ solution myself (98827591), and it seems to be similar to the code in this comment, but I still don't see the way to reduce it to FFT. (the $$$(n-i)^j$$$ term is troublesome)

I think Shayan.P and AliShahali1382 know about it

AliShahali1382

+34

I dont know the O(n.log(n)) solution but I had a O(n.log(n)^2) with FFT and divide and conquer. here dp1 and dp2 have same definitions as the editorial.

Spoiler

ghoshsai5000

My solution to

$$$C$$$

was slightly different. I divided the matrix into

$$$2 \times 2$$$

matrices. And solved it independently for each

matrix.

If the matrix has 4 ones, do a flip and make it have 1 one.
If the matrix has 1 one, do a flip and make it have 2 ones.
If the matrix has 2 ones, do a flip and make it have 3 ones
If the matrix has 3 ones, do a flip and make it have 0 ones

Here is my code and explanation

rgnerdplayer

Div1E editorial when

rguy23

Mehrdad_Sohrabi Please provide the implementations also.

+24

Auto comment: topic has been updated by AliShahali1382 (previous revision, new revision, compare).

MikeTheCoder

I don't understand B's solution Sum of Medians.

Let A = [0 24 34 58 62 64 69 78]. n = 2, k = 4. Length = n * k = 8.

If you take ceil(n / 2) numbers from the end and floor(n / 2) numbers from the beginning for each group, you get this:

n = 2. ceil( 2 / 2) = ceil(1) = 1.

Pick 1 number from the end and 1 number from beginning.

Group G = [[78 , 0] , [69, 24], [64, 34], [62, 58]].

Now take median of each one and sum them up, Median = ceil( n / 2). sum = 0 + 24 + 34 + 58 = 116. This is not equal to the answer of 165.

Let's assume you sorted each group though, G = [[0, 78], [24, 69], [34, 64], [58, 62]] Sum = 78 + 69 + 64 + 62 = 273. This is still not equal to answer of 165.

How does the solution work?

← Rev. 5 →

please see the definition of median, median of [0, 78] = 0

NightRage

This 98841172 my solution for problem "Binary Table", I think it's easier to understand it.

+20

Some of the problem were quite nice theoretically, but no fun at all to code. Or maybe it's just that I don't enjoy the coding as much now that I'm retired.

On problem B I got TLE despite having the intended big-O, but the unordered_map constant factor was too high. Problem C I had to spend a lot of time integrating the binary search into the segment tree structure (because just putting it on top of the segment tree adds a log factor that made it too tight). And on problem E I really enjoyed working out the maths (I didn't think I would, but it turns out to be a very nice result), but trying to compute the union of the paths that get painted black was fiddly and my solution is still suffering from time and memory limit errors.

satylogin

We don't actually need binary search with the amount of info that we are maintaining it seems: https://mirror.codeforces.com/contest/1440/submission/100607410

SHZhang

Solution for D1E

Firstly, it can be shown that the game is equivalent to the following game:

Instead of coloring squares, imagine there are tokens on them. Initially, let all black squares contain 1 token and all white squares contain no tokens. In one move, one removes a token, but may add 1 token to any subset of the ancestors of the square from which the token was removed. There can be multiple tokens within the same square. A player loses when in his turn, there are no tokens remaining.

See the editorial of 494E - Sharti, a very similar problem, for a detailed explanation.

Now, in general, we can calculate Grundy values for a game by breaking it down into independent games and XOR'ing these values together. For this problem, we consider each initial token to be an independent game.

How do we find the Grundy number for a game whose only starting token is at $$$(x, y)$$$? Turns out, the Grundy number is $$$2^{x+y}$$$. This can be proven using induction on $$$x+y$$$, with the root as a base case.

We can now see that when we perform the cheating operation, we flip an arbitrary number of bottommost bits in the Grundy number of the overall game. As the second player, we want the Grundy number to become 0. It is not hard to see that the number of cheating operations necessary to do so is equal to the number of pairs of adjacent bits in the Grundy number that differ from each other, as each cheating operation reduces this value by at most 1, and it is easy to construct a sequence of cheating operations that are exactly this long.

We build a tree out of the nodes that are endpoints of paths given in the input, in addition to any LCAs of any pair of these nodes. There is a well-known algorithm to solve this problem using a stack after sorting the nodes by DFS order; see 1320E - Treeland and Viruses for an example. After building the tree, which contains at most O(m) nodes, we can find the edges of the tree that are covered by at least one input path using a simple DFS, and use this to express the Grundy number of the game as the XOR of intervals of 1 bits, and thus solve the problem.

The most annoying part: how to find LCAs and to sort nodes in DFS order, given that the tree is prohibitively large and cannot be preprocessed in full (which is necessary for the usual LCA algorithms, and the normal way of finding DFS order). It is possible to do both, by looking at the recursive structure of the tree and the binary representations of nodes' positions. The details, however, are extremely complicated. I spent several hours debugging due to a number of bugs in these two functions, and ended up having to rewrite the DFS ordering several times.

My code can be found in my submissions list, but bear in mind it is filled with debugging statements, massive commented out sections, and whole functions that have been abandoned. It is not nice to look at.

hardikkapoor

Hi, can you please tell me why this code is giving TLE on test 99? (problem DIV1C) 117855762 I have tried many things to optimize the code, but nothing works. The complexity is O(logn*log(maxn)*(n+q)). Thanks for your time.

A_G

2 года назад, # |

Problem 1439D - INOI Final Contests can be solved in $$$O(m)$$$ because the answer is

$$$\dbinom{m}{2}\times 2^m\times (n+1-m)\times \left(\displaystyle\sum_{i=0}^{m-2}\frac{(m-2)!}{i!}(n+1)^i\right).$$$

(No, I don't have a proof.)

NeverCompromise

19 месяцев назад, # |

In div1-C, second traversal on segment tree can be implemented in a funny manner (first walk up and then walk down): link

PresHerobrine

13 месяцев назад, # |

However, I have an $$$\Theta(m)$$$ solution for Problem D, here is my submission. The key is EGF of dp1 and dp2 can be expressed simply with $$$T(x)$$$, which is $$$T(x) = x \exp T(x)$$$, the euler tree function.

Блог пользователя Mehrdad_Sohrabi