Разбор Технокубок 2019 — Отборочный Раунд 1 (и открытые рейтинговые раунды Codeforces Round 512 Div.1, Div.2)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Разбор

Решение

#include<bits/stdc++.h>

using namespace std;

int main() {
	int n; cin >> n;
	
	int curMax = 0;
	for(int i = 0; i < n; i++) {
		int curAns; cin >> curAns;
		curMax = max(curMax, curAns);
	}
	puts(curMax > 0 ? "HARD" : "EASY");
	return 0;
}

1030B - Вася и кукурузное поле

Разбор

Решение

#include<bits/stdc++.h>

using namespace std;

int n, d;
int m;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	cin >> n >> d;
	cin >> m;
	for(int i = 0; i < m; ++i){
		int x, y;
		cin >> x >> y;
		
		bool ok = true;
		if(!((x - y) <= d && (x - y) >= -d)) 
			ok = false;
		if(!((x + y) <= n + n - d && (x + y) >= d))
			ok = false;

		if(ok) puts("YES");
		else puts("NO");
	}
	return 0;
}

1030C - Вася и золотой билет

Разбор

Решение

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	cin >> n >> s;
	int sum = 0;
	for(int i = 0; i < n - 1; ++i){
		sum += s[i] - '0';
		
		bool ok = true;
		int pos = i + 1;
		int sum2 = 0;
		while(pos < n){
			sum2 = s[pos++] - '0';
			while(pos < n && sum2 + s[pos] - '0' <= sum){
				sum2 += s[pos] - '0';
				++pos;
			}
			if(sum2 != sum) ok = false;
		}
		
		if(sum2 != sum) ok = false;
		if(ok){
			puts("YES");
			return 0;
		}
	}
	
	puts("NO");	
	return 0;
}

1030D - Вася и треугольник

Разбор

Решение

#include<bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b){
	return a? gcd(b % a, a) : b;
}

int main() {
	//freopen("input.txt", "r", stdin);
	
    long long n, m, k;
    cin >> n >> m >> k;
    
    bool isEven = k % 2 == 0;
    long long p = n * m;
	if(isEven) k /= 2;
	
	if(p % k != 0){
		cout << "NO" << endl;
		return 0;
	}
	
	long long x = gcd(n, k);
	k /= x;
	long long a = n / x;
		
	x = gcd(m, k);
	k /= x;
	assert(k == 1);
	long long b = m / x;
		
	
	if(!isEven){
		if(a < n)
			a += a;
		else{
			assert(b < m);
			b += b;
		}
	}
	
	cout << "YES" << endl;
	cout << "0 0\n";
	cout << 0 << ' ' << b << endl;
	cout << a << ' ' << 0 << endl;
	
	return 0;
}

1030E - Вася и хорошие последовательности

Разбор

Решение

#include<bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 9;

int n;
long long a[N];
int b[N];
int cnt[2][N];

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	cin >> n;
	for(int i = 0; i <n; ++i){
		cin >> a[i];
		b[i] = __builtin_popcountll(a[i]);	
	}
	
	long long res = 0;
	int sufSum = 0;
	cnt[0][n] = 1;
	for(int i = n - 1; i >= 0; --i){
		int sum = 0, mx = 0;
		int lstJ = i;
		int add = 0;
		for(int j = i; j < n && j - i < 65; ++j){
			sum += b[j];
			mx = max(mx, b[j]);
			if(mx > sum - mx && sum % 2 == 0) --add;
			lstJ = j;
		}		
		
		sufSum += b[i];
		add += cnt[sufSum & 1][i + 1];
		res += add;	
		
		cnt[0][i] = cnt[0][i + 1];
		cnt[1][i] = cnt[1][i + 1];
		if(sufSum & 1) ++cnt[1][i];
		else ++cnt[0][i];
	}
	
	cout << res << endl;
	return 0;
}

1030F - Сдвигаем ящики

Разбор

Решение с деревом Фенвика

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
typedef long long li;

const int MOD = int(1e9) + 7;

int norm(int a) {
	if(a >= MOD)
		a -= MOD;
	if(a < 0)
		a += MOD;
	return a;
}

int norm(const li &a) {
	return norm(int(a % MOD));
}

int mul(int a, int b) {
	return int((a * 1ll * b) % MOD);
}

const int N = 200 * 1000 + 555;

int n, q;
int a[N], w[N];

inline bool read() {
	if(!(cin >> n >> q))
		return false;
	fore(i, 0, n)
		assert(scanf("%d", &a[i]) == 1);
	fore(i, 0, n)
		assert(scanf("%d", &w[i]) == 1);
	return true;
}

li fW[N], fAW[N];

void inc(li f[N], int pos, li val) {
	for(; pos < N; pos |= pos + 1)
		f[pos] += val;
}

li sum(li f[N], int pos) {
	li ans = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		ans += f[pos];
	return ans;
}

li getSum(li f[N], int l, int r) {
	return sum(f, r - 1) - sum(f, l - 1);
}

int getNSum(li f[N], int l, int r) {
	return norm(sum(f, r - 1) - sum(f, l - 1));
}

inline void solve() {
	fore(i, 0, n) {
		a[i] -= i;
		inc(fW, i, w[i]);
		inc(fAW, i, mul(a[i], w[i]));
	}
	
	fore(_, 0, q) {
		int x, y;
		assert(scanf("%d%d", &x, &y) == 2);
		if(x < 0) {
			x = -x - 1;
			inc(fW, x, -w[x]);
			inc(fAW, x, -mul(a[x], w[x]));
			
			w[x] = y;
			inc(fW, x, w[x]);
			inc(fAW, x, mul(a[x], w[x]));
		} else {
			x--;
			li sum = getSum(fW, x, y);
			
			int lf = x, rg = y;
			while(rg - lf > 1) {
				int mid = (lf + rg) >> 1;
				if(2 * getSum(fW, x, mid) > sum)
					rg = mid;
				else
					lf = mid;
			}
			assert(x <= lf && lf < y);
			
			int ans = norm(mul(a[lf], getNSum(fW, x, lf)) - getNSum(fAW, x, lf));
			ans = norm(ans + norm(getNSum(fAW, lf, y) - mul(a[lf], getNSum(fW, lf, y))) );
			printf("%d\n", ans);
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

Решение с деревом отрезков

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}

template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	out << "[";
	fore(i, 1, int(v.size())) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

const int INF = int(1e9);
const li INF64 = li(1e18);

const int MOD = int(1e9) + 7;

int norm(int a) {
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}

int norm(const li &a) {
	return norm(int(a % MOD));
}

int mul(int a, int b) {
	return int((a * 1ll * b) % MOD);
}

const int N = 300 * 1000 + 555;

int n, q;
int a[N], w[N];

inline bool read() {
	if(!(cin >> n >> q))
		return false;
	fore(i, 0, n)
		assert(scanf("%d", &a[i]) == 1);
	fore(i, 0, n)
		assert(scanf("%d", &w[i]) == 1);
	return true;
}

li TW[4 * N], TAW[4 * N];

void addVAl(li T[4 * N], int v, int l, int r, int pos, int val) {
	if(l + 1 == r) {
		assert(l == pos);
		T[v] += val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos < mid)
		addVAl(T, 2 * v + 1, l, mid, pos, val);
	else
		addVAl(T, 2 * v + 2, mid, r, pos, val);
	T[v] = T[2 * v + 1] + T[2 * v + 2];
}

li getSum(li T[4 * N], int v, int l, int r, int lf, int rg) {
	if(l == lf && r == rg)
		return T[v];
	int mid = (l + r) >> 1;
	li ans = 0;
	if(lf < mid)
		ans += getSum(T, 2 * v + 1, l, mid, lf, min(mid, rg));
	if(rg > mid)
		ans += getSum(T, 2 * v + 2, mid, r, max(lf, mid), rg);
	return ans;
}

int getNSum(li T[4 * N], int l, int r) {
	if(l >= r) return 0;
	return int(getSum(T, 0, 0, n, l, r) % MOD);
}

pair<int, li> getPos(int v, int l, int r, int lf, int rg, li val) {
	if(l == lf && r == rg) {
		if(TW[v] <= val)
			return make_pair(INF, TW[v]);
		if(l + 1 == r)
			return make_pair(l, 0);
	}
	int mid = (l + r) >> 1;
	
	int res = INF;
	li sum = 0;
	if(lf < mid) {
		auto cur = getPos(2 * v + 1, l, mid, lf, min(mid, rg), val);
		res = min(res, cur.x);
		sum += cur.y;
	}
	if(rg > mid && res == INF) {
		auto cur = getPos(2 * v + 2, mid, r, max(lf, mid), rg, val - sum);
		res = min(res, cur.x);
		sum += cur.y;
	}
	return make_pair(res, sum);
}

inline void solve() {
	fore(i, 0, n) {
		a[i] -= i;
		addVAl(TW, 0, 0, n, i, w[i]);
		addVAl(TAW, 0, 0, n, i, mul(a[i], w[i]));
	}
	
	fore(_, 0, q) {
		int x, y;
		assert(scanf("%d%d", &x, &y) == 2);
		if(x < 0) {
			x = -x - 1;
			addVAl(TW, 0, 0, n, x, -w[x]);
			addVAl(TAW, 0, 0, n, x, -mul(a[x], w[x]));
			
			w[x] = y;
			addVAl(TW, 0, 0, n, x, w[x]);
			addVAl(TAW, 0, 0, n, x, mul(a[x], w[x]));
		} else {
			x--;
			li sum = getSum(TW, 0, 0, n, x, y);
			int pos = getPos(0, 0, n, x, y, sum / 2).x;
			assert(x <= pos && pos < y);
			
			int ans = norm(mul(a[pos], getNSum(TW, x, pos)) - getNSum(TAW, x, pos));
			ans = norm(ans + norm(getNSum(TAW, pos, y) - mul(a[pos], getNSum(TW, pos, y))) );
			printf("%d\n", ans);
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

1030G - Линейный конгруэнтный генератор

Разбор

Решение с Dynamic Connectivity

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}

template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	out << "[";
	fore(i, 0, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

const int MOD = int(1e9) + 7;

int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}

int binPow(int a, int k) {
	int ans = 1;
	while(k > 0) {
		if(k & 1) ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

const int M = 2000 * 1000 + 555;
const int N = 200 * 1000 + 555;

int n, p[N];

inline bool read() {
	if(!(cin >> n))
		return false;
	fore(i, 0, n)
		assert(scanf("%d", &p[i]) == 1);
	return true;
}

int minD[M];
vector<pt> ps[M];

void precalc() {
	iota(minD, minD + M, 0);
	fore(i, 2, M) {
		if(minD[i] < i)
			continue;
		
		for(li j = i * 1ll * i; j < M; j += i)
			minD[j] = min(minD[j], i);
	}
	
	fore(i, 2, M) {
		int v = i;
		ps[i].clear();
		
		while(v > 1) {
			int md = minD[v];
			if(ps[i].empty() || ps[i].back().x != md)
				ps[i].emplace_back(md, 0);
			ps[i].back().y++;
			v /= md;
		}
	}
}

int baseA[M], cntNotZero = 0;

int a[M];
int mark[M];

void insert(int v) {
	if(a[v] < 1) {
		a[v] = 1;
		mark[v] = 1;
		return;
	}
	for(auto p : ps[v - 1]) {
		a[p.x] = max(a[p.x], p.y);
		if(mark[p.x]) {
			mark[p.x] = 0;
			insert(p.x);
		}
	}
}

vector<int*> pnt;
vector<int> val;

void upd(int &pos, int nval) {
	pnt.push_back(&pos);
	val.push_back(pos);
	
	pos = nval;
}

void roll_back() {
	*(pnt.back()) = val.back();
	pnt.pop_back();
	val.pop_back();
}

bool ok[N];
int cntSame = 0;
vector<int> Top[4 * N];

void addOp(int v, int l, int r, int lf, int rg, int val) {
	if(l == lf && r == rg) {
		Top[v].push_back(val);
		return;
	}
	int mid = (l + r) >> 1;
	if(lf < mid)
		addOp(2 * v + 1, l, mid, lf, min(mid, rg), val);
	if(rg > mid)
		addOp(2 * v + 2, mid, r, max(lf, mid), rg, val);
}

void insertDC(int v) {
	if(a[v] < 1) {
		upd(a[v], 1);
		upd(mark[v], 1);
		if(a[v] == baseA[v])
			upd(cntSame, cntSame + 1);
		return;
	}
	for(auto p : ps[v - 1]) {
		if(a[p.x] < p.y) {
			upd(a[p.x], p.y);
			if(a[p.x] == baseA[p.x])
				upd(cntSame, cntSame + 1);
		}
		if(mark[p.x]) {
			upd(mark[p.x], 0);
			insertDC(p.x);
		}
	}
}

void calcAns(int v, int l, int r) {
	int curOp = sz(pnt);
	for(int cv : Top[v])
		insertDC(cv);
	
	if(l + 1 == r) {
		ok[l] = cntSame == cntNotZero;
	} else {
		int mid = (l + r) >> 1;
		calcAns(2 * v + 1, l, mid);
		calcAns(2 * v + 2, mid, r);
	}
	while(sz(pnt) > curOp)
		roll_back();
}

inline void solve() {
	memset(baseA, 0, sizeof baseA);
	memset(a, 0, sizeof a);
	memset(mark, 0, sizeof mark);
	
	fore(i, 0, n)
		insert(p[i]);
		
	cntNotZero = 0;
	fore(i, 0, M) {
		baseA[i] = a[i];
		cntNotZero += a[i] > 0;
	}
	
	memset(a, 0, sizeof a);
	memset(mark, 0, sizeof mark);
	fore(i, 0, n) {
		if(i > 0)
			addOp(0, 0, n, 0, i, p[i]);
		if(i + 1 < n)
			addOp(0, 0, n, i + 1, n, p[i]);
	}
	calcAns(0, 0, n);
	
	int lcm = 1;
	fore(i, 1, M)
		lcm = mul(lcm, binPow(i, baseA[i]));
	int add = 0;
	fore(i, 0, n)
		if(ok[i])
			add = 1;
	cout << (lcm + add) % MOD << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	precalc();
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

Жадное решение

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int MOD = int(1e9) + 7;

int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}

int binPow(int a, int k) {
	int ans = 1;
	while(k > 0) {
		if(k & 1) ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

const int M = 2000 * 1000 + 555;

int minD[M];
vector<pt> ps[M];

inline void precalc() {
	iota(minD, minD + M, 0);
	
	fore(val, 2, M) {
		if(minD[val] < val)
			continue;
			
		for(li j = val * 1ll * val; j < M; j += val)
			minD[j] = min(minD[j], val);
	}
	
	fore(i, 2, M) {
		int v = i;
		ps[i].clear();
		
		while(v > 1) {
			int md = minD[v];
			if(ps[i].empty() || ps[i].back().x != md)
				ps[i].emplace_back(md, 0);
			ps[i].back().y++;
			v /= md;
		}
	}
}

int n;
vector<int> p;

inline bool read() {
	if(!(cin >> n))
		return false;
	p.assign(n, 0);
	fore(i, 0, n)
		assert(scanf("%d", &p[i]) == 1);
	return true;
}

int a[M], cnt[M];

inline void solve() {
	sort(p.begin(), p.end(), greater<int>());
	
	for(int& cp : p) {
		if(a[cp] == 0) {
			a[cp] = 1;
			cnt[cp] = 1;
		} else {
			cp--;
			for(auto np : ps[cp]) {
				if(a[np.x] < np.y) {
					a[np.x] = np.y;
					cnt[np.x] = 1;
				} else if(a[np.x] == np.y)
					cnt[np.x]++;
			}
		}
	}
	
	int add = 0;
	for(int cp : p) {
		bool un = false;
		for(auto np : ps[cp])
			un |= (a[np.x] == np.y && cnt[np.x] == 1);
		if(!un)
			add = 1;
	}
	
	int lcm = 1;
	fore(i, 2, M)
		lcm = mul(lcm, binPow(i, a[i]));
	cout << (lcm + add) % MOD << endl;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int t = clock();
#endif
	cout << fixed << setprecision(10);

	precalc();
	if(read()) {
		solve();	
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - t << endl;
#endif
	}
	return 0;
}

1053E - Эйлеров обход

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define PII pair <int, int>

const int N = 1e6 + 7;

int n;
int in[N];
int ans[N];
bool used[N];
vector <int> unused;

int cnt;
deque <PII> cur;
vector <PII> getEqual;

set <int> S;
vector <int> place[N];
vector <pair <int, int> > order;

bool check(){
	if(in[1] != 0 && in[n + n - 1] != 0 && in[1] != in[n + n - 1])
		return false;
	
	for(int i = 1; i + 1 < n + n; ++i)
		if(in[i] == in[i + 1] && in[i] != 0)
			return false;
	
	for(int i = 1; i < n + n; ++i){
		if(in[i] == 0)
			continue;

		if(place[in[i]].size() == 0)
			order.push_back({i, in[i]});
		place[in[i]].push_back(i);
	}
	
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j < place[i].size(); ++j)
			if(place[i][j]%2 != place[i][j - 1]%2)
				return false;
	
	S.insert(n + n);
	sort(order.begin(), order.end());
	
	for(auto v: order){
		auto it = S.lower_bound(v.first);
		if(*it < place[v.second].back())
			return false;
		
		for(int c: place[v.second])
			S.insert(c);
	}
	
	return true;
}

inline int get(){
    if(unused.size() == 0){
        puts("no");
        exit(0);
    }

	int ret = unused.back();
	unused.pop_back();
	return ret;
}

void go(){
	deque <PII> help;
	while(help.size() + cur.size() >= 3){
		if(help.size() < 3){
			help.push_back(cur.front());
			cur.pop_front();
			continue;
		}
		
		PII v1 = help.back(); help.pop_back();
		PII v2 = help.back(); help.pop_back();
		PII v3 = help.back(); help.pop_back();
		
		if(v1.st == 0 && v2.st != 0 && v3.st != 0){
			ans[v1.nd] = v3.st;
			help.push_back(v3);
		}
		else{
			help.push_back(v3);
			help.push_back(v2);
			help.push_back(v1);
		}
		
		if(cur.size() == 0)
			break;
		
		help.push_back(cur.front());
		cur.pop_front();
	}
	
	while(help.size()){
		cur.push_back(help.front());
		help.pop_front();
	}
}

void solve(int root){
	int need = (cur.size() + 1) / 2 - cnt;
	if(need < 0){
	    puts("no");
	    exit(0);
	}
	deque <PII> help;
	
	while(cur.size()){
		auto v = cur.front();
		cur.pop_front();

		if(need > 0 && v.st == 0){
			--need;
			v.st = get();
			ans[v.nd] = v.st;
		}
		
		help.push_back(v);
	}
	
	while(help.size()){
		cur.push_front(help.front());
		help.pop_front();
	}

	go();
	if(root == -1 && cur.back().st == 0){
		root = cur.front().st;
		ans[cur.back().nd] = root;

		cur.pop_front();
		cur.pop_back();
		solve(root);
		return;
	}
	
	reverse(cur.begin(), cur.end());
	go();
	
	while(cur.size() > 0){
		auto v = cur.front();
		cur.pop_front();
		
		if(v.st == 0)
			ans[v.nd] = root;
	}
	
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < n + n; ++i){
		scanf("%d", &in[i]);
		used[in[i]] = true;
	}
	
	if(!check()){
		puts("no");
		return 0;
	}
	
	if(in[1] != 0)
		in[n + n - 1] = in[1];
	else if(in[n + n - 1] != 0)
		in[1] = in[n + n - 1];
	
	for(int i = 1; i <= n; ++i){
		if(!used[i])
			unused.push_back(i);
		used[i] = false;
	}
	
	for(int i = 1; i < n + n; ++i)
		ans[i] = in[i];
	
	for(int i = 1; i < n + n; ++i){
		if(in[i] == 0){
			getEqual.push_back({in[i], i});
			continue;
		}

		if(used[in[i]]){
			cnt = 0;
			while(getEqual.back().st != in[i]){
				if(getEqual.back().st > 0){
					++cnt;
					used[getEqual.back().st] = false;
				}

				cur.push_front(getEqual.back());
				getEqual.pop_back();
			}
			
			solve(in[i]);
			continue;
		}
		
		getEqual.push_back({in[i], i});
		used[in[i]] = true;
	}
	
	cnt = 0;
	while(getEqual.size()){
		if(getEqual.back().st > 0){
			++cnt;
			used[getEqual.back().st] = false;
		}

		cur.push_front(getEqual.back());
		getEqual.pop_back();
	}
	
	solve(-1);
	puts("yes");
	for(int i = 1; i < n + n; ++i)
		printf("%d%c", ans[i], i == n + n - 1 ? '\n' : ' ');
	return 0;
}

#include<bits/stdc++.h> using namespace std; int main () { map<char,int> mymap; mymap['a']=10; mymap['b']=20; for(auto it=mymap.begin();it!=mymap.end();it++) if(it->first=='a') mymap.erase(it); for(auto p:mymap) cout<<p.first<<" "<<p.second<<endl; return 0; }

#include <bits/stdc++.h> using namespace std; #define st first #define nd second #define PII pair <int, int> const int N = 1e6 + 7; int n; int in[N]; int ans[N]; bool used[N]; vector <int> unused; int cnt; vector <PII> cur; vector <PII> getEqual; int reval[N]; int place[N]; vector <pair <int, int> > order; bool check(){ if(in[1] != 0 && in[n + n - 1] != 0 && in[1] != in[n + n - 1]) return false; for(int i = 1; i + 1 < n + n; ++i) if(in[i] == in[i + 1] && in[i] != 0) return false; int t = 0; for(int i = 1; i < n + n; ++i){ if(in[i] == 0) continue; if(reval[in[i]] == 0){ reval[in[i]] = ++t; place[in[i]] = i; } } cur.push_back({0, 0}); for(int i = 1; i < n + n; ++i){ if(in[i] == 0) continue; if((place[in[i]] & 1) != (i & 1)) return false; while(reval[in[i]] <= cur.back().st) cur.pop_back(); if(place[in[i]] < cur.back().nd) return false; cur.push_back({reval[in[i]], i}); } cur.clear(); return true; } inline int get(){ if(unused.size() == 0){ puts("no"); exit(0); } int ret = unused.back(); unused.pop_back(); return ret; } void go(){ vector <PII> help; reverse(cur.begin(), cur.end()); while(help.size() + cur.size() >= 3){ if(help.size() < 3){ help.push_back(cur.back()); cur.pop_back(); continue; } PII v1 = help[help.size() - 1]; PII v2 = help[help.size() - 2]; PII v3 = help[help.size() - 3]; if(v1.st == 0 && v2.st != 0 && v3.st != 0){ ans[v1.nd] = v3.st; help.pop_back(); help.pop_back(); } if(cur.size() == 0) break; help.push_back(cur.back()); cur.pop_back(); } if(cur.size() == 0) cur = help; } void solve(int root){ int need = (cur.size() + 1) / 2 - cnt; if(need < 0){ puts("no"); exit(0); } for(auto &v: cur) if(v.st == 0 && need > 0){ --need; v.st = get(); ans[v.nd] = v.st; } reverse(cur.begin(), cur.end()); go(); if(root == -1 && cur.back().st == 0){ root = cur[0].st; ans[cur.back().nd] = root; cur.pop_back(); reverse(cur.begin(), cur.end()); cur.pop_back(); reverse(cur.begin(), cur.end()); solve(root); return; } reverse(cur.begin(), cur.end()); go(); for(auto &v: cur) if(v.st == 0) ans[v.nd] = root; cur.clear(); } int main(){ scanf("%d", &n); for(int i = 1; i < n + n; ++i){ scanf("%d", &in[i]); used[in[i]] = true; } if(!check()){ puts("no"); return 0; } if(in[1] != 0) in[n + n - 1] = in[1]; else if(in[n + n - 1] != 0) in[1] = in[n + n - 1]; for(int i = 1; i <= n; ++i){ if(!used[i]) unused.push_back(i); used[i] = false; } for(int i = 1; i < n + n; ++i) ans[i] = in[i]; for(int i = 1; i < n + n; ++i){ if(in[i] == 0){ getEqual.push_back({in[i], i}); continue; } if(used[in[i]]){ cnt = 0; while(getEqual.back().st != in[i]){ if(getEqual.back().st > 0){ ++cnt; used[getEqual.back().st] = false; } cur.push_back(getEqual.back()); getEqual.pop_back(); } reverse(cur.begin(), cur.end()); solve(in[i]); continue; } getEqual.push_back({in[i], i}); used[in[i]] = true; } cnt = 0; while(getEqual.size()){ if(getEqual.back().st > 0){ ++cnt; used[getEqual.back().st] = false; } cur.push_back(getEqual.back()); getEqual.pop_back(); } reverse(cur.begin(), cur.end()); solve(-1); puts("yes"); for(int i = 1; i < n + n; ++i) printf("%d%c", ans[i], i == n + n - 1 ? '\n' : ' '); return 0; }

By xoring with number with N-bits you can remove no more than N-bits. Xoring with 0000001111 will remove no more than 4 bits. Xoring with 0000000011 will remove no more than 2 bits. Xoring with 0000000011 will remove no more than 2 bits.

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

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

manish_joshi

6 лет назад, # |

+95

Editorial launched even before System testing. I'm loving this !

→ Ответить

yujinwunz

6 лет назад, # ^ |

← Rev. 2 →

+59

Next time, editorial before contest ends!

killer_god

It happened already check https://codeforces.com/blog/entry/60209

P___

+16

Why not before contest starts?

fmqjpt

:( For most of the time I thought that you can only do one swap per integer in Div1B, guess I need to read more carefully next time

am1tbh47

I thought there were zeros in the array :(

OneLastTime

Fastest editorial ever launched. Enjoyed this contest :D

Gagarin

← Rev. 3 →

The functions that defines the limits of the x — y values are changed on the B's picture.

adedalic

Yes they are. Overlooked it when drew the picture.

csumanth98

Why is mymap.erase(it) giving runtime error. I know that it=mymap.erase(it) should be done. But the first one is running in all other compilers like hackerrank, codechef, my mac laptop. Why is it not running here in codeforces?

lohit_97

Iterating and Erasing simultaneously causes undefined behaviour.

Why is it running on almost all other compilers then?

Also I came to know a few days back that long and long long are not the same in codeforces but same on almost all other compilers.

Why is codeforces compiler different?

TooNewbie

+14

long is 4-byte data type while long long is 8-byte. In which compiler they have the same range?

See this.

All other ide's at https://wandbox.org https://ide.geeksforgeeks.org https://www.codechef.com/ide and my macbook gave the ouput as 9223372036854775807 for both.

Strange.

oskar

+19

It's not.

In 64-bit systems long will be the 8-byte data type.

It's C++ standard. You can read more here: cppreference: Fundamental types.

And int has to be less than long but it's not similar on different compilers. Also read cppreference.

Check it yourselves.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a;
    long b;
    long long c;

    cout << sizeof(a) << " ";
    cout << sizeof(b) << " ";
    cout << sizeof(c) << "\n";
}

Codeforces output: 4 4 8

My pc output (64-bit): 4 8 8

Dword

No. In the C++11 standart method "erase(iterator)" returns iterator on the next element in container. So "it = mymap.erase(it)" is correct code.

VLADO

Can someone explain solution for D? How do you get to sides a and b? Why are we dividing k by 2 if it is even, why are we multiplying later, etc.

blue__legend

area of the triangle will be (a*b)/2 = (n*m)/k writing it as a*b = (2*n*m)/k we are calculating a in terms of n and b in terms of m. so we could've done something similar to link

But it will be just writing extra code.

Ahs_58

If a>n can be true how you sure that in 2nd if condition

here

if(a>n){
    k=kf;
    x=gcd(n,k);
    k/=x;
    a=n/x;
    x=gcd(m,k);
    k/=x;
    b=2*m/x;
}

b>m will be always false. Can you please explain??

sorry for bad english.

since a*b = (2 * n * m) / k; if( a > n ) => b < (2*m/k) since, k>=2 => k/2 >= 1 => b < m / (k/2); => b < m

hieplpvip

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

Let's consider only the case when one point is at $$$(0,0)$$$. For other cases, you can always move to this case (by shifting the points).

We'll build a rectangle inside the rectangle $$$n \times m$$$, with area equal to $$$2*m*n/k$$$, and we'll split the rectangle to get the triangle.

When $$$k$$$ is even ($$$k=2t$$$), we need to build a rectanble with area $$$m*n/t$$$. This number must be an integer, so $$$m*n$$$ must be divisible by t. This leads to the solution in the editorial. $$$g = gcd(t,n)$$$; $$$n = a * g$$$; $$$m = b * g'$$$ with $$$g' = t/g$$$ and $$$a,b$$$ is the sides of the rectangle
When $$$k$$$ is odd, $$$m*n$$$ must be divisible by $$$k$$$. Similarly, we have: $$$g = gcd(k,n)$$$; $$$n = a * g$$$; $$$m = b * g'$$$ with $$$g' = k/g$$$. Note that at this time, $$$a$$$ and $$$b$$$ is the sides of the rectangle with area $$$n*m/k$$$. We need to double one side to get the desired rectangle.

If $$$a < n \rightarrow g \geq 3$$$ (because $$$g$$$ is neither 1 nor even) $$$\rightarrow a \leq n/3 \rightarrow 2a < n$$$

If $$$a = n \rightarrow g = 1 \rightarrow g' = k \geq 3$$$ (note that $$$k$$$ is odd). Similarly, we get $$$2b < m$$$

So we can always double $$$a$$$ or $$$b$$$.

Omar_Morsi

+27

Thanks for your effort in writing this editorial.

I wasn't able to solve problem Div.2 E.

When I read the editorial I find you are writing "It can be proven" for the key idea of the problem.

Please mention the proof or mention the intuition behind the two conditions.

+15

Make 0 is equivalent to pairing ones in such way that there is no pair with ones from the same number. If max>sum/2 it's obviously impossible. Otherwise, just divide all ones in two groups of the same size in such way that there is no more than one number with ones in both groups. And there is always a way to pair ones from different groups.

Terminators

I was confused about this . Thanks a lot.

towrist

Thanks adedalic. I would just like to point out that we can prove that such a division is always possible since

Sum is even
The number which has ones in both groups is actually the largest $$$b_i$$$.

And then we can just match pairs from different groups.

TheOneYouWant

Can someone help me understand why I was failing Div 2E, pretest 8? Would be really grateful

https://codeforces.com/contest/1058/submission/43335816

P.S. I used the same approach that the editorialist used

I figured it out — it should have been tot[i-1] instead of tot[i], and j-1 instead of j. Passes now

I_love_myself

← Rev. 4 →

Кто может помочь с Е? 43334510
У меня идея аналогичная, но реализация сильно отличается. Я фиксирую левую границу и сдвигаю ее на 1, поддерживая cnt[k][j] — количество текущих суффиксов, таких, что k — четность суммы бит на суффиксе, j — сумма бит на суффиксе, если j < 63 и cnt[k][63] — аналогично, но сумма бит >= 63. Тогда ответ, очевидно, — сумма по $\text{[math]}$ , где j от cntbit[i] до 63. А чтобы обновить cnt, нужно сделать все переходы вида: $\text{[math]}$ .

dalbaeb69

Когда будут списки тех, кто прошел?

Завтра

LiteYagami__

-8

My code is giving correct answer on local compiler but giving false answer on codeforces compiler. My whole contest went bad due to this error. Atleast my rating should be reverted back. 43309972

I checked test case 10 on codeblocks compiler as well as codechef IDE. Both of them are giving output as "Yes". My code is completely correct but still got WA.

You must check "KpartitionsPossible" until 9 * n

The problem is not that, the problem is that the code is giving correct output on codeblocks and codechef ide but not here.

Aleks5d

you didn't check 'pos' != -1 in line 28

UPD: i changed line 28

else if (prefix_sum[i] - prefix_sum[pos] >  total_sum / K) ->
else if (prefix_sum[i] - (pos == -1 ? 0 : prefix_sum[pos]) > total_sum / K)

and it was accepted

43343643

Thanks for your effort. But why does this give the correct answer on codeblocks and codechef IdE and other compilers?

+11

because ide can eat some bugs and re)

-6

So how do I even make sure that my code is correct? This way i'll never know for sure if my code is correct or not before submitting. I still feel this has been a little unfair to me.

When you try access an index out of bounds, many times, compilers on codechef or other online ones, tend to return zero or garbage value. Basically, it tries to access element at pos*(data_type_size) from the base of the array. So, if pos is -1, it access the element before 0th element of the array.

-16

Thanks a lot for your help. I guess i can't even trust compilers when it comes to codeforces. :(

nns2009

+18

The problem is not in the compiler. Suppose you have the code:

int arr[2];
cout << arr[0] << ' ' << arr[1] << endl;

What this code is supposed to print? There is no certain behaviour because you haven't assigned anything to 'arr'. It will just print what was laying there in the memory and it may differ from launch to launch. The same thing happened in your case.

Thanks a lot. Made this completely clear to me.

-14

Who cares about rating? There's a contest like every 3-4 days.

-9

But when your contest is going good and you would have achieved blue in this very contest and you did not because of such errors,it does feel sad. :(

bmerry

+17

The tutorial for Div 1E claims that if you have two equal values then there is a subtree between them which can be solved independently of the rest of the problem. But that's not necessarily true e.g. given the input 1 2 0 3 1 the only right answer is 1 2 1 3 1, and the interval 2 1 3 does not describe an Euler tour of a subtree of 1.

Anadi

+26

I wrote this tutorial about month ago, now I see a lot of small mistakes in it. This is O(n) solution:

Solution

And a little bit modified tutorial:

Tutorial

First let's try to find some conditions whether it is possible to recover correct euler tour. Of course for every euler tour a_i ≠ a_i + 1 and a₁ = a_2n - 1 (because we start and finish in root).

Moreover if there exist four index i₁ < i₂ < i₃ < i₄ such that a_i₁ = a_i₃ and a_i₂ = a_i₄ and a_i₁ ≠ a_i₂ than answer is NO (because vertex is an ancestor of another or there is no relation between them) — let's call it "crossing elements" condition.

There are more conditions — parity of positions of all occurences of element x are the same (because we visit every edge in our subtree twice) and between two equal elements with distance 2k there can be at most k distinct elements.

It turns out that those conditions are sufficient — we will prove it by constructing an answer.

So first let's observe that if we have to equal elements it means that there is subtree (or maybe subtrees) between them — we can solve it almost independently from the rest of a tree (all we need to remember is root of this subtree) and then forget about this subtree. So as long as we have two equal elements i < j than we can first solve euler tour between them and then delete elements i + 1, i + 2..., j. So now we want to solve euler tour where no element occur more than once.

Let's say that this tour has length 2k - 1 then if we have less than k elements we can replace any 0 with any unused elements. We can't have more because of our conditions.

Now if there are three elements in a row with values x, y, 0 or 0, y, x than we can replace them with x, y, x and replce it with x. If we get rid of all triplets like this than we have tour in form of a₁, 0, a₂, 0, ..., 0, a_k. It's easy to observe that we can replace every 0 with our root (subtree's root). There is a special case when we don't have any root (if solving for whole tree), than we have to find any vertex which can be root and then solve our problem. Straightforward implementation will be O(n²) but it can be easily reduced to O(nlogn) and it can be even reduced to O(n), but O(nlogn) was enough to be accepted.

To solve this in O(n) we should start with making check of some conditions. It's easy to check most of them except "crossing elements" condition and count the number of distinct elements between two equal elements. We will deal with the second condition while generating correct answer. For "crossing elements" we can for every value x compute value r_x equal to number of distinct elements which appears in input before first occurence of x. Now just iterate over every non-zero element (in order from 1 to 2n - 1 with deque/vector of elements with smaller r_x than our current element. Then with some easy checks we can determine if our condition is true.

After checking conditions we want to create a vector of unused elements (with 0 occurences in our tour). Now we can iterate over array as long as there are no two equal elements in our prefix, if we find two equal elements then we can solve part between them and delete them from our current prefix (details in code).

Now add elements as long as in our part of length 2k - 1 there are less than k elements. If it turns out that we don't have enough "unused" elements it means that the last unchecked condition doesn't hold.

How to find all triplets in O(n)? We can make two steps — in first steps find all triplets x, y, 0 (iterate with stack from left to right) and in second step find all triplets 0, y, x (similarly iterate from right to left). At the end replace all zeroes between with root.

Big thanks to Grzmot who wrote great statement and helped me with proving that this solution is correct!

aman28rwt

Can someone explain the second condition of Div2E maximal element should be lower or equal to the sum of all other elements

UPD Got it! :)

Explain it, please.

Suppose you have numbers:

1111111111 (10x1)
0000001111 (4x1)
0000000011 (2x1)
0000000011 (2x1)

Can you change the position of bits so the xor of the numbers equals to zeros?

In total you can only remove 4+2+2 bits but you have 10 bits in the number 1111111111 so you cannot remove two last bits and thus this sequence is bad.

Can You please explain why these two conditions are sufficient?

Let me give it a try.

I hope you understand why, even bits are required. Let me try to explain the other condition.

Lets say for in a subarray for size K, [a1,a2,a3,...,ak] is count of set bits (setbits array). Also, lets assume a1 >= a2 >= a3 .. >= ak, so a1 is the maximum in the setbits array. Now, I will try to greedily nullify the a1 bits. So, first I nullify a2 bits of a1 using a2. Now, (a1-a2) bits of a1 are left, and a2 is nullified. Now I will greedily use, a3 bits to nullify those (a1-a2) bits of a1. Two cases arise:

a3 <= (a1-a2)
a3 > (a1-a2)

For the first case, I use, all of a3, and now I need to nullify (a1-a2-a3), so I go ahead with using a4, and move ahead. Again, two similar cases arise.

For the second case, so I can at max use (a2-a1) bits of a3, and will be left with (a3-a2+a1) bits,(say x, for simplictity) of a3. I don't want that.

So, basically, what I will do is, I will take x bits from a2, and x bits from a3, such that, a2+a3-2x = a1, so now a1 can be nullified, and then x bits from a2 and x from a3 can nullify each other, so we are left with zero.

Although, this is not a very formal proof, I hope I was able to give enough intuition for the constructive algorithm to arrange the bits when the two conditions are satisfied.

Thank you lohit_97.

Eddagdeg

5 лет назад, # ^ |

Hello what about this exapmle 1111 1111 1100 sum of 1's is even and max elemnt is lower or equal to sum of all others but those numbers do form not good sequence! UPD:I got it

iota

I not understand the editorial for Div2-F.Please can you or someone else explain that too?

Thanks!

aryanc403

I also need that. Can someone please explain us??

MB1151

For the second case your explanation gives x=(a2+a3-a1)/2.How do u prove that this is an integer?

If it isn't then there is a number with an extra bit after it which will help us nullify it.

EDIT: I was so waiting for someone to ask this :P

_Anas__

Loved the tutorial of problem E.....Thanks a lot.

ILoveDoraemon

Roms Test cases of D problem seems to be weak :( . Some users coded for smaller k like k=2(and the test cases don't include 'yes' with k=3 or more for the worst case) and got AC.

Can provide link to one such submission?

https://codeforces.com/contest/1058/submission/43318617 : works for 5s on k=3,n=m=1e9-1

Bhj2001

It also depends on the processor of your machine. Maybe your machine is slow.

I checked it on custom invocation, btw the solution is O(sqrt(n*m/k)), which takes O(1e9) in worst case

Pretest 10 was 1000000000 1000000000 2

LOL

"the test cases don't include 'yes' with k=3 or more for the worst case"

Hi! I tried my best to understand the editorial for Div2-F https://codeforces.com/contest/1030/problem/F but could not understand it.

My doubts are in understanding the proof that keeping 1 box unmoved is optimal and how does that total cost of shifting left parts in the end equal to a_k*S(l,k-1) — sum(w_i*a_i)?

Ghost0fSparta

Can somebody explain DIV2 E editorial with the sample test case 1?

3
6 7 14

Winniechen

F can also be done with only BIT in O(logn)

VenenoRoadster

You are right, so did segment tree.

natofp

How?

Fours

In tutorial of the problem Div:2-D, how to prove b=(m/k') is always an integer.

Frozencode

Notice that the area is always a multiple of one-half.

So after you divide k by 2 ,(n*m)/k' will be a integer.

Let's make an assumption that m/k'=x/y (gcd(x,y)=1),

Because (n*m)/k' is a integer,n/(gcd(n,k))should be a multiple of y,

That comes to a contradiction because you should divide n by y(both n and k have the factor--y).

As a result,m/k' is always an integer.

houtaruijika

In problem E, How to prove that if maximal element is lower or equal to the sum of all other elements then the subsequence is good ?

barni120400

if this condition holds and the sum of the sequence is even, you can decrease the two biggest numbers by one and preserve this property. so, at every step you can decrease the sum of the sequence by 2 and eventually it's sum will become zero, which means this squence is good.

proof: let k be the number of occurences of the maximal number x in a sequence with even sum and 2*x<=sum. in case k=1 or k=2: the operation above decreases the maximal number at least by one and decreases the sum exacly by two so the invariant still holds.

in case k>=4, after the operation there are at least two numbers with max value x so the sum is at least 2*x which means the invariant holds.

in case k=3, after the operation the max element is x and the sequence has sum of at least x+(x-1)+(x-1)=3*x-2 which is greater or equal 2*x for every x>=2. the case x=1 can't happen because the sum of the sequence will be odd, so also in here the invariant hold

r57shell

"and eventually it's sum will become zero, which means this squence is good." why this means sequence is good? Me also waiting proof of this

Decrease two numbers corresponds to position two ones in the binary representation of the original numbers at the same place. When the ones are at the same place in both numbers, the XOR will cancel one with the other, and we can ignore them. If the sum of the sequence reached zero it means that every one has another which cancels it, and the XOR result is zero.

Ah, thanks. I was thinking about partition problem. I was trying to find counter example that if you have array satisfying this two conditions, and it can't be devided into two of equal sums. But your proof is not related to partition problem, because here you can use bits of single number in any pair.

TediDinuta

Can someone explain to me why doubled area of any triangle with integer coordinates is always integer? How can we demonstrate that?

tfg

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

Area of triangle (0, 0), v = (x1, y1), u = (x2, y2) is |x1 * y2 — x2 * y1| / 2

you can draw the minimal rectangle with sides parallel to the x and y axis that blocks the triangle (for example, the rectangle corrisponding to triangle (0,0), (1,5) , (2,4) is (0,0) , (5,0), (5,4) , (0,4)). it's divided into 4 triangles, the original one and 3 more Straight-angle triangles. it's clear that each one of them has integer doubled area, and the rectangle's area is also an integer, so the original triangle must also have integer doubled area.

Thank you!

In problem F, how can we actually do this part: find k in(nlogn) by "descending" down the Segment Tree in

idxcalccalc

In the fourth paragraph of the 1053E, the "than" in the first row should be "then".

Alexit

D2E была бы интересней, если вместо массива было бы дерево.

index_

“Problem B” Can anybody explain me,why x+y=d — diagonal?

nondeterministicDecider

In DIV2 Problem E, Something Strange is happening. Here: http://codeforces.com/contest/1058/submission/43418325 in Testcase 1 and same code on IDEone: https://www.ideone.com/iiTZkx Getting WA on test case 1 on Judge but produces correct output on my machine.

Also, I am interested in knowing the result of test case 5.I am using prefix sum here. My program produces 7 as result, Because no. of set bits are: 8 16 16 18 22. So, for 8, there are 0 prefix, 16 : 0 prefix, 16 : 2, 18: 2 prefix and 22: 3 prefix. Total equals to 7. Please explain how the answer is 3 for this test case?

Jonno

Hi, I suggest compiling with the flag -Wall

In lines 59 and 73 you have the condition j > (i-66, 0), maybe you forgot a max? Also, the variable maxm is not initialized in 0 so it could have garbage

I don't know if this is the only problem but I hope it helps

Dee_code

hey can anyone tell why this solution is giving WA for second task?......
when i am submitting like this it is giving AC -
int sum=pow(2,freq)-1;
link for correct solution. https://www.codechef.com/viewsolution/20327375 but when i am using this-
cout pow(2,freq)-1 ;
it is not giving AC
link...
https://www.codechef.com/viewsolution/20329958
thanks in advance..... @arpa

Function pow probably return float value, try convert to int like that: (int)pow(2,freq)-1. And use please logic operations, pow(2,freq) equal 1 << freq.

problem link https://www.codechef.com/problems/MGCSET
but why this solution is giving AC for subtask-1
when i am printing the answer like this
cout pow(2,freq)-1 ;
solution link https://www.codechef.com/viewsolution/20329958
@Alexit
thanks in advance...

because if float value >= 1e6 you print exponentially value. cout << pow(2,20)+1 << "\n"; //print 1.04858e+06 cout << (int)pow(2,20)+1 << "\n"; //print 1048577

prakhar897

In Div2 D, Doubled area of any triangle with integer coordinates is always integer. Can anyone explain this statement.Why is it always true?

panipuri8

https://www.mathopenref.com/coordtrianglearea.html — Area of a triangle when the three vertices are known.

Since all points need to be integral, the formula will always yield a whole number or a (whole number/2). Hence!

MeePwn

Div2E does it means when r-l>60 and sum(l,r)%2==0 and max(l,r)*2<=sum(l,r), you can always divide the ones into two groups with same size? how to prove that?

consecutivelimit

+10

My solution of problem E:

If i < j and a_i = a_j ≠ 0, a[i..j] is an Euler tour, we can deal with a[i..j] and replace it with a_i.

Since a[i..j) doesn't contain the same elements except 0's, we can do this operation:

If there are 3 consecutive elements a_i - 1, a_i, a_i + 1, a_i ≠ 0 and a_i - 1, a_i + 1 contain exactly one 0 (or a_i - 1 = a_i + 1 ≠ 0), we can regard a_i as a leaf and let a_i - 1 = a_i + 1 (equals to the non-zero element), then remove a_i and a_i + 1. It can be proved correct.

After operations, combine the first and the last element to form a cycle, if there are two consecutive non-zero elements, there mustn't be any zero and no solution exists (because a tree with two or more vertices must contain a leaf). Otherwise, any two non-zero elements aren't neighbors, all the elements can be regarded as leaves, it's easy to construct.

After there aren't any i < j that a_i = a_j, we can deal with the whole series using the same way.

All operations can be done by stack in linear time.

Time complexity: O(n).

sneffort

In DIV2 E, can someone explain " Let's find a way to decide whether fixed segment is good or not. It can be proven that two conditions must be met. At first, sum of bi at this segment should be even. At second, maximal element should be lower or equal to the sum of all other elements." How about this case: b1=3, b2=4, b5=5, i think this satisfy the condition, but this case is not good. Am i right?

webeseit

← Rev. 5 →

Let's see, how we can get zero in this case. As we can move the ones we can get something like this:

11111

11110

11100

Shift the bits of b2 to two positions to the right, make the xor of b2 and b5(I mean the xor of numbers from which b2 and b5 were got) and then you can get zero as you get two numbers which contain 3 ones.

I understand, thx

Вопрос по разбору Div2F. " В конце концов, все что нужно делать — для заданного [ l , r ] находить максимальное k , что S ( l , k − 1 ) ≤ S ( l , r ) 2 , но S ( l , k )

S ( l , r ) 2 (
или ≥ не играет роли)."

Наверное здесь имелось в виду не максимальное k, а k, отвечающее ящику с максимальным весом, удовлетворяющее приведенным выше условиям?

Нет, именно, максимальное k. Так как веса положительные, то S(l, k) строго возрастает с ростом k.

Кажется я понял, спасибо.

farmersrice

How do people come up with the intuition for problems like div1 C? Once I read the editorial it's so clear but I thought for half an hour and I didn't even get to the first observation. Is "solve more problems" the only way?

Ozymandias

5 лет назад, # |

Interesting problems...

King_of_the_city

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

This is My Solution for Problem D And I Wonder Why I didn't Get Time Limit exceeded . Is This because Test cases weren't be enough Or Something Else ????????????????????????? https://codeforces.com/contest/1030/submission/150139674

khaledkunbargi

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

Can anyone explain problem B? Vasya and Cornfield ?

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